EXPLICIT EXPANDERS OF EVERY DEGREE AND SIZE
EXPLICIT EXPANDERS OF EVERY DEGREE AND SIZE
复制标题
DOI：
10.1007/s00493-020-4429-x
复制
发表时间：
2021-02-01
期刊：
影响因子：
1.1
通讯作者：
Alon, Noga
中科院分区：
文献类型：
--
作者：
Alon, Noga
An（n，d，lambda）-graph是n个顶点上的常规图，其中任何非平凡特征值的绝对值最多都是lambda。对于任何常数的d> = 3，epsilon> 0和所有足够大的n，我们表明存在确定性的poly（n）时间算法，该算法输出A a（n，d，lambda）-graph（在n个顶点上） （0）（epsilon）和n> n（0）（d; epsilon）我们提出了一个强烈的明确结构（M; d; lambda） - 用lambda的图表
An (n, d, lambda)-graph is a d regular graph on n vertices in which the absolute value of any nontrivial eigenvalue is at most lambda. For any constant d >= 3, epsilon > 0 and all sufficiently large n we show that there is a deterministic poly(n) time algorithm that outputs an (n, d, lambda)-graph (on exactly n vertices) with lambda d(0)(epsilon) and n>n(0)(d; epsilon) we present a strongly explicit construction of an (m;d;lambda)-graph with lambda