Generalizing the Ray-Chaudhuri--Wilson theorem , Frankl and Wilson  proved the following intersection theorem, one of the most important results in extremal set theory:
This theorem has numerous applications in combinatorics and in geometry (e.g., the disproof of Borsuk's conjecture by Kahn and Kalai  (cf. , Sec. 5.6.), an explicit construction of Ramsey graphs, and geometric applications related to the Hadwiger-problem .)
Frankl and Wilson  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  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  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.
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 (, Section 7.3, Conjecture C(r)).
Babai and Frankl conjectured that conditions (b) and (c)
of Theorem 1.2 imply
We can even strengthen statement (c) of Theorem 1.2 as follows:
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
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 , to represent the Boolean ``OR'' function mod m. Any reduction of the degree of such polynomials would yield improved explicit Ramsey graphs.