CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Algorithms, Combinatorics and Optimization Seminar
Penny Haxell
Title: Stability and algorithms for independent transversals

Abstract: An independent transversal (IT) in a vertex-partitioned graph G is an independent set in G consisting of one vertex in each partition class. This is a very basic notion that comes up in many combinatorial problems. There are various criteria that guarantee the existence of an IT in a given graph G. For example, if each partition class has size at least (G) then G has an IT.

We consider stability questions for independent transversals, and show in particular that if each partition class of G has size close to (G) but G does not have an independent transversal, then it contains an induced subgraph with a very special structure.

The known proofs of the criteria mentioned above do not give efficient algorithms for actually finding an IT. Here we also discuss appropriate weakenings of such results that do have effective proofs.

Date: Thursday, November 2, 2017
Time: 3:30 pm
Location: Wean Hall 8220
Note: Before the talk, at 3:10 pm, there will be tea and cookies in Wean Hall 6220.