Hostname: page-component-669899f699-2mbcq Total loading time: 0 Render date: 2025-04-25T20:08:57.518Z Has data issue: false hasContentIssue false
  • English
  • Français

A VERY SHORT PROOF OF SIDORENKO’S INEQUALITY FOR COUNTS OF HOMOMORPHISMS BETWEEN GRAPHS

Part of: Combinatorial probability Graph theory

Published online by Cambridge University Press:  14 April 2025

LUKAS LÜCHTRATH Open the ORCID record for LUKAS LÜCHTRATH [Opens in a new window]  and
CHRISTIAN MÖNCH Open the ORCID record for CHRISTIAN MÖNCH [Opens in a new window]
LUKAS LÜCHTRATH
Affiliation:
Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstr. 39, 10117 Berlin, Germany e-mail: [email protected]
CHRISTIAN MÖNCH*
Affiliation:
Johannes Gutenberg–Universität Mainz, Staudingerweg 9, 55128 Mainz, Germany
*
e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

Sidorenko’s inequalitygraph homomorphismpartial order

MSC classification

Primary: 05C35: Extremal problems
Secondary: 60C05: Combinatorial probability
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , First View , pp. 1 - 5
Check for updates
Copyright
© The Author(s), 2025. Published by Cambridge University Press on behalf of Australian Mathematical Publishing Association Inc

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

Footnotes

The first author received support from the Leibniz Association within the Leibniz Junior Research Group on Probabilistic Methods for Dynamic Communication Networks as part of the Leibniz Competition, grant no. J105/2020. The second author’s research is funded by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), grant no. SPP 2265 443916008.

References

Csikvári, P. and Lin, Z., ‘Graph homomorphisms between trees’, Electron. J. Combin. 21(4) (2014), Article no. 4.9, 38 pages.CrossRefGoogle Scholar
Gopalan, P., Servedio, R. A. and Wigderson, A., ‘Degree and sensitivity: tails of two distributions’, in: 31st Conference on Computational Complexity, Leibniz International Proceedings in Informatics, 50 (ed. Raz, R.) (Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016), Article no. 13, 23 pages.Google Scholar
Hoffman, A. J., ‘Three observations on nonnegative matrices’, J. Res. Nat. Bur. Standards Sect. B 71B (1967), 39–41.CrossRefGoogle Scholar
Kurauskas, V., ‘On local weak limit and subgraph counts for sparse random graphs’, J. Appl. Probab. 59(3) (2022), 755–776.CrossRefGoogle Scholar
Levin, D. A. and Peres, Y., ‘Counting walks and graph homomorphisms via Markov chains and importance sampling’, Amer. Math. Monthly 124(7) (2017), 637–641.CrossRefGoogle Scholar
Sidorenko, A., ‘A partially ordered set of functionals corresponding to graphs’, Discrete Math. 131(1–3) (1994), 263–277.CrossRefGoogle Scholar