MATH 8803  Algebraic Methods in Combinatorics
Spring 2010  Tuesday/Thursday 13:3015:00
Home Assignments
Topics covered
The Polynomial Method

Lecture 1:
Verifying string equality (aka ReedSolomon 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 (SarafSudan). The LinesvsJoints problem.

Lecture 4:
CauchyDavenport Theorem using the Combinatorial Nullstellensatz.
ErdosGinzburgZiv Lemma using ChevalleyWarning Theorem.

Lecture 5:
The ErdosGinzburgZiv lemma using Cauchy Davenport.
The covering number of
affine hyperplanes using ChevalleyWarning. Proof of
ChevalleyWarning using CombinatorialNullstellensatz. The
Permanent Lemma.

Lecture 6:
Proof of CombinatorialNullstellensatz. Orientations and graph
coloring (AlonTarsi Theorem).

Lecture 7:
The choice number of planar bipartite graphs. Another proof of Combinatorial Nullstellensatz. The ErdosHeilbronn Conjecture.

Lecture 8:
Direct proofs of CauchyDavenport and ChevalleyWarning. Regular subgraphs
in dense graphs (Pyber).
MilnorThom Theorem and Sign Patterns of Polynomials

Lecture 9:
Lower bounds for linear decision trees (DobkinLipton). The MilnorThom
Theorem and
its applications to lower bounds for algebraic decision trees
(SteeleYao).

Lecture 10:
BenOr'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 (AlonScheinerman).
Rank Arguments

Lecture 13:
OddTown Theorem and related issues.

Lecture 14:
EvenTown Theorem. Strong EvenTown 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. Selfcorrecting of Hadamard code. The Plotkin Bound.

Lecture 18:
Dual Fisher Inequality. Number of lines determined by noncollinear points. Partitioning K_n into complete subgraphs.
Partitioning K_n into complete bipartite subgraphs (GrahamPollack).
Number of edges in 3critical hypergraphs (Seymour).
Spaces of Polynomials

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

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

Lecture 21:
Missing Intersection Theorem. Uniform and nonuniform Intersection Theorems (RayChaudhuriWilson).

Lecture 22:
Chromatic number of R^n (FranklWilson). Counter example to Borsuk's conjecture (KahnKalai).

Lecture 23:
Bollobas's Theorem via Permutations (Lubell), Polynomials (Lovasz) and
Resultants (Blokhuis). Relation
to Helly property of hypergraph vertexcover.
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
PerronFrobenius 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. CourantFischer Theorem.

Lecture 26:
Spectral characterization of stronglyregular graphs. HoffmanSingleton 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 linegraphs of regular graphs. Petersen graph is not Hamiltonian.

Lecture 28:
Spectrum of Cayley graphs over the hypercube. Cayley Expanders over the hypercube using smallbias
probability spaces. Lower bound for degree of Cayley expanders over Abelian groups (AlonRoichman).