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
default for all languages
No label defined
    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