Directed graphs with lower orientation Ramsey thresholds

arXiv2211.07033MaRDI QIDQ6417107FDOQ6417107

Bruno Pasqualotto Cavalar, Tássio Naia, Gabriel Ferreira Barros, G. O. Mota, Yoshiharu Kohayakawa

Publication date: 13 November 2022

Abstract: We investigate the threshold $p_{vecH}=p_{vecH}(n)$ for the Ramsey-type property $G(n,p)ovecH$, where $G(n,p)$ is the binomial random graph and $GovecH$ indicates that every orientation of the graph $G$ contains the oriented graph $vecH$ as a subdigraph. Similarly to the classical Ramsey setting, the upper bound $p_{vecH}leqC{n}^{-1/m_2(vecH)}$ is known to hold for some constant $C=C(vecH)$, where $m_2(vecH)$ denotes the maximum $2$-density of the underlying graph $H$ of $vecH$. While this upper bound is indeed the threshold for some $vecH$, 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. We also discuss the threshold for oriented trees.

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

This page was built for publication: Directed graphs with lower orientation Ramsey thresholds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6417107)