everything.study
18.212

Algebraic Combinatorics

3-0-9 units · Undergraduate

Applications of algebra to combinatorics. Topics include walks in graphs, the Radon transform, groups acting on posets, Young tableaux, electrical networks.

Spring 2019

Topics

  • Catalan numbers: drunkard’s walk problem, generating function, recurrence relation.
  • Catalan numbers (cont.): formula for C n , reflection principle, necklaces, triangulations of polygons, plane binary trees, parenthesizations.
  • Pattern avoidance in permutations. Stack- and queue-sortable permutations. Young diagrams and Young tableaux. Hook-length formula.
  • Frobenius-Young identity. Schensted correspondence. Longest increasing and decreasing subsequences in permutations.
  • Proof of the hook-length formula based on a random hook walk.
  • Hook walks (cont.). Linear extensions of posets. Hook-length-type formulas for shifted shapes and trees.
  • q -factorials and q -binomial coefficients.
  • Grassmannians over finite fields: Gaussian elimination and row-reduced echelon form.
  • Sets and multisets. Statistics on permutations: inversions, cycles, descents.
  • Statistics on permutations (cont.). Equidistributed statistics. Major index. Records. Exceedances. Stirling numbers.
  • Stirling numbers (cont.). Set-partitions. Rook placements on triangular boards. Non-crossing and non-nesting set-partitions.
  • Eulerian numbers. Increasing binary trees. 3 Pascal-like triangles: Eulerian triangles, Stirling triangles of 1 st and 2 nd kind.
  • Discussion of problem set 1.
  • Discussion of problem set 1 (cont.).
  • Posets and lattices. Boolean lattice. Partition lattice. Young’s lattice.
  • Distributive lattices. Birkhoff’s fundamental theorem for finite distributive lattices.
  • Sperner’s property. Symmetric chain decompositions. Sperner’s and Dilworth’s theorems. Greene’s theorem.
  • Greene’s theorem vs Schensted correspondence. Up and down operators. Differential posets.
  • Differential posets (cont.). Fibonacci lattice. Unimodality of Gaussian coefficients.
  • Proof of unimodality of Gaussian coefficients (cont.). Theory of partitions. Euler’s pentagonal number theorem.
  • Partition theory (cont.). Franklin’s combinatorial proof of Euler’s pentagonal number theorem. Jacobi’s triple product identity.
  • Partition theory (cont.). Combinatorial proof of Jacobi’s triple product identity. Enumeration of trees. Cayley’s formula. Simple inductive proof of Cayley’s formula.
  • Two combinatorial proofs of Cayley’s formula.
  • Discussion of problem set 2.
  • Discussion of problem set 2 (cont.).
  • Matrix Tree Theorem. Spanning trees. Laplacian matrix of a graph. Reciprocity formula for spanning trees. Examples: complete graphs, complete bipartite graphs.
  • Matrix Tree Theorem (cont.). Products of graphs. Number of spanning trees in the hypercube graph. Oriented incidence matrix.
  • Proof of Matrix Tree Theorem using Cauchy-Binnet formula. Weighted and directed version of Matrix Tree Theorem. In-trees and out-trees.
  • Proof of Directed Matrix Tree Theorem based on induction.
  • Proof of Directed Matrix Tree Theorem via the Involution Principle. Electrical Networks and Kirchhoff’s Laws.
  • Electrical networks (cont.). Kirchhoff’s matrix. Relations of electrical networks with Matrix Tree Theorem and spanning trees. Series-parallel connections. Probabilistic interpretation of the electrical potential in terms of random walks on graphs.
  • Eulerian cycles in digraphs and B.E.S.T. theorem.
  • Parking functions. Tree inversion polynomials.
  • Pascal triangle. Bernoulli numbers. Riemann zeta function. Binary trees. Catalan numbers.
  • Lindstrom-Gessel-Viennot lemma. Lindstrom Theorem.
  • Proof of Lindstrom-Gessel-Viennot lemma. Weighted version of Lindstrom-Gessel-Viennot lemma. Plane partitions.
  • MacMahon Proposition. Rhombus tiling. Domino tiling. Kasteleyn Theorem. Temperley Theorem.
  • Discussion of problem set 3.
  • Plane partitions. Symmetric polynomials. Semi-standard Young tableau. Schur polynomial. Jacobi-Trudi Theorem. Hook-content formula.

Readings

Prerequisites & course information

Prereq: 18.701 or 18.703 U (Spring) 3-0-9 units

Sources