论文标题
跨越稀疏扩展器的树木
Spanning trees in sparse expanders
论文作者
论文摘要
给定整数$ n \geδ\ ge 2 $，令$ \ nrecal {t}（n，δ）$是所有$ n $ vertex树的集合，最多最高$δ$。 Alon，Krivelevich和Sudakov在2007年的一个问题要求确定最佳的光谱间隙条件，迫使$（n，d，λ）$ - 图为$ \ MATHCAL {t}（t}（n，δ）$ - 通用，不，即，它包含$ \ Mathcal {t}（t}（n，δ）$的所有成员。在本文中，我们表明，对于足够大的整数$ n $，以及所有$δ\ in \ mathbb {n} $，每个$（n，d，λ）$ - 带有\ [λ\ le \ frac {d} {2Δ^^2Δ^^^^^^^^{5 \ sqrt {5 \ sqrt {\ sqrt {\ n}}} δ）$ - 通用。作为直接的推论，这意味着阿隆巧妙地构建了三角形的无稀疏扩展器是$ \ Mathcal {t}（n，δ）$ - 通用，它提供了此类图的明确结构，因此解决了约翰逊，克里维尔维奇和samotij的问题。我们的主要结果是在更加一般的环境下制定的，即$（n，d）$ - 扩展器。更确切地说，我们表明存在绝对常数$ c，c> 0 $，因此以下语句适用于足够大的整数$ n $。 （1）。对于所有$δ\ in \ mathbb {n} $，每个$（n，δ^{5 \ sqrt {\ log n}}）$ - Expander是$ \ MATHCAL {t}（t}（n，δ）$ - unidence。 （2）。对于所有$δ\ in \ m athbb {n} $，带有$δ\ le c \ sqrt {n} $，每个$（n，cΔn^{1/2}）$ - expander是$ \ mathcal {t}（t}（t}（n，δ）$ - universal。 这两种结果都显着改善了约翰逊，克里维尔维奇和萨姆托吉的结果，并对本地稀疏的扩张器和破坏者游戏产生了进一步的影响，这些游戏也大大改善了以前已知的结果。
Given integers $n\ge Δ\ge 2$, let $\mathcal{T}(n, Δ)$ be the collection of all $n$-vertex trees with maximum degree at most $Δ$. A question of Alon, Krivelevich and Sudakov in 2007 asks for determining the best possible spectral gap condition forcing an $(n, d,λ)$-graph to be $\mathcal{T}(n, Δ)$-universal, namely, it contains all members of $\mathcal{T}(n, Δ)$ as a subgraph simultaneously. In this paper we show that for sufficiently large integer $n$ and all $Δ\in \mathbb{N}$, every $(n, d,λ)$-graph with \[ λ\le\frac{d}{2Δ^{5\sqrt{\log n}}} \] is $\mathcal{T}(n, Δ)$-universal. As an immediate corollary, this implies that Alon's ingenious construction of triangle-free sparse expander is $\mathcal{T}(n, Δ)$-universal, which provides an explicit construction of such graphs and thus solves a question of Johannsen, Krivelevich and Samotij. Our main result is formulated under a much more general context, namely, the $(n,d)$-expanders. More precisely, we show that there exist absolute constants $C,c>0$ such that the following statement holds for sufficiently large integer $n$. (1).For all $Δ\in \mathbb{N}$, every $(n, Δ^{5\sqrt{\log n}})$-expander is $\mathcal{T}(n, Δ)$-universal. (2).For all $Δ\in \mathbb{N}$ with $Δ\le c\sqrt{n}$, every $(n, CΔn^{1/2})$-expander is $\mathcal{T}(n, Δ)$-universal. Both results significantly improve a result of Johannsen, Krivelevich and Samotij, and have further implications in locally sparse expanders and Maker-Breaker games that also improve previously known results drastically.
