Algebraic Graph Theory Seminar - Robert Jajcay (6.4.2018)
Friday 6.4.2018 at 13:30, Lecture room M 213
By: Martin Mačaj
Genus polynomials of graphs
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.