A very short proof of Sidorenko's inequality for counts of homomorphisms between graphs
Loading...
Date issued
Authors
Editors
Journal Title
Journal ISSN
Volume Title
Publisher
Reuse License
Abstract
A fundamental extremality result due to Sidorenko [‘A partially ordered set of functionals corresponding to graphs’, Discrete Math. 131(1–3) (1994), 263–277] states that among all connected graphs G on k vertices, the k-vertex star maximises the number of graph homomorphisms of G into any graph H. We provide a new short proof of this result using only a simple recursive counting argument for trees and Hölder’s inequality.
Description
Keywords
Citation
Published in
Bulletin of the Australian Mathematical Society, 113, 1, Cambridge University Press, London, 2025, https://doi.org/10.1017/S000497272500019X