Math 402/802 (2021)

Enumerative Combinatorics (projects)

tiling
composition of an integer
bijective proof
inclucion-exclusion principle
Task
Learn a new theorem in enumerative combinatorics and communicate it in written form.
Requirements
  • Each student will focus on a different combinatorial result.
  • The written document will introduce/motivate, correctly state, and prove a theorem. It will also include at least one interesting example, construction, or special case illustrating the theorem. The article will be as self-contained as possible. The new document must be typed, be at most eight pages in length (with one inch margins and a 12pt font), and be available in PDF format.
Assessment
Project grades will be computed as follows:
Due Date Element Weight
2021.10.08 outline 10%
2021.11.12 rough draft 20%
2021.11.19 feedback 20%
2021.12.03 project 50%
Advice
Paul R. Halmos and Steven L. Kleiman each provide some suggestions on how to present mathematics.
Comments
By design, this assignment is very open-ended. Students are strongly encouraged to explore examples. Students are also encouraged to formulate, test, and prove their own conjectures. Here are some questions that you may want to consider:
  • What was the original motivation or historical context for your theorem?
  • Can you give more than one proof of your theorem?
  • Does your theorem have any interesting specializations or important applications?
  • Can your theorem be generalized?
Potential Topics
The following results are natural candidates:
  1. Alternating permutations
  2. Art gallery theorem [AZ14, §39] — YOUTONG FANG
  3. Aztec diamond theorem [Ai07, §1.H]
  4. BEST theorem [Ai07, §9.H], [LW01, §11] — CAROLINE MORAL RUMOLD
  5. Bounding permanents [AZ14, §37], [LW01, §11]
  6. Cayley formula [AZ14, §32], [LW01, §2] — ALEX DARCOVICH
  7. Combinatorial congruences [BQ03, §8]
  8. Combinatorial nullstellensatz [TV10, §9.1]
  9. Combinatorics of continued fractions [BQ03, §4]
  10. Combinatorics of harmonic numbers [BQ03, §7]
  11. Crossing lemma [AZ, §44]
  12. De Bruijn sequences [LW01, §8] — ARITRA SAHA
  13. Dehn-Sommerville relations [BR15, §5.1]
  14. Ehrhart theorem [BR15, §3.3]
  15. Erdős–Ko–Rado theorem [AZ14, §29], [LW01, §6] — JOHNATHAN FRAMPTON
  16. Eulerian circuits [Ai07, §9.H], [St13, §10]
  17. Finite Kakeya problem [AZ14, §34] — ISRA MOHAMMED
  18. Friendship theorem [AZ14, §43] — OLIVIA GRACE
  19. Hadamard matrices [LW01, §18], [St13, §12.6]
  20. Hamming bound [LW01, §20] — STEFAN CRUCEAT
  21. Jacobi triple product [Ai07, §9.H]
  22. Lindström–Gessel–Viennot lemma [Ai07, §5.4], [AZ14, §31]
  23. Matrix-Tree theorem [Ai07, §5.H], [LW01, §36], [St13, §9]
  24. Marriage theorem [AZ14, §29], [LW01, §43] — EMILY CULLINGWORTH
  25. Pentagonal number theorem [Ai07, §3.4], [AZ14; §33] — WANSHAN LI
  26. Pick's theorem [BR15, §2.6] — IAN MCCLEAN
  27. q-binomial coefficients [LW01, §24], [St13, §6]
  28. Sperner's lemma [AZ14, §27.6], [LW01, §6] — HOLLY BRIEN
  29. Sylvester-Gallai theorem — MICHAEL IRVINE
  30. Szemerédi–Trotter theorem [TV10, §8.2] — HARLEY EASTON
  31. Tiling rectangles [AZ14, §28], [St13, §11.5]
  32. Zeckendorf's theorem; [GKP94, §6.6] — ASHLEY CORIC
References
[Ai07] Martin Aigner, A course in enumeration, Graduate Texts in Mathematics 238, Springer, 2007, ISBN: 978-3-540-39032-9
[AZ14] Martin Aigner and Günter Ziegler, Proofs from The Book, Fifth edition, Springer-Verlag, Berlin, 2014, ISBN: 978-3-662-44204-3
[BQ03] Arthur Benjamin and Jennifer Quinn, Proofs that really count, The Dolciani Mathematial Exposition 27, Mathematical Association of America, Washington, 2003, ISBN: 0-88385-333-7
[BR15] Matthais Beck and Sinai Robins, Computing the continuous discretely, Second edition, Undergraduate Texts in Mathematics, Springer, New York, 2015, ISBN: 978-1-4939-2968-9
[GKP94] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics, Second Edition, Addison-Wesley, 1994, ISBN: 0-201-55802-5
[St13] Richard Stanley, Algebraic combinatorics, Undergraduate Texts in Mathematics, Springer, New York, 2013, ISBN: 978-1-4614-6997-1
[TV10] Terance Tao and Van H. Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics 105, Cambridge University Press, Cambridge, 2010, ISBN: 978-0-521-13656-3
[LW01] Jacobus H. van Lint and Richard M. Wilson, A course in combinatorics, Second edition, Cambridge University Press, Cambridge, 2001, ISBN: 0-521-00601-5