Standard monomials for \(q\)-uniform families and a conjecture of Babai and Frankl (Q1407186)

From MaRDI portal





scientific article; zbMATH DE number 1978732
Language Label Description Also known as
English
Standard monomials for \(q\)-uniform families and a conjecture of Babai and Frankl
scientific article; zbMATH DE number 1978732

    Statements

    Standard monomials for \(q\)-uniform families and a conjecture of Babai and Frankl (English)
    0 references
    0 references
    0 references
    27 January 2004
    0 references
    This very interesting paper proves affirmatively Babai's and Frankl's conjecture: Let \(k\) be an integer and \(q\) a prime power where \(2q-2 \leq n.\) Let \(A_1,\dots ,A_m\) be a subset-family of \([n]\) where \(| A_i| \equiv k \pmod q\) for all \(i\) and \(| A_i\cap A_j| \not\equiv k \pmod q\) for all pairs \(i\neq j.\) Then \(m \leq {n \choose q-1}.\) The proof is based on the ``standard'' linear bound method enriched with arguments involving Gröbner-standard monomials.
    0 references
    uniform set systems
    0 references
    inclusion matrix
    0 references
    Gröbner basis
    0 references
    Gröbner-standard monomials
    0 references
    reduction
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references