Variations on Sidorenko's conjecture in tournaments
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916123426947072 |
|---|---|
| author | Fox, Jacob Himwich, Zoe Mani, Nitya Zhou, Yunkun |
| author_facet | Fox, Jacob Himwich, Zoe Mani, Nitya Zhou, Yunkun |
| contents | We study variants of Sidorenko's conjecture in tournaments, where new phenomena arise that do not have clear analogues in the setting of undirected graphs. We first consider oriented graphs that are systematically under-represented in tournaments (called tournament anti-Sidorenko). We prove that such oriented graphs must be quite sparse; specifically, the maximum number of edges of a $k$-vertex oriented graph which is tournament anti-Sidorenko is $(1+o(1))k\log_2 k$.
We also give several novel constructions of oriented graphs that are systematically over-represented in tournaments (tournament Sidorenko); as a representative example, we show that most ways to delete an edge from a transitive tournament yield a tournament Sidorenko oriented graph. As an illustration of our methods, we characterize which orientations of stars are tournament Sidorenko and which are tournament anti-Sidorenko. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08418 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Variations on Sidorenko's conjecture in tournaments Fox, Jacob Himwich, Zoe Mani, Nitya Zhou, Yunkun Combinatorics We study variants of Sidorenko's conjecture in tournaments, where new phenomena arise that do not have clear analogues in the setting of undirected graphs. We first consider oriented graphs that are systematically under-represented in tournaments (called tournament anti-Sidorenko). We prove that such oriented graphs must be quite sparse; specifically, the maximum number of edges of a $k$-vertex oriented graph which is tournament anti-Sidorenko is $(1+o(1))k\log_2 k$. We also give several novel constructions of oriented graphs that are systematically over-represented in tournaments (tournament Sidorenko); as a representative example, we show that most ways to delete an edge from a transitive tournament yield a tournament Sidorenko oriented graph. As an illustration of our methods, we characterize which orientations of stars are tournament Sidorenko and which are tournament anti-Sidorenko. |
| title | Variations on Sidorenko's conjecture in tournaments |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2402.08418 |