Explicit near-Ramanujan graphs of every degree
Explicit near-Ramanujan graphs of every degree
复制标题
DOI：
10.1145/3357713.3384231
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Sidhanth Mohanty;R. O'Donnell;Pedro Paredes
中科院分区：
文献类型：
--
作者：
Sidhanth Mohanty;R. O'Donnell;Pedro Paredes
对于每个常数d≥3和n > 0，我们给出了一个确定性的多(n)时间算法，该算法输出Θ(n)个顶点上的d正则图є-near-Ramanujan；也就是说，它的特征值在大小上以2√d−1 + k为界（不包括d的单个平凡特征值）。
For every constant d ≥ 3 and є > 0, we give a deterministic poly(n)-time algorithm that outputs a d-regular graph on Θ(n) vertices that is є-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by 2√d−1 + є (excluding the single trivial eigenvalue of d).