DMS Combinatorics Seminar

Speaker: Craig Larson (Virginia Commonwealth U)

Title: Independent Sets in Graphs & LP Theory

Abstract: Integer programming, together with linear programming relaxations of integer programs, were used beginning in the 60s as a tool for finding maximum independent sets in graphs and bounding the independence number.  Several attractive results appeared in the 70s and 80s---often in linear programming journals. Many related ideas reappeared later in a purely graph theoretic context and several essentially equivalent theorems were rediscovered and reproved. This talk will survey these ideas, connections and theorems.