Some advances on Sidorenko's conjecture

DOI10.1112/JLMS.12142MaRDI QIDQ4646248zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

bipartite graphhomomorphismsSidorenko property

Mathematics Subject Classification ID

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

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.

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

Cited in

(42)

• The exact minimum number of triangles in graphs with given order and size
• On the local approach to Sidorenko's conjecture
• Finite reflection groups and graph norms
• A Property on Monochromatic Copies of Graphs Containing a Triangle
• Sidorenko's conjecture for blow-ups
• Some progress on the Aharoni-Korman conjecture
• Graph norms and Sidorenko's conjecture
• Impartial digraphs
• Inequalities for doubly nonnegative functions
• Tropicalization of graph profiles
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Cut distance identifying graphon parameters over weak* limits
• On some graph densities in locally dense graphs
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• A path forward: tropicalization in extremal combinatorics
• The step Sidorenko property and non-norming edge-transitive graphs
• Off-diagonal commonality of graphs via entropy
• Tree-Degenerate Graphs and Nested Dependent Random Choice
• The Turán number of blow-ups of trees
• Left-cut-percolation and induced-Sidorenko bigraphs
• 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
• An approximate version of Sidorenko's conjecture
• On the extremal number of subdivisions
• Domination inequalities and dominating graphs
• A reverse Sidorenko inequality
• Forcing quasirandomness with triangles
• 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
• Sidorenko's conjecture, colorings and independent sets
• Paths of given length in tournaments
• 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)