Multivalued generalizations of the Frankl-Pach theorem

DOI10.1142/S0219498811005282MaRDI QIDQ5389512zbMATH OpenOpenAlexFDO

Authors Gábor Hegedüs, Lajos Rónyai

Publication date 21 April 2012

Published in Journal of Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.4660

zbMATH Keywords

\(n\)-tuple systemGröbner basisshattered setstandard monomialuniform family

Mathematics Subject Classification ID

Extremal set theory (05D05) Combinatorial aspects of commutative algebra (05E40) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25)

Abstract: P. Frankl and J. Pach proved the following uniform version of Sauer's Lemma. Let $n,d,s$ be natural numbers such that $dleqn$, $s+1leqn/2$. Let $cFsubseteq[n]choosed$ be an arbitrary $d$-uniform set system such that $cF$ does not shatter an $s+1$-element set, then ${\displaystyle }$ |cF|leq {n choose s}.${\displaystyle }$ We prove here two generalizations of the above theorem to $n$-tuple systems. To obtain these results, we use Gr"obner basis methods, and describe the standard monomials of Hamming spheres.

Recommendations

• Shattering news
• VC dimension and a union theorem for set systems
• Defect Sauer results
• A generalization of Sauer's lemma
• Standard monomials and extremal point sets

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• A forbidden configuration theorem of Alon
• A generalization of Sauer's lemma
• Coordinate density of sets of vectors
• Existence of submatrices with all possible columns
• Gröbner bases for complete uniform families
• scientific article; zbMATH DE number 3712896 (Why is no real title available?)
• scientific article; zbMATH DE number 1332320 (Why is no real title available?)
• scientific article; zbMATH DE number 736296 (Why is no real title available?)
• scientific article; zbMATH DE number 3308309 (Why is no real title available?)
• On disjointly representable sets
• On the density of families of sets
• On the density of sets of vectors
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the VC-dimension of uniform hypergraphs
• Shattering news
• The lex game and some applications
• Traces of antichains

Cited in

(3)

• A generalization of Sauer's lemma
• Defect Sauer results
• MODEL THEORY AND COMBINATORICS OF BANNED SEQUENCES

This page was built for publication: Multivalued generalizations of the Frankl-Pach theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5389512)