5
$\begingroup$

A theorem in graph theory is as the following,

Let $G=(V,E)$ be a finite graph where $V$ is the set of vertexes and $E$ is the set of edges. Then there exists a vertex subset $W$, i.e. $W \subset V$, such that the number of edges connecting $W$ and $W^C$ is at least $\frac{|E|}{2}$, where $W^C = V\backslash W$ and $|E|$ is the total number of edges in the graph $G$.

The question is to prove this theorem by a probabilistic approach.

My idea is as follows: Let $|V|=n,|W|=m$, then the maximum number of possible edges between $W,W^C$ is $m\times(n-m)$. The maximum number of possible edges in graph $G$ is $C_n^2 = \frac{n!}{2!\times(n-2)!}$. We can treat the edges as if they were randomly scattered in the $C_n^2$ positions, and with probability $p=\frac{m\times(n-m)}{C_n^2}$ one edge would connect $W,W^C$.

Then it is like a Bernoulli trial of $|E|$ times with success probability $p=\frac{m\times(n-m)}{C_n^2}$, and the probability there are at least $\frac{|E|}{2}$ edges connecting $W,W^C$ is $\sum\limits_{k = \left\lceil {\frac{1}{2}|E|} \right\rceil }^{|E|} {C_{|E|}^k{p^k}{{(1 - p)}^{|E| - k}}} $. But this probability is for a particular $W$. We need to show with probability there exists one or more such $W$ satisfying the conditions of the above-mentioned theorem. I got stuck here. Anyone can help with this proof? Thank you!

$\endgroup$
  • 1
    $\begingroup$ It's often easier to think about the expected number of edges across a random cut instead of the specific probabilities. Can you show that the expected number of edges connecting $W$ and $W^C$ is $\frac{|E|}{2}$? $\endgroup$ – Michael Biro Oct 21 '15 at 17:06
  • $\begingroup$ @MichaelBiro Thank you for the suggestion. I kind of got it. So for any $W$ of size $m$, the expectation of number of edges bridging $W$ and $W^C$ is simply $p|E|$ where $p=\frac{m\times(n-m)}{C_n^2}=\frac{2m(n-m)}{n(n-1)}$. We only need to show $p\ge \frac{1}{2}$ for some $m=1,2,...,n-1$, which is now a trivial problem, right? $\endgroup$ – Sherry Oct 21 '15 at 18:04
  • $\begingroup$ @MichaelBiro The response from my professor is that using expectation might not be rigorous. The objective is to show with probability 1 there exists $W$ st. there are at least half of the edges laying between $W$ and $W^C$ (and the expectation approach I show in the previous comment does support a guess that such $W$ should be of size $|V|/2$). However, the expectation of number of edges exceeding $|E|/2$ only implies with positive probability that there exists such $W$. Can you help think again about the problem? Thank you! $\endgroup$ – Sherry Oct 23 '15 at 1:57
  • $\begingroup$ If there is a positive probability of selecting a $W$ with that property, then there must exist a $W$ with that property. This is the heart of the probabilistic method - it uses probability to prove something with certainty. $\endgroup$ – Michael Biro Oct 23 '15 at 2:01
  • 1
    $\begingroup$ @MichaelBiro From my understanding, the graph is finite, so with positive probability that there are at least half edges are placed between $W$ and $W^C$ does not guarantee this event happens based on my "random edge placing". So probably my way of modeling the problem is not correct. $\endgroup$ – Sherry Oct 23 '15 at 2:09
6
+100
$\begingroup$

Take the graph $G = (V,E)$ and for each vertex, randomly select whether it will lie in $W$ with independent probability $p = \frac{1}{2}$. For each edge $e_i \in E$, define the random variable $X_i$, which is $1$ if $e$ connects $W$ to $W^C$, and $0$ otherwise. Then, $\mathbb{P}(X_i = 1) = \frac{1}{2}$, and $\mathbb{E}(X_i) = \frac{1}{2}$.

By linearity of expectation: $$\mathbb{E}(\text{number of edges connecting $W$ and $W^C$}) = \mathbb{E}(\sum X_i) = \sum E(X_i) = \sum \frac{1}{2} = \frac{|E|}{2}$$

Since the expected number of edges crossing the cut is $\frac{|E|}{2}$, there must be at least one choice of $W$ that has at least $\frac{|E|}{2}$ edges crossing the cut.

You can see that the claim holds with certainty because if you assume that all possible choices for $W$ have fewer than $\frac{|E|}{2}$ edges crossing the cut, then we get the contradictory:

$$\mathbb{E}(\text{number of edges connecting $W$ and $W^C$}) < \frac{|E|}{2}$$

ETA: To those who are still confused - here is a small explicit example: Suppose $V = \{v_1, v_2\}$ and $E = \{(v_1,v_2)\}$.

We consider all possible choices for $W$, where vertices are independently placed in $W$ with probability $\frac{1}{2}$:

  1. $W = \emptyset$. No edges cross the cut. This has probability $\mathbb{P}(v_1 \notin W \cap v_2 \notin W) = \frac{1}{2}\cdot \frac{1}{2} = \frac{1}{4}$.
  2. $W = \{v_1\}$. One edge crosses the cut. This has probability $\mathbb{P}(v_1 \in W \cap v_2 \notin W) = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$.
  3. $W = \{v_2\}$. One edge crosses the cut. Again, this has probability $\mathbb{P}(v_1 \notin W \cap v_2 \in W) = \frac{1}{4}$.
  4. $W = \{v_1,v_2\}$. No edge crosses the cut. Again, probability is $\frac{1}{4}$.

Then, $\mathbb{P}((v_1,v_2) \textrm{ crosses the cut}) = \frac{1}{2}$ and the expected number of crossing edges is $$0\cdot \frac{1}{4} + 1\cdot \frac{1}{4}+1\cdot \frac{1}{4}+0\cdot \frac{1}{4} = \frac{1}{2} = \frac{|E|}{2}$$

If all of the possibilities had fewer than $\frac{|E|}{2}$ edges crossing the cut, the expectation would have to be less than $\frac{|E|}{2}$. Therefore, there must be at least one choice for $W$ such that at least $\frac{|E|}{2}$ edges crosses the cut. In this case, one such choice is $W = \{v_1\}$.

$\endgroup$
  • $\begingroup$ How do you get $P(X_i=1)=1/2$? $\endgroup$ – Tony Oct 23 '15 at 3:33
  • $\begingroup$ Thanks for you reply. I still have trouble understanding your solution. For example, given random variables $X_i, i=1,2,...,n$ st. $(X_1+X_2+...+X_n)/n > a$, then I can surely see one of the X_i must take a value larger than $a$ no matter what the realization is. However, I don't understand why one of $X_i$ must be larger than $a$ provided $\Bbb{E}X_i>a$, or $\Bbb{E}((X_1+X_2+...+X_n)/n) > a$. Could you help add more details in your answer? $\endgroup$ – Sherry Oct 23 '15 at 5:24
  • $\begingroup$ @Tony If edge $e_i = (a,b)$ then $\mathbb{P}(X_i = 1) = \mathbb{P}((a \in W \cap b \in W^C) \cup (a \in W^C \cap b \in W)) = \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{2}$. $\endgroup$ – Michael Biro Oct 23 '15 at 11:28
  • $\begingroup$ @Sherry If every cut has fewer than $\frac{|E|}{2}$ edges crossing it then $\mathbb{E}(\textrm{number of edges connecting $W$ and $W^c$}) =\sum_{i = 0}^{|E|} i \cdot \mathbb{P}(\textrm{$i$ edges connect $W$ and $W^C$}) < \sum_{i = 0}^{|E|} \frac{|E|}{2} \cdot \mathbb{P}(\textrm{$i$ edges connect $W$ and $W^C$})= \frac{|E|}{2} \sum_{i = 0}^{|E|} \cdot \mathbb{P}(\textrm{$i$ edges connect $W$ and $W^C$}) = \frac{|E|}{2}$. This directly contradicts the calculation that the expectation is $\frac{|E|}{2}$. This means that at least one $W$ must be crossed by at least $\frac{|E|}{2}$ edges. $\endgroup$ – Michael Biro Oct 23 '15 at 11:34
  • $\begingroup$ @MichaelBiro The probability seems not trivially $1/2$ for every $X_i$ because edges cannot overlap. I assume you let $|W|=|V|/2$? Every time one edge $e$ connects $W$ and $W^C$, then all forthcoming edges cannot overlap $e$. $\endgroup$ – Tony Oct 23 '15 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.