1
$\begingroup$

The following is a question from a past paper:

Let $G$ be a graph with an even number of vertices. Show that the vertices of $G$ can be partitioned into two parts $A$ and $B$ of equal size such that the number of edges between $A$ and $B$ is strictly larger than $\frac{|E|}{2}$.

Hint: Consider a random partition of the vertices into two parts of the same size.

I think I have shown that such a partition exists if the statement were for the number of edges between $A$ and $B$ is at least $\frac{|E|}{2}$. I have done this using expectations but I am unsure of how to proceed, or if this was even the correct approach in the first place!

Solution so far:

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

Then, using the linearity of expectation:

$\mathbb{E}(number\ of\ edges\ connecting\ A\ and\ B)=\frac{|E|}{2}$

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

Assume that all possible choices for $A,B$ have fewer than $\frac{|E|}{2}$ edges crossing the partition, then we get that:

$\mathbb{E}(number\ of\ edges\ connecting\ A\ and\ B)<\frac{|E|}{2}$

which is a contradiction.

I am unsure how to proceed to get to the required strict inequality and would appreciate any hints on that, and also, if this is the wrong approach or there is something wrong with my work so far, a different answer would be appreciated as there are no mark schemes!

Thank you in advance!

$\endgroup$
2
$\begingroup$

Your derivation is not correct, because if you randomly assign a vertex to one of $A$ and $B$, it is not guaranteed the $A$ and $B$ obtained are of equal size.

Suppose there are $2n$ vertices in the graph. There are totally $\binom{2n}{n}$ possible partitions, in which $A$ and $B$ are of equal size. We randomly sample one of such partitions.

Now consider an edge $e = (u, v)$ of $G$. There are two possibilities such that $e$ connects $A$ and $B$: $(1)$ $u \in A, v \in B\ $; $(2)$ $u \in B, v \in A$. For either case, there are $\binom{2n - 2}{n-1}$ corresponding partitions.

Let $X_e$ be a random variable such that $X_e = 1$ if $e$ connects $A$ and $B$ and $ = 0$ otherwise. We have $$ \mathsf{E}(X_e) = \Pr(X_e = 1) = \frac{2\binom{2n-2}{n-1}}{\binom{2n}{n}} = \frac{n}{2n-1} > \frac{1}{2} $$ Therefore, the expected total # of edges connecting $A$ and $B$ is more than $\frac{|E|}{2}$.

$\endgroup$
  • $\begingroup$ Ah yes, thank you so much for taking the time to explain. Just out of curiosity for future problems, if the partition sets did not need to be of equal size, would my >= derivation have been correct or is there just a complete flaw in my reasoning? $\endgroup$ – mathcomp Mar 12 '17 at 9:10
  • 1
    $\begingroup$ @mathcomp Your derivation looks good to me if the question does not require the sets to be of equal size and the bound is just greater than or equal to $|E| / 2$. $\endgroup$ – PSPACEhard Mar 12 '17 at 9:26
  • $\begingroup$ Thank you so much! Your help has definitely broadened my understanding! $\endgroup$ – mathcomp Mar 12 '17 at 9:28
  • $\begingroup$ If it wouldnt be too much trouble, I am having an issue with another combinatorics question, and would appreciate any help on that too if you have the time: math.stackexchange.com/questions/2181561/… $\endgroup$ – mathcomp Mar 12 '17 at 9:30

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.