Natural bounded concentrators. (English) Zbl 0822.05038
An \((n, \theta, k,\alpha)\)-bounded concentrator is a bipartite graph with \(n\) inputs, \(\theta n\) outputs, \(\theta< 1\), at most \(kn\) edges, and any set of at most \(\alpha n\) inputs is covered by a perfect matching. The author provides a direct construction of a family of bounded concentrators in which \(n\) tends to infinity linearly and \(\theta\), \(k\), and \(\alpha\) are fixed.
Reviewer: P.Horák (Bratislava)
MSC:
| 05C35 | Extremal problems in graph theory |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
References:
| [1] | Alon, N.; Galil, Z.; Milman, V., Better expanders and superconcentrators, J. of Alg., 8, 337-347 (1987) · Zbl 0641.68102 · doi:10.1016/0196-6774(87)90014-9 |
| [2] | Bassalygo, L. A., Asymptotically optimal switching circuits, Problems Information Transmission, 17, 206-211 (1981) · Zbl 0486.94021 |
| [3] | Drinfeld, V. G., The proof of Peterson’s Conjecture forGL(2) over global field of characteristicp, Functional Analysis and its Applications, 22, 28-43 (1988) · Zbl 0662.12012 · doi:10.1007/BF01077720 |
| [4] | Efrat, I., Automorphic spectra on the tree ofPGL_2, Enseign. Math., 37, 2, 31-34 (1991) · Zbl 0743.11029 |
| [5] | Gelbart, S., Automorphic Forms on Adele Groups (1975), Princeton: Princeton University Press, Princeton · Zbl 0329.10018 |
| [6] | Gaber, O.; Galil, Z., Explicit construction of linear sized superconcentrators, J. of Comp Sys. Sci., 22, 407-420 (1981) · Zbl 0487.05045 · doi:10.1016/0022-0000(81)90040-4 |
| [7] | I. M. Gelfand, M. I. Graev, andI. I. Pyatetskii-Shapiro:Representation Theory and Automorphic Functions, W. B. Saunders Com., 1969. · Zbl 0177.18003 |
| [8] | D. Gorenstein:Finite Groups, Chelsea, 1980. · Zbl 0463.20012 |
| [9] | Klawe, M., Limitations on explicit constructions of expanding graphs, SIAM J. Comp., 13, 155-156 (1984) · Zbl 0537.68068 |
| [10] | Lang, S., SL_2(R) (1985), New-York: Springer-Verlag, New-York |
| [11] | Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 3, 261-277 (1988) · Zbl 0661.05035 · doi:10.1007/BF02126799 |
| [12] | A. Lubotzky:Discrete Groups, Expanding Graphs and Invariant Measures, Birkhauser Progress in Math, 1994. · Zbl 0826.22012 |
| [13] | G. A. Margulis: Explicit construction of concentrators,Problems of Inform. Transmission (1975), 325-332. |
| [14] | M. Morgenstern: Ramanujan diagrams,SIAM J. of Discrete Math., November 1994. · Zbl 0811.05045 |
| [15] | Morgenstern, M., Existence and explicit construction ofq+1 regular Ramanujan graphs for every prime powerq, J. Combinatorial Theory, 62, 1, 44-62 (1994) · Zbl 0814.68098 · doi:10.1006/jctb.1994.1054 |
| [16] | M. Morgenstern: Ramanujan Diagrams and Explicit Construction of Expanding Graphs,Ph.D. Thesis, Hebrew Univ. of Jerusalem, 1990. |
| [17] | Prasad, G., Strong approximation for semi-simple groups over function fields, Ann. of Math., 105, 553-572 (1977) · Zbl 0348.22006 · doi:10.2307/1970924 |
| [18] | J. P. Serre:Trees, Springer-Verlag, 1980. · Zbl 0548.20018 |
| [19] | A. Siegel: On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications,30th Annual IEEE conference on Foundations of Computer Science, (1989), 20-25. |
| [20] | Tanner, R. M., Explicit concentrators from generalizedn-gons, SIAM J. of Alg. Disc. Math., 5, 287-294 (1984) · Zbl 0554.05045 · doi:10.1137/0605030 |
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.
