Séminaire Topologies
Le 07 juin 2018 à 11:15 - salle 430

Moffatt Iain

The Tutte polynomial of a graph and its extensions

This talk will focus on graph polynomials, which are polynomial valued graph invariants. Arguably, the most important and best studied graph polynomial is the Tutte polynomial. It is important not only because it encodes a large amount of combinatorial information about a graph, but also because of its applications to areas such as statistical physics (as the Ising and Potts models) and knot theory (as the Jones and homfly polynomials).

Because of its importance the Tutte polynomial has been extended to various classes of combinatorial objects. For some objects there is more than one definition of a "Tutte polynomial". For example, there are three different definitions for the Tutte polynomial of graphs in surfaces: M. Las Vergnas' 1978 polynomial, B. Bollobás and O. Riordan's 2002 ribbon graph polynomial, and V. Kruskal's polynomial from 2011. On the other hand, for some objects, such as digraphs, there is no wholly satisfactory definition of a Tutte polynomial. Why is this? Why are there three different Tutte polynomials of graphs in surfaces? Which can claim to be the Tutte polynomial of a graph in a surface? More generally, what does it mean to be the Tutte polynomial of a class of combinatorial objects? In this talk I will describe a way to canonically construct Tutte polynomials of combinatorial objects, and, using this framework, will offer answers to these questions.