The reviewed record of science sign in
Pith

arxiv: 2211.07033 · v2 · pith:TYDOZZIO · submitted 2022-11-13 · math.CO

Directed graphs with lower orientation Ramsey thresholds

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:TYDOZZIOrecord.jsonopen to challenge →

classification math.CO
keywords graphgraphsboundorientationramseyrootedsomethreshold
0
0 comments X
read the original 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}\leq Cn^{-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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.