next up previous
Next: Introduction

Superpolynomial Size Set-Systems with Restricted Intersections mod 6 and Explicit Ramsey Graphs

Vince Grolmusz
\begin{thanks}
{Department of Computer Science, E\uml otv\uml os University, Bu...
...the Department of Computer Science at The University of
Chicago.}
\end{thanks}

Dedicated to the memory of Paul Erdos


Abstract:

We construct a system ${\cal H}$ of $\exp(c\log^2n/\log\log n)$ subsets of a set of n elements such that the size of each set is divisible by 6 but their pairwise intersections are not divisible by 6. The result generalizes to all non-prime-power moduli m in place of m=6. This result is in sharp contrast with results of Frankl and Wilson (1981) for prime power moduli and gives strong negative answers to questions by Frankl and Wilson (1981) and Babai and Frankl (1992). We use our set-system ${\cal H}$ to give an explicit Ramsey-graph construction, reproducing the logarithmic order of magnitude of the best previously known construction due to Frankl and Wilson (1981). Our construction uses certain mod m polynomials, discovered by Barrington, Beigel and Rudich (1994).



 

Vince Grolmusz
1999-11-08