# Consecutive Ramsey numbers

Search

Subjects

- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)

About Erdös

About This Site

**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,

#### 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
*

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

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 \).