Essentially every unimodular matrix defines an expander

被引：1

作者：

Cai, JY ^{[1
]}

机构：

[1] SUNY Buffalo, Dept Comp Sci & Engn, Buffalo, NY 14260 USA

[2] Univ Wisconsin, Dept Comp Sci, Madison, WI 53706 USA

来源：

THEORY OF COMPUTING SYSTEMS | 2003年 / 36卷 / 02期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1007/s00224-002-1017-y

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We generalize the construction of Gabber and Galil to essentially every unimodular matrix in SL2(Z). It is shown that every parabolic or hyperbolic fractional linear transformation explicitly defines an expander of bounded degree and constant expansion. Thus all but a vanishingly small fraction of unimodular matrices define expanders.

引用

页码：105 / 135

页数：31

共 38 条

[1] SORTING IN C LOG N PARALLEL STEPS [J].

AJTAI, M ;

KOMLOS, J ;

SZEMEREDI, E .

COMBINATORICA, 1983, 3 (01) :1-19

[2] RECURSIVE CONSTRUCTION FOR 3-REGULAR EXPANDERS [J].

AJTAI, M .

COMBINATORICA, 1994, 14 (04) :379-416

[3]

Ajtai M., 1987, P 19 ANN ACM S THEOR, P132

[4]

AJTAI M, 1990, TRIBUTE P ERDOS, P1

[5] BETTER EXPANDERS AND SUPERCONCENTRATORS [J].

ALON, N ;

GALIL, Z ;

MILMAN, VD .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1987, 8 (03) :337-347

[6] LAMBDA-1, ISOPERIMETRIC-INEQUALITIES FOR GRAPHS, AND SUPERCONCENTRATORS [J].

ALON, N ;

MILMAN, VD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 38 (01) :73-88

[7] EIGENVALUES AND EXPANDERS [J].

ALON, N .

COMBINATORICA, 1986, 6 (02) :83-96

[8] EIGENVALUES, GEOMETRIC EXPANDERS, SORTING IN ROUNDS, AND RAMSEY THEORY [J].

ALON, N .

COMBINATORICA, 1986, 6 (03) :207-219

[9]

Alon N., 1990, Proceedings. 31st Annual Symposium on Foundations of Computer Science (Cat. No.90CH2925-6), P544, DOI 10.1109/FSCS.1990.89575

[10]

Alon N., 1984, P 25 ANN S FDN COMP, P320

← 1 2 3 4 →