Unavoidable Traces Of Set Systems |
| |
Authors: | József Balogh Béla Bollobás |
| |
Institution: | (1) Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA |
| |
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. |
| |
Keywords: | 05C35 05C65 05D05 |
本文献已被 SpringerLink 等数据库收录! |
|