An approximate version of Sidorenko's conjecture
From MaRDI portal
Publication:616156
DOI10.1007/S00039-010-0097-0zbMATH Open1228.05285arXiv1004.4236OpenAlexW2126244044WikidataQ122903458 ScholiaQ122903458MaRDI QIDQ616156FDOQ616156
Authors: Jacob Fox, David Conlon, Benny Sudakov 
Publication date: 7 January 2011
Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)
Abstract: A beautiful conjecture of ErdH{o}s-Simonovits and Sidorenko states that if H is a bipartite graph, then the random graph with edge density p has in expectation asymptotically the minimum number of copies of H over all graphs of the same order and edge density. This conjecture also has an equivalent analytic form and has connections to a broad range of topics, such as matrix theory, Markov chains, graph limits, and quasirandomness. Here we prove the conjecture if H has a vertex complete to the other part, and deduce an approximate version of the conjecture for all H. Furthermore, for a large class of bipartite graphs, we prove a stronger stability result which answers a question of Chung, Graham, and Wilson on quasirandomness for these graphs.
Full work available at URL: https://arxiv.org/abs/1004.4236
Recommendations
Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Inequalities for sums, series and integrals (26D15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)
Cites Work
- Hypergraph regularity and the multidimensional Szemerédi theorem
- Quasi‐random graphs with given degree sequences
- Quasi-random graphs
- Non-averaging subsets and non-vanishing transversals
- The number of cliques in graphs of given order and size
- Weak quasi-randomness for uniform hypergraphs
- Quasirandom Groups
- A new upper bound for diagonal Ramsey numbers
- Pseudo-random graphs
- A Holder Type Inequality for Symmetric Matrices with Nonnegative Entries
- Dependent random choice
- Density theorems for bipartite graphs and related Ramsey-type results
- On the Minimal Density of Triangles in Graphs
- A correlation inequality for bipartite graphs
- Structure and randomness. Pages from year one of a mathematical blog
- Very large graphs
- Quasi-Random Set Systems
- Graph norms and Sidorenko's conjecture
- Multiplicities of subgraphs
- A Disproof of a Conjecture of Erdős in Ramsey Theory
- On the Ramsey multiplicities of graphs—problems and recent results
- There exist graphs with super‐exponential Ramsey multiplicity constant
- Title not available (Why is that?)
- Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture
- Domination between trees and application to an explosion problem
- On the density of a graph and its blowup
- Ramsey problem on multiplicities of complete subgraphs in nearly quasirandom graphs
- Bipartite subgraphs and quasi-randomness
- Title not available (Why is that?)
- A MATRIX INEQUALITY
Cited In (57)
- A Property on Monochromatic Copies of Graphs Containing a Triangle
- Left-cut-percolation and induced-Sidorenko bigraphs
- More non-bipartite forcing pairs
- Extremal numbers and Sidorenko's conjecture
- Toward characterizing locally common graphs
- Domination inequalities and dominating graphs
- On uncommon systems of equations
- Interview with David Conlon
- Extremal results on feedback arc sets in digraphs
- The exact minimum number of triangles in graphs with given order and size
- No additional tournaments are quasirandom-forcing
- On the lower tail variational problem for random graphs
- On replica symmetry of large deviations in random graphs
- On the local approach to Sidorenko's conjecture
- Small dense subgraphs of a graph
- Finite reflection groups and graph norms
- Dependent random choice
- Sidorenko's conjecture for blow-ups
- Approximate Euler characteristic, dimension, and weak pigeonhole principles
- Tropicalization of graph profiles
- Impartial digraphs
- Supersaturation of \(C_4\): from Zarankiewicz towards Erdős-Simonovits-Sidorenko
- 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
- Quasirandom-Forcing Orientations of Cycles
- Tree-Degenerate Graphs and Nested Dependent Random Choice
- The step Sidorenko property and non-norming edge-transitive graphs
- Edges not in any monochromatic copy of a fixed graph
- Approximate versions of Melamed's theorem
- Two approaches to Sidorenko's conjecture
- On tripartite common graphs
- Minimum degree and the graph removal lemma
- Threshold Ramsey multiplicity for odd cycles
- An elementary analog of the operator method in additive combinatorics
- Non-bipartite \(k\)-common graphs
- Convex graphon parameters and graph norms
- Hereditary quasirandomness without regularity
- Unified approach to the generalized Turán problem and supersaturation
- On Sidorenko's conjecture for determinants and Gaussian Markov random fields
- Anti-Ramsey Multiplicities
- Lower bound on the size of a quasirandom forcing set of permutations
- Non-three-colourable common graphs exist
- Extremal results in sparse pseudorandom graphs
- Some advances on Sidorenko's conjecture
- Forcing quasirandomness with triangles
- On the KŁR conjecture in random graphs
- A reverse Sidorenko inequality
- Weak quasi-randomness for uniform hypergraphs
- 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
- Supersaturation problem for color-critical graphs
- Sidorenko's conjecture, colorings and independent sets
- Lower bounds for integral functionals generated by bipartite graphs
- Popular progression differences in vector spaces II
This page was built for publication: An approximate version of Sidorenko's conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616156)
