Spring 2024:
Math 580: Combinatorics; graduate course at UIUC.
MWF: 12:00-12:50 EB 303
Test 1: March 6: Wednesday 5-7 pm, location: TBA
Test 2: April 25: Thursday 5-7 pm, location: TBA
Office hours: After class.
Study sessions: Wednesdays 2:00-3:50pm, [The Instructor likely attend only 2:30-3:20] Lincoln Hall 1066
Final exam: Friday, May 3 1:30--4:30 p.m, in the class room.
Homework problems Spring 2024: (likely to be announced via Canvas)
Lectures: Those note follow Doug West: Combinatorial Mathematics book, in average, one lecture notes covers about one 50 minutes lecture (or maybe a bit more). Note that there is some overlap between consecutive lectures, in order to fit material of one class into one file.
Lecture I: page1, page2, page 3: Basic counting, Pigeonhole Principle, Words.
Lecture II: Binomial Theorem, Pascal triangle, Basic identities of binomial coefficients.
Lecture III: Delannoy numbers, Cayley formula (number of trees).
Lecture IV: Corollaries of Cayley formula proof; Ballot theorem;
Lecture V: Catalan numbers, Number of rooted binary trees, Number of triangulations, Section 2.1: Fibonacci recurrences, Number of deragements of permutations, basic recursion formulas,
Lecture VI: Number of simple k-words on [n]; numbef of partitions of [n] into k non-empty classes; Number of permutations with k-cycles; 2.2 Section: solution methods;
Lecture VII: Characteristic equations, Tower of Hanoi, Number of regions of plane, Inhomogeneous sequences, Generating function method.
Lecture VIII: Main Theorem of linear recurrences, Section 2.3: Substitution method. Chapter 3.1: Ordinary Generating functions,
Lecture IX: Section 3.1: Ordinary Generating functions, Permutation statistic, Worpitzky Theorem.
Lecture X: Worpitzky Theorem; Section 3.2: OGF Coefficients; Snake Oil;
Lecture XI: Snake Oil, Section 3.3: Exponential Generating functions,
Lecture XII: Stirling number of seconds kind; Stirling number (first kind); Binomial Inversion formula; Exponential Formula, Partition of an n-set; Permutations and Involutions;
Lecture XIII: Number of connected graphs; Exponential Formula; Partitions of an n-set; Permutations and Involutions; Langrange Involuation Formula; Section 3.4: Partitions of Integers;
Lecture XIV: Hardy-Ramanujan formula on number of partitions; Ferrer's diagram; Fallon's formula; Euler's formula; 4.1 Section: Inclusion Exclusion Formula; Stirling's numbers;
Lecture XV: Inclusion Exclusion Formula; Generalized PIE; Disjoint Path Systems; MacMahon Theorem; Section 4.2: Pólya-Redfield Method;
Lecture XVI: Generalization of derangements; Signed Involutions; Section 4.2: Pólya-Redfield Method; Burnside Lemma;
Lecture XVII: Determinants, disjoint paths systems; MacMahon Theorem on number of rhombic tilings; Section 4.2: Polya-Redfield counting; Burnside lemma; Number of colorings of the cube.
Lecture XVIII: Burnside lemma; Number of colorings of the cube.
Lecture XIX: Section 4.3: General ballot problem, Chapter 5: Concepts of graphs; Petersen graph,
Lecture XX: Kneser graph, Hypercube, Section 5.2: Handshake lemma, Rectangles partitioned into rectangles with integer sidelengths, Havel-Hakini on degree sequences.
Lecture XXI: Bipartite subgraphs of graphs, Turan Theorem, Directed graphs, Kings in tournaments, Section 5.3: connectivity, Min degree 2 implies having cycle, Eulerian circuits.
Lecture XXII: Cut vertex, cut edge, Eulerian circuits. Section 5.4: Trees, Chapter 6: matchings, Halls Theorem, Hakini Theorem, Birkhoff-Neumann on double stochastic matrices.
Lecture XXIII: Trees, Chapter 6: matchings, Halls Theorem, Hakini Theorem, Birkhoff-Neumann on double stochastic matrices. Defect formula for bipartite graphs, König-Egerváry theorem, Gallai Theorem, König Theorem.
Lecture XXIV: Defect formula for bipartite graphs, König-Egerváry theorem, Gallai Theorem, König Theorem. Section 6.2: Matchings in general graphs, Tutte Theorem, Berge-Tutte formula.
Lecture XXV: Berge-Tutte formula, k-regular multigraph having one-factor, Peterson Theorem, Peterson 2-factor theorem, Section 6.3: Augmenting lines, Section 7.1: Connectivity parameters.
Lecture XXVI: Section 7.1: Connectivity parameters, Whitney Theorem, Blocks, Section 7.2: k-connected graphs, Menger Theorem.
Lecture XXVII: Section 7.2: k-connected graphs, Menger Theorem, Expansion lemma, Dirac Theorem (k points in a cycle in k-connected graphs).
Lecture XXVIII: Fan Lemma, Ford-Fulkerson Common System Distinct Representatives, 2,3-connected graphs, Whitney theorem for ear-decomposition, Robbins Theorem.
Lecture XXIX: Section 7.3: Hamilton cycles, Ore Lemma, Dirac Theorem, Chvatal condition on Hamiltonicity, Chvatal-Erdos condition, Erdos-Gallai on circumference.
Lecture XXX: Erdos-Gallai on circumference, Chapter 8.1: Vertex coloring, Brooks Theorem (no proof), Szekered-Wilf Theorem, Gallai-Roy Theorem, Mycielski construction, Sectionm 8.2: Color-critical graphs.
Lecture XXXI: Mycielski construction, Sectionm 8.2: Color-critical graphs, List coloring, Section 8.3: edge-coloring, König: every bipartite graph is max-degree colorable, Perfect graphs.
Lecture XXXII: Section 8.3: edge-coloring, König: every bipartite graph is max-degree colorable, Perfect graphs. Chapter 9: Planar graphs.
Lecture XXXIII: Chapter 9: Planar graphs. Outerplanar graphs. Euler formula. Characterization of regular polyhedra. Section 9.2: Structure of planar graphs. Section 9.3: Coloring planar graphs, proof of 5-color theorem. Example for applying the discharging method.
Lecture XXXIV : Section 9.2: Structure of planar graphs. Section 9.3: Coloring planar graphs, proof of 5-color theorem. Example for applying the discharging method. Chapter 10.2: Ramsey Theory, probabilistic lower bound on diagonal Ramsey, Inductive proof of general Ramsey theorem (that Ramsey numbers are finite).
Lecture XXXV: Inductive proof of general Ramsey theorem (that Ramsey numbers are finite). Erdõs- Szekeres: points in convex position, Chvatal: Ramsey trees vs cliques, Burr- Erdõs- Spencer: Ramsey of m vertex disjoint triangles, Section 10.3: Schur Theorem, Chapter 14.1: Erdõs: minimum number of edges of non-2-colorable n-uniform hypergraphs, Pluhár, Kozik-Cherkasin lower bounds, Improving diagonal Ramsey lower bounds.
Lecture XXXVI: Chapter 14.1: Erdõs: minimum number of edges of non-2-colorable n-uniform hypergraphs, Pluhár, Kozik-Cherkasin lower bounds, Improving diagonal Ramsey lower bounds. Symmetric Erdõs- Lovász Local Lemma (statement), application to diagonal Ramsey. Existence of large girth, large chromatic number graphs, Caro-Wei proof of Turán Theorem. Markov's Inequality. Second Moment Method, Chebyshev Inequality. In G(n,p) thresholds for connectivity and having no isolated vertex.
Lecture XXXVII : Caro-Wei proof of Turán Theorem. Markov's Inequality. Second Moment Method, Chebyshev Inequality. In G(n,p) thresholds for connectivity and having no isolated vertex. Chapter 13: Latin squares. Existence of n-1 pairwise orthogonal Latin squares of order n. Projective planes. Construction. Reimann: Constructing bipartite C_4-free graphs. Köváry- Sós- Turán: upper bound on the number of edges of bipartite C_4-free graphs.
Lecture XXXVIII: Szemerédi Regularity Lemma [statement only]. Embedding Lemma, Counting Lemma. Chapter 13: Latin squares. Existence of n-1 pairwise orthogonal Latin squares of order n. Projective planes. Construction. Reimann: Constructing bipartite C_4-free graphs. Köváry- Sós- Turán: upper bound on the number of edges of bipartite C_4-free graphs. Block desings.
Lecture XXXIX: Block desings. Fisher's Inequality, Bose theorem, Hadamard matrix, Difference sets.
Lecture XL: Chapter 12: Posets, Dilworth Theorem, Sperner Theorem, LYMB Inequality, Erdõs-Ko-Rado Theorem, Katona circle method, Hoffman bound,
Note that some of the lectures notes are covering more than one 50 minutes class.