Orientation Ramsey thresholds for cycles and cliques

Abstract

If $G$ is a graph and $\vec{H}$ is an oriented graph, we write $G\to \vec{H}$ to say that every orientation of the edges of $G$ contains $\vec{H}$ as a subdigraph. We consider the case in which $G=G(n,p)$, the binomial random graph. We determine the threshold $p_{\vec{H}}=p_{\vec{H}}(n)$ for the property $G(n,p)\to \vec{H}$ for the cases in which $\vec{H}$ is an acyclic orientation of a complete graph or of a cycle.

13 pages, 2 figures