WIAS Preprint No. 3120, (2024)

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


Authors

  • Lüchtrath, Lukas
    ORCID: 0000-0003-4969-806X
  • Mönch, Christian

2020 Mathematics Subject Classification

  • 05C35 60C05

Keywords

  • Sidorenko's inequality, graph homomorphism

DOI

10.20347/WIAS.PREPRINT.3120

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 graphs G on k vertices, the k-1-edge star maximises the number of graph homomorphisms of G into any graph H.

Appeared in

Download Documents