Gröbner bases for complete uniform families. (English) Zbl 1045.13011

The main result of the paper is the determination of a reduced Gröbner basis for the polynomial ideal over a field which vanishes on the set of characteristic vectors of the complete uniform families \({[n] \choose d}\) of \(d\)-subsets of \([n]=\{1,2, \ldots , n\}\). It turns out that the Gröbner basis is dependent only on the order of the variables. Applications to known combinatorial results are given.


13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
12Y05 Computational aspects of field theory and polynomials (MSC2010)
Full Text: DOI


[1] W.W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, American Mathematical Society, 1994. · Zbl 0803.13015
[2] M. Aigner, “Lexicographic matching in Boolean algebras,” Journal of Combinatorial Theory, Ser.B 14 (1973), 187-194. · Zbl 0274.05003
[3] R.E.L. Aldred and R.P. Anstee, “On the density of sets of divisors,” Discrete Math. 137 (1995), 345-349. · Zbl 0820.05056
[4] R.P. Anstee, L. Rónyai, and A. Sali, “Shattering news,” Graphs and Combinatorics 18 (2002), 59-73. · Zbl 0990.05123
[5] R.P. Anstee and A. Sali, “Sperner families of bounded VC-dimension,” Discrete Math. 175 (1997), 13-21. · Zbl 0887.05052
[6] L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics, September 1992.
[7] T. Becker and V. Weispfenning, Gr¨obner Bases—A Computational Approach to Commutative Algebra, Springer-Verlag, Berlin, 1993. · Zbl 0772.13010
[8] A. Bernasconi and L. Egidi, “Hilbert function and complexity lower bounds for symmetric Boolean functions,” Information and Computation 153 (1999), 1-25. · Zbl 1004.06013
[9] T. Bier, “Remarks on recent formulas of Wilson and Frankl,” Europ. J. Combin. 14 (1993), 1-8. · Zbl 0774.05014
[10] A.M. Cohen, H. Cuypers, and H. Sterk (Eds.), Some Tapas of Computer Algebra, Springer-Verlag, Berlin, 1999. · Zbl 0924.13021
[11] P. Frankl, “Intersection theorems and mod p rank of inclusion matrices,” J. Combin. Theory A 54 (1990), 85-94. · Zbl 0744.05008
[12] R.L. Graham, D.E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989. · Zbl 0668.00003
[13] R. Smolensky, “On representations by low-degree polynomials,” in Proc. of the 34th IEEE Symposium on the Foundations of Computer Science, 1993, pp. 130-138.
[14] R.M. Wilson, “A diagonal form for the incidence matrices of t-subsets vs. k-subsets,” Europ. J. Combin. 11 (1990), 609-615. · Zbl 0747.05016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.