# A problem on constructive Ramsey bounds (\$100)

Give a constructive proof that $r(k) > (1+c)^k$ for some $$c >0$$.

In other words, construct a graph on $$n$$ vertices which does not contain any clique of size $$c' \log n$$ and does not contain any independent set of size $$c' \log n$$.

Attempts have been made over the years to construct Ramsey graphs (i.e., with small cliques and independent sets) without much success. Abbott [1] gave a recursive construction with cliques and independence sets of size $$c n^{\log 2 / \log 5}$$. Nagy [12] gave a construction reducing the size to $$cn^{1/3}$$. A breakthrough finally occurred several years ago with the result of Frankl [5] who gave the first Ramsey construction with cliques and independent sets of size smaller than $$n^{\epsilon}$$ for any $$\epsilon > 0$$. Chung [4] further improved this to $$e^{c(\log n )^{3/4} (\log \log n)^{1/4}}$$.

Here we will outline a construction of Frankl and Wilson [6] for Ramsey graphs with cliques and independent sets of size at most $$e^{c (\log n \log \log n )^{1/2}}$$. In other words,

$$\displaystyle r(k) > k^{c \log k / \log \log k}.$$

This construction is based upon their beautiful theorem on set intersections:

#### Theorem

Let $$p$$ denote a prime power and suppose $$\mu_0, \mu_1, \ldots, \mu_s$$ are distinct non-zero residues modulo $$p$$. We consider a family $${\mathcal F}$$ consisting of $$k$$-sets of an $$n$$-set with the property that for all $$S, T \in {\mathcal F}$$, we have $$\vert S \cap T\vert \equiv \mu_i$$ (mod $$p$$) for some $$i$$, $$0 \leq i \leq s$$. Then

$$\displaystyle \vert{\mathcal F} \vert \leq \binom{n}{s}.$$

Now, we consider the graph $$G$$ which has vertex set $$V = \{ F \subseteq \{ 1 , \cdots , m \} :~ ~\vert F \vert ~= q^2 - 1 \}$$ and edge set $$E = \{( F , F^{\prime} ) : ~\mid F \cap F^{\prime} \mid \not\equiv - 1 ( \bmod \: q )\}$$. The above theorem implies that $$G$$ contains no clique or independent set of size $$\left( \! \! \! \begin{array}{c} {m} { q-1} \end{array} \! \! \! \right)$$. By choosing $$m = q^3$$, we obtain a graph on $$n = \left( \! \! \! \begin{array}{c} m {q^2 - 1} \end{array} \! \! \! \right)$$ vertices containing no clique or independent set of size $$e^{c(\log \, n \, \log \, \log \, n)^{1/2}}$$.

Work has also been done on constructing off-diagonal Ramsey graphs -- for example finding triangle-free graphs with small independent sets.

Alon [2] constructed graphs to show that

$$\displaystyle R(3, k) = \Omega(n^{3/2}).$$

Kostochka, Pudlák, and Rodl [7] constructive graphs showing

$$\displaystyle R(4, k) = \Omega(n^{8/5}),$$

$$\displaystyle R(5, k) = \Omega(n^{5/3}),$$

$$\displaystyle R(6, k) = \Omega(n^{2}).$$

Alon and Pudlák [3] also constructed a general lower bound, showing that there is a fixed $$\epsilon$$ such that, for large $$m$$,

$$\displaystyle R(s, m) \ge m^{\epsilon \sqrt{\log s / \log \log s}}$$

There has been a great deal of development in explicit constructions of so-called expander graphs. (which are graphs with certain isoperimetric properties). In particular, Lubotzky, Phillips and Sarnak [8] and Margulis [9] [10] [11] have successfully obtained explicit constructions for expander graphs. Although there has been much hope, these constructions have not lead to constructing Ramsey graphs on $$n$$ vertices which contain no clique of size $$c \log n$$ and no independent set of size $$c \log n$$.

Bibliography
1 H. L. Abbott, Lower bounds for some Ramsey numbers, Discrete Math. 2 (1972), 289-293.

2 N. Alon, Explicit Ramsey graphs and orthonormal labelings, Electron. J. Combin. 1 (1994), R12.

3 N. Alon and P. Pudlák, Constructive lower bounds for off-diagonal Ramsey numbers, Israel J. Math. 122 (2001), 243–-251.

4 F. R. K. Chung, A note on constructive methods for Ramsey numbers, J. Graph Th. 5 (1981), 109-113.

5 P. Frankl, A constructive lower bound for some Ramsey numbers, Ars Combinatoria 3 (1977), 297-302.

6 P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), 357-368.

7 A. Kostochka, P. Pudlák, V. Rodl, Some constructive bounds on Ramsey numbers, J. Comb. Theory B. 100 (2010), 439-445.

8 A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261-277.

9 G. A. Margulis, Arithmetic groups and graphs without short cycles, 6th Internat. Symp. on Information Theory, Tashkent (1984) Abstracts 1, 123-125. (in Russian)

10 G. A. Margulis, Some new constructions of low-density parity check codes, 3rd Internat. Seminar on Information Theory, convolution codes and multi-user communication, Sochi (1987), 275-279. (in Russian)

11 G. A. Margulis, Explicit group theoretic constructions of combinatorial schemes and their applications for the construction of expanders and concentrators, Problemy Peredaci Informacii (1988). (in Russian)

12 Zs. Nagy, A constructive estimation of the Ramsey numbers, Mat. Lapok 23 (1975), 301-302.