Constructing highly regular expanders from hyperbolic Coxeter groups

Show simple item record Conder, Marston Lubotzky, Alexander Schillewaert, Jeroen Thilmany, François 2022-05-23T04:25:03Z 2022-05-23T04:25:03Z 2021-10-08
dc.identifier.citation (2021). Transactions of the American Mathematical Society, 375(01), 325-350.
dc.identifier.issn 0002-9947
dc.description.abstract A graph X is defined inductively to be (a0, . . ., an-1)-regular if X is a0-regular and for every vertex v of X, the sphere of radius 1 around v is an (a1, . . ., an-1)-regular graph. Such a graph X is said to be highly regular (HR) of level n if an-1 ≠ 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 PW,M, which form an infinite family of expander graphs when (W, S) is indefinite and PW,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.
dc.language en
dc.publisher American Mathematical Society (AMS)
dc.relation.ispartofseries Transactions of the American Mathematical Society
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
dc.subject Science & Technology
dc.subject Physical Sciences
dc.subject Mathematics
dc.subject SUBGROUPS
dc.subject GRAPHS
dc.subject math.GR
dc.subject math.CO
dc.subject 20F55, 05C48 (Primary), 51F15, 22E40, 05C25 (Secondary)
dc.subject 0101 Pure Mathematics
dc.subject 0102 Applied Mathematics
dc.title Constructing highly regular expanders from hyperbolic Coxeter groups
dc.type Journal Article
dc.identifier.doi 10.1090/tran/8456
pubs.issue 01
pubs.begin-page 325
pubs.volume 375 2022-04-30T19:06:51Z
dc.rights.holder Copyright: American Mathematical Society en
pubs.end-page 350
pubs.publication-status Published
dc.rights.accessrights en
pubs.subtype Article
pubs.subtype Journal
pubs.elements-id 817162 Science Mathematics
dc.identifier.eissn 1088-6850
pubs.record-created-at-source-date 2022-05-01

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace