×

Expanders and diffusers. (English) Zbl 0612.68061

Expander graphs are ingredients for making concentrating, switching, and sorting networks, and are closely related to sparse, doubly-stochastic matrices called diffusers. The best explicit examples of diffusers are defined by means of the action of elements of the matrix group SL(2,\({\mathbb{Z}})\) on certain finite mathematical objects. Some corresponding, explicit expanders were introduced by Margulis. However, Gabber and Galil were the first to obtain good estimates for the expanders and produce from them a family of directed acyclic superconcentrators having density 271.8. We review various techniques for making expanders from diffusers. We also demonstrate asymptotic upper bounds on the strength of algebraically defined classes of degree k diffusers. Each upper bound is given as the norm of a diffusion operator on an infinite discrete group, and bounds for several examples are calculated. Numerical evidence is supplied in support of our conjecture that these bounds can be achieved by certain algebraically defined examples. The conjecture, if true, would lead to superconcentrators of density less than 58.

MSC:

68R10 Graph theory (including graph drawing) in computer science
15B51 Stochastic matrices
05C20 Directed graphs (digraphs), tournaments
60G50 Sums of independent random variables; random walks
94C15 Applications of graph theory to circuits and networks
20G40 Linear algebraic groups over finite fields
65F50 Computational methods for sparse matrices
Full Text: DOI

References:

[1] Ajtai, M.; Komlós, J.; Szemerédi, E., Sorting in \(c\,{\rm log}\,n\) parallel steps, Combinatorica, 3, 1, (1983) · Zbl 0523.68048
[2] An O(nlogn) sorting networkProc. 15th Annual ACM Symposium on Theory of ComputingBoston198319
[3] Alon, N., Eigenvalues and expanders, Combinatorica, 6, 83, (1986) · Zbl 0661.05053
[4] Alon, N.; Galil, Z.; Milman, V. D., Better expanders and superconcentrators, J. Algorithms, 8, 337, (1987) · Zbl 0641.68102
[5] Eigenvalues, expanders and superconcentratorsProc. 25th Annual Symposium on Foundations of Computer ScienceGainesville, Florida1984320322
[6] Alon, N.; Milman, V. D., \(λ\sb 1,\) isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B, 38, 73, (1985) · Zbl 0549.05051
[7] Bassalygo, L. A., Asymptotically optimal switching circuits, Problemy Peredachi Informatsii, 17, 81, (1981) · Zbl 0486.94021
[8] Bassalygo, L. A.; Pinsker, M. S., The complexity of an optimal non-blocking commutation scheme without reorganization, Problemy Peredači Informacii, 9, 84, (1973) · Zbl 0327.94051
[9] Chung, F. R. K., On concentrators, superconcentrators, generalizers, and nonblocking networks, Bell System Tech. J., 58, 1765, (1979) · Zbl 0415.94021
[10] Day, MahlonMarsh, Convolutions, means, and spectra, Illinois J. Math., 8, 100, (1964) · Zbl 0122.11703
[11] Gabber, Ofer; Galil, Zvi, Explicit constructions of linear-sized superconcentrators, J. Comput. System Sci., 22, 407, (1981) · Zbl 0487.05045 · doi:10.1016/0022-0000(81)90040-4
[12] Hewitt, E.; Ross, K., Abstract Harmonic Analysis, Vol. 1, (1963) · Zbl 0115.10603
[13] Kesten, Harry, Symmetric random walks on groups, Trans. Amer. Math. Soc., 92, 336, (1959) · Zbl 0092.33503
[14] Kesten, Harry, Full Banach mean values on countable groups, Math. Scand., 7, 146, (1959) · Zbl 0092.26704
[15] Klawe, Maria, Limitations on explicit constructions of expanding graphs, SIAM J. Comput., 13, 156, (1984) · Zbl 0537.68068 · doi:10.1137/0213011
[16] Margulis, G. A., Explicit constructions of concentrators, Problemy Peredachi Informatsii, 9, 71, (1973) · Zbl 0312.22011
[17] On the complexity of a concentratorProc. 7th International Teletraffic ConferenceStockholm1973318/1-318/4June
[18] Pippenger, Nicholas, Superconcentrators, SIAM J. Comput., 6, 298, (1977) · Zbl 0361.05035 · doi:10.1137/0206022
[19] Tanner, R. Michael, Explicit concentrators from generalized {\it N}-gons, SIAM J. Algebraic Discrete Methods, 5, 287, (1984) · Zbl 0554.05045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.