About this event
LearningTORONTO 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.