Name
Abstract | ||
|---|---|---|
Let q be a power of a prime p, and let n, d, l be integers such that 1 <= n, 1 <= q. Consider the modulo q complete l-wide family: F = {F subset of [n] : there exists f is an element of Zi s.t. d <= f < d + l and vertical bar F vertical bar f (mod q)}. We describe a Grobner basis of the. vanishing ideal I(F) of the set of characteristic vectors of F over fields of characteristic p. It turns out that this set of polynomials is a Grobner basis for all term orderings <, for which the order of the variables is x(n) < x(n-1) < ... < x(1). We compute the Hilbert function of 1(F), which yields formulae for the modulo p rank of certain inclusion matrices related to F. We apply our results to problems from extremal set theory. We prove a sharp tipper bound of the cardinality of a modulo q l-wide family, which shatters only small sets. This is closely related to a conjecture of Frankl [13] on certain l-antichains. The formula of the Hilbert function also allows us to obtain an upper bound oil the size of a set system with certain restricted intersections, generalizing a bound proposed by Babai and Frankl [6]. The paper generalizes and extends the results of [15], [16] and [17]. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1017/S0963548308009619 | COMBINATORICS PROBABILITY & COMPUTING |
DocType | Volume | Issue |
Journal | 18 | 3 |
ISSN | Citations | PageRank |
0963-5483 | 0 | 0.34 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bálint Felszeghy | 1 | 11 | 1.36 |
| Gábor Hegedüs | 2 | 36 | 7.38 |
| Lajos Rónyai | 3 | 397 | 52.05 |