A question about Ramsey type statements

101 Views Asked by At

Suppose we ask for the minimum $R(H)$ s.t every $2-$coloring of the complete graph $K_{R(H)}$ must contain a monochromatic copy of $H$. It is known that $R(H)$ is finite for all $H$. What can be said about $R(H)$ as a function of $H$. Meaning, what types of graphs yield a lower/higher Ramsey number?

Intuitively it seems, for example, that if the number of edges $m = \Theta(n)$ for some class of graphs $H_n$, then $R(H_n)\leq R(K_n)$. This might be wildly wrong though.

Sorry if this is a bit qualitative but any ideas/known results in this general direction would be of help.

1

There are 1 best solutions below

0
On

Adding to the answer above, I want to explain why $K_n$ gives the highest Ramsey number of all graphs on $n$ vertices. I'll use $R(n)$ to denote $R(K_n)$.

As you stated, Ramsey guaranties that every 2 coloring of $K_{R(n)}$ contains a monochromatic $K_n$. So in particular, since $G$ is a subgraph of $K_n$, every 2-coloring of $K_{R(n)}$ contains a monochromatic G.

So for every graph $G$ such that $V(G)=n$, it follows that $R(G)\le R(n)$.