On the proofs of Leighton’s Graph Covering Theorem and a notion dual to commensurability
Nicholas Touikan · 2025
Read On the proofs of Leighton’s Graph Covering Theorem and a notion dual to commensurability by Nicholas Touikan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-01839.txt.
Introduction
Nicholas Touikan and Ashot Minasyan revisit proofs of Leighton's graph covering theorem and a dual group notion. The theorem says graphs sharing one covering tree share a finite cover too. An older proof used tree lattices to reach that result.
The pair give two graphs with a common finite cover that tree lattices cannot produce. Their example rests on an explicit commensuration between groups. They then prove a broad theorem on when such a link comes from co-commensuration. The machinery shows normal virtual retracts are virtual direct summands. An appendix adds uses for graphs of groups and separability. The work sharpens a classic theorem's proof landscape.
Catalog record
| CREATOR | Nicholas Touikan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-01839
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the proofs of Leighton’s Graph Covering Theorem and a notion dual to commensurability Nicholas Touikan Abstract Leighton’s Graph Covering Theorem states that if two finite graphs have the same universal covering tree, then they also have a common finite degree cover. Bass and Kulkarni gave an alternative proof of this fact using tree lattices. We give an example of two graphs that admit a common finite cover which can not be obtained using tree lattice techniques. The argument naturally leads to the question of when a commensuration can be induced by an embedding into a common finite index overgroup. We give necessary and sufficient conditions for when this is possible. 1 Introduction Leighton’s Graph Covering Theorem [ Lei82 ] asserts that if two finite graphs have the same universal covering tree then they admit a finite common covering space, answering a question posed in [ AG81 ] . Since, there have been various extensions of this result. There have been three proof strategies: constructing a finite cover by solving an integer programming problem (for example [ Lei82 , Woo21 ] ), using tree lattice techniques (for example [ BK90 ] ), or using groupoids (for example [ She22 ] ). The theorem has also been generalized to decorated graphs and cube complexes [ Woo21 , She22 , Woo23 , She24 ] . In [ Neu10 ] and [ She22 ] different strategies are compared. There have also been negative results giving the limitation to generalization such as [ BS22 ] that states, for example, that if two finite graphs are covered by a common regular quasitree, this pair of coverings may not factor through a finite graph. Other “non-Leighton” examples have been constructed using non-positively curved square complexes [ Wis96 , BM00 ] and there has even been work in finding minimal examples [ JW09 , DK23 , DK25 ] . This paper is concerned with a different question: Question 1.1 . Given two finite graphs X_{1},X_{2} with the same universal covers, does the the tree-lattice approach in [ BK90 ] give all possible common finite covers of X_{1} and X_{2} ? We will now describe our approach to resolving this question, while also giving previously known results. Two groups G_{1},G_{2} are commensurable if they have a common finite index subgroup (up to isomorphism). In particular, any pair of topological spaces (that admit well-defined fundamental groups) that have a common finite degree covering space will have commensurable fundamental groups. One way to show that two groups are commensurable is to show that they both embed as finite index subgroups in a common overgroup. This second property is dual to commensurability and we call it co-commensurability . This is the basis of the approach in [ BK90 ] : if X_{1},X_{2} are finite graphs with the common universal cover T then actions by deck transformations of \Gamma_{1}=\pi_{1}(X_{1}) and \Gamma_{2}=\pi_{1}(X_{2}) on T give embeddings \Gamma_{1},\Gamma_{2}\leq\mathrm{Isom}(T) . While there is no reason a-priori to expect \Gamma_{1},\Gamma_{2} to have non-trivial intersection in \mathrm{Isom}(T) , it is shown [ BK90 , Theorem 4.7] that there is a discrete subgroup \Phi\leq\mathrm{Isom}(T) and g_{1},g_{2}\in\mathrm{Isom}(T) such that [\Phi:\Gamma_{i}^{g_{i}}]<\infty,i=1,2 . This in turn implies [\Gamma_{i}^{g_{i}}:\Gamma_{1}^{g_{1}}\cap\Gamma_{2}^{g_{2}}]<\infty,i=1,2 . Thus, any two such \Gamma_{1},\Gamma_{2} are co-commensurable and a common finite cover is obtained by taking the quotient T/(\Gamma_{1}^{g_{1}}\cap\Gamma_{2}^{g_{2}}) . In [ Neu10 ] , so-called fat graphs are used to give discrete finite index overgroups. Co-commensurability easily implies commensurability and it is natural to ask whether the converse is true. It turns out that there are commensurable groups that cannot be embedded as finite index subgroups of a common overgroup. The most well-known examples are non-conjugate maximal uniform lattices \Gamma_{1},\Gamma_{2}\leq\mathrm{Isom}(\mathbb{H}^{n}) , i.e. fundamental groups of hyperbolic orbifolds that cannot properly cover other orbifolds, that are commensurable in \mathrm{Isom}(\mathbb{H}^{n}) , i.e. [\Gamma_{i}:\Gamma_{1}\cap\Gamma_{2}]<\infty,i=1,2 , but, by definition of maximal, cannot be both be contained in a common finite index discrete subgroup of \mathrm{Isom}(\mathbb{H}^{n}) . In other words, for any subgroup \Gamma_{1},\Gamma_{2}\leq H\leq\mathrm{Isom}(\mathbb{H}^{n}) we have [H:\Gamma_{i}]=\infty . This phenomenon can occur for so-called arithmetic lattices (see [ Mar91 , MR03 ] ). Now if we were able to find an “abstract” overgroup \Gamma_{1},\Gamma_{2}\leq K that contained \Gamma_{1},\Gamma_{2} as finite index overgroups, then a result of Tukia [ Tuk86 , Tuk94 ] and Mostow rigidity [ Mos68 ] (see also [ DK18 , Chapters 23-24] for a contemporary and unified account) imply that K can actually be embedded (modulo a finite kernel) as a subgroup of \mathrm{Isom}(\mathbb{H}^{n}) (in fact a uniform lattice) containing \Gamma_{1},\Gamma_{2} as proper finite index subgroups, contradicting maximality of \Gamma_{1},\Gamma_{2} as uniform lattices. Commensurability therefore does not imply co-commensurability. While the question of (co-) commensurability within the class of free groups is easily settled (all finite rank nonabelian free groups embed as finite index subgroups of F_{2} ), the more subtle question of whether a specific embedding of a group H as a finite index subgroup of two free groups F_{1},F_{2} can be induced by an embedding into a common overgroup K , i.e. where we have a diagram of inclusions as finite index subgroups \hbox to137.65pt{\vbox to79.96pt{\pgfpicture\makeatletter\hbox{\hskip 68.82632pt\lower-39.9792pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{}{}{{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{{}}{{}}{{}}{{}}}{{{\lx@inpgf@ignorespaces}}}{{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-68.82632pt}{-36.31947pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{60}\lxSVG@closescope }}}{{{\lx@inpgf@ignorespaces{}}}{{}}{{}}{{}}{{}}}} \lxSVG@closescope }}} {}{}{ {}{}{}}{}{ {}{}{}} {{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{ {}{}}{}{}{{}{}}}}}{{}}{}{}{}{}{}{{{}{}}}{}{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}}{}{}{}{}{} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{0.85658}{0.51602}{-0.51602}{0.85658}{-27.20432pt}{12.67822pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{60}\lxSVG@closescope }}} \lxSVG@closescope }}} \lxSVG@closescope {}{}{ {}{}{}}{}{ {}{}{}} {{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{ {}{}}{}{}{{}{}}}}}{{}}{}{}{}{}{}{{{}{}}}{}{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}}{}{}{}{}{} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{0.85658}{-0.51602}{0.51602}{0.85658}{20.54199pt}{16.69171pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{60}\lxSVG@closescope }}} \lxSVG@closescope }}} \lxSVG@closescope {}{}{ {}{}{}}{}{ {}{}{}} {{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{ {}{}}{}{}{{}{}}}}}{{}}{}{}{}{}{}{{{}{}}}{}{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}}{}{}{}{}{} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{0.84589}{-0.53336}{0.53336}{0.84589}{-31.56969pt}{-16.86696pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{60}\lxSVG@closescope }}} \lxSVG@closescope }}} \lxSVG@closescope {}{}{ {}{}{}}{}{ {}{}{}} {{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{ {}{}}{}{}{{}{}}}}}{{}}{}{}{}{}{}{{{}{}}}{}{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}}{}{}{}{}{} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{0.84589}{0.53336}{-0.53336}{0.84589}{24.99055pt}{-21.01527pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{60}\lxSVG@closescope }}} \lxSVG@closescope }}} \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}, was still unknown. It turns out that a necessary condition is that H contains a normal subgroup N that is itself simultaneously normal in both F_{1} and F_{2} . This property in turn implies that the associated amalgamated free product F_{1}*_{H}F_{2} admits a virtually free quotient and therefore also a finite quotient (see Lemma 2.3 ). The amalgamated free products of free groups constructed in [ Bha94 ] give examples of commensurations that can not be induced by a co-commensuration (see Corollary 2.4 .) This example still doesn’t settle Question 1.1 . Using the more refined constructions in [ Rat07 ] , we are able to show that there is a finite graph Z that covers graphs X_{1} and X_{2} such that the induced commensuration cannot be induced by a co-commensuration (see Theorem 3.1 ) thus: The answer to Question 1.1 is “no”. Question 1.1 was motivated by the author’s attempts to generalize the approach in [ BK90 ] to other contexts in order to create common finite covers. Being able to do so has been a key step in recent quasi-isometric rigidity results of graphs of groups such as [ SW22 , MSSW23 ] . For example, although the preprint [ TT23 ] was withdrawn due to gap mistake in the main argument, the authors (apparently correctly) applied the method of [ BK90 ] to show that if two groups \Gamma_{1},\Gamma_{2} acted freely, combinatorially, and cocompactly on a so-called churro-waffle space X (i.e. they are uniform lattices in \mathrm{Aut}(X) ) then