Rutgers Discrete Mathematics Seminar

Title: Existence and applications of independent systems of representatives

Speaker: Andrew King, Columbia University

Date: Tuesday, March 22, 2011 2:00pm

Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ


Given a graph whose vertices are partitioned into r sets, an independent system of representatives (ISR) is a stable set intersecting each of these partition sets. In this talk I will discuss several existence conditions for an ISR, as well as some covering/colouring results and applications to other problems. In particular, I will discuss a new generalization of Haxell's existence condition; this new condition is motivated by the question of when we can find a stable set hitting every maximum clique in a graph.