论文标题
在常规图上保留短周期的频谱
Spectrum preserving short cycle removal on regular graphs
论文作者
论文摘要
我们描述了一种新的方法，可以在维持光谱界限（邻接矩阵的非平凡特征值）的同时删除常规图上的短周期，只要图形具有某些组合特性即可。这些组合特性与短周期之间的数量和距离有关，并且已知在均匀随机的常规图中很高的可能性发生。 使用此方法，我们可以显示两个涉及高环形频谱扩展器图的结果。首先，我们表明给定$ d \ geq 3 $和$ n $，存在明显的分布$ d $ - rekular $θ（n）$ - 顶点图，其中其样品具有Girth $ω（\ log_ {d-1} n）$和属于$ε$ -Near-ramanujan;也就是说，其特征值的幅度为$ 2 \ sqrt {d -1} +ε$（不包括$ d $的单个微不足道特征值）。然后，对于每个常数$ d \ geq 3 $和$ε> 0 $，我们给出了确定性的poly $（n）$ - 时间算法，输出$θ（n）$ - $θ（n）$ - $ε$ -near-near-near-near-ramanujan和girth $ the $ d $ regult图的时间Arxiv：1909.06988。
We describe a new method to remove short cycles on regular graphs while maintaining spectral bounds (the nontrivial eigenvalues of the adjacency matrix), as long as the graphs have certain combinatorial properties. These combinatorial properties are related to the number and distance between short cycles and are known to happen with high probability in uniformly random regular graphs. Using this method we can show two results involving high girth spectral expander graphs. First, we show that given $d \geq 3$ and $n$, there exists an explicit distribution of $d$-regular $Θ(n)$-vertex graphs where with high probability its samples have girth $Ω(\log_{d - 1} n)$ and are $ε$-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by $2\sqrt{d - 1} + ε$ (excluding the single trivial eigenvalue of $d$). Then, for every constant $d \geq 3$ and $ε> 0$, we give a deterministic poly$(n)$-time algorithm that outputs a $d$-regular graph on $Θ(n)$-vertices that is $ε$-near-Ramanujan and has girth $Ω(\sqrt{\log n})$, based on the work of arXiv:1909.06988 .
