Tutte colloquium-Gary Au

Title:Worst-case instances of the stable set problem of graphs for the Lovász–Schrijver SDP hierarchy

Abstract:(Based on joint work with Levent Tunçel.)

In this talk, we discuss semidefinite relaxations of the stable set problem of graphs generated by the lift-and-project operator LS_+ (due to Lovász and Schrijver), and present some of our recent progress on this front. In particular, we show that for every positive integer k, the smallest graph with LS_+-rank k contains exactly 3k vertices. This result is sharp and settles a conjecture posed by Lipták and Tunçel from 2003.

The talk will be accessible to a general audience, and does not assume any prior knowledge of lift-and-project methods.