Maximising homomorphism counts between digraphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911530339008512 |
|---|---|
| author | Lüchtrath, Lukas Mönch, Christian |
| author_facet | Lüchtrath, Lukas Mönch, Christian |
| contents | We prove a Sidorenko-type inequality for directed trees: for every oriented tree $T$ on $k$ vertices and every finite directed graph $G$, the homomorphism count hom$(T,G)$ is bounded above by the maximum of the two pure star counts hom$(S_{0,k-1},G)$ and hom$(S_{k-1,0},G)$. In other words, among all directed trees on $k$ vertices, the pure in- and out-stars maximise the homomorphism count into host digraphs. The proof is purely combinatorial, based on an iterative leaf-reallocation scheme combined with Hölder's inequality. We further investigate the corresponding homomorphism order on directed trees, discuss refinements via tail-truncation and pointwise bounds for rooted host graphs, and record several consequences, e.g. for random directed graph models and local weak limits, where the inequality reduces tree statistics to controlled pure in- and out-degree moments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_18847 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Maximising homomorphism counts between digraphs Lüchtrath, Lukas Mönch, Christian Combinatorics Probability 05C20, 05C80, 60C05 We prove a Sidorenko-type inequality for directed trees: for every oriented tree $T$ on $k$ vertices and every finite directed graph $G$, the homomorphism count hom$(T,G)$ is bounded above by the maximum of the two pure star counts hom$(S_{0,k-1},G)$ and hom$(S_{k-1,0},G)$. In other words, among all directed trees on $k$ vertices, the pure in- and out-stars maximise the homomorphism count into host digraphs. The proof is purely combinatorial, based on an iterative leaf-reallocation scheme combined with Hölder's inequality. We further investigate the corresponding homomorphism order on directed trees, discuss refinements via tail-truncation and pointwise bounds for rooted host graphs, and record several consequences, e.g. for random directed graph models and local weak limits, where the inequality reduces tree statistics to controlled pure in- and out-degree moments. |
| title | Maximising homomorphism counts between digraphs |
| topic | Combinatorics Probability 05C20, 05C80, 60C05 |
| url | https://arxiv.org/abs/2603.18847 |