×

Explicit construction of a Ramanujan \((n_1,n_2,\dots,n_{d-1})\)-regular hypergraph. (English) Zbl 1180.11016

In the article under review, the explicit construction of Ramanujan hypergraphs, which are certain simplicial complexes (introduced in the author’s thesis), generalizations of Ramanujan graphs, are given. Such hypergraphs are described in terms of Cayley graphs of various groups. An explicit description is given of the hypergraph as the Cayley graph of the groups \(\text{PSL}_{d}(\mathbb{F}_{r})\) and \(\text{PGL}_{d}(\mathbb{F}_{r})\) with respect to a certain set of generators, over a finite field \(\mathbb{F}_{r}\) with \(r\) elements.
This work generalizes work of M. Morgenstern [SIAM J. Discrete Math. 7, No. 4, 560–570 (1994; Zbl 0811.05045)], which in turn extends work of A. Lubotzky, R. Phillips and P. Sarnak [Combinatorica 8, No. 3, 261–277 (1988; Zbl 0661.05035)]. The paper is self contained. A detailed discussion of the basics of the skew polynomial ring \(\mathbb{F}_{q^{d}}\) is given. Then the arithmetic groups associated to the ring are discussed. Finally using the properties of \(\mathbb{F}_{q^{d}},\) the explicit construction of the hypergraphs are given.

MSC:

11F72 Spectral theory; trace formulas (e.g., that of Selberg)
11B75 Other combinatorial number theory
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
11R58 Arithmetic theory of algebraic function fields
22E40 Discrete subgroups of Lie groups
51E24 Buildings and the geometry of diagrams
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K. Brown, Buildings , Springer, New York, 1989.
[2] L. Carlitz, On polynomials in a Galois field, Bull. Amer. Math. Soc. 38 (1932), 736–744. · Zbl 0005.38702
[3] -, On certain functions connected with polynomials in a Galois field, Duke Math. J. 1 (1935), 137–168. · Zbl 0012.04904
[4] -, A set of polynomials , Duke Math. J. 6 (1940), 486–504. · Zbl 0026.05304
[5] -, Some special functions over GF\((q,x)\), Duke Math. J. 27 (1960), 139–158. · Zbl 0097.25904
[6] D. I. Cartwright, Harmonic Functions on Buildings of, Type \(\tilde{A}_n\) , Sympos. Math. 39 , Cambridge Univ. Press, Cambridge, 1999. · Zbl 0958.51015
[7] D. I. Cartwright and T. Steger, A family of \(\tilde{A}_n\)-groups, Israel J. Math. 103 (1998), 125–140. · Zbl 0923.51010
[8] G. Davidoff, P. Sarnak, and A. Vallete, Elementary Number Theory, Group Theory, and Ramanujan Graphs , London Math. Soc. Stud. Texts 55 , Cambridge Univ. Press, Cambridge, 2003. · Zbl 1032.11001
[9] J. D. Dixon, M. P. F. Du Sautoy, A. Mann, and D. Segal, Analytic Pro-p-Groups , London Math. Soc. Lecture Note Ser. 157 , Cambridge Univ. Press, Cambridge, 1991. · Zbl 0744.20002
[10] V. G. Drinfel’D [drinfeld], Proof of the Petersson conjecture for \(\mathrm{GL}(2)\) over a global field of characteristic p (in Russian), Funktsional. Anal. i Prilozhen. 22 , no. 1 (1988), 34–54.; English translation in Funct. Anal. Appl. 22 (1988), 28–43.
[11] B. Farb and R. K. Dennis, Noncommutative Algebra , Grad. Texts in Math. 144 , Springer, New York, 1993. · Zbl 0797.16001
[12] N. Jacobson, Finite-Dimensional Division Algebras over Fields , Springer, Berlin, 1996. · Zbl 0874.16002
[13] T. Y. Lam, A First Course in Noncommutative Rings , Grad. Texts in Math. 131 , Springer, New York, 1986.
[14] S. Lang, Algebra , Addison Wesley, Reading, Mass., 1965.
[15] -, \(\mathrm{SL}_2(R)\) , reprint of the 1975 ed., Grad. Texts in Math. 105 , Springer, New York, 1985.
[16] W.-C. W. Li, Ramanujan hypergraphs , Geom. Funct. Anal. 14 (2004), 380–399. · Zbl 1084.05047
[17] A. Lubotzky, R. Phillips, and P. Sarnak, “Explicit expanders and the Ramanujan Conjectures” in Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (Berkeley, Calif., 1986) , Assoc. for Computing Machinery, New York, 1986, 240–246.
[18] -, Ramanujan graphs , Combinatorica 8 (1988), 261–277. · Zbl 0661.05035
[19] A. Lubotzky, B. Samuels, and U. Vishne, Explicit constructions of Ramanujan complexes of type \(\tilde{A}_d\) , European J. Combin. 26 (2005), 965–993. · Zbl 1135.05038
[20] -, Ramanujan complexes of type \(\tilde{A}_d\) , Israel J. Math. 149 (2005), 267–299. · Zbl 1087.05036
[21] C. C. Macduffee, An Introduction to Abstract Algebra , Wiley, New York, 1940. · JFM 66.0034.02
[22] M. Morgenstern, Existence and explicit construction of \(q+1\) regular Ramanujan graphs for every prime power q , J. Combin. Theory Ser. B 62 (1994), 44–62. · Zbl 0814.68098
[23] O. Ore, On a special class of polynomials , Trans. Amer. Math. Soc. 35 (1933), 559–584.; Errata , Trans. Amer. Math. Soc. 36 (1934), 275. \({\!}\); Mathematical Reviews (MathSciNet): JSTOR: links.jstor.org
[24] -, Theory of non-commutative polynomials , Ann. of Math. (2) 34 (1933), 480–508. JSTOR: · Zbl 0007.15101
[25] M. Ronan, Lectures on Buildings , Perspect. Math. 7 , Academic Press, Boston, 1989. · Zbl 0694.51001
[26] -, Buildings: Main ideas and applications, I: Main ideas , Bull. London Math. Soc. 24 (1992), 1–51.; II : Arithmetic groups, buildings and symmetric spaces , Bull. London Math. Soc. 24 (1992), 97–126. \({\!}\); Mathematical Reviews (MathSciNet): · Zbl 0753.51009
[27] M. Rosen, Number Theory in Function Fields , Grad. Texts in Math. 210 , Springer, New York, 2002.
[28] P. Sarnak, Some Applications of Modular Forms , Cambridge Tracts in Math. 99 , Cambridge Univ. Press, Cambridge, 1990. · Zbl 0721.11015
[29] A. Sarveniazi, Ramanujan \((n_1,n_2,\ldots,n_{d-1})\)-regular hypergraphs based on Bruhat-Tits buildings of type \(\tilde{A}_{d-1}\) , Ph.D. dissertation, University of Göttingen, Göttingen, Germany, 2003. · Zbl 1068.05048
[30] -, Ramanujan \((n_1,n_2,\ldots,n_{d-1})\)-regular hypergraphs , I: Definition and abstract construction , preprint, 2004.
[31] W. Scharlau, Quadratic and Hermitian Forms , Grundlehren Math. Wiss. 270 , Springer, Berlin, 1985. · Zbl 0584.10010
[32] J.-P. Serre, A Course in Arithmetic , Grad. Texts in Math. 7 , Springer, New York, 1973. · Zbl 0256.12001
[33] -, Linear Representations of Finite Groups , Grad. Texts in Math. 42 , Springer, New York, 1977. · Zbl 0355.20006
[34] -, Trees , Springer, New York, 1980.
[35] G. Shimura, Introduction to the Arithmetic Theory of Automorphic Functions , Kanô Memorial Lectures 1 , Publ. Math Soc. Japan 11 , Princeton Univ. Press, Princeton, 1971. · Zbl 0221.10029
[36] A. Terras, Fourier Analysis on Finite Groups and Applications , London Math. Soc. Stud. Texts 43 , Cambridge Univ. Press, Cambridge, 1999. · Zbl 0928.43001
[37] M.-F. Vignéras, Arithmétique des algèbres de quaternions, Lecture Notes in Math. 800 , Springer, Berlin, 1980. · Zbl 0422.12008
[38] A. Weil, Basic Number Theory , Grundlehren Math. Wiss. 144 , Springer, New York, 1967. · Zbl 0176.33601
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.