Convex graphon parameters and graph norms

Joonkyung Lee, Bjarne Schülke

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume242
Issue number2
DOIs
StatePublished - 2021 Apr
Externally publishedYes

Fingerprint

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

Cite this