The step Sidorenko property and non-norming edge-transitive graphs

DOI10.1016/J.JCTA.2018.09.012zbMATH Open1401.05269DBLPjournals/jct/KralMPW19arXiv1802.05007OpenAlexW2964291645WikidataQ57601308 ScholiaQ57601308MaRDI QIDQ1633367FDOQ1633367

Marcin Wrochna, Péter Pál Pach, Daniel Král', Taísa L. Martins

Publication date: 19 December 2018

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: Sidorenko's Conjecture asserts that every bipartite graph H has the Sidorenko property, i.e., a quasirandom graph minimizes the density of H among all graphs with the same edge density. We study a stronger property, which requires that a quasirandom multipartite graph minimizes the density of H among all graphs with the same edge densities between its parts; this property is called the step Sidorenko property. We show that many bipartite graphs fail to have the step Sidorenko property and use our results to show the existence of a bipartite edge-transitive graph that is not weakly norming; this answers a question of Hatami [Israel J. Math. 175 (2010), 125-150].

Full work available at URL: https://arxiv.org/abs/1802.05007

Recommendations

• Some advances on Sidorenko's conjecture
• Convex graphon parameters and graph norms
• An approximate version of Sidorenko's conjecture
• Sidorenko's conjecture for blow-ups
• Graph norms and Sidorenko's conjecture

zbMATH Keywords

graph limitsSidorenko's conjectureweakly norming graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42)

Cites Work

• Limits of dense graph sequences
• Title not available (Why is that?)
• Non-three-colourable common graphs exist
• Title not available (Why is that?)
• Quasi-random graphs
• On Sets of Acquaintances and Strangers at any Party
• A Holder Type Inequality for Symmetric Matrices with Nonnegative Entries
• A correlation inequality for bipartite graphs
• Title not available (Why is that?)
• Graph norms and Sidorenko's conjecture
• Multiplicities of subgraphs
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• 2-colorings of complete graphs with a small number of monochromatic \(K_ 4\) subgraphs
• An approximate version of Sidorenko's conjecture
• Two approaches to Sidorenko's conjecture
• Some advances on Sidorenko's conjecture
• Ramsey problem on multiplicities of complete subgraphs in nearly quasirandom graphs
• Bipartite subgraphs and quasi-randomness
• Finite reflection groups and graph norms
• On the local approach to Sidorenko's conjecture

Cited In (9)

• On graph norms for complex‐valued functions
• Two remarks on graph norms
• Weakly norming graphs are edge-transitive
• Cut distance identifying graphon parameters over weak* limits
• Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
• Subgraph densities in Markov spaces
• Convex graphon parameters and graph norms
• Relating the cut distance and the weak* topology for graphons
• Lower bounds for integral functionals generated by bipartite graphs

This page was built for publication: The step Sidorenko property and non-norming edge-transitive graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1633367)