Gröbner Bases for Complete Uniform Families
Gábor Hegedüs
and Lajos Rónyai
Hungarian Academy of Sciences and Budapest University of Technology and Economics Computer and Automation Institute Hungary
DOI: 10.1023/A:1022934815185
Abstract
We describe (reduced) Gröbner bases of the ideal of polynomials over a field, which vanish on the set of characterisic vectors of the complete unifom families ( \text d [ n] ) (_{{\text{ }}d}^{[n]} ) . An interesting feature of the results is that they are largely independent of the monomial order selected. The bases depend only on the ordering of the variables. We can thus use past results related to the lex order in the presence of degree-compatible orders, such as deglex. As applications, we give simple proofs of some known results on incidence matrices.
Pages: 171–180
Keywords: Gröbner basis; uniform family; inclusion matrix; Hilbert function
Full Text: PDF
References
1. W.W. Adams and P. Loustaunau, An Introduction to Gr\ddot obner Bases, American Mathematical Society, 1994.
2. M. Aigner, “Lexicographic matching in Boolean algebras,” Journal of Combinatorial Theory, Ser. B 14 (1973), 187-194.
3. R.E.L. Aldred and R.P. Anstee, “On the density of sets of divisors,” Discrete Math. 137 (1995), 345-349.
4. R.P. Anstee, L. Rónyai, and A. Sali, “Shattering news,” Graphs and Combinatorics 18 (2002), 59-73.
5. R.P. Anstee and A. Sali, “Sperner families of bounded VC-dimension,” Discrete Math. 175 (1997), 13-21.
6. L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics, September 1992.
7. T. Becker and V. Weispfenning, Gr\ddot obner Bases-A Computational Approach to Commutative Algebra, Springer-Verlag, Berlin, 1993.
8. A. Bernasconi and L. Egidi, “Hilbert function and complexity lower bounds for symmetric Boolean functions,” Information and Computation 153 (1999), 1-25.
9. T. Bier,“Remarks on recent formulas of Wilson and Frankl,” Europ. J. Combin. 14 (1993), 1-8. HEGED \Acute\Acute US AND R ÓNYAI
10. A.M. Cohen, H. Cuypers, and H. Sterk (Eds.), Some Tapas of Computer Algebra, Springer-Verlag, Berlin, 1999.
11. P. Frankl, “Intersection theorems and mod p rank of inclusion matrices,” J. Combin. Theory A 54 (1990), 85-94.
12. R.L. Graham, D.E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989.
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.
2. M. Aigner, “Lexicographic matching in Boolean algebras,” Journal of Combinatorial Theory, Ser. B 14 (1973), 187-194.
3. R.E.L. Aldred and R.P. Anstee, “On the density of sets of divisors,” Discrete Math. 137 (1995), 345-349.
4. R.P. Anstee, L. Rónyai, and A. Sali, “Shattering news,” Graphs and Combinatorics 18 (2002), 59-73.
5. R.P. Anstee and A. Sali, “Sperner families of bounded VC-dimension,” Discrete Math. 175 (1997), 13-21.
6. L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics, September 1992.
7. T. Becker and V. Weispfenning, Gr\ddot obner Bases-A Computational Approach to Commutative Algebra, Springer-Verlag, Berlin, 1993.
8. A. Bernasconi and L. Egidi, “Hilbert function and complexity lower bounds for symmetric Boolean functions,” Information and Computation 153 (1999), 1-25.
9. T. Bier,“Remarks on recent formulas of Wilson and Frankl,” Europ. J. Combin. 14 (1993), 1-8. HEGED \Acute\Acute US AND R ÓNYAI
10. A.M. Cohen, H. Cuypers, and H. Sterk (Eds.), Some Tapas of Computer Algebra, Springer-Verlag, Berlin, 1999.
11. P. Frankl, “Intersection theorems and mod p rank of inclusion matrices,” J. Combin. Theory A 54 (1990), 85-94.
12. R.L. Graham, D.E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989.
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.