Search

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 have a common neighborhood almost as large as in the random graph of the same edge-density. There are two well-known applications of this lemma. The first is a theorem of F\"uredi [Combinatorica, 11 (1991), pp. 75--79] and Alon, Krivelevich, and Sudakov [Combin. Probab. Comput., 12 (2003), pp. 477--494] 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 [J. Combin. Theory Ser. B, 156 (2022), pp. 299--309] to the family of so-called (r, t)-blowups of a tree. A second application is a theorem of Conlon, Fox, and Sudakov [Geom. Funct. Anal., 20 (2010), pp. 1354--1366], confirming a special case of a conjecture of Erd\H os and Simonovits and of Sidorenko, showing that if H is a bipartite graph that contains a vertex that is completely joined 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 homomorphism is at least.... In this paper, 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. [ABSTRACT FROM AUTHOR]