Algebraic Graph Theory Seminar - Tatiana Jajcayová (1.3.2019)
March 1st 2019 at 13:00, Room IX at FMFI UK
Speaker: Tatiana Jajcayová (Comenius University)
Title: Inverse semigroups of partial automorphisms of graphs
Time and place: 1.3.2019, 13:00, M/IX
Abstract:
The problem of determining the full automorphism group of a combinatorial struc-ture (for example a graph) is one of the well-known computationally hard problems.The focus of our project is on an extension of the automorphism group problemto that of inverse semigroup problem. The full inverse semigroup of partial auto-morphisms of a combinatorial structure is a much richer algebraical structure thatcontains more detailed local information about the underlying object. By a partialautomorphism of a nite graph we understand an isomorphism between its vertexinduced subgraphs. The set of all partial automorphisms of a given nite graphforms an inverse monoid under composition (of partial maps).
The goal is to apply the algebraic methods of partial permutation semigroup theoryto the class of graphs that admit none or only very few automorphisms and typicallyresist the use of methods from permutation group theory. The results involvingpartial automorphisms and use of inverse monoids may o er new insights into somewell known and long open problems from Graph Theory, as we will illustrate withsome examples.
In our presentation, we will briey mention some classical results (E. Hrushovski;Extending Partial Isomorphisms of graphs, Combinatorica '92) which coincides withour approach to partial automorphisms, as well as discuss some di erent approacheswhich recently appeared (T. Chih & D. Plessas Graphs and Their Inverse Semi-groups, Discrete Mathematics '17)
This is joint work with Maria Szendrei, Nora Szakacs, and Robert Jajcay.