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