Section 1.1: Understanding Graph Cuts

Consider an undirected graph ( G = (V, E) ), where ( V ) represents the set of vertices with ( N ) elements, and ( E ) denotes the set of edges consisting of ( M ) elements. A cut in this graph involves partitioning the vertex set ( V ) into two subsets ( A ) and ( B ). The size of this cut is determined by the number of edges that link vertices from ( A ) to those in ( B ). For clarity, imagine a graph with 5 vertices and 6 edges, along with a cut that encompasses 5 edges.

We can assert the following claim regarding cuts in graphs. Various methods exist for proving this assertion, including a greedy algorithm that reliably computes such partitions, providing a constructive proof. Today, we will explore a proof that employs randomness. The core concept is both straightforward and brilliant: we recognize that the total number of possible bipartitions of the vertex set ( V ) is finite, specifically:

[ 2^N ]

What if we randomly select a cut from the graph and calculate the expected number of edges that are cut?

This approach may yield beneficial insights. Suppose we can ascertain the expected size ( T ) of a randomly chosen cut and find that ( T geq M/2 ). This indicates that when considering all possible cuts, the average size (i.e., the total number of edges cut across all cuts divided by the number of cuts) is at least ( M/2 ).

To elaborate, the number of distinct bipartitions indeed amounts to ( 2^N ). However, we can simplify our analysis: the number of edges cut in a partition ( (A,B) ) equals that in ( (B,A) ). Therefore, the total number of unique cuts reduces to:

[ 2^{N-1} ]

Let ( t(1), ldots, t(q) ) denote the sizes of the edges cut in all these different partitions. From our previous discussion, we can conclude that:

[ frac{1}{q} sum_{i=1}^{q} t(i) geq frac{M}{2} ]

This suggests the existence of at least one term ( t(i) ) that is greater than or equal to ( M/2 ). If we assume otherwise, stating that each ( t(j) < M/2 ) for all ( j ), we reach a contradiction, reinforcing the notion that if the expected value of a random variable equals ( Z ), then at least one instance must meet or exceed ( Z ).

The implications of this finding are profound: if the expected size of a randomly chosen cut is at least ( M/2 ), we can deterministically assert that a cut exists with a size of at least ( M/2 ). This encapsulates the essence of the Probabilistic Method, which gained prominence through the work of the remarkable Paul Erdős.

Section 1.2: Utilizing Randomness to Compute Expected Sizes

Now, let's address a potential challenge: how do we compute the expected size of a random cut? The solution is elegantly simple: we will utilize independent random coin flips. Specifically, we will demonstrate how these flips can create a uniform distribution over all possible bipartitions ( {A,B} ). The total number of such bipartitions is ( q = 2^{N-1} ). The method involves flipping a coin for each vertex ( u ) in ( V ); if the result is heads, we assign ( u ) to set ( A ), otherwise to set ( B ).

To verify this method, consider a fixed bipartition ( {A,B} ). The random process generates this exact bipartition if every vertex in ( A ) corresponds to heads and every vertex in ( B ) corresponds to tails. Given that all coin flips are independent and unbiased, the probability of generating the bipartition ( {A,B} ) is:

[ frac{1}{q} ]

However, since order does not matter, we must also account for the reverse configuration ( {B,A} ). Hence, the resulting probability of obtaining ( {A,B} ) doubles, confirming that our random process indeed generates a uniform sample from all graph cuts.

Now, we can confidently calculate the expected size ( T ) of a random cut using indicator random variables. Let ( X ) denote the size of the cut sampled from our coin flip process. The expected value ( E[X] = T ). We can list the edges of the graph as ( e(1), ldots, e(M) ), and define a random variable ( X(i) ) for each edge, where ( X(i) = 1 ) if the edge is cut, and ( 0 ) otherwise.

Through the linearity of expectation, we find:

[ E[X] = E[X(1) + X(2) + ldots + X(M)] = E[X(1)] + E[X(2)] + ldots + E[X(M)] ]

Next, we need to establish the expected value of each term in this sum. For any edge ( e = (u,v) ), the probability that it is cut arises when ( u ) is assigned to ( A ) and ( v ) to ( B ), or vice versa. The probability of ( u ) being in ( A ) and ( v ) in ( B ) is ( frac{1}{4} ) (due to independent coin flips), as is the case for the opposite configuration. Thus, the overall probability of cutting edge ( e ) is:

[ frac{1}{2} ]

This reasoning applies universally across all edges in the graph, leading us to conclude that:

[ E[X(e)] = frac{1}{2} ]

Consequently, we have shown that when sampling a cut uniformly at random, the expected size of the cut is ( frac{M}{2} ), affirming the existence of a cut with size at least ( frac{M}{2} ). This completes our proof.