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

An Application: Ramsey Graphs

The set-system ${\cal H}$ of Theorem 1.2 yields new families of explicit Ramsey-graphs.

Theorem 4.1 (Frankl-Wilson, 1981)   For $t\geq3$, there exists an explicitly constructible graph on $\exp\bigg(c{(\log t)^2\over(\log \log t)}\bigg)$ vertices which does not contain either a complete graph or an independent set of size t.

The constant c given in [6] is $c={1\over 4}$. Our construction yields $c={2\over81}$ 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 $r\geq 2$, $t\geq3$, there exists an explicitly constructible r-coloring of the edges of the complete graph on $\exp\bigg(c_r{(\log t)^r\over(\log \log t)^{r-1}}\bigg)$ vertices such that no color contains a complete graph on t vertices. Here $c_r=c/p_r^{2r}\sim c(r\ln r)^{-2r}$, where pr is the $r^{\hbox{th}}$ 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 ${\cal H}$, where ${\cal H}$ is a set-system with the properties stated in Theorem 1.2, with $h=\lfloor t^{1/p_r}\rfloor$. We define an r-coloring of the edges of K by colors 1,2,...,r as follows: edge UV, where $U,V\in{\cal H}$, has color i if

\begin{displaymath}i=\min_{j\in\{1,2,...,r\}}\{j:p_j \hbox{ does not divide } \vert U\cap V\vert\}.\end{displaymath}

Now suppose that K contains a monochromatic complete graph Ci of $\ell_i$ vertices in color i. Then the sets, corresponding to the vertices of Ci, give a family of $\ell_i$ 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,

\begin{displaymath}\ell_i\leq{h\choose p_i-1}<t.\end{displaymath}

$\Box$
next up previous
Next: Open Problems Up: Superpolynomial Size Set-Systems with Previous: The Lower Bound
Vince Grolmusz
1999-11-08