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