Unavoidable traces of set systems

DOI10.1007/S00493-005-0039-XMaRDI QIDQ2368593zbMATH OpenOpenAlexFDO

Authors József Balogh, Béla Bollobás

Publication date 27 June 2006

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-005-0039-x

zbMATH Keywords

\(k\)-systemhomogeneous sequence

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Extremal set theory (05D05)

Review text

\textit{N. Sauer} [J. Comb. Theory, Ser. A 13, 145--147 (1972; Zbl 0248.05005)], \textit{S. Shelah} [Pac. J. Math. 41, 247--261 (1972; Zbl 0239.02024)] and \textit{V. N. Vapnik} and \textit{A. Ya. Chervonenkis} [Theor. Probab. Appl. 16, 264--280 (1971; Zbl 0247.60005)] showed that if a hypergraph on \(n\) vertices contains sufficiently many edges then it contains a full trace on some large set. \textit{P. Frankl} and \textit{J. Pach} [Combinatorica 4, 39--45 (1984; Zbl 0534.05003)] obtained results of the same spirit for the case when the size of the ground set is not bounded. In this paper three sequences of structures are given such that every set system consisting of sufficiently many sets contains at least one of these structures with many sets.

Recommendations

• scientific article; zbMATH DE number 3887691
• Forbidding complete hypergraphs as traces
• Edge Multiplicity and Other Trace Functions
• Some best possible bounds concerning the traces of finite sets
• On extremal problems concerning the traces of sets

Cited in

(20)

• \(l\)-trace \(k\)-Sperner families of sets
• Kneser ranks of random graphs and minimum difference representations
• Multi-symbol forbidden configurations
• Forbidden families of minimal quadratic and cubic configurations
• Inclusionwise minimal completely separating systems
• Disjoint representability of sets and their complements
• Unavoidable subprojections in union-closed set systems of infinite breadth
• Vapnik-Chervonenkis density in some theories without the independence property. I
• Forbidden configurations: boundary cases
• Traceable Sets
• scientific article; zbMATH DE number 3887691 (Why is no real title available?)
• Edge Multiplicity and Other Trace Functions
• Repeated columns and an old chestnut
• Kneser ranks of random graphs and minimum difference representations
• Forbidden configurations and product constructions
• Forbidden Berge hypergraphs
• Multivalued matrices and forbidden configurations
• Forbidden configurations and repeated induction
• Linear algebra methods for Forbidden configurations
• Minimum difference representations of graphs

This page was built for publication: Unavoidable traces of set systems

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