So this is short optional video, 
really just for fun, I want to point
out an interesting consequence tracking
algorithm has about a
problem that is in pure graph theory. So,
to motivate the question, I want to remind
you of something we discussed in passing,
which is that a graph may have more than
one minimum cut. So, there may be distinct
cuts which are tied for the fewest number
of crossing edges. For a concrete example,
you could think about a tree. So, if you
just look at a star graph, that is hubs and
spokes, it's evident that if you isolate
any leaf by itself, then you get a minimum
cut with exactly one crossing edge. In
fact, if you think about it for a little
while, you'll see that in any tree you'll
have N-1 different minimum cuts,
each with exactly one crossing edge. >>The
question concerns counting the number of
minimum cuts. Namely, given that a graph
may have more than one minimum cut, what
is the largest number of minimum cuts that
a graph with N vertices can have? We know
the answer is at least N-1. We
already discussed how trees have N-1 distinct minimum cuts. We know the
answer at most something like 2^N,
because a graph only has roughly 2^N
cuts. In fact, the answer is both
very nice and wedged in between. So the
answer is exactly N choose 2, where N is
the number of vertices. This is also known
as N(N-1)/2. So
it can be bigger than it is in trees, but
not a lot bigger. In particular, graphs
have only; undirected graphs have only
polynomially many minimum cuts.
And that's been a useful fact in a number
of different applications. So, I'm going
to prove this back to you. All I need is
one short slide on the lower bound and
then one slide for the upper bound, which
follows from properties of the random
contraction algorithm. >>So for the lower
bound, we don't have to look much beyond
our trees example. We're just gonna look
at cycles. So for any value of N, consider
the N cycle. So here, for example, is the N
cycle with N = 8. That would be
an octagon. And the key observation is
that, just like in the tree, how
moving each of the N-1 edges
breaks the tree into two pieces and
defines the cut. With a cycle, if you
remove just one edge, you don't get a cut.
The thing remains connected, but if you
remove any pair of edges, then that
induces a cut of the graph, corresponding
to the two pieces that will remain. No matter
which pair of edges you remove, you get a
distinct pair of groups, distinct cuts.
So ranging overall N choose 2
choices of pairs of edges, you generate
N choose 2 different cuts. Each of
these cuts has exactly two crossing edges,
and it's easy to see that's the fewest
possible. >>So that's the lower bound, which
was simple enough. Let's now move on to
the upper bound, which, a purely
count-all fact will follow from an
algorithm. So consider any graph that has
N vertices, and let's think about the
different minimum cuts of that graph. What
we're going to use is that the analysis of
the contraction algorithm proceeded in a
fairly curious way. So remember how we
define the success probability of a
contraction algorithm. We fixed up front,
some min cut (A, B). And we defined the
contraction algorithm, the basic
contraction algorithm, before the repeated
trials. We defined the contraction
algorithm as successful, if and only if it
output the minimum cut (A, B) that we
designated upfront. If it output some
other minimum cut, we didn't count it. We
said nope, that's a failure. So we
actually analyzed a stronger property than
what we were trying to solve, which is
outputting a given min cut (A, B) rather than
just any/all min cut. So how is that
useful? Well, let's apply it here. For each
of these T minimum cuts of this graph, we
can think about the probability that the
contraction algorithm outputs that particular
min cut. So we're gonna instantiate the
analysis with a particular minimum cut (Ai, Bi). And what we proved in the analysis
is that the probability that the algorithm
outputs the cut (Ai, Bi), not just any/all
min cut. But, in fact, this exact
cut (Ai, Bi) is bounded below by. We, in
the end, we made a sloppy inequality. We
said it's at least 1/(N^2). But
if you go back to the analysis, you'll see
that it was, in fact, 2/N(N-1),
also known as 1/(N choose 2).
So instantiating the contraction
algorithm success probability analysis
without all of the repeated trials
business, we show that for each of these T
cuts, for each fixed cut (Ai, Bi), the
probability that this algorithm outputs
that particular cut is at least 1/(N choose 2).
>>Let's introduce a name for
this event, the event that the contraction
algorithm outputs the Ith min cut. Let's
call this Si. The key observation is that
the Sis are disjoint events. Remember an
event is just a subset of stuff that could
happen. So one thing that could happen is
that the algorithm outputs the Ith main
cuts, and by this joint, we just mean that
there is no outcome that in a given pair
of events. And that's because the
contraction algorithm at N to the [inaudible],
once it makes its conflicts, it
outputs a single cut is a distinct cut. It
can only output a dest one of them. >>Why is
it important that these Sis are disjoint
events? Well, with disjoint events, the
probabilities <i>add</i> the probability of the
union of a bunch of disjoint events is the
sum of the probabilities of constituent
events. If you want to think about this
pictorially, and just draw a big box,
denoting everything that could happen
omega, and then these SIs just these
[inaudible] that don't overlap. So S1, S2, S3,
and so on. Now the sum or probabilities of
this joint events can sum to, at most,
1, right? The probability of all of
omega is 1, and these SIs have not
overlap and are packed into omega, so the
sum of their probabilities is gonna be
smaller. >>We're adding up formally. We have
that the sum of the probabilities. Which
we can lower bound by the number of
different events. And remember there are T
different min cuts for some parameter T.
For each min cut (Ai, Bi), a lower bound of
the probability that, that could spit out
as output is 1/(N choose 2). So a
lower bound on the sum of all of these
probabilities is the number of them, T
times the probability lower bound,
1/(N choose 2), and this has got to be
at most 1. Rearranging, what do we find?
T, the number of different mid-cuts, is
bounded above by N choose 2. Exactly the
lower bound provided by the N cycle. The N
cycle has N choose 2 distinct minimum
cuts. No other graph has more. Every graph
has only a polynomial number indeed, at
most a quadratic number of minimum cuts.