Algebraic Methods in Combinatorics, Fall 2014

What:

The applications of algebra to (Hungarian-style) combinatorics are relatively rare, but powerful. This course is devoted to such applications.

We will assume a solid knowledge of linear algebra, and a basic familiarity with groups and rings. Additional algebraic background will be introduced in the course.

Techniques covered include the rank argument, multilinear polynomials, combinatorial Nullstellensatz, Chevalley–Warning theorem, extrapolation arguments, Bezout's theorem.

Applications include Lindström's theorem, Fisher's inequalities, intersection patterns of sets, counting unit-distance graphs, theorems of Radon and Tverberg, explicit constructions of Ramsey graphs, counterexample(s) to Borsuk's conjecture, Shannon capacity of graphs, Cauchy–Davenport theorem and its extensions, regular subgraphs, Berlekamp–Welch algorithm, solutions to the joints problem and to the finite field Kakeya.

Resources:

There are two books devoted to applications of linear algebra to combinatorics.

• Linear algebra methods in combinatorics, by László Babai and Péter Frankl, Department of Computer Science, University of Chicago, preliminary version, 1992. [library]
• Thirty-three miniatures (mathematical and algorithmic applications of linear algebra), by Jiří Matoušek, Amer. Math. Soc., 2010. [library] [online]

We will cover mostly material from the former book, but I also highly recommend the latter as a nice bed-time reading.

• The best exposition of combinatorial Nullstellensatz is in the original paper by Noga Alon.
• For Kakeya problem in finite fields, see the original paper of Dvir, as well as papers by Saraf–Sudan and by Dvir–Kopparty–Saraf–Sudan.
• Equations over finite fields: an elementary approach, by Wolfgang Schmidt contains the most accessible exposition of Stepanov's method that I know of. [library]
• Chapter 11 Analytic Number Theory by Iwaniec and Kowalski contains the proof of the special case of Stepanov's method that we covered. [library] [online]

More resources will be added to this page as the course progresses.

More fun:

More fun can be had at my office hours on Mondays 2:30–3:30pm and Thursdays 9:30–10:30am in Wean 6202 or 6th floor lounge. I am also available by appointment.

Course activities:

There will be regular homeworks.

Students are expected to fully participate in the class. Discussions during the lectures are encouraged.

Lectures:

• August 25: Introduction. Oddtown/Eventown. Lindstrom's theorem. Radon's theorem.
• August 27: Two-distance sets. Skew Oddtown. Fisher's inequality.
• August 29: Blokhius's theorem on two-distance sets. Graham–Pollak theorem. Introduction to intersecting families. Rank argument notes
• September 1: Labor Day
• September 3: No class 1
• September 5: No class 2
• September 8: Frankl–Wilson theorem. Multilinear polynomials. Chromatic number of the space.Homework #1
• September 10: Kahn–Kalai on Borsuk's conjecture. Randomness extraction as a motivation for explicit constructions of Ramsey graphs. Frankl–Wilson constructions.
• September 12: Ray-Chaudhuri–Wilson's theorem. Points in general position. Bollobás's theorem.
• September 15: Multilinear functions. Alternating functions. Wedge product.
• September 17: Subspace and threshold versions of Bollobás's theorem. Tensor products. Notes on multilinear algebra
• September 17 (evening): Shannon capacity. Shannon capacity of C₅. See Miniature 28 from Matoušek's book.
• September 19: Radon's lemma and Helly's theorem. Centerpoints. Colorful Carathéodory theorem (statement).
• September 19 (evening): Shannon capacity of the union. Subadditivity and Fekete's lemma. See Miniature 29 from Matoušek's book. The lower bound of 2m^1/2 is from the original paper of Alon.
• September 22: Colorful Carathéodory theorem. Tverberg's theorem. Homework #2
• September 24: Schwartz–Zippel lemma. Identity testing. Vanishing on Cartesian products. Combinatorial Nullstellensatz (part I).
• September 26: Combinatorial Nullstellensatz (part II). Hilbert's Nullstellensatz (statement). Cauchy–Davenport theorem. Chevalley–Warning theorem. Erdős–Ginzburg–Ziv theorem (prime modulus).
• September 29: No class
• October 1: No class
• October 3: Erdős–Ginzburg–Ziv theorem (general modulus). Group rings. Olson's theorem. Chevalley–Warning theorem revisited.
• October 6: Preissman–Mischler–Karasev–Petrov theorem. Restricted sumsets. Regular subgraphs.
• October 8: Regular subgraphs of somewhat dense graphs after Pyber. Edge list chromatic number (part I). Homework #3
• October 10: Edge list chromatic number (part II). Edge list chromatic number of bipartite planar graphs.
• October 13: Extrapolation. Berlekamp–Welch algorithm. Szemerédi–Trotter theorem (statement). Joints problems over R.
• October 15: Kakeya problem. Arithmetic Kakeya problem. Sketch of construction of Kakeya set in R². Dvir's bound on Kakeya set in finite field. Multiplicity of vanishing.
• October 17: Mid-semester break
• October 20: High-order vanishing and Kakeya sets. Construction of small Kakeya sets. Hasse derivatives. Homework #4
• October 22: Properties of Hasse derivatives. Schwartz–Zippel with multiplicities. Higher-order of vanishing and Kakeya sets (part I).
• October 24: Higher-order of vanishing and Kakeya sets (part II). Weil's theorem (motivation and statement).
• October 27: Weil's theorem for hyperelliptic curves via Stepanov's method (construction of the auxiliary polynomial).
• October 29: Weil's theorem for hyperelliptic curves via Stepanov's method (fixing a mistake + non-vanishing). Intersection of subgroup translates.
• October 31: Bezout's theorem for plane curves (motivation + statement). Resultants. Proof of Bezout's theorem (part I).
• November 3: Gauss's lemma. Proof of Bezout's theorem (part II). General Bezout's theorem (motivation).
• November 5: Dimension and degree (intuition + intimidation). Turán's problem for bipartite graphs. Kővári–Sós–Turán theorem. Upper bound on the number of edges in graphs of given girth. Projective duality. C₄-free graphs. Homework #5
• November 7: Wenger's constructions of C_2k-free graphs for k=2,3,5.
• November 10: Probabilistic algebraic construction of K_s,t-free graphs.
• November 12: Zero and sign patterns of polynomials.
• November 14: Sign-rank can be large. Ben-Or's lower bound for Distinctness.
• November 17: Graphs determined by polynomial inequalities are not Ramsey. Borsuk–Ulam theorem (statement). Ham-sandwich theorem.
• November 19: Veronese embedding. Polynomial ham-sandwich theorem. Crude asymmetric Kővári–Sós–Turán theorem (Zarankiewicz problem).
• November 21: Szemerédi–Trotter theorem. Point-curve incidences.
• November 24: Point-curve incidences. The unit distance problem. The distinct distance problem. The distinct distance problem as a point-line incidence question.
• December 1: Ruled surfaces. Trivial bounds.