Strong orientations of graphs and Cheeger’s inequality

02/09/2016 - 12:15pm
02/09/2016 - 1:10pm
Sinan Aksoy (UCSD)

In this talk, we establish mild conditions under which almost all of an undirected graph's orientations are strongly connected. Unless prohibitively large, a minimum degree requirement alone is insufficient; it neither suffices to only control a graph's “bottleneck” through an isoperimetric condition. However, we prove that a mild combination of these properties ensures (almost all) a graph's orientations are strongly connected. We provide constructions to show these conditions are, up to a small factor, best possible. We will also discuss how the isoperimetric condition can be reinterpreted as a spectral condition via Cheeger’s inequality.

Millikan 2099, Pomona College