A linear bound on some size Ramsey numbers

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

The following problem is due to Erdös, Faudree, Rousseau and Schelp [2], [1].

A Ramsey size linear problem (proposed by Erdös, Faudree, Rousseau and Schelp [1])

Suppose a graph \(G\) satisfies the property that every subgraph of \(G\) on \(p\) vertices has at most \(2p-3\) edges. Is it true that, for any graph \(H\) on \(n\) edges, \begin{equation} r(G,H) \leq cn? \end{equation}

In [1], it was shown that for a graph \( G\) with \( p\) vertices and \( q\) edges, we have

\(\displaystyle r(G,K_n) > c (n / \log n)^{(q-1)/(p-2)} \)

for \( n \) sufficiently large.

This implies that for a graph \( G\) with \( p\) vertices and \( 2p-2\) edges, the inequality (1) does not hold for all \( H\) with \( n \) edges.

In the other direction, in [1] it was shown that for any graph \( G\) with \( p\) vertices and at most \( p+1\) edges, (1) holds.

Bibliography
1 P. Erdös, R. Faudree, C. C. Rousseau and R. H. Schelp, Ramsey size linear graphs, Combin. Probab. Comput. 2 (1993), 389-399.

2 S. A. Burr, P. Erdös, R. J. Faudree, C. C. Rousseau and R. H. Schelp, Ramsey-minimal graphs for multiple copies, Nederl. Akad. Wetensch. Indag. Math. 40 (1978), 187-195.