Tree-Degenerate Graphs and Nested Dependent Random Choice

DOI10.1137/22M1483554zbMATH Open1520.05054arXiv2201.10699OpenAlexW4385767331MaRDI QIDQ6046815FDOQ6046815

Authors: Tao Jiang 

Publication date: 6 September 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: The celebrated dependent random choice lemma states that in a bipartite graph an average vertex (weighted by its degree) has the property that almost all small subsets $S$ in its neighborhood has common neighborhood almost as large as in the random graph of the same edge-density. Two well-known applications of the lemma are as follows. The first is a theorem of F"uredi and of Alon, Krivelevich, and Sudakov showing that the maximum number of edges in an $n$-vertex graph not containing a fixed bipartite graph with maximum degree at most $r$ on one side is $O(n^{2-1/r})$. This was recently extended by Grzesik, Janzer and Nagy to the family of so-called $(r,t)$-blowups of a tree. A second application is a theorem of Conlon, Fox, and Sudakov, confirming a special case of a conjecture of ErdH{o}s and Simonovits and of Sidorenko, showing that if $H$ is a bipartite graph that contains a vertex complete to the other part and $G$ is a graph then the probability that the uniform random mapping from $V(H)$ to $V(G)$ is a homomorphismis at least $left[frac2|E(G)||V(G){|}^{2}ight{]}^{|E(H)|}$. In this note, we introduce a nested variant of the dependent random choice lemma, which might be of independent interest. We then apply it to obtain a common extension of the theorem of Conlon, Fox, and Sudakov and the theorem of Grzesik, Janzer, and Nagy, regarding Tur'an and Sidorenko properties of so-called tree-degenerate graphs.

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

Recommendations

• The Turán number of blow-ups of trees
• An approximate version of Sidorenko's conjecture
• Dependent random choice
• Some advances on Sidorenko's conjecture
• On the extremal number of subdivisions

zbMATH Keywords

random choice lemmaSidorenko propertiesTurán nuimber

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• The history of degenerate (bipartite) extremal graph problems
• Non-averaging subsets and non-vanishing transversals
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dependent random choice
• A correlation inequality for bipartite graphs
• Title not available (Why is that?)
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
• Graph norms and Sidorenko's conjecture
• An approximate version of Sidorenko's conjecture
• Two approaches to Sidorenko's conjecture
• Some advances on Sidorenko's conjecture
• On a Turán type problem of Erdős
• Inequalities for functionals generated by bipartite graphs
• Small dense subgraphs of a graph
• More on the extremal number of subdivisions
• Sidorenko's conjecture for blow-ups
• Maximum number of almost similar triangles in the plane
• The Turán number of blow-ups of trees
• On the Turán number of the blow-up of the hexagon

Cited In (1)

• Dependent random choice

This page was built for publication: Tree-Degenerate Graphs and Nested Dependent Random Choice

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