TR-2001-29
Constructing large set systems with given intersection sizes modulo composite numbers
Samuel Kutin. 30 August, 2001.
Communicated by Laszlo Babai.
Abstract
We consider $k$-uniform set systems over a universe of size $n$ such
that the size of each pairwise intersection of sets lies in one of $s$
residue classes mod $q$, but $k$ does not lie in any of these $s$
classes. A celebrated theorem of Frankl and Wilson (1981) states that
any such set system has size $n \choose s$ when $q$ is prime. In a
remarkable recent paper, Grolmusz (2000) constructed set systems of
size $\Omega(\exp(c \log^2 n / \log \log n))$ when $q = 6$. We give
a new, simpler construction achieving a slightly improved bound. Our
construction combines a technique of Frankl (1983) of ``applying
polynomials to set systems'' with Grolmusz's idea of employing
polynomials introduced by Barrington, Beigel, and Rudich (1994).
We also extend Frankl's original argument to arbitrary prime-power
moduli: for any $\epsilon > 0$, we construct systems of
size $n^{s + g(s)}$, where $g(s) = \Omega(s^{1-\epsilon})$.
Original Document
The original document is available in Postscript (uploaded 31 August, 2001 by
Nicholas Russo).
