Unavoidable traces of set systems

József Balogh, Béla Bollobás

Research output: Contribution to journalArticlepeer-review

Abstract

Sauer, Shelah, Vapnik and Chervonenkis proved that if a set system on n vertices contains many sets, then the set system has full trace on a large set. Although the restriction on the size of the groundset cannot be lifted, Frankl and Pach found a trace structure that is guaranteed to occur in uniform set systems even if we do not bound the size of the groundset. In this note we shall give three sequences of structures such that every set system consisting of sufficiently many sets contains at least one of these structures with many sets.

Original languageEnglish (US)
Pages (from-to)633-643
Number of pages11
JournalCombinatorica
Volume25
Issue number6
DOIs
StatePublished - Dec 2005
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Unavoidable traces of set systems'. Together they form a unique fingerprint.

Cite this