Size Ramsey number for graphs of bounded degree

The size Ramsey number \( \hat{r}(G,H)\) is the least integer \( m\) for which there exists a graph \( F\) with \( m\) edges so that in any coloring of the edges of \( F\) in red and blue, there is always either a red copy of \( G\) or a blue copy of \( H\). Sometimes we write \( F \rightarrow (G,H)\) to denote this. For \( G=H\), we denote \( \hat{r}(G,G)\) by \( \hat{r}(G)\).

A size Ramsey problem for bounded degree graphs(proposed by Beck and Erdös [6])

For a graph \(G\) on \(n\) vertices with bounded degree \(d\) , prove that \[ \hat{r}(G) \leq c n \] where \(c\) depends only on \(d\).

The case for paths was proved by Beck [2] (see also [6]) by using the following very nice result of Pósa [7]: Suppose that in a graph \( G\), any subset \( X\) of the vertex set of size at most \( n\) satisfies:

\(\displaystyle \vert \{ y \not \in X : y \sim x \in X \} \vert \geq 2 \vert X\vert -1. \)

Then \( G\) contains a path with \( 3n-2\) vertices.

Based on this result, Alon and Chung [1] explicitly construct a graph with \( cn\) edges so that no matter how we delete all but an \( \epsilon\)-fraction of the vertices or edges, the remaining graph still contains a path of length \( n\).

We point out that a directed version of this problem was considered by Erdös, Graham and Szemerédi[3] in 1975. Let \( g(n)\) denote the least integer such that there is a directed acyclic graph \( G\) with \( g(n)\) edges having the property that for any set \( X\) of \( n\) vertices of \( G\), there is a directed path on \( G\) of length \( n\) which does not hit \( X\). Then they show

\(\displaystyle c_1 \frac{n \log n}{\log \log n} < g(n) < c_2 n \log n \)

for constants \( c_1, c_2 > 0\).

Friedman and Pippenger [4] extended Pósa's result:

Suppose that in a graph \( G\), any subset \( X\) consisting of at most \( 2n-2\) vertices satisfies:

\(\displaystyle \vert \{ y \not \in X : y \sim x \in X \} \vert \geq (d+1) \vert X\vert. \)

Then \( G\) contains every tree with \( n\) vertices and maximum degree at most \( d\).

Using the above fact, they showed that

\(\displaystyle \hat{r}(T) \leq c n \)

for any tree with \( n\) vertices and bounded maximum degree.

Haxell, Kohayakawa, and Łuczak [5] proved that the size Ramsey number for \( C_n\) has a linear upper bound.

Bibliography
1 N. Alon and F. R. K. Chung, Explicit constructions of linear-sized tolerant networks, Discrete Math. 72 (1988), 15-20.

2 J. Beck, On size Ramsey number of paths, trees, and circuits, I, J. Graph Theory 7 (1983), 115-129.

3 P. Erdös, R. L. Graham and E. Szemerédi. On sparse graphs with dense long paths, Computers and mathematics with applications, pp. 365-369, Pergamon, Oxford, 1976

4 J. Friedman and N. Pippenger, Expanding graphs contain all small trees, Combinatorica 7 (1987), 71-76.

5 P. E. Haxell, Y. Kohayakawa and T. Łuczak, The induced size-Ramsey number of cycles, Combin. Probab. Comput. 4 (1995), 217-239.

6 J. Nešetril and V. Rödl, eds., Mathematics of Ramsey Theory, Springer-Verlag, Berlin, 1990.

7 L. Pósa, Hamiltonian circuits in random graphs, Discrete Math. 14 (1976), 359-364.