Polynomial method in combinatorics
In mathematics, the polynomial method is an algebraic approach to combinatorics problems that involves capturing some combinatorial structure using polynomials and proceeding to argue about their algebraic properties. Recently, the polynomial method has led to the development of remarkably simple solutions to several long-standing open problems. The polynomial method encompasses a wide range of specific techniques for using polynomials and ideas from areas such as algebraic geometry to solve combinatorics problems. While a few techniques that follow the framework of the polynomial method, such as Alon's Combinatorial Nullstellensatz, have been known since the 1990s , it was not until around 2010 that a broader framework for the polynomial method has been developed. Mathematical overview. Many uses of the polynomial method follow the same high-level approach. The approach is as follows: Example. As an example, we outline Dvir's proof of the Finite Field Kakeya Conjecture using the polynomial method. Finite Field Kakeya Conjecture: Let formula_1 be a finite field with formula_2 elements. Let formula_3 be a Kakeya set, i.e. for each vector formula_4there exists formula_5 such that formula_6 contains a line formula_7. Then the set formula_6 has size at least formula_9where formula_10 is a  constant that only depends on formula_11. Proof: The proof we give will show that formula_6 has size at least formula_13. The bound of formula_9 can be obtained using the same method with a little additional work. Assume we have a Kakeya set formula_6 with formula_16 Consider the set of monomials of the form formula_17 of degree exactly formula_18. There are exactly formula_19 such monomials. Thus, there exists a nonzero homogeneous polynomial formula_20 of degree formula_18 that vanishes on all points in formula_6"." Note this is because finding such a polynomial reduces to solving a system of formula_23 linear equations for  the coefficients. Now we will use the property that formula_6 is a Kakeya set to show that formula_25 must vanish on all of formula_26. Clearly formula_27. Next, for formula_28, there is an formula_29 such that the line formula_7 is contained in formula_6. Since formula_25 is homogeneous, if formula_33 for some formula_34 then formula_35 for any formula_36. In particular formula_37 for all nonzero formula_38. However, formula_39 is a polynomial of degree formula_18 in formula_41 but it has at least formula_42 roots corresponding to the nonzero elements of formula_1 so it must be identically zero. In particular, plugging in formula_44 we deduce  formula_45. We have shown that formula_45 for all formula_4 but formula_25 has degree less than formula_49 in each of the variables so this is impossible by the Schwartz–Zippel lemma. We deduce that we must actually have formula_50 Polynomial partitioning. A variation of the polynomial method, often called polynomial partitioning, was introduced by Guth and Katz in their solution to the Erdős distinct distances problem. Polynomial partitioning involves using polynomials to divide the underlying space into regions and arguing about the geometric structure of the partition. These arguments rely on results from algebraic geometry bounding the number of incidences between  various algebraic curves. The technique of polynomial partitioning has been used to give a new proof of the Szemerédi–Trotter theorem via the polynomial ham sandwich theorem and has been applied to a variety of problems in incidence geometry. Applications. A few examples of longstanding open problems that have been solved using the polynomial method are: