Advanced Search

Given a graph H and an integer r ≥ 2, let G → (H,r) denote the Ramsey property of a graph G, that is, every r-coloring of the edges of G results in a monochromatic copy of H. Further, let $m\left(G\right)=ma{x}_{F\subseteq G}\left|E\left(F\right)\right|/\left|V\left(F\right)\right|$ and define the Ramsey density $m_{inf}(H,r)$ as the infimum of m(G) over all graphs G such that G → (H,r). In the first part of this paper we show that when H is a complete graph Kₖ on k vertices, then $m_{inf}(H,r)=(R-1)/2$, where R = R(k;r) is the classical Ramsey number. As a corollary we derive a new proof of the result credited to Chvatál...