每个固定度数下的确定性非二部Ramanujan图
Deterministic nonbipartite Ramanujan graphs in every fixed degree
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件研究Ramanujan图的确定性构造。作者声称对每个固定整数d≥3，给出确定性算法，在每个足够大的偶数顶点数n上构造简单非二部d正则Ramanujan图，并以多项式位运算输出完整邻接表，指数可依赖于d；每个非平凡邻接特征值严格位于-2√(d-1)与2√(d-1)之间。该手稿为AI产生，尚未经独立审查或同行评议。
- 对每个固定d≥3，声称确定性构造简单非二部d正则Ramanujan图。
- 构造覆盖每个足够大的偶数顶点数n，输出完整邻接表。
- 非平凡邻接特征值严格落在±2√(d-1)之间。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
For every fixed integer d ≥ 3, we give a deterministic algorithm that constructs a simple nonbipartite d-regular Ramanujan graph on every sufficiently large even number n of vertices. It outputs the full adjacency list in polynomially many bit operations, with an exponent that may depend on d. Every nonconstant adjacency eigenvalue lies strictly between $`-2\sqrt{d-1}`$ and $`2\sqrt{d-1}`$.
用户标记：未标记
固定编号：18afcd3597928374
原文来源