MATH 8803 - Algebraic Methods in Combinatorics

Spring 2010 - Tuesday/Thursday 13:30-15:00

School of Mathematical Sciences
Georgia Institute of Technology

Instructor: Asaf Shapira

Course procedures, syllabus and text books

Home Assignments

• Home Assignment I

• Home Assignment II

• Home Assignment III

• Home Assignment IV

Topics covered

The Polynomial Method

• Lecture 1: Verifying string equality (aka Reed-Solomon Codes). Schwart's Lemma. Checking if a bipartite graph has a perfect matching.

• Lecture 2: Lower bound for Kakeya problem over finite fields (Dvir). A small Kakeya set.

• Lecture 3: An improved lower bound for Kakeya sets (Saraf-Sudan). The Lines-vs-Joints problem.

• Lecture 4: Cauchy-Davenport Theorem using the Combinatorial Nullstellensatz. Erdos-Ginzburg-Ziv Lemma using Chevalley-Warning Theorem.

• Lecture 5: The Erdos-Ginzburg-Ziv lemma using Cauchy Davenport. The covering number of affine hyperplanes using Chevalley-Warning. Proof of Chevalley-Warning using Combinatorial-Nullstellensatz. The Permanent Lemma.

• Lecture 6: Proof of Combinatorial-Nullstellensatz. Orientations and graph coloring (Alon-Tarsi Theorem).

• Lecture 7: The choice number of planar bipartite graphs. Another proof of Combinatorial Nullstellensatz. The Erdos-Heilbronn Conjecture.

• Lecture 8: Direct proofs of Cauchy-Davenport and Chevalley-Warning. Regular subgraphs in dense graphs (Pyber).

Milnor-Thom Theorem and Sign Patterns of Polynomials

• Lecture 9: Lower bounds for linear decision trees (Dobkin-Lipton). The Milnor-Thom Theorem and its applications to lower bounds for algebraic decision trees (Steele-Yao).

• Lecture 10: Ben-Or's Lower Bound for Algebraic Computations. Warren's Theorem and its application to sign patterns of polynomials.

• Lecture 11: Application of sign patterns to Ramsey properties of graphs defined by real polynomials (Alon).

• Lecture 12: Application of sign patterns to the relation between rank and containment properties of partial orders (Alon-Scheinerman).

Rank Arguments

• Lecture 13: Odd-Town Theorem and related issues.

• Lecture 14: Even-Town Theorem. Strong Even-Town Theorem. Fisher's Inequality. Nagy's Ramsey Construction. Lindstrom's Theorem.

• Lecture 15: Approximating small depth circuits using low degree polynomials (Razborov's approximation method). Lower bound for small depth circuits computing the Majority function.

• Lecture 16: Lower bound for small depth circuits computing the Parity function.

• Lecture 17: Hadamard Matrices/Code. Lindsey's Lemma. Self-correcting of Hadamard code. The Plotkin Bound.

• Lecture 18: Dual Fisher Inequality. Number of lines determined by non-collinear points. Partitioning K_n into complete subgraphs. Partitioning K_n into complete bipartite subgraphs (Graham-Pollack). Number of edges in 3-critical hypergraphs (Seymour).

Spaces of Polynomials

• Lecture 19: Bounds for 1-distance and 2-distance sets.

• Lecture 20: An improved bound for 2-distance sets (Blokhius). The Modular Intersection Theorem and explicit Ramsey Graphs (Frankl-Wilson)

• Lecture 21: Missing Intersection Theorem. Uniform and non-uniform Intersection Theorems (Ray-Chaudhuri-Wilson).

• Lecture 22: Chromatic number of R^n (Frankl-Wilson). Counter example to Borsuk's conjecture (Kahn-Kalai).

• Lecture 23: Bollobas's Theorem via Permutations (Lubell), Polynomials (Lovasz) and Resultants (Blokhuis). Relation to Helly property of hypergraph vertex-cover.

Eigenvalues of Graphs

• Lecture 24: Charaterization of eigenvalues using Rayleigh quotients. First and second eigenvalues and their relation to degrees and connectivity of graphs. The Perron-Frobenius Theorem and uniqueness of stationary distributions. A bound on the chromatic number (Wilf).

• Lecture 25: Smallest eigenvalue and bipartiteness. Hoffman's bounds for the independence and chromatic numbers of graphs. Courant-Fischer Theorem.

• Lecture 26: Spectral characterization of strongly-regular graphs. Hoffman-Singleton Theorem. The Friendship Theorem.

• Lecture 27: Relation between diameter and number of distinct eigenvalues. Decomposing K_10 into 3 Petersen graphs. The Interlacing Theorem. The spectrum of line-graphs of regular graphs. Petersen graph is not Hamiltonian.

• Lecture 28: Spectrum of Cayley graphs over the hypercube. Cayley Expanders over the hypercube using small-bias probability spaces. Lower bound for degree of Cayley expanders over Abelian groups (Alon-Roichman).