Math 535, Fall 2016
Combinatorics I: Algebraic Methods
General
Course Information
Meeting time:
Monday and Wednesday 1:30 pm - 2:45 pm in E406
Instructor: Hao Huang
Textbook and Reading Materials:
1. L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science, Preliminary Version 2.
2. J. Matousek, Thirty-three miniatures: Mathematical and Algorithmic Applications of Linear Algebra.
3. L. Guth, Polynomial Methods in Combinatorics, University Lecture Series Volume 64.
4. N. Alon, Combinatorial Nullstellensatz.
5. N. Alon, Tools from higher algebra.
Syllabus: Please click here for the
syllabus of this course, which includes more details on the course
goal, grading scheme, exam and homework policy.
Course Schedule
The materials
covered in the classes will be updated and posted below after each
class.
Aug 24 (W) Course
introduction, Odd/Eventown, Fisher's Inequality.
Aug 29 (M) Designs showing tthe tightness of Fisher's Inequality, Two-distance set, Lindstrom's Theorem.
Aug 31 (W)
Unit distance problem (introduction), Graham-Pollak Theorem, De Bruijn-Erdos Theorem, Sylvester-Gallai Theorem.
Sep 5 (M) --- no class.
Sep 7 (W) Erdos-Faber-Lovasz Conjecture, Tiling irrational rectangles by squares, Hilbert's third problem, brief introduction of Kakeya problem.
Sep 12 (M) Finite field Kakeya Theorem (Dvir's result and Saraf-Sudan result), The joint problem in Combinatorial Geometry.
Sep 14 (W)
Four theorems on restricted intersections.
Sep 19 (M)
Applications of the restricted intersection theorems: (1)
explicit construction of Ramsey graphs, (2) Grolmusz's construction.
Sep 21 (W) Applications of the
restricted intersection theorems: (3) Chromatic number of R^d, (4)
Counterexamples to Borsuk's Conjecture, Melzak's Theorem.
Sep 26 (M)
Proof of Bollobas Theorem and its extensions.
Sep 28 (W)
Prague dimension; The Berlekamp-Welch Algorithm, Sudan's Theorem.
Oct 3 (M)
The Capset Problem.
Oct 5 (W) Wedge-product method: another proof of Bollobas Theorem, The vector space version.
Oct 10 (M)
--- no class.
Oct 12 (W) Convexity I: Helly's Theorem, Radon's Lemma, Jung's Theorem, Centerpoint Theorem.
Oct 17 (M)
Convexity II: Caratheodory Theorem, corollary
for compact set, proof of Caratheodory via Helly, Colorful Caratheodory
Theorem.
Oct 19 (W) Convexity III: Tverberg's Theorem, colorful Tverberg, second proof of Centerpoint Theorem, First selection Lemma.
Oct 24 (M) An introduction to Spectral Graph Theory (properties of first eigenvalue, Cauchy Interlacing Theorem, Min-max Theorem).
Oct 26 (W)
More spectral graph theory: Higman-Sims
technique, Cvetkovic bound, Hoffman's bound (regular proof +
interlacing proof), Wilf's Theorem.
Oct 31 (M)
The smallest eigenvalue (bipartiteness), spectral proof of Erdos-Ko-Rado, Erdos hypergraph matching conjecture.
Nov 2 (W)
The friendship problem, Hoffman-Singleton Theorem, Decomposition of K10 into Petersen graphs, Petersen graph is non-Hamiltonian.
Nov 7 (M)
Graph Laplacian, a proof of Kirchhoff's Matrix-Tree Theorem.
Nov 9 (W) Expander graph, Cheeger's Inequality.
Nov 14 (M)
Alon-Boppana Theorem, Ramanujan graphs.
Nov 16 (W)
Chevalley-Warning Theorem, existence of regular subgraphs, Erdos-Ginzburg-Ziv Theorem.
Nov 21 (M)
Proof of Kemnitz conjecture (weaker bound), Davenport constant and Olson's Theorem.
Nov 23 (W)
--- no class.
Nov 28 (M)
Combinatorial Nullstellensatz I: proof of the
Nullstellensatz, Cauchy-Davenport Theorem (with the Dyson e-transform
proof).
Nov 30 (W)
Combinatorial
Nullstellensatz II: Restricted sums and Erdos-Heilbronn Conjecture, an
alternative proof of Chevalley-Warning, Alon-Tarsi, graph coloring and
choosability.
Dec 5 (M)
Combinatorial Nullstellensatz III: The
permanent Lemma, Jaeger's Conjecture, Unit cube covered by hyperplanes,
Preissman-Mischler-Karasev-Petrov Theorem.