1. Upper bounds on probability thresholds for asymmetric Ramsey properties
- Author
-
Kohayakawa, Yoshiharu, Schacht, Mathias, and Spöhel, Reto
- Subjects
Mathematics - Combinatorics ,05C80, 05C55 - Abstract
Given two graphs $G$ and $H$, we investigate for which functions $p=p(n)$ the random graph $G_{n,p}$ (the binomial random graph on $n$ vertices with edge probability $p$) satisfies with probability $1-o(1)$ that every red-blue-coloring of its edges contains a red copy of $G$ or a blue copy of $H$. We prove a general upper bound on the threshold for this property under the assumption that the denser of the two graphs satisfies a certain balancedness condition. Our result partially confirms a conjecture by the first author and Kreuter, and together with earlier lower bound results establishes the exact order of magnitude of the threshold for the case in which $G$ and $H$ are complete graphs of arbitrary size. In our proof we present an alternative to the so-called deletion method, which was introduced by R\"odl and Ruci\'{n}ski in their study of symmetric Ramsey properties of random graphs (i.e. the case $G=H$), and has been used in many proofs of similar results since then.
- Published
- 2016
- Full Text
- View/download PDF