Leighton's Theorem: extensions, limitations, and quasitrees
Leighton’s Theorem states that if there is a tree T that covers two finite graphs G1 and G2, then there is a finite graph Gˆ that is covered by T and covers both G1 and G2. We prove that this result does not extend to regular covers by graphs other than trees. Nor does it extend to non-regular cover...
Main Authors: | , |
---|---|
Format: | Journal article |
Language: | English |
Published: |
Mathematical Sciences Publishers
2022
|
_version_ | 1797107495630536704 |
---|---|
author | Bridson, M Shepherd, S |
author_facet | Bridson, M Shepherd, S |
author_sort | Bridson, M |
collection | OXFORD |
description | Leighton’s Theorem states that if there is a tree T that covers two finite graphs G1 and G2, then there is a finite graph Gˆ that is covered by T and covers both G1 and G2. We prove that this result does not extend to regular covers by graphs other than trees. Nor does it extend to non-regular covers by a quasitree, even if the automorphism group of the quasitree contains a uniform lattice. But it does extend to regular coverings by quasitrees. |
first_indexed | 2024-03-07T07:16:57Z |
format | Journal article |
id | oxford-uuid:840fdf21-3fa9-4fe3-b977-54082f62d225 |
institution | University of Oxford |
language | English |
last_indexed | 2024-03-07T07:16:57Z |
publishDate | 2022 |
publisher | Mathematical Sciences Publishers |
record_format | dspace |
spelling | oxford-uuid:840fdf21-3fa9-4fe3-b977-54082f62d2252022-08-19T09:19:10ZLeighton's Theorem: extensions, limitations, and quasitreesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:840fdf21-3fa9-4fe3-b977-54082f62d225EnglishSymplectic ElementsMathematical Sciences Publishers2022Bridson, MShepherd, SLeighton’s Theorem states that if there is a tree T that covers two finite graphs G1 and G2, then there is a finite graph Gˆ that is covered by T and covers both G1 and G2. We prove that this result does not extend to regular covers by graphs other than trees. Nor does it extend to non-regular covers by a quasitree, even if the automorphism group of the quasitree contains a uniform lattice. But it does extend to regular coverings by quasitrees. |
spellingShingle | Bridson, M Shepherd, S Leighton's Theorem: extensions, limitations, and quasitrees |
title | Leighton's Theorem: extensions, limitations, and quasitrees |
title_full | Leighton's Theorem: extensions, limitations, and quasitrees |
title_fullStr | Leighton's Theorem: extensions, limitations, and quasitrees |
title_full_unstemmed | Leighton's Theorem: extensions, limitations, and quasitrees |
title_short | Leighton's Theorem: extensions, limitations, and quasitrees |
title_sort | leighton s theorem extensions limitations and quasitrees |
work_keys_str_mv | AT bridsonm leightonstheoremextensionslimitationsandquasitrees AT shepherds leightonstheoremextensionslimitationsandquasitrees |