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

Open Mathematics (2003)

• Volume: 1, Issue: 2, page 198-207
• ISSN: 2391-5455

top

## Abstract

top
Let n, k, α be integers, n, α>0, p be a prime and q=p α. Consider the complete q-uniform family $ℱ\left(k,q\right)=\left\{K\subseteq \left[n\right]:\left|K\right|\equiv k\left(modq\right)\right\}$ 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 $ran{k}_{{𝔽}_{p}}I\left(ℱ\left(k,q\right),\left(\begin{array}{c}\left[n\right]\\ ⩽\ell \end{array}\right)\right)⩽\left(\begin{array}{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.

## How to cite

top

Gábor Hegedűs, and Lajos Rónyai. "Standard monomials for q-uniform families and a conjecture of Babai and Frankl." Open Mathematics 1.2 (2003): 198-207. <http://eudml.org/doc/268782>.

@article{GáborHegedűs2003,
abstract = {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\lbrace \{K \subseteq \left[ n \right]:\left| K \right| \equiv k(mod q)\} \right\rbrace$ 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.},
author = {Gábor Hegedűs, Lajos Rónyai},
journal = {Open Mathematics},
keywords = {05D05; 13P10; 05B20},
language = {eng},
number = {2},
pages = {198-207},
title = {Standard monomials for q-uniform families and a conjecture of Babai and Frankl},
url = {http://eudml.org/doc/268782},
volume = {1},
year = {2003},
}

TY - JOUR
AU - Gábor Hegedűs
AU - Lajos Rónyai
TI - Standard monomials for q-uniform families and a conjecture of Babai and Frankl
JO - Open Mathematics
PY - 2003
VL - 1
IS - 2
SP - 198
EP - 207
AB - 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\lbrace {K \subseteq \left[ n \right]:\left| K \right| \equiv k(mod q)} \right\rbrace$ 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.
LA - eng
KW - 05D05; 13P10; 05B20
UR - http://eudml.org/doc/268782
ER -

## References

top
1. [1] W.W. Adams and P. Loustaunau: An Introduction to Gröbner Bases, American Mathematical Society, 1994. Zbl0803.13015
2. [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 Zbl0990.05123
3. [3] L. Babai and P. Frankl: Linear algebra methods in combinatorics, September 1992.
4. [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. Zbl0829.68057
5. [5] T. Becker and V. Weispfenning: Gröbner bases- a computational approach to commutative algebra, Springer-Verlag, Berlin, Heidelberg, 1993.
6. [6] A.M. Cohen, H. Cuypers, H. Sterk (eds.): Some Tapas of Computer Algebra, Springer-Verlag, Berlin, Heidelberg, 1999. Zbl0924.13021
7. [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. [8] K. Friedl and L. Rónyai: “Order-shattering and Wilson's theorem”, Discrete Mathematics, to appear. Zbl1023.05130
9. [9] R.L. Graham, D.E. Knuth, O. Patashnik: Concrete Mathematics, Addison-Wesley, Reading, Massachusetts, 1989. Zbl0668.00003
10. [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 Zbl1045.13011
11. [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. Zbl0747.05016

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.