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)

Syllabus Spring 2024

General Homework Problems:

General Syllabus

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.3Exponential 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: Polya 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 XXVISection 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 XXXErdos-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.