Applications of Polynomials in Combinatorics

Combinatorics is notorious for its lack of major methods: perhaps the only exception is the ‘probabilistic method’, invented, applied and popularised by Paul Erd˝os. Nevertheless, over the years, algebraic methods based on linear algebra, polynomials, external products and group rings have been used more and more. In this short course I shall present several examples of this, leading to elegant proofs of substantial theorems. My emphasis will be on applications of polynomials.
This course is aimed at undergraduates and graduate students: the only prerequisite are basic algebra, and a willingness to think. At the end I shall distribute detailed notes about the results I have covered. The papers in the list below cover way more than I shall present.

Alon, N., Combinatorial Nullstellensatz, in Recent Trends in Combinatorics (M´atrah´aza, 1995), Combin. Probab. Comput. 8 (1999), 7–29.
Alon, N., S. Friedland and G. Kalai, Every 4-regular graph plus an edge contains a 3-regular subgraph, J. Combin. Theory Ser. B 37 (1984) 92–93.
Alon, N., M.B. Nathanson, and I.Z. Ruzsa, The polynomial method and restricted sums of congruence classes, J. Number Theory 56 (1996) 404–417.
Ax, J., Zeroes of polynomials over finite fields, Amer. J. Math. 86 (1964) 255–261.
Bateman, M., and N.H. Katz, New bounds on cap sets, J. Amer. Math. Soc. 25 (2012) 585–613.
Blokhuis, A., A new upper bound for the cardinality of 2-distance sets in Euclidean space, in Convexity and Graph Theory, Jerusalem, 1981, North-Holland Math. Stud. 87, North-Holland,
Amsterdam, 1984, pp. 65–66.
Croot, E., V.F. Lev and P.P. Pach, Progression-free sets in Z4 n are exponentially small, Ann. of Math. (2) 185 (2017) 331–337.
Dias da Silva, J.A., and Y.O. Hamidoune, Cyclic subspaces of Grassmann derivations, Bull. London Math. Soc. 26 (1994) 140–146.
Dvir, Z., Incidence theorems and their applications, Found. Trends Theor. Comput. Sci. 6 (2010) 257–393. [survey]
Edel, Y., Extensions of generalized product caps, Des. Codes Cryptogr. 31 (2004) 5–14.
Ellenberg, J. S., and D. Gijswijt, On large subsets of F n q with no three-term arithmetic progression, Ann. of Math. (2) 185 (2017) 339–343.
Elsholtz, C., Lower bounds for multidimensional zero sums, Combinatorica 24 (2004) 351–358.
Erd˝os, P., and H. Heilbronn, On the addition of residue classes mod p, Acta Arith. 9 (1964) 149–159.
Hamidoune, Y. O., A.S Llad´o and O. Serra, On restricted sums, Combin. Probab. Comput. 9 (2000) 513–518.
Larman, D.G., C.A. Rogers and J.J. Seidel, On two-distance sets in Euclidean space, Bull. London Math. Soc. 9 (1977), 261–267.
Reiher, C., On Kemnitz’ conjecture concerning lattice-points in the plane, Ramanujan J. 13 (2007), 333–337.
R´onyai, L., On a conjecture of Kemnitz, Combinatorica 20 (2000) 569–573.
Savchev, S., and F. Chen, Kemnitz’ conjecture revisited, Discrete Math. 297 (2005) 196–201.
Tao, T., Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory, EMS Surv. Math. Sci. 1 (2014) 1–46. [survey]