Colloquium talk: Independent Transversals and Reconfiguration

TORONTO METROPOLITAN UNIVERSITY DEPARTMENT OF MATHEMATICS COLLOQUIUM

Dr. Penny Haxell

Combinatorics & Optimization Department, University of Waterloo

Independent Transversals and Reconfiguration

Abstract: An independent transversal (IT) of a graph G with a given vertex partition P is an independent set in G consisting of one vertex in each of the parts of P. This is a very general notion, and many problems in mathematics can be expressed by asking whether a particular graph G with a particular choice of P has an IT. Various criteria involving properties of G and P are known that will guarantee the existence of an IT in G.

More broadly, one may wish to consider the space of all IT’s for a given G and P, and investigate how they are related. For example, under what conditions is this space connected, in the sense that one can transition from any IT to any other via a sequence of single-vertex modifications? It has been shown (Buys-Kang-Ozeki, Wdowinski) that with conditions only very slightly stronger than those ensuring the existence of a single IT, this connectivity property also holds.

Here we explore further questions of this type, for example what conditions guarantee that such reconfiguration paths in the space of all IT’s are short, and whether they can be found efficiently.