Back to Search
Start Over
TREE-DEGENERATE GRAPHS AND NESTED DEPENDENT RANDOM CHOICE.
- Source :
-
SIAM Journal on Discrete Mathematics . 2023, Vol. 37 Issue 3, p1805-1817. 13p. - Publication Year :
- 2023
-
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 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]
- Subjects :
- *BIPARTITE graphs
*RANDOM graphs
*HOMOMORPHISMS
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 37
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 173328545
- Full Text :
- https://doi.org/10.1137/22M1483554