Convex graphon parameters and graph norms

Joonkyung Lee, Bjarne Schülke

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


Sidorenko’s conjecture states that the number of copies of a bipartite graph H in a graph G is asymptotically minimised when G is a quasirandom graph. A notorious example where this conjecture remains open is when H = K5,5C10. It was even unknown whether this graph possesses the strictly stronger, weakly norming property. We take a step towards understanding the graph K5,5C10 by proving that it is not weakly norming. More generally, we show that ‘twisted’ blow-ups of cycles, which include K5,5C10 and C6☐K2, are not weakly norming. This answers two questions of Hatami. The method relies on the analysis of Hessian matrices defined by graph homomorphisms, by using the equivalence between the (weakly) norming property and convexity of graph homomorphism densities. We also prove that Kt,t minus a perfect matching, proven to be weakly norming by Lovász, is not norming for every t > 3.

Original languageEnglish
Pages (from-to)549-563
Number of pages15
JournalIsrael Journal of Mathematics
Issue number2
Publication statusPublished - 2021 Apr

Bibliographical note

Funding Information:
We would like to thank Sasha Sidorenko for suggesting to prove Theorem 1.6, and Jan Hladký for explaining the result [6] in which he and his colleagues obtained a partial version of Theorem 1.5. We are also grateful to David Conlon, Christian Reiher, and Mathias Schacht for helpful comments and discussions.

Funding Information:
Research supported by ERC Consolidator Grant PEPCo 724903.

Funding Information:
Research supported by G.I.F. Grant Agreements No. I-1358-304.6/2016. Acknowledgements

Publisher Copyright:
© 2021, The Hebrew University of Jerusalem.

All Science Journal Classification (ASJC) codes

  • Mathematics(all)


Dive into the research topics of 'Convex graphon parameters and graph norms'. Together they form a unique fingerprint.

Cite this