Sidorenko's conjecture for blow-ups

DOI10.19086/DA.21472zbMATH Open1473.05141arXiv1809.01259OpenAlexW3141567130MaRDI QIDQ3382237

David Conlon, Joonkyung Lee

Publication date: 20 September 2021

Published in: discrete Analysis (Search for Journal in Brave)

Abstract: A celebrated conjecture of Sidorenko and ErdH{o}s-Simonovits states that, for all bipartite graphs $H$, quasirandom graphs contain asymptotically the minimum number of copies of $H$ taken over all graphs with the same order and edge density. This conjecture has attracted considerable interest over the last decade and is now known to hold for a broad range of bipartite graphs, with the overall trend saying that a graph satisfies the conjecture if it can be built from simple building blocks such as trees in a certain recursive fashion. Our contribution here, which goes beyond this paradigm, is to show that the conjecture holds for any bipartite graph $H$ with bipartition $AcupB$ where the number of vertices in $B$ of degree $k$ satisfies a certain divisibility condition for each $k$. As a corollary, we have that for every bipartite graph $H$ with bipartition $AcupB$, there is a positive integer $p$ such that the blow-up $H_A^p$ formed by taking $p$ vertex-disjoint copies of $H$ and gluing all copies of $A$ along corresponding vertices satisfies the conjecture. Another way of viewing this latter result is that for every bipartite $H$ there is a positive integer $p$ such that an $L^p$-version of Sidorenko's conjecture holds for $H$.

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

zbMATH Keywords

Sidorenko's conjecturegraph homomorphism inequalities

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• The clique density theorem
• An approximate version of Sidorenko's conjecture
• Supersaturated graphs and hypergraphs
• Finite reflection groups and graph norms
• A correlation inequality for bipartite graphs
• Two approaches to Sidorenko’s conjecture
• Dependent random choice
• The number of cliques in graphs of given order and size
• On the Minimal Density of Triangles in Graphs
• Some advances on Sidorenko's conjecture
• FROM GRAPH LIMITS TO HIGHER ORDER FOURIER ANALYSIS
• Flag algebras
• Graph norms and Sidorenko's conjecture

Related Items (23)

Cut distance identifying graphon parameters over weak* limits ⋮ On tripartite common graphs ⋮ Threshold Ramsey multiplicity for odd cycles ⋮ Non-bipartite \(k\)-common graphs ⋮ A path forward: tropicalization in extremal combinatorics ⋮ Impartial digraphs ⋮ Locally common graphs ⋮ Tree-Degenerate Graphs and Nested Dependent Random Choice ⋮ On some graph densities in locally dense graphs ⋮ Toward characterizing locally common graphs ⋮ Rouquier dimension of some blow-ups ⋮ Extremal results on feedback arc sets in digraphs ⋮ A Property on Monochromatic Copies of Graphs Containing a Triangle ⋮ Common graphs with arbitrary connectivity and chromatic number ⋮ Paths of given length in tournaments ⋮ Extended commonality of paths and cycles via Schur convexity ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Simple graph density inequalities with no sum of squares proofs ⋮ On uncommon systems of equations ⋮ Domination inequalities and dominating graphs ⋮ Interview with David Conlon ⋮ Threshold Ramsey multiplicity for paths and even cycles ⋮ Two remarks on graph norms

This page was built for publication: Sidorenko's conjecture for blow-ups