next up previous
Next: Preliminaries Up: Superpolynomial Size Set-Systems with Previous: Superpolynomial Size Set-Systems with

Introduction

Generalizing the Ray-Chaudhuri--Wilson theorem [8], Frankl and Wilson [6] proved the following intersection theorem, one of the most important results in extremal set theory:

Theorem 1.1 (Frankl-Wilson)   Let ${\cal F}$ be a set-system over a universe of n elements. Suppose $\mu_0,\mu_1,...,\mu_s$ are distinct residues modulo a prime p, such that for all $F\in{\cal F}$,

\begin{displaymath}\vert F\vert=k\equiv\mu_0\pmod{p},\end{displaymath}

where $k+s\leq n$, and for any two distinct $F, G\in{\cal F}$:

\begin{displaymath}\vert F\cap G\vert\equiv\mu_i\pmod{p} \hbox{ for some $i$, } 1\leq i\leq s.\end{displaymath}

Then

\begin{displaymath}\vert{\cal F}\vert\leq {n\choose s}.\eqno{(1)}\end{displaymath}

$\Box$

This theorem has numerous applications in combinatorics and in geometry (e.g., the disproof of Borsuk's conjecture by Kahn and Kalai [7] (cf. [1], Sec. 5.6.), an explicit construction of Ramsey graphs, and geometric applications related to the Hadwiger-problem [6].)

Frankl and Wilson [6] asked whether inequality (1) remains true when the modulus p is replaced by a composite number m, or at least in the subcase s=m-1.

Frankl [5] answered the first of these questions (arbitrary $s\leq m$) in the negative: he constructed faster growing set-systems for m=6, as well as for m=p2, p prime. For m=6, Frankl's set-systems satisfy s=3 and $\vert{\cal F}\vert\approx cn^4$.

On the other hand, Frankl and Wilson [6] proved that inequality (1) remains in force when s=m-1 and m is a prime power.

In this paper we consider non-prime-power moduli m. For any such modulus, we give a very strong negative answer to both versions of the Frankl-Wilson question: we prove that for s=m-1, no upper bound of the form nf(m) exists. More precisely, we prove the following.

Theorem 1.2   Let m be a positive integer, and suppose that m has r>1 different prime divisors: $m=p_1^{\alpha_1}p_2^{\alpha_2}...p_r^{\alpha_r}$. Then there exists c=c(m)>0, such that for every integer h>0, there exists an explicitly constructible uniform set-system ${\cal H}$ over a universe of h elements, such that
(a)
$\vert{\cal H}\vert\geq \exp\bigg(c{(\log h)^r\over
(\log \log h)^{r-1}}\bigg)$,
(b)
$\forall H\in {\cal H}: \ \vert H\vert\equiv0\pmod{m}$,
(c)
$\forall G, H\in {\cal H}, G\ne H: \ \vert G\cap H\vert\not\equiv0\pmod{m}$.

Remark 1.3   The value of c is roughly pr-r, where pr is the largest prime divisor of m. The size of the sets in the set-system we construct is

\begin{displaymath}h^{{r-1\over {2r-1}}+o(1)}. \eqno{(2)}\end{displaymath}


We note that for fixed m (m is not a prime power), the size of ${\cal H}$ grows faster than any polynomial of n. This is quite surprising, since previously it was believed that the failure of the attempts to prove a polynomial upper bound was due to the lack of techniques to handle non-prime-power composite moduli.

Our result gives a strong negative answer to a conjecture of Babai and Frankl ([1], Section 7.3, Conjecture C(r)). Babai and Frankl conjectured that conditions (b) and (c) of Theorem 1.2 imply

\begin{displaymath}\vert{\cal H}\vert\leq {h\choose m-1};\end{displaymath}

whereas our result shows that no bound of the form hf(m) exists for composite, non-prime power moduli m.

We can even strengthen statement (c) of Theorem 1.2 as follows:

Theorem 1.4   Theorem 1.2 remains valid if we add the following condition:
(d)
$\forall G, H\in {\cal H}$, $G\ne H$ and $\forall i\in\{1,2,\ldots,r\}$, we have $\vert G\cap H\vert\equiv0\pmod{p_i^{\alpha_i}}$ or $\vert G\cap H\vert\equiv1\pmod{p_i^{\alpha_i}}$.

Remark 1.5   Theorem 1.4 implies that there exist super-polynomial size set-systems ${\cal H}$ such that the size of each set in ${\cal H}$ is divisible by m and the sizes of the pairwise intersections of the sets in ${\cal H}$ occupy at most 2r-1 residue classes mod m out of the possible m-1 nonzero residue classes.

In fact, this result can be further strengthened: 3 residue classes of intersection size suffice! This answers a question of Peter Frankl (private communication).

Corollary 1.6  

Let m be a positive integer, and suppose that m has r>1 different prime divisors: $m=p_1^{\alpha_1}p_2^{\alpha_2}...p_r^{\alpha_r}$. Then there exists c=c(m)>0, such that for every integer h>0, there exists an explicitly constructible uniform set-system ${\cal H}$ over a universe of h elements such that

(a)
$\vert{\cal H}\vert\geq \exp\bigg(c{(\log h)^2\over
\log \log h}\bigg)$,
(b)
$\forall H\in {\cal H}: \ \vert H\vert\equiv0\pmod{m}$,
(c)
the sizes of the pairwise intersections $\vert G\cap H\vert$ ( $G, H\in {\cal H}$, $G\ne H$) occupy only 3 residue classes mod m, none of which is 0.


One of the striking applications of the Frankl-Wilson theorem for prime moduli was an explicit construction of graphs of size $\exp(c\log^2n/\log\log n)$ without homogeneous subsets (cliques or anti-cliques) of size n. These are the largest explicit Ramsey-graphs known to-date. As an application of our Theorem 1.2 , we give an alternative construction of explicit Ramsey graphs of the same logarithmic order of magnitude, i.e., of size $\exp(c'\log^2n/\log\log n)$. (But our c' is less than their c).

A key ingredient of our construction is a low-degree polynomial constructed by Barrington, Beigel and Rudich [2], to represent the Boolean ``OR'' function mod m. Any reduction of the degree of such polynomials would yield improved explicit Ramsey graphs.


next up previous
Next: Preliminaries Up: Superpolynomial Size Set-Systems with Previous: Superpolynomial Size Set-Systems with
Vince Grolmusz
1999-11-08