Standard monomials for \(q\)-uniform families and a conjecture of Babai and Frankl
type: Item
instance of: scholarly article
title: Standard monomials for \(q\)-uniform families and a conjecture of Babai and Frankl
zbMATH Open document ID: 1034.05045
DOI: 10.2478/BF02476008
author: Lajos Rónyai
author: Gábor Hegedüs
published in: Central European Journal of Mathematics
publication date: 2004-01-27T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 13P10
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 1978732
zbMATH Keywords: uniform set systems
zbMATH Keywords: inclusion matrix
zbMATH Keywords: Gröbner basis
zbMATH Keywords: Gröbner-standard monomials
zbMATH Keywords: reduction
Wikidata QID: Q123184002
reviewed by: Péter L. Erdős
MaRDI profile type: MaRDI publication profile
cites work: Q4305609
cites work: Shattering news
cites work: Representing Boolean functions as polynomials modulo composite numbers
cites work: Q4693774
cites work: Some tapas of computer algebra
cites work: Intersection theorems and mod \(p\) rank of inclusion matrices
cites work: Order shattering and Wilson's theorem
cites work: Q4040797
cites work: Gröbner bases for complete uniform families
cites work: A diagonal form for the incidence matrices of \(t\)-subsets vs. \(k\)- subsets
full work available at URL: https://doi.org/10.2478/bf02476008
OpenAlex ID: W2052993730
description: scientific article; zbMATH DE number 1978732