Seminár z teórie grafov - Roman Nedela (24.11.2016)

vo štvrtok 24.11.2016 o 9:50 hod. v miestnosti M/213

---

Prednášajúci: Roman Nedela (Západočeská univerzita, Plzeň)

Názov: Cayley recognition problem for graphs on 4p vertices

Termín: 24.11.2016, 9:50 hod., M/213

Abstrakt:
In the context of several algorithmic problems, we shall discuss results about the complexity of the Cayley recognition and the Cayley isomorphism problems. We shall present a new result, done in the collaboration with I. Ponomarenko, that for graphs on 4p vertices these problems can be solved in a polynomial time. In our proof, as is the case also in the recent Babai's result on the complexity of the graph isomorphism problem, the Weisfeiler- Leman stabilisation algorithm producing the smallest coherent algebra for a prescribed set of integer matrices plays an important role.

---