On the Size of Set Systems on [n] Not Containing
Weak (r, \Delta)-Systems
Authors: Vojtech Rodl and Lubos Thoma
ABSTRACT
Let $r\ge 3$ be an integer. A weak $(r, \Delta)$-system is a family
of $r$ sets such that all pairwise intersections among the members have
the same cardinality.
We show that for $n$ large enough, there exists a family ${\cal F}$
of subsets of $[n]$ such that ${\cal F}$ does not contain a weak
$(r, \Delta)$-system and $|{\cal F}| \ge 2^{ {1\over 3} \cdot
n^{1/5}\log^{4/5}(r-1)}.$
This improves an earlier result of P. Erd\H{o}s and E. Szemer\'edi.
DIMACS Home Page