Some advances on Sidorenko's conjecture

DOI10.1112/JLMS.12142zbMATH Open1433.05166arXiv1510.06533OpenAlexW3125560146WikidataQ122958699 ScholiaQ122958699MaRDI QIDQ4646248FDOQ4646248

Authors: David Conlon, Jeong Han Kim, Choongbum Lee, Joonkyung Lee 

Publication date: 11 January 2019

Published in: Journal of the London Mathematical Society (Search for Journal in Brave)

Abstract: A bipartite graph $H$ is said to have Sidorenko's property if the probability that the uniform random mapping from $V(H)$ to the vertex set of any graph $G$ is a homomorphism is at least the product over all edges in $H$ of the probability that the edge is mapped to an edge of $G$. In this paper, we provide three distinct families of bipartite graphs that have Sidorenko's property. First, using branching random walks, we develop an embedding algorithm which allows us to prove that bipartite graphs admitting a certain type of tree decomposition have Sidorenko's property. Second, we use the concept of locally dense graphs to prove that subdivisions of certain graphs, including cliques, have Sidorenko's property. Third, we prove that if $H$ has Sidorenko's property, then the Cartesian product of $H$ with an even cycle also has Sidorenko's property.

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

Recommendations

• Two approaches to Sidorenko's conjecture
• Sidorenko's conjecture for blow-ups
• Sidorenko's conjecture, colorings and independent sets
• An approximate version of Sidorenko's conjecture
• On the local approach to Sidorenko's conjecture

zbMATH Keywords

bipartite graphhomomorphismsSidorenko property

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Cited In (42)

• The exact minimum number of triangles in graphs with given order and size
• On the local approach to Sidorenko's conjecture
• A Property on Monochromatic Copies of Graphs Containing a Triangle
• Finite reflection groups and graph norms
• Sidorenko's conjecture for blow-ups
• Graph norms and Sidorenko's conjecture
• Some progress on the Aharoni-Korman conjecture
• Tropicalization of graph profiles
• Impartial digraphs
• Inequalities for doubly nonnegative functions
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• On some graph densities in locally dense graphs
• Cut distance identifying graphon parameters over weak* limits
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• A path forward: tropicalization in extremal combinatorics
• Off-diagonal commonality of graphs via entropy
• Tree-Degenerate Graphs and Nested Dependent Random Choice
• The step Sidorenko property and non-norming edge-transitive graphs
• Left-cut-percolation and induced-Sidorenko bigraphs
• The Turán number of blow-ups of trees
• Two approaches to Sidorenko's conjecture
• Threshold Ramsey multiplicity for odd cycles
• Non-bipartite \(k\)-common graphs
• Convex graphon parameters and graph norms
• Extremal numbers and Sidorenko's conjecture
• Hereditary quasirandomness without regularity
• Toward characterizing locally common graphs
• Locally common graphs
• On the extremal number of subdivisions
• An approximate version of Sidorenko's conjecture
• Domination inequalities and dominating graphs
• Forcing quasirandomness with triangles
• A reverse Sidorenko inequality
• On uncommon systems of equations
• Interview with David Conlon
• Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting)
• Threshold Ramsey multiplicity for paths and even cycles
• Paths of given length in tournaments
• Sidorenko's conjecture, colorings and independent sets
• Lower bounds for integral functionals generated by bipartite graphs
• Extremal results on feedback arc sets in digraphs
• Popular progression differences in vector spaces II

This page was built for publication: Some advances on Sidorenko's conjecture

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