Zusammenfassung für den Vortrag am 02.05.2017 (10:00 Uhr)Seminar on Nonlinear Algebra
Florian Kohl (Freie Universität Berlin)
Transfer-Matrix Methods meet Ehrhart Theory
Siehe auch die Homepage der/des Vortragenden.
Counting (proper) colorings of graphs is a classical problem in combinatorics with connections to many different fields. In this talk, we want to examine proper k-colorings of graphs of the form G×Pn, where G is any graph, and where Pn is the path graph on n nodes. There are two special cases, namely (1) where k is fixed but not n, and (2) where n is fixed but not k. In (1), the number of colorings can be determined using the transfer-matrix method, and in (2), the number of colorings can be counted using the chromatic polynomial/Ehrhart theory. We will use the symmetry of G × Pn to combine the two methods to get explicit formulas (depending on k and n) counting the number of colorings and we will give a restricted version of the famous reciprocity theorem for the chromatic polynomial. Furthermore, we will describe the doubly asymptotic behavior of graphs G × Cn, where Cn is the cycle graph with n nodes as both n and k go to infinity. This is joint work with Alexander Engström.