Combinatorics of Posets (Math 206A, Fall 2020)

Instructor: Igor Pak
(see email instructions on the bottom of the page).

CCLE Website: is here.

Class schedule: MWF 2:00 - 2:50 pm, via Zoom.
Zoom meeting link and password will be sent by email from the course my.ucla site.

Office Hours: M 3-4, via Zoom (stay after class).

Grading: The grade will be based on attendance, class participation (20%), and homeworks (80%) which will be posted below.

Difficulty: This is a graduate class in Combinatorics. Students are assumed to be fully familiar with undergraduate Combinatorics and Graph Theory (see Math 180 and Math 184).

Content

Lecture notes: Individual lecture notes are posted on CCLE website if and when they come available.

Update: All lecture notes can now be download in one large file, 188 pages, 92 Mb.
Warning: these are neither checked nor edited. Possibly, completely useless to anyone.

Reading

Textbooks:

• R.P. Stanley, Enumerative Combinatorics (EC), vol 1 (second edition), and vol. 2. Download vol 1 from the author's website.
• D.B. West, Combinatorial Mathematics, see Ch. 12 on CCLE website.
• S. Jukna, Extremal combinatorics. With applications in computer science (second edition), Springer, 2011, see Ch. 9 on CCLE website.
• W. T. Trotter, Combinatorics and partially ordered sets. Dimension theory, Johns Hopkins University Press, 1992, see Ch. 1 on CCLE website (to be posted).
• Ph. Flajolet and R. Sedgewick, Analytic Combinatorics, CUP, 2009, available from here.
• R. Diestel, Graph Theory, Springer, 2016 (5th edition).
• A. Schrijver, Combinatorial Optimization, volumes A, B, and C, about 2000 pages, Springer, 2004, short sections on CCLE.
• B. Sagan, The Symmetric Group, Second Ed., Springer, 2000, see portion of Ch. 3 on CCLE (also downloadable from the Springer website via UCLA library proxy).
• N. Alon and J. Spencer, The Probabilistic Method, Wiley, 2016, see Ch. 6 on CCLE.

None of these are required, all are recommended. Selected relevant chapters will be posted on CCLE.

Surveys:

• C. Greene and D.J. Kleitman, Proof techniques in the theory of finite sets, in Studies in combinatorics, MAA, 1978, 22-79 (huge file on CCLE).
• G. Brightwell, Models of random partial orders, in Surveys in combinatorics, BCC, 1993, 53-83.
• G. Brightwell and D. West, Partially Ordered Sets, Chapter 11 in Handbook of Discrete and Combinatorial Mathematics, CRC Press, 2000, 717-752.
• W.T. Trotter, Partially ordered sets, Chapter 8 in Handbook of combinatorics, Elsevier, 1995, 433-480.

Lecture by lecture background reading

1. Basic notions
   • See West (§12.1), Trotter's survey (§1), or Jukna (§9.1.1)

2. Dilworth's theorem
   • Dilworth's theorem
   • See West, Ch. 12.
   • R.P. Dilworth, A Decomposition Theorem for Partially Ordered Sets, Ann. of Math., 1950.
   • M.A. Perles, A proof of Dilworth's decomposition theorem for partially ordered sets, Israel J. Math., 1963
   • E.C. Milner, Dilworth's decomposition theorem in the infinite case, in The Dilworth theorems, Birkhauser, 1990, 30-35.

3. Gallai-Milgram theorem
   • See West, Ch. 12.
   • T. Gallai and A.N. Milgram Verallgemeinerung eines graphentheoretischen Satzes von Rédei, Acta Sci. Math., 1960
   • S. Bessy and S. Thomassé, Spanning a strong digraph by α circuits: a proof of Gallai's conjecture, Combinatorica, 2007.
   • J.M. Brochet and M. Pouzet, Gallai-Milgram properties for infinite graphs, Discrete Math., 1991.

4. Chains and antichains in the Boolean lattice
   • de Bruijn-Tengbergen-Kruyswijk theorem (see West, Ch. 12, Sym chains decomposition section).
   • Greene-Kleitman bracket sequences construction (ibid.)
   • Fubini numbers (see Flajolet-Sedgewick, "surjection numbers" on p. 110, 243-245, 259-260).
   • Hansel theorem (see West, Ch. 12)

5. Gray codes and universal sequences
   • Gray codes and De Bruijn sequences (see J. Matousek and J. Nesetril, Invitation to Discrete Mathematics, §4.5).
   • Universal sequences and the Lipski Theorem (see Jukna, Thm 9.4).
   • F. Chung, P. Diaconis and R. Graham, Universal cycles for combinatorial structures, Discrete Math., 1992.
   • F. Ruskey, Combinatorial Gray Code, in Encyclopedia of Algorithms, Springer, 2016.

6. Extremal Combinatorics
   • LYM inequality (see West, Ch. 12).
   • q-LYM inequality (see more on q-binomial coefficients in Stanley, §1.7).
   • Littlewood-Offord Problem (see M. Aigner and G. Ziegler, Proofs from the Book, 5th Edition, Ch. 24).
   • Bollobás's Theorem (see Jukna, Ch. 9 and this remark, or these lecture notes by Jacob Fox).
   • Further Bollobás-type theorems via Linear Algebra (see L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics, §6.2).

7. Perfect graphs
   • See Diestel, §5.5; see also earlier sections for notations and some background.
   • Weak Perfect Graph Conjecture.
   • Strong Perfect Graph Conjecture.
   • Chordal graph.
   • another self-contained presentation Lovász's proof of the WPGC is in this thesis by Andrew King (§3.2).
   • C.T. Hoang and R. Sritharan, Perfect Graphs, in Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, 2015.

8. Subsets of distinct numbers via Sperner's property (using LA)
   • R. Proctor, Solution of Two Difficult Combinatorial Problems with Linear Algebra, Amer. Math. Monthly, 1982.
   • R.P. Stanley, Weyl groups, the hard Lefschetz theorem, and the Spemer property, SIAM J. Algebraic Discrete Methods, 1980.
   • R.P. Stanley, The Erdős-Moser Conjecture, talk slides, 2009.
   • Sequence A025591, OEIS.
   • B.D. Sullivan, On a Conjecture of Andrica and Tomescu, Journal of Integer Sequences, 2013.

9. Greene-Kleitman theorems and permutations
   • For permutation posets see RSK correspondence in Sagan, §3.1, 3.3 and 3.5 (the proofs require intermediate sections).
   • For connection of RSK and patience sorting, see D. Aldous and P. Diaconis, Longest increasing subsequences..., Bull. AMS, 1999.
   • T. Britz and S. Fomin, Finite posets and Ferrers shapes, Advances in Math., 2001 (a readable survey on the subject).

10. Greene-Kleitman theorems via Combinatorial Optimization
    • Min-cost circulation Thm. (Schrijver, §12.1-2)
    • Greene-Kleitman theorems (Schrijver, §14.6-7)
    • A. Frank, On chain and antichain families of a partially ordered set, JCTA, 1980.
    • N. Linial, Extending the Greene-Kleitman theorem to directed graphs, JCTA, 1981.

11. Operations on posets and distributive lattices
    • See Stanley, §3.1-4
    • Distributive lattice
    • Fundamental Theorem for Finite Distributive Lattices

12. Linear extensions, labeled trees and standard Young tableaux
    • Linear extensions of posets (see Stanley, §3.5)
    • Number of linear extensions of series-parallel posets.
    • Zigzag posets and alternating permutations (see R. Stanley, A survey of alternating permutations, §1).
    • For asymptotics of the number of alternating permutations, see Flajolet-Sedgewick, pages 5, 144, and 269.
    • Hook-length formula (see Sagan, §3.10-11)
    • Uniform hook-walk proofs: Greene-Nijenhuis-Wilf for Young tableaux, and Sagan-Yeh for increasing trees.
    • W. Feit, The degree formula for the skew-representations of the symmetric group, PAMS (1953).

13. Bounds on the number of linear extensions
    • Weak Bruhat order
    • For upper/lower bounds via chains/antichains, see §2.1 in A. Morales, I. Pak and G. Panova, Asymptotics of the number of standard Young tableaux of skew shape, Europ. J. Comb., 2018.
    • I.A. Bochkov and F.V. Petrov, The bounds for the number of linear extensions via chain and antichain coverings (2020).
    • For permutation posets as ideas in the weak Bruhat order see S. Felsner and L. Wernisch, Markov chains for linear extensions, the two-dimensional case, SODA (1997).
    • For 2-dim posets vs. Bruhat orders, see also Lemma 3.1 in S. Dittmer and I. Pak, Counting linear extensions of restricted posets, 2018.

14. Asymptotics of the number of linear extensions
    • superfactorial and G-function (see asymptotics section). See also Example VI.9 in Flajolet-Sedgewick.
    • square poset example in §2.3 of the Morales-Pak-Panova paper.
    • For general Young diagrams and the tilted square conjecture, see I. Pak, Skew shape asymptotics, a case-based introduction, §4 and §12.2.
    • For number of linear extension of the Boolean lattice, see J. Sha and D.J. Kleitman, The number of linear extensions of subset ordering, Discrete Math. 1987.
      See also Cooper's note computing asymptotics in the Sha-Kleitman's paper.
    • G.R. Brightwell and P. Tetali, The number of linear extensions of the boolean lattice, Order, 2003.

15. Schützenberger's promotion and its applications
    • Jeu de taquin
    • M.P. Schützenberger, Promotion des morphismes d'ensembles ordonnés (in French), Discrete Math., 1972.
    • Stanley's theorem on the number of reduced factorizations in R. Stanley, On the number of Reduced decompositions..., Europ. J. Comb., 1984.
    • For the Lascoux-Schützenberger bijection, see §5 in A. Edelman and C. Greene, Balanced tableaux, Advances in Math., 1987.
    • More details with all the proofs are in A. Garsia, The saga of reduced factorizations, LACIM, 2002,

16. Schützenberger's evacuation and its applications
    • P. Edelman, T. Hibi and R.P. Stanley, A recurrence for linear extensions, Order, 1989.
    • See §2 in R.P. Stanley, Promotion and evacuation, Electronic Journal Combin., 2008.
    • C. Malvenuto and C. Reutenauer, Evacuation of labelled graphs, Discrete Math., 1994.
    • M.D. Haiman, Dual equivalence with applications..., Discrete Math., 1992.

17. Domino and P-domino tabelaux
    • See §3 in R.P. Stanley, Promotion and evacuation, Electronic Journal Combin., 2008.
    • A. Berenstein and A.N. Kirillov, Domino tableaux, Schützenberger involution, and the symmetric group action, Discrete Math., 2000.
    • J. R. Stembridge, Canonical bases and self-evacuating tableaux, Duke Math. J., 1996.
    • See §2.3 M.A.A. van Leeuwen, The Robinson-Schensted and Schützenberger algorithms, an elementary approach, Electron. J. Combin., 1996.
    • See case r=2 in S. Fomin and D. Stanton, Rim Hook Lattices, St. Petersburg Math Journal, 1997.
    • D.W. Stanton and D.E. White, A Schensted algorithm for rim hook tableaux, JCTA, 1985.
    • T. Lam, Growth diagrams, domino insertion and sign-imbalance, JCTA, 2004

18. Poset sorting and HLF
    • See §3.10 in Sagan and this NPS website (in French)
    • J-C Novelli, I. Pak and A.V. Stoyanovsky, A direct bijective proof of the hook-length formula, DMTCS, 1997.
    • I. Fischer, A bijective proof of the hook-length formula for shifted standard tableaux, 2001.
    • B. Beáta, Bijective proofs of the hook formula for rooted trees, Ars Comb, 2012.

19. P-partition theory
    • See §3.15 in Stanley, EC1.
    • R.P. Stanley, Ordered structures and partitions, Harvard University, thesis, 1971.
    • A.P. Hillman and R.M. Grassl, Reverse Plane Partitions and Tableau Hook Numbers, JCTA, 1976.
    • See also volume argument in I. Pak, Hook Length Formula and Geometric Combinatorics, SLC, 2001.

20. Poset polytopes
    • R.P. Stanley, Two poset polytopes, Discrete and Computational Geometry, 1986.
    • See also Schrijver, §5.9 and §14.5.

21. Applications of poset polytopes via Ehrhart polynomial and Alexandrov-Fenchel inequalities
    • Order polynomial
    • Ehrhart polynomial
    • R.P. Stanley, A chromatic-like polynomial for ordered sets, Conf Proc., May 1970.
    • Mixed volume
    • R.P. Stanley, Two combinatorial applications of the Aleksandrov-Fenchel inequalities, JCTA, 1981.
    • J. Kahn and M. Saks, Balancing poset extensions, Order, 1984.

22. More applications and generalizations of poset polytopes
    • T. Ligget, Ultra Logconcave Sequences and Negative Dependence, JCTA, 1997.
    • For upper bound on #LE for posets with LYM property, see §5 in G.R. Brightwell and P. Tetali, linked above.
    • For more on the upper bound, see §8.8 in G.R. Brightwell and W.T. Trotter, Counting Linear Extensions: Polyhedral Methods, Section 8 of monograph draft.
    • J. Kahn and J.H. Kim, Entropy and Sorting, Jour. Comp. Sci. Systems, 1995.
    • L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math., 1972.
    • See also §2 of L. Lovász and A. Schrijver, Matrix cones, projection representations, and stable set polyhedra, DIMACS, 1990.

23. Correlation inequalities
    • Ahlswede-Daykin inequality.
    • Corolary 2 on p. 4564 in A. Hammett and B. Pittel, How often are two permutations comparable?, Trans. AMS, 2008.
    • Lemma in D.J. Kleitman, Families of non-disjoint subsets, JCT, 1966.
    • Alon-Spencer, §6.1, see Ch. 6 on CCLE.

24. The FKG and XYZ inequalities
    • Alon-Spencer, §6.2-3, see Ch. 6 on CCLE.
    • FKG inequality
    • XYZ inequality
    • C.M. Fortuin, P.W. Kasteleyn and J. Ginibre, Correlation inequalities on some partially ordered sets, CMP, 1971.
    • L.A. Shepp, The XYZ conjecture and the FKG inequality, Annals of Probability, 1982.
    • P.M. Winkler, Correlation among partial orders, SIAM Jour. ADM, 1983.

25. Proof of the XYZ inequality
    • Alon-Spencer, §6.4, see Ch. 6 on CCLE.
    • For applications of XYZ inequality, see P. Winkler, Average height in a partially ordered set, Discrete Math., 1982.
    • G.R. Brightwell and W.T. Trotter, A combinatorial approach to correlation inequalities, Discrete Math., 2002.
    • Strict XYZ inequality and an extension is in P.C. Fishburn, A correlational inequality for linear extensions of a poset, Order, 1984.

26. Comparisons via Linear extensions
    • Nontransitive dice
    • 1/3 - 2/3 conjecture
    • Thm 1 in P.M. Winkler, Average height in a partially ordered set, Discrete Math., 1982.
    • P.C. Fishburn, On the family of linear extensions of a partial order, JCTB, 1974.
    • P.J. Polymath, Intransitive dice VI, Gowers' weblog, 2017.
    • J. Hązła et al., The probability of intransitivity in dice and close elections, PTRF, 2020.
    • N. Linial, The information-theoretic bound is good for merging, SIAM Jour. Comput., 1984.
    • S.S. Kislitsyn, A finite partially ordered set and its corresponding set of permutations, Mathematical Notes, 1968.
    • M.L. Fredman, How good is the information theory bound in sorting?, Theor. Comp. Sci., 1976.

27. Kahn-Saks theorem via Grünbaum's theorem
    • Grünbaum's theorem
    • J. Kelner's friendly lecture notes (Grünbaum via Brunn-Minkowski)
    • For the friendly proof of a weak version of Kahn-Saks see §12.3 in J. Matousek, Lectures on Discrete Geometry, 2002.
    • J. Kahn and M. Saks, Balancing poset extensions, Order, 1984.
    • G.R. Brightwell, S. Felsner and W.T. Trotter, Balancing pairs and the cross product conjecture, Order, 1995.

28. Sorting probability, duality and complexity
    • A. Sidorenko, Inequalities for the number of linear extensions, Order, 1991.
    • B. Bollobás, G. Brightwell and A. Sidorenko, Geometrical techniques for estimating numbers of linear extensions, Eur. Jour. Combin., 1999.
    • T. Tao, Open question: the Mahler conjecture on convex bodies, Tao's blog, 2007.
    • J. Komlós, A strange pigeon-hole principle, Order, 1990.
    • W.T. Trotter, W.V. Gehrlein and P.C. Fishburn, Balance theorems for height-2 posets, Order, 1992.
    • E.J. Olson and B.E. Sagan, On the 1/3 - 2/3 Conjecture, Order, 2018.
    • S.H. Chan, I. Pak and G. Panova, Sorting probability for large Young diagrams, 2020.
    • S.H. Chan, I. Pak and G. Panova, Sorting probability of Catalan posets, 2020.
    • G. Brightwell and P. Winkler, Counting linear extensions, Order, 1991.
    • S. Dittmer and I. Pak, Counting linear extensions of restricted posets, 2019.

Home assignments

• HA1 is here, due Oct 19.

• HA2 is here, due Nov 2.

• HA3 is here, due Nov 16.

• HA4 is here, due Dec 4.

Collaboration policy:
For the home assignments, you can form discussion groups of up to 3 people each. In fact, I would like to encourage you to do that. You can discuss problems but have to write your own separate solutions. You should write the list of people in you group on top of each HA.

Click here to return to Igor Pak Home Page.

To e-mail me, click here and delete .zzz
Put Math 206A in the Subject line.

You must begin your email with "Dear Professor Pak," and nothing else in the first line.
Any and all grade discussion must be done from your official UCLA email. Enclose your UCLA id number and full name as on the id on the bottom.

Last updated 12/11/2020.