Large Three-Way Cuts Subject:

Large Three-Way Cuts

Subject: Discrete Maths And Probabilities (CS 70)

In class, we have seen that for every graph G = (V,E) with |V| vertices and |E| edges, the vertex set V can be partitioned in two sets A,B such that the number of edges between A and B is at least |E|. Here, we'll prove a similar result for the case where we're allowed to partition V into three sets: A, B, andC. (Recall that the sets A, B, C form a partition of V iff A∪B∪C=V and A∩B = B∩C =C∩A = 0/.)

(a) Suppose we sample a random partition of V by choosing which set each vertex goes into uniformly at random from {A,B,C} independently. What is our sample space? How big is it?

(b) For two distinct vertices u, v ∈ V calculate the probability that u and v lie in different sets.

(c) Compute the expected number of edges that cross between the sets in our random partition. (An edge "crosses between the sets" if its two endpoints are in different sets.)

(d) Prove that there exists some partition (A,B,C) of V such that the number of edges that cross between the sets is at least 2|E|. 3