Article contents
Algebraic Properties of Modulo q Complete ℓ-Wide Families
Published online by Cambridge University Press: 01 May 2009
Abstract
Let q be a power of a prime p, and let n, d, ℓ be integers such that 1 ≤ n, 1 ≤ ℓ < q. Consider the modulo q complete ℓ-wide family:
We describe a Gröbner basis of the vanishing ideal I() of the set of characteristic vectors of over fields of characteristic p. It turns out that this set of polynomials is a Gröbner basis for all term orderings ≺, for which the order of the variables is xn ≺ xn−1 ≺ ⋅⋅⋅ ≺ x1.
We compute the Hilbert function of I(), which yields formulae for the modulo p rank of certain inclusion matrices related to .
We apply our results to problems from extremal set theory. We prove a sharp upper bound of the cardinality of a modulo q ℓ-wide family, which shatters only small sets. This is closely related to a conjecture of Frankl [13] on certain ℓ-antichains. The formula of the Hilbert function also allows us to obtain an upper bound on 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].
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2008
References
- 3
- Cited by