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