2022/01/26 by Tao Jiang, Sean Longbrake, Jiang, Tao +1 · 1 citation
Computer Science · Mathematics · #05 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2201.10699
openalex publication_date 2022/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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üredi 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(n2-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 Erdő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 [(2|E(G)|)/(|V(G)|2)]|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án and Sidorenko properties of so-called tree-degenerate graphs.