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 LjubljaniPovzetek: 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.