ABSTRACT
Federico Ardila San Francisco State University, San Francisco, CA, USA; Universidad de los Andes, Bogota´, Colombia
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 What is a good answer? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Generating functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.1 The ring of formal power series . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.2 Ordinary generating functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.2.1 Operations on combinatorial structures and their generating functions . . . . . . . . . . . . . . . . . . . . 13
1.3.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3.3 Exponential generating functions . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.3.3.1 Operations on labeled structures and their exponential generating functions . . . . . . . . . . . . . 28
1.3.3.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.3.4 Nice families of generating functions . . . . . . . . . . . . . . . . . . . . . . . 36
1.3.4.1 Rational generating functions . . . . . . . . . . . . . . . . 36 1.3.4.2 Algebraic and D-finite generating functions . . . 38
1.4 Linear algebra methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 1.4.1 Determinants in combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
1.4.1.1 Preliminaries: Graph matrices . . . . . . . . . . . . . . . . 43 1.4.1.2 Walks: the transfer matrix method . . . . . . . . . . . . 44 1.4.1.3 Spanning trees: the matrix-tree theorem . . . . . . 50 1.4.1.4 Eulerian cycles: the BEST theorem . . . . . . . . . . . 53 1.4.1.5 Perfect matchings: the Pfaffian method . . . . . . . 56 1.4.1.6 Routings: the Lindstro¨m-Gessel-Viennot
lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 1.4.2 Computing determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
1.4.2.1 Is it known? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
1.4.2.2 Row and column operations . . . . . . . . . . . . . . . . . . 66 1.4.2.3 Identifying linear factors . . . . . . . . . . . . . . . . . . . . . 66 1.4.2.4 Computing the eigenvalues . . . . . . . . . . . . . . . . . . . 67 1.4.2.5 LU factorizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 1.4.2.6 Hankel determinants and continued fractions . 68
1.5 Posets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 1.5.1 Basic definitions and examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 1.5.2 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 1.5.3 Zeta polynomials and order polynomials . . . . . . . . . . . . . . . . . . . 77 1.5.4 The inclusion-exclusion formula . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 1.5.5 Mo¨bius functions and Mo¨bius inversion . . . . . . . . . . . . . . . . . . . . 81
1.5.5.1 The Mo¨bius function . . . . . . . . . . . . . . . . . . . . . . . . . 81 1.5.5.2 Mo¨bius inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 1.5.5.3 The incidence algebra . . . . . . . . . . . . . . . . . . . . . . . . 85 1.5.5.4 Computing Mo¨bius functions . . . . . . . . . . . . . . . . 86
1.5.6 Eulerian posets, flag f -vectors, and flag h-vectors . . . . . . . . . . . 91 1.6 Polytopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
1.6.1 Basic definitions and constructions . . . . . . . . . . . . . . . . . . . . . . . . . 93 1.6.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 1.6.3 Counting faces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 1.6.4 Counting lattice points: Ehrhart theory . . . . . . . . . . . . . . . . . . . . . 102
1.7 Hyperplane arrangements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 1.7.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 1.7.2 The characteristic polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 1.7.3 Properties of the characteristic polynomial . . . . . . . . . . . . . . . . . 112
1.7.3.1 Deletion and contraction . . . . . . . . . . . . . . . . . . . . . 112 1.7.3.2 Sign alternation and unimodality . . . . . . . . . . . . . 114 1.7.3.3 Graphs and proper colorings . . . . . . . . . . . . . . . . . 114 1.7.3.4 Free arrangements . . . . . . . . . . . . . . . . . . . . . . . . . . 115 1.7.3.5 Supersolvability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
1.7.4 Computing the characteristic polynomial . . . . . . . . . . . . . . . . . . . 117 1.7.5 The cd-index of an arrangement . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
1.8 Matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 1.8.1 Main example: Vector configurations and linear matroids . . . 127 1.8.2 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 1.8.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 1.8.4 Basic constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 1.8.5 A few structural results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 1.8.6 The Tutte polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
1.8.6.1 Explicit definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 1.8.6.2 Recursive definition and universality property . 138 1.8.6.3 Activity interpretation . . . . . . . . . . . . . . . . . . . . . . . 140 1.8.6.4 Finite field interpretation . . . . . . . . . . . . . . . . . . . . . 140
1.8.7 Tutte polynomial evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 1.8.7.1 General evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . 142
1.8.7.2 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 1.8.7.3 Hyperplane arrangements . . . . . . . . . . . . . . . . . . . . 146 1.8.7.4 Algebras from arrangements . . . . . . . . . . . . . . . . . 146 1.8.7.5 Error-correcting codes . . . . . . . . . . . . . . . . . . . . . . . 147 1.8.7.6 Probability and statistical mechanics . . . . . . . . . 148 1.8.7.7 Other applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
1.8.8 Computing the Tutte polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 1.8.9 Generalizations of the Tutte polynomial . . . . . . . . . . . . . . . . . . . . 153 1.8.10 Matroid subdivisions, valuations, and the Derksen-Fink
invariant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
1.1 Introduction Enumerative combinatorics is about counting. The typical question is to find the number of objects with a given set of properties.
