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.