Aleksander Malnič (Pef UL, Slovenija): Algorithmic and complexity aspects of lifting automorphisms

Datum objave: 23. 3. 2010
Seminar za teorijo grup in kombinatoriko
Četrtek, 1. 4. 2010, od 17h do 19h, učilnica 016, Pedagoška fakulteta Univerze v Ljubljani
Povzetek: Combinatorial theory of graph covers emerged approximately forty years ago in the context of maps on surfaces, with the final solution of the long standing Heawood's Map Colour Problem as the primary incentive. It soon  became  an indispensable tool in Algebraic graph theory as well --  mostly due to problems such as  classification of graphs and maps on surfaces in terms of their symmetries. An important  topic in this setting is the problem of lifting automorphisms; indeed, one has good control over  symmetries of the covering graph provided that  enough many automorphisms of the base graph lift. In the talk I'll  discuss  certain algorithmic and complexity problems related  to liftings.