96-57: On the Size of Set Systems on [n] Not Containing Weak (r, \Delta)-Systems

DIMACS TR: 96-57

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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-57.ps.gz

DIMACS Home Page