IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Independent sets of fixed size

  • Feb. 19, 2021
  • 2:30 p.m.

Abstract

We consider natural extremal and algorithmic problems on independent sets in sparse graphs. A conjecture of Khan states that over regular graphs, a disjoint union of complete bipartite graphs maximises the number of independent sets of any given size, and we discuss a proof of this fact for large graphs. The proof also gives an algorithm for approximating the number of independent sets of fixed size in bounded-degree graphs, though the maximum size permitted is not optimal. We then discuss a different approach to this problem that permits larger sizes, and show that the new approach is optimal by identifying a computational phase transition for the problem. Our methods are closely connected to statistical physics. These results comprise joint work with Matthew Jenssen and Will Perkins.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC