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 be a set-system over a universe of n elements. Suppose are distinct residues modulo a prime p, such that for all ,

where , and for any two distinct :

Then

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

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: . Then there exists c=c(m)>0, such that for every integer h>0, there exists an explicitly constructible uniform set-system over a universe of h elements, such that
(a)
,
(b)
,
(c)
.

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

We note that for fixed m (m is not a prime power), the size of 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

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)
, and , we have or .

Remark 1.5   Theorem 1.4 implies that there exist super-polynomial size set-systems such that the size of each set in is divisible by m and the sizes of the pairwise intersections of the sets in 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: . Then there exists c=c(m)>0, such that for every integer h>0, there exists an explicitly constructible uniform set-system over a universe of h elements such that

(a)
,
(b)
,
(c)
the sizes of the pairwise intersections ( , ) 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 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 . (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: Preliminaries Up: Superpolynomial Size Set-Systems with Previous: Superpolynomial Size Set-Systems with
Vince Grolmusz
1999-11-08