Consecutive Ramsey numbers

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.