## Constructing highly regular expanders from hyperbolic Coxeter groups

HTML articles powered by AMS MathViewer

- by Marston Conder, Alexander Lubotzky, Jeroen Schillewaert and François Thilmany PDF
- Trans. Amer. Math. Soc.
**375**(2022), 325-350 Request permission

## Abstract:

A graph $X$ is defined inductively to be $(a_0,\dots ,a_{n-1})$-regular if $X$ is $a_0$-regular and for every vertex $v$ of $X$, the sphere of radius $1$ around $v$ is an $(a_1,\dots ,a_{n-1})$-regular graph. Such a graph $X$ is said to be highly regular (HR) of level $n$ if $a_{n-1}\neq 0$. Chapman, Linial and Peled [Combinatorica 40 (2020), pp. 473–509] studied HR-graphs of level $2$ and provided several methods to construct families of graphs which are expanders “globally and locally”, and asked about the existence of HR-graphs of level $3$.

In this paper we show how the theory of Coxeter groups, and abstract regular polytopes and their generalisations, can be used to construct such graphs. Given a Coxeter system $(W,S)$ and a subset $M$ of $S$, we construct highly regular quotients of the 1-skeleton of the associated Wythoffian polytope $\mathcal {P}_{W,M}$, which form an infinite family of expander graphs when $(W,S)$ is indefinite and $\mathcal {P}_{W,M}$ has finite vertex links. The regularity of the graphs in this family can be deduced from the Coxeter diagram of $(W,S)$. The expansion stems from applying superapproximation to the congruence subgroups of the linear group $W$.

This machinery gives a rich collection of families of HR-graphs, with various interesting properties, and in particular answers affirmatively the question asked by Chapman, Linial and Peled.

## References

- N. Alon and V. D. Milman,
*$\lambda _1,$ isoperimetric inequalities for graphs, and superconcentrators*, J. Combin. Theory Ser. B**38**(1985), no. 1, 73–88. MR**782626**, DOI 10.1016/0095-8956(85)90092-9 - Yves Benoist and Pierre de la Harpe,
*Adhérence de Zariski des groupes de Coxeter*, Compos. Math.**140**(2004), no. 5, 1357–1366 (French, with English summary). MR**2081159**, DOI 10.1112/S0010437X04000338 - E. R. Berlekamp, J. H. van Lint, and J. J. Seidel,
*A strongly regular graph derived from the perfect ternary Golay code*, A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) North-Holland, Amsterdam, 1973, pp. 25–30. MR**0364015** - Armand Borel,
*Density properties for certain subgroups of semi-simple groups without compact components*, Ann. of Math. (2)**72**(1960), 179–188. MR**123639**, DOI 10.2307/1970150 - N. Bourbaki,
*Éléments de mathématique. Algèbre. Chapitre 9*, Springer-Verlag, Berlin, 2007 (French). Reprint of the 1959 original. MR**2325344** - J. H. Conway and M. J. T. Guy,
*Four-dimensional archimedean polytopes*,*Proceedings of the Colloquium on Convexity at Copenhagen*, pages 38–39, 1965. - M. Conder, I. Hubard, and E. O’Reilly-Regueiro,
*Construction of chiral polytopes of large rank with alternating or symmetric automorphism group*, 2020. To appear. - Michael Chapman, Nati Linial, and Yuval Peled,
*Expander graphs—both local and global*, Combinatorica**40**(2020), no. 4, 473–509. MR**4150879**, DOI 10.1007/s00493-019-4127-8 - Marston Conder and Colin Maclachlan,
*Compact hyperbolic 4-manifolds of small volume*, Proc. Amer. Math. Soc.**133**(2005), no. 8, 2469–2476. MR**2138890**, DOI 10.1090/S0002-9939-05-07634-3 - H. S. M. Coxeter,
*Wythoff’s Construction for Uniform Polytopes*, Proc. London Math. Soc. (2)**38**(1935), 327–339. MR**1576319**, DOI 10.1112/plms/s2-38.1.327 - H. S. M. Coxeter,
*Regular and semi-regular polytopes. I*, Math. Z.**46**(1940), 380–407. MR**2181**, DOI 10.1007/BF01181449 - H. S. M. Coxeter,
*Regular Polytopes*, Methuen & Co., Ltd., London; Pitman Publishing Corp., New York, 1948; 1949. MR**0027148** - H. S. M. Coxeter,
*Regular honeycombs in hyperbolic space*, Proceedings of the International Congress of Mathematicians, 1954, Amsterdam, vol. III, Erven P. Noordhoff N. V., Groningen; North-Holland Publishing Co., Amsterdam, 1956, pp. 155–169. MR**0087114** - H. S. M. Coxeter,
*Regular and semiregular polytopes. II*, Math. Z.**188**(1985), no. 4, 559–591. MR**774558**, DOI 10.1007/BF01161657 - Irit Dinur and Tali Kaufman,
*High dimensional expanders imply agreement expanders*, 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, IEEE Computer Soc., Los Alamitos, CA, 2017, pp. 974–985. MR**3734297**, DOI 10.1109/FOCS.2017.94 - Jozef Dodziuk,
*Difference equations, isoperimetric inequality and transience of certain random walks*, Trans. Amer. Math. Soc.**284**(1984), no. 2, 787–794. MR**743744**, DOI 10.1090/S0002-9947-1984-0743744-X - E.L. Elte,
*The semiregular polytopes of the hyperspaces*, Dissert. Univ. Groningen. Groningen: Hoitsema, 1912. - E. Friedgut and Y. Iluz,
*Hyper-regular graphs and high dimensional expanders*, 2020. In preparation. - Howard Garland,
*$p$-adic curvature and the cohomology of discrete subgroups of $p$-adic groups*, Ann. of Math. (2)**97**(1973), 375–423. MR**320180**, DOI 10.2307/1970829 - T. Gosset. On the regular and semi-regular figures in space of $n$ dimensions.
*Messenger Math.*, 29:43–48, 1900. - Roger A. Horn and Charles R. Johnson,
*Topics in matrix analysis*, Cambridge University Press, Cambridge, 1991. MR**1091716**, DOI 10.1017/CBO9780511840371 - Shlomo Hoory, Nathan Linial, and Avi Wigderson,
*Expander graphs and their applications*, Bull. Amer. Math. Soc. (N.S.)**43**(2006), no. 4, 439–561. MR**2247919**, DOI 10.1090/S0273-0979-06-01126-8 - Tali Kaufman and David Mass,
*High dimensional random walks and colorful expansion*, 8th Innovations in Theoretical Computer Science Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 67, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, pp. Art. No. 4, 27. MR**3754928** - Alexander Lubotzky and Avinoam Mann,
*On groups of polynomial subgroup growth*, Invent. Math.**104**(1991), no. 3, 521–533. MR**1106747**, DOI 10.1007/BF01245088 - Alexander Lubotzky,
*Free quotients and the first Betti number of some hyperbolic manifolds*, Transform. Groups**1**(1996), no. 1-2, 71–82. MR**1390750**, DOI 10.1007/BF02587736 - Alexander Lubotzky,
*High dimensional expanders*, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. I. Plenary lectures, World Sci. Publ., Hackensack, NJ, 2018, pp. 705–730. MR**3966743** - A. Malcev,
*On isomorphic matrix representations of infinite groups*, Rec. Math. [Mat. Sbornik] N.S.**8 (50)**(1940), 405–422 (Russian, with English summary). MR**0003420** - Peter McMullen and Egon Schulte,
*Abstract regular polytopes*, Encyclopedia of Mathematics and its Applications, vol. 92, Cambridge University Press, Cambridge, 2002. MR**1965665**, DOI 10.1017/CBO9780511546686 - Guennadi A. Noskov and Èrnest B. Vinberg,
*Strong Tits alternative for subgroups of Coxeter groups*, J. Lie Theory**12**(2002), no. 1, 259–264. MR**1885045** - M. S. Pinsker,
*On the complexity of a concentrator*,*7th International Telegraffic Conference*, pages 318/1–318/4, 1973. - B. Russell and A.N. Whitehead.
*Principia Mathematica*, volume 2. Cambridge University Press, Cambridge, 1912. - Gert Sabidussi,
*Graph multiplication*, Math. Z.**72**(1959/60), 446–457. MR**209177**, DOI 10.1007/BF01162967 - Alireza Salehi Golsefidy,
*Super-approximation, I: $\mathfrak {p}$-adic semisimple case*, Int. Math. Res. Not. IMRN**23**(2017), 7190–7263. MR**3802123**, DOI 10.1093/imrn/rnw208 - Alireza Salehi Golsefidy,
*Super-approximation, II: the $p$-adic case and the case of bounded powers of square-free integers*, J. Eur. Math. Soc. (JEMS)**21**(2019), no. 7, 2163–2232. MR**3959861**, DOI 10.4171/JEMS/883 - V. Schlegel,
*Theorie der homogen zusammengesetzten Raumgebilde*, Leipzig: Engelmann. Nova Acta Acad. Leop.-Carol. XLIV., 1883. - Kisao Takeuchi,
*Arithmetic triangle groups*, J. Math. Soc. Japan**29**(1977), no. 1, 91–106. MR**429744**, DOI 10.2969/jmsj/02910091 - J. Tits,
*Groupes et géométries de Coxeter*, Bures-sur-Yvette: I.H.E.S., Notes polycopiées, 1961. - Paul M. Weichsel,
*The Kronecker product of graphs*, Proc. Amer. Math. Soc.**13**(1962), 47–52. MR**133816**, DOI 10.1090/S0002-9939-1962-0133816-6 - Bohdan Zelinka,
*Locally regular graphs*, Math. Bohem.**125**(2000), no. 4, 481–484. MR**1802296**

## Additional Information

**Marston Conder**- Affiliation: Department of Mathematics, University of Auckland, 38 Princes Street, Auckland 1010, New Zealand
- MR Author ID: 50940
- ORCID: 0000-0002-0256-6978
- Email: m.conder@auckland.ac.nz
**Alexander Lubotzky**- Affiliation: Einstein institute of mathematics Edmund J. Safra campus of the Hebrew University Givat Ram, Jerusalem 91904, Israel
- MR Author ID: 116480
- ORCID: 0000-0001-7281-1142
- Email: alex.lubotzky@mail.huji.ac.il
**Jeroen Schillewaert**- Affiliation: Department of Mathematics, University of Auckland, 38 Princes Street, Auckland 1010, New Zealand
- MR Author ID: 831547
- Email: j.schillewaert@auckland.ac.nz
**François Thilmany**- Affiliation: Department of Mathematics, KU Leuven, Celestijnenlaan 200B, 3001 Leuven, Belgium
- Email: francois.thilmany@kuleuven.be
- Received by editor(s): October 14, 2020
- Received by editor(s) in revised form: April 13, 2021
- Published electronically: October 8, 2021
- Additional Notes: Grant support: the first author by N.Z. Marsden Fund (project UOA1626), the first and third authors by UoA (FRDF grant 3719917 ‘Geometry and symmetry’), the second author by NSF (grant DMS-1700165) and ERC (Horizon 2020 programme, grant 692854), and the fourth author by FNRS (CR FC 4057) and KU Leuven (PDM 19145). This material is based upon work supported by a grant from the Institute for Advanced Study. All four authors thank the Margaret and John Kalman Trust for the financial support of the Michael Erceg Senior Visiting Fellowship at the University of Auckland (UoA) which the first author was awarded. The first and fourth authors thank UoA for its hospitatility. The present work grew out of their visit at UoA
- © Copyright 2021 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**375**(2022), 325-350 - MSC (2020): Primary 20F55, 05C48; Secondary 51F15, 22E40, 05C25
- DOI: https://doi.org/10.1090/tran/8456
- MathSciNet review: 4358669

Dedicated: Dedicated to John Conway (1937-2020) and Ernest Vinberg (1937-2020), for their phenomenal insights and outstanding contributions in the fields of algebra, combinatorics and geometry