# A linear bound on some size Ramsey numbers

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

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

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.