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

DOI10.1016/J.JCTA.2018.09.012MaRDI QIDQ1633367zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 19 December 2018

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

Full work available at URL https://arxiv.org/abs/1802.05007, http://wrap.warwick.ac.uk/108614/7/WRAP-step-Sidorenko-property-non-norming-edge-graphs-Kral-2018.pdf

zbMATH Keywords

graph limitsSidorenko's conjectureweakly norming graphs

Mathematics Subject Classification ID

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

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

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

Cites work

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

Cited in

(10)

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

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)