Some Meeting Points of Gröbner Bases and Combinatorics

Summary Let $$ \mathbb{F} $$ be a field, $$ V \subseteq {\mathbb{F}^n} $$ be a set of points, and denote by I(V) the vanishing ideal of V in the polynomial ring $$ \mathbb{F}\left[ {{x_1}, \ldots ,{x_n}} \right] $$ . Several interesting algebraic and combinatorial problems can be formulated in terms of some finite V, and then Gröbner bases and standard monomials of I(V) yield a powerful tool for solving them. We present the Lex Game method, which allows one to efficiently compute the lexicographic standard monomials of I(V) for any finite set $$ V \subseteq {\mathbb{F}^n} $$ . We apply this method to determine the Gröbner basis of I(V) for some V of combinatorial and algebraic interest, and present four applications of this type. We give a new easy proof of a theorem of Garsia on a generalization of the fundamental theorem of symmetric polynomials. We also reprove Wilson’s theorem concerning the modulo p rank of some inclusion matrices. By examining the Gröbner basis of the vanishing ideal of characteristic vectors of some specific set systems, we obtain results in extremal combinatorics. Finally, we point out a connection among the standard monomials of I(V) and I(V c ), where V⊆{0,1} n and V c ={0,1} n ∖V. This has immediate consequences in combinatorial complexity theory. The main results have appeared elsewhere in several papers. We collected them into a unified account to demonstrate the usefulness of Gröbner basis methods in combinatorial settings.