## 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).