Maximising homomorphism counts between digraphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.18847
curl -X POST /api/v1/records/arxiv/2603.18847/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.18847/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'