Algebraic Methods in Combinatorics, Spring 2019

What:

The course is about algebraic aspects of (Hungarian-style) combinatorics. This is an application-driven course. Throughout the course, our aim is to prove inequalities about concrete combinatorial objects. We will see how techniques from linear algebra and a little bit of algebraic geometry to achieve this goal.

This is an advanced graduate course. To benefit from this course, you must have basic familiarity with combinatorics, and be extremely comfortable with linear algebra. You also need to have the hard-to-define “mathematical maturity”, which includes broad familiarity with the common undergraduate mathematical background, skill in abstract reasoning, and general interest in pretty mathematics. In particular, you need to be acquainted with finite fields, groups and with rudiments of real analysis. However, I will not assume familiarity with concepts not usually taught to mathematics undergraduate students. In particular, this course requires no prior knowledge of algebraic geometry.

Algebraic techniques I expect to cover in the course include:

• Rank argument
• Restricted intersection theorems
• Multilinear linear algebra (tensor products and exterior powers)
• Linear algebra modulo composite number
• Combinatorial Nullstellensatz
• Extrapolation arguments
• Tensor rank
• Algebraic geometry “for engineers”
• Explicit and random constructions of extremal graphs
• Polynomial partitioning

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]

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

More fun:

I am often in my office; feel free to drop by with short questions or just to chat math. If you have a longer question, or just want to make sure of a meeting time, please talk to me in class or send me an e-mail to make an appointment.

Course activities:

By the end of each Sunday, you must send me by e-mail a question about the material covered that week. If you have no questions, it can be a pro forma question (with an answer), or a problem you made up. This is worth 10% of the grade.

There will be no in-class tests. There will be several homeworks. For PhD students, the homeworks will completely determine the grade. For undergraduate and master students, at the end of the semester there will be a 30-minute oral test on a randomly chosen topic covered in the class. The test will count for 50% of the grade.

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

Lectures:

• January 14: Class introduction. Oddtown/Eventown. Equal unions. Radon's lemma. Two-distance sets.
• January 16: Introductions. Blokhius's theorem on two-distance sets. Graham–Pollak theorem. Intersecting families. Ray-Chaudhuri–Wilson's theorem. Multilinear polynomials.
• January 21: Martin Luther King day
• January 23: Frankl–Wilson theorem. Basic constructions. Steiner triple systems. Homework #1
• January 28: Subspace-based constructions. Chromatic number of the space. Kahn–Kalai on Borsuk's conjecture. Explicit constructions for Ramsey graphs (including motivation).
• January 30: (Unofficial meeting) Sunflowers. Sunflower lemma. {0,1,3}-intersecting families.
• February 4: Multilinear maps. Tensor products. Shannon capacity.
• February 6: Shannon capacity of C₅. Shannon capacity of a union. Homework #2
• February 11: Alternating functions. Wedge products. Bollobás's theorem.
• February 13: Weakly saturated graphs. Černý's conjecture. Subspace and threshold versions of Bollobás's theorem.
• February 18: General position for subspaces. Proof of subspace version of Bollobás's theorem. Polynomial functions of matrix entries. Perturbed identity matrices.
• February 20: Almost sharpness of Johnson–Linderstauss. Almost balanced codes. Matrices over rings. Applying polynomials to set systems. Restricted intersections modulo prime powers (part I).
• February 25: Restricted intersections modulo prime powers (part II). Grolmusz's construction. Radon's lemma again. Carathéodory's theorem. Colorful Carathéodory. Homework #3
• February 27: Tverberg's theorem. Schwartz–Zippel lemma. Identity testing. Vanishing on Cartesian products. Combinatorial Nullstellensatz.
• March 4: Cauchy–Davenport theorem. Restricted addition. Covering by hyperplanes. Chevalley–Warning. Erdős–Ginzburg–Ziv theorem (prime modulus). Erdős–Ginzburg–Ziv theorem (general modulus). Regular subgraphs.
• March 6: Regular subgraphs after Pyber. Coefficient shuffling. Preissman–Mischler–Karasev–Petrov theorem.
• March 11–15: Spring break. No class.
• March 18: Olson's theorem. Joints problems over R. Homework #4
• March 20: Kakeya's problem over R (statement and a construction). Kakeya's problem over F_q.
• March 25: Multiplicity. Hasse derivatives. Good bounds in Kakeya problem over F_q (part I).
• March 27: Good bounds in Kakeya problem over F_q (part II). Rédei's theorem (statement and constructions).
• April 1: Rédei's theorem (proof). Projective geometry, especially over finite fields. Projective duality.
• April 3: Ovals. Hyperovals. Conics. Segre's theorem (part I).
• April 8: Segre's theorem (part II). Some constructions of Turán graphs.
• April 10: Varieties. Ideals. Nullstellensatz (statement). Resultants (part I). Bollobás's theorem via resultants.
• April 15: Resultants (part II). Nullstellensatz (proof). Bezout's theorem (intimidation). Bezout's inequality (statement). Homework #5
• April 17: Coordinate rings. Hilbert function. Bezout's inequality (proof).
• April 22: Lang–Weil theorem (statement, intuition and proof idea). Upper bound for Turán numbers of K_s,t-free graphs. Random constructions of K_s,t-free graphs. Random algebraic construction of Turán graphs (part I).
• April 24: Random algebraic construction of Turán graphs (part II): main part.
• April 29: Construction of Turán graphs (part III): G-invariant ideals. Borsuk–Ulam theorem (statement). Ham sandwich theorem.
• May 1: Polynomial partitioning. Szemerédi–Trotter theorem.