The structure of quasi-transitive graphs avoiding a minor with applications to the Domino Conjecture.:00

-- Ugo Gioccanti (G-SCOP (Grenoble))

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.

Category: seminars
Tags: Team seminar graphs