DMS Combinatorics Seminar

Time: Dec 01, 2022 (02:00 PM)
Location: ZOOM



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.