Tatiana Jajcayova: Inverse monoids of partial automorphisms of combinatorial structures

Datum objave: 28. 9. 2019
Seminar za diskretno matematiko
Torek, 1. 10. 2019, od 10h do 12h, Plemljev seminar, Jadranska 19

The problem of determining the full automorphism group of a combinatorial structure (for example a graph) is one of the well-known hard problems. The results involving partial automorphisms and use of inverse monoids may offer new insights into some well known and long open problems from Graph Theory, as we will illustrate with some examples.

A partial automorphism of a combinatorial structure is an isomorphism between its induced substructures. The set of all partial automorphisms of a given structure forms an inverse monoid under composition of partial maps. In our presentation, we describe the algebraic structure of such inverse monoids by the means of the standard tools of inverse semigroup theory, and give a characterization of inverse monoids which arise as inverse monoids of partial graph (digraph and edge-colored digraph) automorphisms.

We will also briefly mention a paper with a different approach to partial automorphisms (T. Chih & D. Plessas Graphs and Their Inverse Semigroups, Discrete Mathematics '17), as well as discuss some classical results (E. Hrushovski; Extending Partial Isomorphisms of graphs, Combinatorica '92) which coincides with our approach to partial automorphisms, and related very resent results (Eurocomb 2019) of Matej Konečný et al. on Extending partial automorphisms of n-partite tournaments.