Next: Open Problems Up: Superpolynomial Size Set-Systems with Previous: The Lower Bound

# An Application: Ramsey Graphs

The set-system of Theorem 1.2 yields new families of explicit Ramsey-graphs.

Theorem 4.1 (Frankl-Wilson, 1981)   For , there exists an explicitly constructible graph on vertices which does not contain either a complete graph or an independent set of size t.

The constant c given in [6] is . Our construction yields only.

In addition to giving a novel proof of Theorem 4.1, we extend it to the case of several colors:

Theorem 4.2   For , , there exists an explicitly constructible r-coloring of the edges of the complete graph on vertices such that no color contains a complete graph on t vertices. Here , where pr is the prime, and c>0 is an absolute constant.

The existence of graphs with more than 2(t-1)/2 vertices without a complete graph or an independent set of size t is known from the famous theorem of Erdos [4]. The probabilistic proof of that theorem immediately implies the existence of an r-coloring of the edges of the complete graph on r(t-1)/2 vertices, without a monochromatic complete graph on t vertices. For more than two colors, no explicit Ramsey-graph constructions seem to have appeared prior to the present work. It does not seem immediate how one could modify the Frankl-Wilson construction to more than two colors.

Proof. Let m=p1p2....pr, where pi is the ith prime. Let K be a complete graph on vertex-set , where is a set-system with the properties stated in Theorem 1.2, with . We define an r-coloring of the edges of K by colors 1,2,...,r as follows: edge UV, where , has color i if

Now suppose that K contains a monochromatic complete graph Ci of vertices in color i. Then the sets, corresponding to the vertices of Ci, give a family of sets, such that the size of each set is divisible with pi, but the size of the intersection of any two elements of this set-system is not divisible by pi. Consequently, by Theorem 1.1,

Next: Open Problems Up: Superpolynomial Size Set-Systems with Previous: The Lower Bound
Vince Grolmusz
1999-11-08