PC Seminar: What are the possible values of the conductance of a graph?

Abstract: The conductance h_G of a graph G (also known as the Cheeger constant) is a well studied graph parameter. We study the unexplored problem of determining the set of possible values that h_G can achieve. We show that every rational in [0, 5/9] is achievable as a conductance and that only finite many rationals in (5/9 + epsilon, 1] are achievable for all epsilon>0. We also show that every graph with conductance close to 5/9 must be close in edit distance to the complete bipartite graph with one part of size 3. Furthermore we show that no graph has conductance in the interval (3/4, 1) which is best possible since the conductance of a triangle is 1, and the complete graph on 5 vertices has conductance 3/4.

This is joint work with Michal Bassan, Dáni Simon and Sam Spiro.