Math 535, Fall 2016

Combinatorics I: Algebraic Methods

General Course Information
Meeting time:  Monday and Wednesday 1:30 pm - 2:45 pm in E406

: 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.

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.