Maximising homomorphism counts between digraphs

Abstract

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.