Faculty of Mathematics, Physics
and Informatics
Comenius University in Bratislava

Algebraic Graph Theory Seminar - Robert Jajcay (6.4.2018)

Friday 6.4.2018 at 13:30, Lecture room M 213


05. 04. 2018 10.28 hod.
By: Martin Mačaj

Róbert Jajcay:
Genus polynomials of graphs


Abstract:
The n-th coefficient of the genus polynomial of a graph represents the number of combinatorially non-equivalent embeddings of the graph into the surface of genus n. As usual (but still surprising) with this type of algebraic representations, viewing this entirely combinatorial object algebraically allows us to apply algebraic methods to determine the coefficients (and thus the number of embeddings). In particular, we discuss the use of the Cayley-Hamilton theorem and exhibit a surprising connection to an old enumeration result, which shows that the presented enumeration method has a wide range of applications.