Directed graphs with lower orientation Ramsey thresholds

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 c...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-06
Main Authors: Gabriel Ferreira Barros, Bruno Pasqualotto Cavalar, Kohayakawa, Yoshiharu, Guilherme Oliveira Mota, Naia, Tássio
Format: Article
Language:English
Subjects:
Graph theory
Graphs
Polytrees
Trees (mathematics)
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422