Graphs with asymmetric Ramsey properties

Abstract

Given positive integers $k$ and $\ell$ we write $G\to (K_k,K_{\ell })$ if every 2-colouring of the edges of $G$ yields a red copy of $K_k$ or a blue copy of $K_{\ell }$ and we denote by $R(k)$ the minimum $n$ such that $K_n\to (K_k,K_k)$. By using probabilistic methods and hypergraph containers we prove that for every integer $k\ge 3$, there exists a graph $G$ such that $G\nrightarrow (K_k,K_k)$ and $G\to (K_{R(k)-1},K_{k-1})$. This result can be viewed as a variation of a classical theorem of Nešetřil and Rödl [The Ramsey property for graphs with forbidden complete subgraphs, Journal of Combinatorial Theory, Series B, 20 (1976), 243-249], who proved that for every integer $k\ge 2$ there exists a graph $G$ with no copies of $K_k$ such that $G\to (K_{k-1},K_{k-1})$.