The size Ramsey number (Q1227754): Difference between revisions

Let \({\mathcal C}\) be the class of all graphs \(G\) which satisfy \(G \to (G_1,G_2)\). As a way of measuring minimality for members of \({\mathcal C}\), we define the size Ramsey number \(\hat r(G_1,G_2)\) by \(\hat r(G_1,G_2)= \min_{G \in {\mathcal C}} |E(G)|\). As usual, \(\hat r(G)\) signifies \(\hat r(G,G)\). For comparison purposes, we let \(\hat R(G_1,G_2) := \binom{r(G_1,G_2)}{2}\), where \(r(G_1,G_2)\) denotes the standard Ramsey number. It is clear that \(\hat r(G_1,G_2) \leq \hat R(G_1,G_2)\) and we note in the paper that for all \(m,n\), \(\hat r(K_m,K_n) = \hat R(K_m,K_n)\). On the other hand, \(\hat r\) can be much less than \(\hat R\), a notion made precise by the following definition. An infinite sequence of graphs \(\{G_n\}\) is said to be an \(o\)-sequence if \(\hat r(G_n) = o(\hat R(G)n))\) \((n \to \infty)\). We prove several theorems related to the \(o\)-sequence concept. For example, we prove that if \(m\) is fixed, then \(\{K_{m,n}\}\) is an \(o\)-sequence. In the course of this work, we find some new results for standard Ramsey numbers. For example, letting \(K_m * \bar K_n\) denote the graph obtained from \(K_m\) by making one of its vertices adjacent to \(n\) additional vertices, we prove that if \(m\) is fixed and \(n\) is sufficiently large, then \(r(K_m * \bar K_n) = (m-1)(m+n-1)+1\).