Directed graphs with lower orientation Ramsey thresholds

Abstract

We investigate the threshold $p_{\vec{H}}=p_{\vec{H}}(n)$ for the Ramsey-type property $G(n,p)\to \vec{H}$, where $G(n,p)$ is the binomial random graph and $G\to \vec{H}$ indicates that every orientation of the graph $G$ contains the oriented graph $\vec{H}$ as a subdigraph. Similarly to the classical Ramsey setting, the upper bound $p_{\vec{H}}\le C{n}^{-1/m_2(\vec{H})}$ is known to hold for some constant $C=C(\vec{H})$, where $m_2(\vec{H})$ denotes the maximum $2$-density of the underlying graph $H$ of $\vec{H}$. While this upper bound is indeed the threshold for some $\vec{H}$, this is not always the case. We obtain examples arising from rooted products of orientations of sparse graphs (such as forests, cycles and, more generally, subcubic $\{K_3,K_{3,3}\}$-free graphs) and arbitrarily rooted transitive triangles.

12 pages, 1 figure. To appear in RAIRO-Operations Research