Date and Time: 03/13/2026, 14:00--15:00

Location: 25 Park Place, Room 1441

Colloquium: Algorithms for Independent Transversals and Reconfiguration

Speaker: Penny Haxell, University of Waterloo

Speaker's website: https://uwaterloo.ca/combinatorics-and-optimization/profiles/penny-haxell

Title: Algorithms for 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 consider the algorithmic version of this question, and show
that under certain similarly minimal conditions, such 
reconfiguration paths in the space of all IT's can be found efficiently.

Speaker's biography: Penny Haxell earned a bachelor's degree in 1988 from the University of Waterloo, and completed a doctorate in 1993 from the University of Cambridge under the supervision of Béla Bollobás. Since then, she has worked at the University of Waterloo, where she was promoted to full professor in 2004.  Her research accomplishments include results on the Szemerédi regularity lemma, hypergraph generalizations of Hall's marriage theorem (see Haxell's matching theorem), fractional graph packing problems, and strong coloring of graphs.  She was the 2006 winner of the Krieger–Nelson Prize of the Canadian Mathematical Society.

Host: Yi Zhao (yzhao6@gsu.edu)