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 Waterloo 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 2Δ(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 2Δ(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, 2017Time: 3:30 pmLocation: Wean Hall 8220Note: Before the talk, at 3:10 pm, there will be tea and cookies in Wean Hall 6220. |