论文标题
树脱位图和嵌套依赖的随机选择
Tree-degenerate graphs and nested dependent random choice
论文作者
论文摘要
著名的依赖随机选择Lemma指出，在二分图中，平均顶点（按其程度加权）的属性几乎所有小的子集$ s $在其附近的邻居几乎与相同边缘密度的随机图一样大。引理的两个众所周知的应用如下。第一个是Füredi和Alon，Krivelevich和Sudakov的定理，表明$ n $ vertex Graph中的最大边数不包含一个固定的两部分图，最多最高$ r $在一侧为$ o（n^{2-1/r}）$。 Grzesik，Janzer和Nagy最近将其扩展到了所谓的$（R，T）$ - 一棵树的炸弹。第二个应用程序是Conlon，Fox和Sudakov的定理，证实了一种特殊情况的猜想和Simonovits和Sidorenko的特殊情况，表明，如果$ h $是包含另一个角度的两部分图形，则包含另一个零件的顶点，而$ g $是一个图形，然后是$ v的可能性，至少是$ v（$ v（Hom）$ v（Hom $ v（g）$ v（h） $ \ left [\ frac {2 | e（g）|} {| v（g）|^2} \ right]^{| e（h）|} $。 在本说明中，我们引入了依赖的随机选择引理的嵌套变体，这可能具有独立的兴趣。然后，我们将其应用于Conlon，Fox和Sudakov定理的共同扩展以及Grzesik，Janzer和Nagy的定理，涉及所谓的树脱位图的Turán和Sidorenko特性。
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(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 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 $\left[\frac{2|E(G)|}{|V(G)|^2}\right]^{|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.
