MATH 584

METHODS OF COMBINATORICS, Fall 2008

Summary of Lectures

This page contains a summary of the lectures in this course for Fall 2008. It lists only the topics discussed in each lecture. The text provides extensive discussion and additional material, so no additional notes are provided here.


1 8/25Mo: introduction (overview of topics)

Topic 1: Enumeration
2 8/27We: Hook-Length Formula
3 8/29Fr: RSK Correspondence, Schensted's Thm, Planarization
4 9/03We: Jeu de Taquin, Greene's Theorem
5 9/05Fr: Lagrange Inversion, motivated by Cayley's Formula
6 9/08Mo: polya review, bulgarian solitaire, ordinary exponential formula
7 9/10We: isom classes of rooted trees, power group enumeration
8 9/12Fr: snake oil examples, WZ pairs
9 9/15Mo: hypergeometric series, reluctant functions, binomial sequences
10 9/17We: Shift-Invariant operators, expansion theorem
11 9/19Fr: umbral algebra isomorphism theorem, idea of connection coeffs

Topic 2: Ramsey theory and Combinatorial Games
12 9/22Mo: pigeonhole principle (two squares, generalized chess player)
13 9/24We: Stanley-Wilf conjecture, infinite Ramsey intro
14 9/26Fr: infinite Ramsey theorem, compactness, intro canonical Ramsey
15 9/29Mo: canonical Ramsey theorem, pattern Ramsey numbers
16 10/01We: anti-Ramsey numbers (cycles), intro to Schur/Rado/VdWaerden
17 10/03Fr: Van der Waerden's Theorem
18 10/06Mo: apply VdW to Rado's regular equations, start parameter Ramsey
19 10/08We: chromatic Ramsey number, degree Ramsey number
20 10/10Fr: more degree Ramsey, on-line chromatic Ramsey number
21 10/13Mo: more on-line chromatic, forests, triangles & outerplanar, on-line degree Ramsey lower bound
22 10/15We: odr for trees, consistent Painter theorem
23 10/17Fr: intro to game chromatic number
24 10/20Mo: game chromatic number at most 18 for planar graphs

Topic 3: Design theory
25 10/22We: Difference sets, the Multiplier Theorem
26 10/24Fr: Steiner triple systems, resolvable designs
27 10/27Mo: pairwise-balanced designs, orthogonal arrays, disproof of Euler conjecture
28 10/29We: Baranyai's Theorem, covering designs, idea of Rodl nibble
29 10/31Fr: tools for Wilson's Theorem
30 11/03Mo: more pieces of Wilson's Theorem

Topic 4: Topological methods
31 11/05We: Sperner's Lemma, Brouwer Fixed-Point Theorem, bandwidth
32 11/07Fr: equivalence of Sperner, Connector, Hex, Pouzet, Brouwer
33 11/10Mo: Tucker's Combinatorial Lemma
34 11/12We: Borsuk-Ulam Theorem, Kneser Conjecture
35 11/14Fr: Gale's Lemma, Schrijver graphs, Ham Sandwich & applications
36 11/17Mo: disproof of Borsuk's Conjecture

Topic 5: Algebraic methods
36 11/17Mo: RayChaudhuri-Wilson Theorem
37 11/19We: Oddtown Theorem, two-distance sets, large t-uniform family with small intersections
38 11/21Fr: Nonuniform modular RW Theorem, application to Ramsey construction
39 12/1Mo: Omitted-Intersection Theorem, unit-distance graph, modular Snevily Theorem
40 12/3We: combinatorial nullstellensatz, Cauchy-Davenport Theorem
41 12/5Fr: Chevalley-Warning Theorem, transversal of hyperplanes in cubes, existence of regular subgraphs
42 12/8Mo: ex(n;k-regular), generalized factors
43 12/10We: generalized factors, stunted trees, antimagic graphs