Constructing large set systems with given intersection sizes modulo composite numbers

Samuel Kutin. 30 August, 2001.
Communicated by Laszlo Babai.


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).