Ramsey-type problems in orientations of graphs

Abstract

Given an acyclic oriented graph $\vec{H}$ and a graph $G$, we write $G\to \vec{H}$ if every orientation of $G$ has an oriented copy of $\vec{H}$. We define $\vec{R}(\vec{H})$ as the smallest number $n$ such that there exists a graph $G$ satisfying $G\to \vec{H}$. Denoting by $R(H)$ the classical Ramsey number of a graph $H$, we show that $\vec{R}(\vec{H})\le 2R(H{)}^{c{\log }^{2}h}$ for every acyclic oriented graph $\vec{H}$ with $h$ vertices, where $H$ is its underlying undirected graph. We also study the threshold function for the event $\{G(n,p)\to \vec{H}\}$ in the binomial random graph $G(n,p)$. Finally, we consider the isometric case, in which we require that, for every two vertices $x,y\in V(\vec{H})$ and their respective copies $x^{\prime },y^{\prime }$ in $\vec{G}$, the distance between $x$ and $y$ is equal to the distance between $x^{\prime }$ and $y^{\prime }$. We prove an upper bound for the isometric Ramsey number of an acyclic orientation of the cycle, applying the hypergraph container lemma in random graphs.