The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem

EUROCOMB’23

Louis Esperet Ugo Giocanti Clément Legrand-Duchesne

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-059

PDF
Abstract
An infinite graph is quasi-transitive if its vertex set has finitely many orbits under the action of its automorphism group. In this paper we obtain a structure theorem for locally finite quasi-transitive graphs avoiding a minor, which is reminiscent of the Robertson-Seymour Graph Minor Structure Theorem. We prove that every locally finite quasi-transitive graph $G$ avoiding a minor has a tree-decomposition whose torsos are finite or planar; moreover the tree-decomposition is canonical, i.e. invariant under the action of the automorphism group of $G$. As applications of this result, we prove the following. (i) Every locally finite quasi-transitive graph attains its Hadwiger number, that is, if such a graph contains arbitrarily large clique minors, then it contains an infinite clique minor. This extends a result of Thomassen (1992) who proved it in the 4-connected case and suggested that this assumption could be omitted. (ii) Locally finite quasi-transitive graphs avoiding a minor are accessible (in the sense of Thomassen and Woess), which extends known results on planar graphs to any proper minor-closed family. (iii) Minor-excluded finitely generated groups are accessible (in the group-theoretic sense) and finitely presented, which extends classical results on planar groups. (iv) The domino problem is decidable in a minor-excluded finitely generated group if and only if the group is virtually free, which proves the minor-excluded case of a conjecture of Ballier and Stein (2018).

Pages:
425–432
References

Yago Antolín. On Cayley graphs of virtually free groups. Groups Complexity Cryptology, 3(2):301-327, 2011.
https://doi.org/10.1515/gcc.2011.012

Nathalie Aubrun, Sebastián Barbieri, and Emmanuel Jeandel. About the Domino Problem for Subshifts on Groups. In V. Berthé and M. Rigo, editors, Sequences, Groups, and Number Theory, Trends in Mathematics, pages 331-389. Birkhäuser, Cham, 2018.
https://doi.org/10.1007/978-3-319-69152-7_9

Nathalie Aubrun, Sebastián Barbieri, and Etienne Moutot. The domino problem is undecidable on surface groups. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 46:1-46:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.

László Babai. Some applications of graph contractions. Journal of Graph Theory, 1(2):125-130, 1977.
https://doi.org/10.1002/jgt.3190010207

Alexis Ballier and Maya Stein. The domino problem on groups of polynomial growth. Groups, Geometry, and Dynamics, 12(1):93-105, 2018.
https://doi.org/10.4171/GGD/439

Robert L. Berger. The undecidability of the domino problem. Memoirs of the American Mathematical Society, 1966.
https://doi.org/10.1090/memo/0066

Johannes Carmesin, Matthias Hamann, and Babak Miraftab. Canonical trees of treedecompositions. Journal of Combinatorial Theory, Series B, 152:1-26, 2022.
https://doi.org/10.1016/j.jctb.2021.08.004

Reinhard Diestel and Robin Thomas. Excluding a countable clique. Journal of Combinatorial Theory, Series B, 76(1):41-67, 1999.
https://doi.org/10.1006/jctb.1998.1886

Carl Droms. Infinite-ended groups with planar Cayley graphs. Journal of Group Theory, 9(4):487-496, 2006.
https://doi.org/10.1515/JGT.2006.032

Carl Droms, Brigitte Servatius, and Herman Servatius. The structure of locally finite two-connected graphs. Electronic Journal of Combinatorics, 2, 01 1998.
https://doi.org/10.37236/1211

Martin J. Dunwoody. The accessibility of finitely presented groups. Inventiones Mathematicae, 81:449-458, 1985.
https://doi.org/10.1007/BF01388581

Martin J. Dunwoody. Planar graphs and covers. arXiv preprint arXiv:0708.0920, 2007.

Martin Grohe. Quasi-4-connected components. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 8:1-8:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.

Matthias Hamann. Planar transitive graphs. Electronic Journal of Combinatorics, 25:4.8, 2015.
https://doi.org/10.37236/7888

Matthias Hamann. Accessibility in transitive graphs. Combinatorica, 38(4):847-859, 2018.
https://doi.org/10.1007/s00493-017-3361-1

Neil Robertson and Paul Seymour. Graph minors. XVI. Excluding a non-planar graph. Journal of Combinatorial Theory, Series B, 89(1):43-76, 2003.
https://doi.org/10.1016/S0095-8956(03)00042-X

John Stallings. Group theory and three-dimensional manifolds. Yale University Press, 1972.

Carsten Thomassen. The Hadwiger number of infinite vertex-transitive graphs. Combinatorica, 12:481-491, 1992.
https://doi.org/10.1007/BF01305240

Carsten Thomassen and Wolfgang Woess. Vertex-transitive graphs and accessibility. Journal of Combinatorial Theory, Series B, 58(2):248-268, 1993.
https://doi.org/10.1006/jctb.1993.1042

W.T. Tutte. Graph Theory. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1984.

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Louis Esperet, Ugo Giocanti, Clément Legrand-Duchesne

PDF