PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2003 | 1 | 2 | 198-207
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
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
Wydawca
Czasopismo
Rocznik
Tom
1
Numer
2
Strony
198-207
Opis fizyczny
Daty
wydano
2003-06-01
online
2003-06-01
Twórcy
  • Budapest University of Technology and Economics
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_2478_BF02476008
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.