New Sidorenko-type inequalities in tournaments
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908707148791808 |
|---|---|
| author | He, Xiaoyu Mani, Nitya Nie, Jiaxi Tung, Nathan Wei, Fan |
| author_facet | He, Xiaoyu Mani, Nitya Nie, Jiaxi Tung, Nathan Wei, Fan |
| contents | As a directed analog of Sidorenko's conjecture in extremal graph theory, Fox, Himwich, Zhou, and the second author defined an oriented graph $H$ to be tournament Sidorenko (anti-Sidorenko) if the random tournament asymptotically minimizes (maximizes) the number of copies of $H$ among all tournaments. We prove new inequalities of this form for oriented trees and cycles, considering both local and global notions of the Sidorenko property.
We make progress on a conjecture of the aforementioned authors that every tree has an anti-Sidorenko direction, and give a characterization of short paths. For long paths we show that orientations are split symmetrically between being locally Sidorenko and anti-Sidorenko, yet almost all orientations are not globally Sidorenko. Finally, we give algorithms characterizing the local Sidorenko status of paths and cycles when the number of vertices is not divisible by four. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_11222 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New Sidorenko-type inequalities in tournaments He, Xiaoyu Mani, Nitya Nie, Jiaxi Tung, Nathan Wei, Fan Combinatorics As a directed analog of Sidorenko's conjecture in extremal graph theory, Fox, Himwich, Zhou, and the second author defined an oriented graph $H$ to be tournament Sidorenko (anti-Sidorenko) if the random tournament asymptotically minimizes (maximizes) the number of copies of $H$ among all tournaments. We prove new inequalities of this form for oriented trees and cycles, considering both local and global notions of the Sidorenko property. We make progress on a conjecture of the aforementioned authors that every tree has an anti-Sidorenko direction, and give a characterization of short paths. For long paths we show that orientations are split symmetrically between being locally Sidorenko and anti-Sidorenko, yet almost all orientations are not globally Sidorenko. Finally, we give algorithms characterizing the local Sidorenko status of paths and cycles when the number of vertices is not divisible by four. |
| title | New Sidorenko-type inequalities in tournaments |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.11222 |