Combinatorics of minimum cuts and network reliabilityDavid KargerMIT
April 9,

ABSTRACT


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 edgesubgraphs 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. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

