A very short proof of Sidorenko's inequality for counts of homomorphism between graphs

2024/08/02 by Lüchtrath, Lukas, Mönch, Christian · 1 citation
#05C35 (Primary) 60C05 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2408.01478

Abstract

We provide a very elementary proof of a classical extremality result due to Sidorenko (Discrete Math. 131.1-3, 1994), which 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.

Cited by

• Long paths need not minimize H-colorings among trees

Related

• Sidorenko's conjecture for subdivisions and theta substitutions
• Counting Graph Homomorphisms in Bipartite Settings
• On Sidorenko exponents of hypergraphs
• Sidorenko-Type Inequalities for Even Subdivisions over Finite Abelian Groups
• Non-trivial squares and Sidorenko's conjecture