Convex graphon parameters and graph norms

Joonkyung Lee; Bjarne Schülke

doi:10.1007/s11856-021-2112-6

Convex graphon parameters and graph norms

Joonkyung Lee, Bjarne Schülke

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

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 = K_5,5C₁₀. It was even unknown whether this graph possesses the strictly stronger, weakly norming property. We take a step towards understanding the graph K_5,5C₁₀ by proving that it is not weakly norming. More generally, we show that ‘twisted’ blow-ups of cycles, which include K_5,5C₁₀ and C₆☐K₂, 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 K_t,t minus a perfect matching, proven to be weakly norming by Lovász, is not norming for every t > 3.

Original language	English
Pages (from-to)	549-563
Number of pages	15
Journal	Israel Journal of Mathematics
Volume	242
Issue number	2
DOIs	https://doi.org/10.1007/s11856-021-2112-6
Publication status	Published - 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)

Access to Document

10.1007/s11856-021-2112-6

Cite this

@article{d4534d3a4e394164924ebd42f4ee027b,

title = "Convex graphon parameters and graph norms",

abstract = "Sidorenko{\textquoteright}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 {\textquoteleft}twisted{\textquoteright} 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{\'a}sz, is not norming for every t > 3.",

author = "Joonkyung Lee and Bjarne Sch{\"u}lke",

note = "Funding Information: We would like to thank Sasha Sidorenko for suggesting to prove Theorem 1.6, and Jan Hladk{\'y} 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: {\textcopyright} 2021, The Hebrew University of Jerusalem.",

year = "2021",

month = apr,

doi = "10.1007/s11856-021-2112-6",

language = "English",

volume = "242",

pages = "549--563",

journal = "Israel Journal of Mathematics",

issn = "0021-2172",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Convex graphon parameters and graph norms

AU - Lee, Joonkyung

AU - Schülke, Bjarne

N1 - 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.

PY - 2021/4

Y1 - 2021/4

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85102308478&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85102308478&partnerID=8YFLogxK

U2 - 10.1007/s11856-021-2112-6

DO - 10.1007/s11856-021-2112-6

M3 - Article

AN - SCOPUS:85102308478

SN - 0021-2172

VL - 242

SP - 549

EP - 563

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

IS - 2

ER -

Convex graphon parameters and graph norms

Abstract

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this