02/09/2016 - 12:15pm

02/09/2016 - 1:10pm

Speaker:

Sinan Aksoy (UCSD)

Abstract:

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.

Where:

Millikan 2099, Pomona College