MATH 8803 - Algebraic Methods in Combinatorics
Spring 2010 - Tuesday/Thursday 13:30-15:00
The Polynomial Method
Verifying string equality (aka Reed-Solomon Codes). Schwart's Lemma.
Checking if a bipartite graph has a perfect matching.
Lower bound for Kakeya problem over finite fields (Dvir). A small Kakeya set.
An improved lower bound for Kakeya sets (Saraf-Sudan). The Lines-vs-Joints problem.
Cauchy-Davenport Theorem using the Combinatorial Nullstellensatz.
Erdos-Ginzburg-Ziv Lemma using Chevalley-Warning Theorem.
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
Proof of Combinatorial-Nullstellensatz. Orientations and graph
coloring (Alon-Tarsi Theorem).
The choice number of planar bipartite graphs. Another proof of Combinatorial Nullstellensatz. The Erdos-Heilbronn Conjecture.
Direct proofs of Cauchy-Davenport and Chevalley-Warning. Regular subgraphs
in dense graphs (Pyber).
Milnor-Thom Theorem and Sign Patterns of Polynomials
Lower bounds for linear decision trees (Dobkin-Lipton). The Milnor-Thom
its applications to lower bounds for algebraic decision trees
Ben-Or's Lower Bound for Algebraic Computations. Warren's Theorem and its
application to sign patterns of polynomials.
Application of sign patterns to Ramsey properties of graphs defined by real polynomials (Alon).
Application of sign patterns to the relation between rank and containment properties of partial orders (Alon-Scheinerman).
Odd-Town Theorem and related issues.
Even-Town Theorem. Strong Even-Town Theorem. Fisher's Inequality. Nagy's Ramsey Construction. Lindstrom's Theorem.
Approximating small depth circuits using low degree polynomials (Razborov's approximation method). Lower bound
for small depth circuits computing the Majority function.
Lower bound for small depth circuits computing the Parity function.
Hadamard Matrices/Code. Lindsey's Lemma. Self-correcting of Hadamard code. The Plotkin Bound.
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
Bounds for 1-distance and 2-distance sets.
An improved bound for 2-distance sets (Blokhius). The Modular Intersection Theorem and explicit Ramsey Graphs (Frankl-Wilson)
Missing Intersection Theorem. Uniform and non-uniform Intersection Theorems (Ray-Chaudhuri-Wilson).
Chromatic number of R^n (Frankl-Wilson). Counter example to Borsuk's conjecture (Kahn-Kalai).
Bollobas's Theorem via Permutations (Lubell), Polynomials (Lovasz) and
Resultants (Blokhuis). Relation
to Helly property of hypergraph vertex-cover.
Eigenvalues of Graphs
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).
Smallest eigenvalue and bipartiteness. Hoffman's bounds for the independence and chromatic numbers of graphs. Courant-Fischer Theorem.
Spectral characterization of strongly-regular graphs. Hoffman-Singleton Theorem. The Friendship Theorem.
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.
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).