Title: Transversal polynomial of covers of graphs
Presented By: Krystal Guo, Université de Montréal and Centre de Recherches Mathématiques

Abstract:
We explore the interplay between algebraic combinatorics and some algorithmic problems in graph theory. We define a polynomial with connections to correspondence colouring, a recent generalization of list-colouring, and the Unique Games Conjecture. Given a graph G and an assignment of elements of the symmetric group S_r to the edge of G, we define a cover graph: there are sets of r vertices corresponding each vertex of G, called fibres, and for each edge uv, we add a perfect matching between the fibres corresponding to u and v. A transversal subgraph of the cover is an induced subgraph which has exactly one vertex in each fibre. In this setting, we can associate correspondence colourings with transversal cocliques and unique label covers with transversal copies of G. We define a polynomial which enumerates the transversal subgraphs of G with k edges. We show that this polynomial satisfies a contraction-deletion formula. We are able to evaluate this polynomial at -r+1 modulo r^n, despite the complexity of computing this polynomial. This is joint work with Chris Godsil and Gordon Royle.