The structure of quasi-transitive graphs avoiding a minor with applications to the Domino Conjecture.:00
Time: 00:00 -- Location: LRI, 455
summary: An infinite graph is quasi-transitive if its automorphism group has finitely many orbits.
In this talk, I will present 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 (countable) minor has a canonical
tree-decomposition of bounded adhesion with finitely many edge-orbits, whose torsos are finite
or planar. I will take some time to explain every notion involved, and especially what is a
canonical tree-decomposition, and why this notion is crucial to work on quasi-transitive graphs.
The proof of our result is mainly based on a combination of a result of Thomassen (1992) together
with an extensive study of Grohe (2016) on the properties of separations of order 3 in finite graphs.
I will briefly sketch the main ideas of this proof.
Then I will spend some time to give some applications of this structure theorem:
— Minor-excluded finitely generated groups are accessible (in the group-theoretic sense) and finitely presented, which extends classical results on planar groups.
— 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).
This is a joint work with Louis Esperet and Clément Legrand-Duchesne.