Tree-Degenerate Graphs and Nested Dependent Random Choice

DOI10.1137/22M1483554MaRDI QIDQ6046815zbMATH OpenOpenAlexFDO

Authors Tao Jiang

Publication date 6 September 2023

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

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

zbMATH Keywords

random choice lemmaSidorenko propertiesTurán nuimber

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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)