| Lec # | Topics | KEY DATES |
|---|---|---|
| 1 | Course Introduction Ramsey Theorem |
|
| 2 | Additive Number Theory Theorems of Schur and Van der Waerden |
|
| 3 | Lower Bound in Schur's Theorem Erdös-Szekeres Theorem (Two Proofs) 2-Colorability of Multigraphs Intersection Conditions |
|
| 4 | More on Colorings Greedy Algorithm Height Functions Argument for 3-Colorings of a Rectangle Erdös Theorem |
|
| 5 | More on Colorings (cont.) Erdös-Lovász Theorem Brooks Theorem |
|
| 6 | 5-Color Theorem Vizing's Theorem |
Problem set 1 due |
| 7 | Edge Coloring of Bipartite Graphs Heawood Formula |
|
| 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 |
Problem set 2 due |
| 10 | Acyclic Orientations Stanley's Theorem Two Definitions of the Tutte Polynomial |
|
| 11 | More on Tutte Polynomial Special Values External and Internal Activities Tutte's Theorem |
|
| 12 | Tutte Polynomial for a Cycle Gessel's Formula for Tutte Polynomial of a Complete Graph |
|
| 13 | Crapo's Bijection Medial Graph and Two Type of Cuts Introduction to Knot Theory Reidemeister Moves |
|
| 14 | Kauffman Bracket and Jones Polynomial | Problem set 3 due |
| 15 | Linear Algebra Methods Oddtown Theorem Fisher's Inequality 2-Distance Sets |
|
| 16 | Non-uniform Ray-Chaudhuri-Wilson Theorem Frankl-Wilson Theorem |
|
| 17 | Borsuk Conjecture Kahn-Kalai Theorem |
Problem set 4 due |
| 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 |
|
| 20 | Grinberg's Formula Lovász and Babai Conjectures for Vertex-transitive Graphs Dirac's Theorem |
|
| 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 | |
| 23 | Menger Theorem Gallai-Milgram Theorem |
Problem set 5 due |
| 24 | Dilworth Theorem Hall's Marriage Theorem Erdös-Szekeres Theorem |
|
| 25 | Sperner Theorem Two Proofs of Mantel Theorem Graham-Kleitman Theorem |
|
| 26 | Swell Colorings Ward-Szabo Theorem Affine Planes |
Problem set 6 due |
| 27 | Turán's Theorem Asymptotic Analogues |
|
| 28 | Pattern Avoidance The case of S3 and Catalan Numbers Stanley-Wilf Conjecture |
|
| 29 | Permutation Patterns Arratia Theorem Furedi-Hajnal Conjecture |
|
| 30 | Proof by Marcus and Tardos of the Stanley-Wilf Conjecture | Problem set 7 due |
| 31 | Non-intersecting Path Principle Gessel-Viennot Determinants Binet-Cauchy Identity |
|
| 32 | Convex Polyomino Narayana Numbers MacMahon Formula |
|
| 33 | Solid Partitions MacMahon's Theorem Hook-content Formula |
|
| 34 | Hook Length Formula | |
| 35 | Two Polytope Theorem | |
| 36 | Connection to RSK Special Cases |
Problem set 8 due |
| 37 | Duality Number of Involutions in Sn |
|
| 38 | Direct Bijective Proof of the Hook Length Formula | |
| 39 | Introduction to Tilings Thurston's Theorem |
