The following textbooks are the main textbooks for the class:
Stanley, R. P. Enumerative Combinatorics. Vol. I and II. Cambridge, UK: Cambridge University Press, 1999. ISBN: 0521553091 (hardback: vol. I); 0521663512 (paperback: vol. I); 0521560691 (hardback: vol. II).
Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998. ISBN: 0387984917.
———. Extremal Graph Theory. New York, NY: Dover, 2004. ISBN: 0486435962.
Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000. ISBN: 3540663134.
The following textbooks can be used as supplemental reading:
Diestel, R. Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1997. ISBN: 3540261834. (Available electronically on the Graph Theory Web site by R. Diestel).
Matousek, J. Lectures on Discrete Geometry (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 2002. ISBN: 0387953736.
The following readings specifically deal with problem 6 from Problem Set 1:
The original paper is here:
Burago, Ju. D., and V. A. Zalgaller. "Polyhedral embedding of a net." Vestnik Leningrad Univ 15 (1960): 66-80. (In Russian)
A recent relatively simple solution:
Maehara, H. "Acute triangulations of polygons." European J Combin 23 (2002): 45-55.
Interestingly enough, if one allows right triangles there exist plentiful literature:
Baker, B. S., E. Grosse, and C. S. Rafferty. "Nonobtuse triangulation of polygons." Discrete Comput Geom 3 (1988): 147-168.
Bern, M., and D. Eppstein. "Polynomial-size nonobtuse triangulation of polygons." Internat J Comput Geom Appl 2 (1992): 241-255; Errata 449-450.
Bern, M., S. Mitchell, and J. Ruppert. "Linear-size nonobtuse triangulation of polygons." Discrete Comput Geom 14 (1995): 411-428.
The following table lists the readings assigned for each lecture.
| Lec # | Topics | Readings |
|---|---|---|
| 1 | Course Introduction Ramsey Theorem | Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 182-189. ISBN: 0387984917. |
| 2 | Additive Number Theory Theorems of Schur and Van der Waerden | Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 326. ISBN: 3540663134. Khinchin, A. Y. Three Pearls of Number Theory. Mineola, NY: Dover Publications, Inc., 1998, section 1. ISBN: 0486400263. (Reprint of the 1952 translation.) |
| 3 | Lower Bound in Schur's Theorem Erdös-Szekeres Theorem (Two Proofs) 2-Colorability of Multigraphs Intersection Conditions | Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 230, 327, and 65-66. ISBN: 3540663134. |
| 4 | More on Colorings Greedy Algorithm Height Functions Argument for 3-Colorings of a Rectangle Erdös Theorem | Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 66-67. ISBN: 3540663134. Luby, M., D. Randall, and A. Sinclair. "Markov Chain Algorithms for Planar Lattice Structures." FOCS 1995. (Paper) |
| 5 | More on Colorings (cont.) Erdös-Lovász Theorem Brooks Theorem | Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 67. ISBN: 3540663134. Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 145-149. ISBN: 0387984917. |
| 6 | 5-Color Theorem Vizing's Theorem | Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 146-154. ISBN: 0387984917. ———. Extremal Graph Theory. New York, NY: Dover, 2004, pp. 221-234. ISBN: 0486435962. |
| 7 | Edge Coloring of Bipartite Graphs Heawood Formula | Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 154-161. ISBN: 0387984917. ———. Extremal Graph Theory. New York, NY: Dover, 2004, pp. 243-254. ISBN: 0486435962. |
| 8 | Glauber Dynamics The Diameter Explicit Calculations Bounds on Chromatic Number via the Number of Edges, and via the Independence Number | |
| 9 | Chromatic Polynomial NBC Theorem | |
| 10 | Acyclic Orientations Stanley's Theorem Two Definitions of the Tutte Polynomial | Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 335-339. ISBN: 0387984917. |
| 11 | More on Tutte Polynomial Special Values External and Internal Activities Tutte's Theorem | Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 345-354. ISBN: 0387984917. |
| 12 | Tutte Polynomial for a Cycle Gessel's Formula for Tutte Polynomial of a Complete Graph | Gessel, I. M. "Enumerative applications of a decomposition for graphs and digraphs." Discrete Math 139, no. 1-3 (1995): 257–271. (Paper) |
| 13 | Crapo's Bijection Medial Graph and Two Type of Cuts Introduction to Knot Theory Reidemeister Moves | Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 358-363. ISBN: 0387984917. Korn, M., and I. Pak. Combinatorial evaluations of the Tutte polynomial. Preprint (2003) available at Research (Igor Pak Home Page). (Paper) |
| 14 | Kauffman Bracket and Jones Polynomial | Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 364-371. ISBN: 0387984917. |
| 15 | Linear Algebra Methods Oddtown Theorem Fisher's Inequality 2-Distance Sets | Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, section 14. ISBN: 3540663134. |
| 16 | Non-uniform Ray-Chaudhuri-Wilson Theorem Frankl-Wilson Theorem | |
| 17 | Borsuk Conjecture Kahn-Kalai Theorem | Aigner, M., and G. Ziegler. Proof from the BOOK. 2nd ed. New York, NY: Springer-Verlag, August 1998, pp. 83-88. ISBN: 3540636986. |
| 18 | Packing with Bipartite Graphs Testing Matrix Multiplication | |
| 19 | Hamiltonicity, Basic Results Tutte's Counter Example Length of the Longest Path in a Planar Graph | Diestel, R. Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1997, section 10.1. ISBN 3540261834. (Available electronically on the Graph Theory Web site by R. Diestel). |
| 20 | Grinberg's Formula Lovász and Babai Conjectures for Vertex-transitive Graphs Dirac's Theorem | Bollobás, B. Extremal Graph Theory. New York, NY: Dover, 2004, pp. 143-146. ISBN: 0486435962. |
| 21 | Tutte's Theorem Every Cubic Graph Contains either no HC, or At Least Three Examples of Hamiltonian Cycles in Cayley Graphs of Sn | |
| 22 | Hamiltonian Cayley Graphs of General Groups | Pak, I., and R. Radoicic. "Hamiltonian paths in Cayley graphs." Preprint (2002) available at Research (Igor Pak Home Page). (Paper) |
| 23 | Menger Theorem Gallai-Milgram Theorem | Diestel, R. Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1997, sections 2.5, and 3.3. ISBN 3540261834. (Available electronically on the Graph Theory Web site by R. Diestel). |
| 24 | Dilworth Theorem Hall's Marriage Theorem Erdös-Szekeres Theorem | Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 38-39, and 97-100. ISBN: 3540663134. |
| 25 | Sperner Theorem Two Proofs of Mantel Theorem Graham-Kleitman Theorem | Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 40-41, and 45-46. ISBN: 3540663134. |
| 26 | Swell Colorings Ward-Szabo Theorem Affine Planes | Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 43-45, and 161-163. ISBN: 3540663134. |
| 27 | Turán's Theorem Asymptotic Analogues | Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 108-111. ISBN: 0387984917. |
| 28 | Pattern Avoidance The case of S3 and Catalan Numbers Stanley-Wilf Conjecture | |
| 29 | Permutation Patterns Arratia Theorem Furedi-Hajnal Conjecture | Arratia, R. "On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern." Electron J Combin 6, no. 1 (1999). (Paper) |
| 30 | Proof by Marcus and Tardos of the Stanley-Wilf Conjecture | Marcus, A., and G. Tardos. "Excluded permutation matrices and the Stanley-Wilf conjecture." J Combin Theory Ser A 107, no. 1 (2004): 153–160. |
| 31 | Non-intersecting Path Principle Gessel-Viennot Determinants Binet-Cauchy Identity | Stanley, R. P. Enumerative Combinatorics. Vol. I. Cambridge, UK: Cambridge University Press, 1999, section 2.7. ISBN: 0521553091 (hardback : vol. I); 0521663512. (paperback : vol. I). |
| 32 | Convex Polyomino Narayana Numbers MacMahon Formula | Stanley, R. P. Enumerative Combinatorics. Vol. II. Cambridge, UK: Cambridge University Press, 1999, pp. 378. ISBN: 0521560691 (hardback: vol. II). |
| 33 | Solid Partitions MacMahon's Theorem Hook-content Formula | Stanley, R. P. Enumerative Combinatorics. Vol. II. Cambridge, UK: Cambridge University Press, 1999, section 7. ISBN: 0521560691 (hardback: vol. II). |
| 34 | Hook Length Formula | Pak, I. "Hook Length Formula and Geometric Combinatorics." Séminaire Lotharingien de Combinatoire 46 (2001): article B46f. |
| 35 | Two Polytope Theorem | Pak, I. "Hook Length Formula and Geometric Combinatorics." Séminaire Lotharingien de Combinatoire 46 (2001): article B46f. |
| 36 | Connection to RSK Special Cases | Pak, I. "Hook Length Formula and Geometric Combinatorics." Séminaire Lotharingien de Combinatoire 46 (2001): article B46f. |
| 37 | Duality Number of Involutions in Sn | Pak, I. "Hook Length Formula and Geometric Combinatorics." Séminaire Lotharingien de Combinatoire 46 (2001): article B46f. |
| 38 | Direct bijective Proof of the Hook Length Formula | Novelli, J. C., I. Pak, and A. V. Stoyanovsky. "A direct bijective proof of the hook-length formula." Discrete Mathematics and Theoretical Computer Science 1 (1997): 53-67. |
| 39 | Introduction to Tilings Thurston's Theorem | Thurston, W. P. "Conway's tiling groups." Amer Math Monthly 97, no. 8 (1990): 757-773. |