Directed graphs with lower orientation Ramsey thresholds
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909224850685952 |
|---|---|
| author | Barros, Gabriel Ferreira Cavalar, Bruno Pasqualotto Kohayakawa, Yoshiharu Mota, Guilherme Oliveira Naia, Tássio |
| author_facet | Barros, Gabriel Ferreira Cavalar, Bruno Pasqualotto Kohayakawa, Yoshiharu Mota, Guilherme Oliveira Naia, Tássio |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_07033 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Directed graphs with lower orientation Ramsey thresholds Barros, Gabriel Ferreira Cavalar, Bruno Pasqualotto Kohayakawa, Yoshiharu Mota, Guilherme Oliveira Naia, Tássio Combinatorics 05C80, 05D10, 05C20, 05C55 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. |
| title | Directed graphs with lower orientation Ramsey thresholds |
| topic | Combinatorics 05C80, 05D10, 05C20, 05C55 |
| url | https://arxiv.org/abs/2211.07033 |