论文标题
各个程度和大小的显式扩展器
Explicit expanders of every degree and size
论文作者
论文摘要
$（n，d，λ）$ - 图是$ n $顶点上的$ d $常规图，其中任何非平凡特征值的绝对值最多都是$λ$。对于任何常量的$ d \ geq 3 $，$ε> 0 $和所有足够大的$ n $，我们表明，有一种确定性的poly（n）时间算法，该算法将输出$（n，d，λ）$ - graph（完全$ n $ dertices），$λ\λ\λ\ leq 2 \ sqrt \ sqrt \ sqrt {d-sqrt {d-d-d-d-1}+ε$ $。对于任何$ d = p +2 $，带有$ p \ equiv 1 \ bmod 4 $ prime和所有足够大的$ n $，我们描述了$（n，d，λ）$ - graph的强烈明确结构（$λ\ leq \ leq \ leq \ leq \ sqrt {2（d-1） +sqrt {2（d-1） +\ sqrt} （1+ \ sqrt 2）\ sqrt {d-1}+o（1））$，其中$ o（1）$ enter tens $ n $ as as $ n $倾向于无限。对于每$ε> 0 $，$ d> d_0（ε）$和$ n> n_0（d，ε）$，我们提供了$（m，d，λ）$ - 带有$λ<（2+ε）\ sqrt d $和$ m = n+o（n+o（n）$的$（m，d，λ）$的强烈构造。所有构造都是从已知的Ramanujan或几乎Ramanujan图开始的，以适当的方式修改或包装它们。光谱分析依赖于无循环社区中常规图的特征向量的定位。
An $(n,d,λ)$-graph is a $d$ regular graph on $n$ vertices in which the absolute value of any nontrivial eigenvalue is at most $λ$. For any constant $d \geq 3$, $ε>0$ and all sufficiently large $n$ we show that there is a deterministic poly(n) time algorithm that outputs an $(n,d, λ)$-graph (on exactly $n$ vertices) with $λ\leq 2 \sqrt{d-1}+ε$. For any $d=p+2$ with $p \equiv 1 \bmod 4$ prime and all sufficiently large $n$, we describe a strongly explicit construction of an $(n,d, λ)$-graph (on exactly $n$ vertices) with $λ\leq \sqrt {2(d-1)} + \sqrt{d-2} +o(1) (< (1+\sqrt 2) \sqrt {d-1}+o(1))$, with the $o(1)$ term tending to $0$ as $n$ tends to infinity. For every $ε>0$, $d>d_0(ε)$ and $n>n_0(d,ε)$ we present a strongly explicit construction of an $(m,d,λ)$-graph with $λ< (2+ε) \sqrt d$ and $m=n+o(n)$. All constructions are obtained by starting with known ones of Ramanujan or nearly Ramanujan graphs, modifying or packing them in an appropriate way. The spectral analysis relies on the delocalization of eigenvectors of regular graphs in cycle-free neighborhoods.
