Size Ramsey number for graphs of bounded degree
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
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:
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
Friedman and Pippenger [4] extended Pósa's result:
Suppose that in a graph \( G\), any subset \( X\) consisting of at most \( 2n2\) vertices satisfies:
Using the above fact, they showed that
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 linearsized tolerant networks, Discrete Math.
72 (1988), 1520.

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

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

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

5 
P. E. Haxell, Y. Kohayakawa and T. Łuczak, The induced sizeRamsey
number of cycles, Combin. Probab. Comput. 4 (1995), 217239.

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

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