Linear Ramsey numbers

For two graphs \( G\) and \( H\), let \( r(G,H)\) denote the smallest integer \( m\) satisfying the property that if the edges of the complete graph \( K_m\) are colored in red and blue, then there is either a subgraph isomorphic to \( G\) with all red edges or a subgraph isomorphic to \( H\) with all blue edges. When \( G=H\), we write \( r(G)=r(G,G)\).

Among the most interesting problems on graph Ramsey theory are the linear bounds for graphs with certain upper bound constraints on the degrees of the vertices. In 1975, Erdös[8] raised the problem of proving \( r(G) \leq c(\Delta)~ n \) for a graph \( G\) on \( n\) vertices with bounded maximum degree \( \Delta\).

This original problem has been settled in the affirmative by Chvátal, Rödl, Szemerédi and Trotter [1]. Their proof is a beautiful illustration of the power of the regularity lemma of Szemerédi.

Roughly speaking, the regularity lemma says that for any graph \( G\), we can partition \( G\) into a relatively small number of parts such that the bipartite graph between most pairs of parts behaves like a random graph. To be specific, a bipartite graph with vertex set \( A \cup B\) is said to be \( \epsilon\)-regular if for any \( X \subset A\) and \( Y \subset B\) with \( \vert X\vert \geq \epsilon \vert A\vert, \vert Y\vert \geq \epsilon \vert B\vert\), the edge density in the induced subgraph \( X \cup Y\) is essentially the same as the edge density in \( A \cup B\) (differs by at most an additive term of \( \epsilon\)). The bounded number of parts depends only on \( \epsilon\) and is independent of the size of \( G\).

The main part of the proof [1] is accomplished by repeatedly using the \( \epsilon\)-regular property to find a desired monochromatic subgraph. (For an excellent survey article on the regularity lemma and its many applications, the reader is referred to Komlós and Simonovits[6]).

As is typical when using the regularity lemma, the constant \( c(\Delta)\) obtained by Chvátal et al.[1] was rather large (more precisely, it had the form of an exponential tower of \( 2\)'s of height \( \Delta\)). More recently, Eaton[3] used a variant of the regularity lemma to show that one can take

\(\displaystyle c(\Delta) < 2^{2^{c \Delta}} \)

for some \( c >0\). Subsequently, Graham, Rödl and Rucínski[4] showed that it is enough to take

\(\displaystyle c(\Delta) < 2^{c \Delta (\log \Delta)^2} \)

for some \( c >0\) and \( \Delta > 1\). They also show that there are graphs \( G\) with \( n\) vertices and maximum degree \( \Delta\) for which \( r(G) \geq c_0^{\Delta} ~n\) for some \( c_0 > 1\) and \( n\) sufficiently large.

Chen and Schelp [2] extended the result by Chvátal et al.[1], replacing the bounded degree condition by the following weaker requirement. A graph is said to be \( c\)-arrangeable if the vertices can be ordered, say, \( v_1, \ldots, v_n\), such that for each \( i\),

\(\displaystyle \vert \{ j : v_i \sim v_k,\)    for \(\displaystyle k > i,\)    and \(\displaystyle v_k \sim v_j\)    for \(\displaystyle j \leq i \} \vert ~ \leq ~ c. \)

Chen and Schelp proved that for a fixed \( c\), the Ramsey number for \( c\)-arrangeable graphs grows linearly with the size of the graph. They showed that a planar graph is \( 761\)-arrangeable, which was later improved to \( 10\)-arrangeable by Kierstead and Trotter[5]. So, their results imply that planar graphs have linear Ramsey numbers.

In 1996, Rödl and Thomas [7], generalizing results in [2], showed that graphs with bounded genus have linear Ramsey numbers. The following three problems are in fact equivalent (subject to different constants).

Conjecture on Ramsey numbers for subgraphs with bounded average degrees (proposed by Burr and Erdös [8])

For every graph \(G\) on \(n\) vertices in which every subgraph has average degree at most \(c\), \[ r(G) \leq c' n, \] where the constant \(c'\) depends only on \(c\).

Conjecture on Ramsey numbers for bounded arboricity (proposed by Burr and Erdös [8])

If a graph \(G\) on \(n\) vertices is the union of \(c\) forests, then \[ r(G) \leq c' n, \] where the constant \(c'\) depends only on \(c\).

Conjecture on Ramsey numbers for graphs with degree constraints (proposed by Burr and Erdös [8])

For every graph \(G\) on \(n\) vertices in which every subgraph has minimum degree at most \(c\), \[ r(G) \leq c' n \] where the constant \(c'\) depends only on \(c\).

Bibliography
1 V. Chvátal, V. Rödl, E. Szemerédi and W. T. Trotter, The Ramsey number of a graph with bounded maximum degree, J. Comb. Theory Ser. B 34 (1983), 239-243.

2 G. Chen and R. H. Schelp, Graphs with linearly bounded Ramsey numbers, J. Comb. Theory Ser. B 57 (1993), 138-149.

3 N. Eaton. Ramsey numbers for sparse graphs, Discrete Math., 185 (1998), 63-75.

4 R. L. Graham, V. Rödl and A. Rucínski, On graphs with linear Ramsey numbers, J. Graph Theory 3 (2000), 176-192. preprint.

5 H. A. Kierstead and W. T. Trotter, Planar graph colorings with an uncooperative partner, J. Graph Theory 18 (1994), 569-584.

6 J. Komlós and M. Simonovits. Szemerédi's regularity lemma and its applications in graph theory, Combinatorics, Paul Erdösis Eighty, Vol. 2, (D. Miklós, V. T. Sós, T. Szönyi, eds.), Bolyai Soc. Math. Studies, 2 (1996), 97-132.

7 V. Rödl and R. Thomas, Arrangeability and clique subDIVisions, The Mathematics of Paul Erdös, II (R. L. Graham and J. Nešetril, eds.), 236-239, Springer-Verlag, Berlin, 1996.

8 S. A. Burr and P. Erdös, On the magnitude of generalized Ramsey numbers for graphs, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdös on his 60th birthday), Vol. I; Colloq. Math. Soc. János Bolyai, Vol. 10, 215-240, North-Holland, Amsterdam, 1975.