Standard monomials for q-uniform families and a conjecture of Babai and Frankl

• Autorzy: Gábor Hegedűs , Lajos Rónyai
• Języki publikacji: EN

Abstrakty

EN

Let n, k, α be integers, n, α>0, p be a prime and q=p α. Consider the complete q-uniform family $$\mathcal{F}\left( {k,q} \right) = \left\{ {K \subseteq \left[ n \right]:\left| K \right| \equiv k(mod q)} \right\}$$ We study certain inclusion matrices attached to F(k,q) over the field $$\mathbb{F}_p $$ . We show that if l≤q−1 and 2l≤n then $$rank_{\mathbb{F}_p } I(\mathcal{F}(k,q),\left( {\begin{array}{*{20}c} {\left[ n \right]} \\ { \leqslant \ell } \\ \end{array} } \right)) \leqslant \left( {\begin{array}{*{20}c} n \\ \ell \\ \end{array} } \right)$$ 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.

Słowa kluczowe

EN

Gröbner basis; inclusion matrix; set family; 05D05; 13P10; 05B20

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2003
• Tom: 1
• Numer: 2
• Strony: 198-207

Daty

wydano

2003-06-01

online

2003-06-01

Twórcy

autor

Gábor Hegedűs

• Budapest University of Technology and Economics

autor

Lajos Rónyai

Bibliografia

• [1] W.W. Adams and P. Loustaunau: An Introduction to Gröbner Bases, American Mathematical Society, 1994.
• [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
• [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.
• [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.
• [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.
• [9] R.L. Graham, D.E. Knuth, O. Patashnik: Concrete Mathematics, Addison-Wesley, Reading, Massachusetts, 1989.
• [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
• [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.

Identyfikatory

DOI

10.2478/BF02476008