Combinatorics of minimum cuts and network reliability

David Karger


April 9,
refreshments at 3:45pm


We will survey some past work upper bounding the number of cuts in a graph whose value (number of edges) is close to the minimum cut value. We describe two distinct techniques that give an upper bound, tight to within a constant factor, on this quantity as a function of the number of graph vertices and the value of the cut.

With this bound in hand, we generalize a classical result of Erdos and Renyi, that a random graph on n vertices is connected with high probability once it has n log n edges. We show that a similar result holds for random edge-subgraphs of any graph: if the expected number of edges crossing each cut exceeds log n, then the subgraph will be connected with high probability. These results generalize to yield tight approximations to the Tutte Polynomial on a large region of the Tutte Plane.

Speaker's Contact Info: karger(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on April 02, 2003 at 01:03 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.