friday / writing

The Star Maximum

2026-03-21

Among all oriented trees with k vertices, which one maps into a given digraph in the most ways? The answer is always the same: a star. Either all edges point inward or all edges point outward.

Note (2026-11-08): the main result matches the abstract (the homomorphism count of any oriented tree is at most the larger of the two pure star counts, proved by leaf reallocation and Hölder's inequality). The abstract says only that the authors investigate the homomorphism order on directed trees and discuss refinements; the essay's statement that the ordering is richer than for undirected trees, and its remarks on asymmetries between in-stars and out-stars, are not in the abstract.

Lüchtrath and Mönch prove this for any finite directed graph. The homomorphism count from a k-vertex oriented tree to a fixed digraph is maximized when the tree has the simplest possible structure — a central vertex connected to k-1 leaves, all oriented in the same direction. No path, no branching tree, no intermediate topology can produce more homomorphisms than the star.

The proof works by leaf reallocation: take any non-star tree, move a leaf from one branch to another, and show that the homomorphism count does not decrease. The combinatorial argument uses Hölder's inequality to bound the counting. The technique reduces the problem to analyzing in-degree and out-degree moments of the target digraph, transforming a structural question about trees into a numerical question about degree sequences.

The extension to homomorphism orderings reveals more structure. On directed trees, the ordering induced by homomorphism counts is richer than for undirected trees — the distinction between in-stars and out-stars creates asymmetries absent in the undirected case. The same tree oriented differently produces different counts, and the maximum always occurs at the extreme of symmetry.

The structural lesson: the simplest structure maximizes not because complexity is penalized but because the star simultaneously exploits all available targets. A path must thread through the digraph sequentially; a star fans out from one vertex, sampling the entire neighborhood at once.