论文标题
高湾近拉马尼亚图，有损耗的顶点扩展
High-girth near-Ramanujan graphs with lossy vertex expansion
论文作者
论文摘要
Kahale证明了$ D $ -D $ RAMANUJAN图中的线性尺寸集具有顶点膨胀$ \ sim \ frac {d} {2} {2} $，并通过构造了近ramanujan图形的构造，即近ramanujan图形，其顶点扩展不得超过$ \ frac {d} {d} {2} {2} $。但是，卡哈尔的构建遇到了高度局部障碍，以更好地扩展顶点。特别是，扩展的集合与图中的短周期有关。因此，自然要询问高登期的Ramanujan图是否改善了顶点的扩展。我们的结果有两个方面： 1。每$ d = p = p+1 $，对于prime $ p $和无限的$ n $，我们展示了$ n $ vertex $ d $ d $ - 带有girth $ω（\ log_ {d-1} n）$ and vertex and dertex扩展的unied nonding in d+frac {d+1} $ nonding nonding nondy nond and nond and vern nondive e e} $ 2 \ sqrt {d-1}+o \ left（\ frac {1} {\ log n} \ right）$。 2。在带有Girth $ C \ log N $的任何Ramanujan图中，所有大小的集合都由$ n^{0.99c/4} $限制，均具有顶点扩展$（1-O_D（1））D $。 分析我们的构建的工具包括无限图的非背带操作员，Ihara-Bass公式，一种受Bordenave启发的痕量力矩方法，以及Bordenave的Friedman定理证明的启发，以及Kahale的研究方法，用于研究受到扰动图的特征值的分散体。
Kahale proved that linear sized sets in $d$-regular Ramanujan graphs have vertex expansion $\sim\frac{d}{2}$ and complemented this with construction of near-Ramanujan graphs with vertex expansion no better than $\frac{d}{2}$. However, the construction of Kahale encounters highly local obstructions to better vertex expansion. In particular, the poorly expanding sets are associated with short cycles in the graph. Thus, it is natural to ask whether high-girth Ramanujan graphs have improved vertex expansion. Our results are two-fold: 1. For every $d = p+1$ for prime $p$ and infinitely many $n$, we exhibit an $n$-vertex $d$-regular graph with girth $Ω(\log_{d-1} n)$ and vertex expansion of sublinear sized sets bounded by $\frac{d+1}{2}$ whose nontrivial eigenvalues are bounded in magnitude by $2\sqrt{d-1}+O\left(\frac{1}{\log n}\right)$. 2. In any Ramanujan graph with girth $C\log n$, all sets of size bounded by $n^{0.99C/4}$ have vertex expansion $(1-o_d(1))d$. The tools in analyzing our construction include the nonbacktracking operator of an infinite graph, the Ihara--Bass formula, a trace moment method inspired by Bordenave's proof of Friedman's theorem, and a method of Kahale to study dispersion of eigenvalues of perturbed graphs.
