Standard monomials for q-uniform families and a conjecture of Babai and Frankl
Gábor Hegedűs ; Lajos Rónyai
Open Mathematics, Tome 1 (2003), p. 198-207 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

Let n, k, α be integers, n, α>0, p be a prime and q=p α. Consider the complete q-uniform family ℱk,q=K⊆n:K≡k(modq) We study certain inclusion matrices attached to F(k,q) over the field 𝔽p . We show that if l≤q−1 and 2l≤n then rank𝔽pI(ℱ(k,q),n⩽ℓ)⩽nℓ This extends a theorem of Frankl [7] obtained for the case α=1. In the proof we use arguments involving Gröbner bases, standard monomials and reduction. As an application, we solve a problem of Babai and Frankl related to the size of some L-intersecting families modulo q.

Publié le : 2003-01-01
EUDML-ID : urn:eudml:doc:268782 
@article{bwmeta1.element.doi-10_2478_BF02476008,
     author = {G\'abor Heged\H us and Lajos R\'onyai},
     title = {Standard monomials for q-uniform families and a conjecture of Babai and Frankl},
     journal = {Open Mathematics},
     volume = {1},
     year = {2003},
     pages = {198-207},
     zbl = {1034.05045},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_BF02476008}
}

Gábor Hegedűs; Lajos Rónyai. Standard monomials for q-uniform families and a conjecture of Babai and Frankl. Open Mathematics, Tome 1 (2003) pp. 198-207. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_BF02476008/

[1] W.W. Adams and P. Loustaunau: An Introduction to Gröbner Bases, American Mathematical Society, 1994. | Zbl 0803.13015

[2] R.P. Anstee, L. Rónyai, A. Sali: “Shattering news”, Graphs and Combinatorics, Vol. 18, (2002), pp. 59–73. http://dx.doi.org/10.1007/s003730200003 | Zbl 0990.05123

[3] L. Babai and P. Frankl: Linear algebra methods in combinatorics, September 1992.

[4] D.A. Barrington, R. Beigel, S. Rudich: “Representing boolean functions modulo composite numbers”, In: Proc. 24th Annual ACM Symposium on Theory of Computing, Victoria, BC, Canada, 1992, pp. 455–461. | Zbl 0829.68057

[5] T. Becker and V. Weispfenning: Gröbner bases- a computational approach to commutative algebra, Springer-Verlag, Berlin, Heidelberg, 1993.

[6] A.M. Cohen, H. Cuypers, H. Sterk (eds.): Some Tapas of Computer Algebra, Springer-Verlag, Berlin, Heidelberg, 1999. | Zbl 0924.13021

[7] P. Frankl: “Intersection theorems and mod p rank of inclusion matrices”, J. Combin. Theory A, Vol. 54, (1990), pp. 85–94. http://dx.doi.org/10.1016/0097-3165(90)90007-J

[8] K. Friedl and L. Rónyai: “Order-shattering and Wilson's theorem”, Discrete Mathematics, to appear. | Zbl 1023.05130

[9] R.L. Graham, D.E. Knuth, O. Patashnik: Concrete Mathematics, Addison-Wesley, Reading, Massachusetts, 1989. | Zbl 0668.00003

[10] G. Hegedűs and L. Rónyai: “Gröbner bases for complete uniform families”, J. of Algebraic Combinatorics, Vol. 17, (2003), pp. 171–180. http://dx.doi.org/10.1023/A:1022934815185 | Zbl 1045.13011

[11] R.M. Wilson: “A diagonal form for the incidence matrices of t-subsets vs. k-subsets”, European Journal of Combinatorics, Vol. 11, (1990), pp. 609–615. | Zbl 0747.05016