I just proved that, given a simple undirected graph $G=(V,E)$ with $n\geq 2$ vertices and $e$ edges, there exists a partition of the vertex set $V=A\cup B$ such that the number of edges in $A \times B$ is at least $e/2$. Now, on the course notes it is written that if $n=2k$ is even, than clearly the bound $e/2$ can be improved to $\frac{k}{2k-1} \cdot e$. Can anyone give me a clue about why this is "clear"? Thank you
3
-
1$\begingroup$ It's not clear to me. How does your proof of the $e/2$ bound go? $\endgroup$– bofCommented Sep 27, 2019 at 7:40
-
$\begingroup$ In order to partition a graph $G=(V,E)$ we proceed as follows: 1)take any sets $A,B$ such that $V=A\cup B$ and $A \cap B=\emptyset$; 2)consider $a \in A$: if it has strictly more edges in $A$ than in $A\times B$, then move it to $B$. $\endgroup$– mat95Commented Sep 27, 2019 at 13:40
-
$\begingroup$ (Edited) Claim: this process stops when the number of edges in $A\times B$ is at least $e/2$. Proof: call $d_X(v)$ the number of edges connecting a vertex $v$ to vertices $w\in X$. Then you have that the number of edges in $A\times B$ is $1/2(\sum_{a\in A}d_A(a)+\sum_{b\in B}d_B(b))$. Now, the total number of edges in the graph $G$ is $1/2(\sum_{a\in A}(d_A(a)+d_B(a))+\sum_{b\in B}(d_A(b)+d_B(b)))$ and, since $d_A(a)\leq d_B(a)$ and $d_A(b)\leq d_B(b)$ by construction, you can conclude. $\endgroup$– mat95Commented Sep 27, 2019 at 18:38
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I suspect that their intended proof for $e/2$ was as follows.
Choose a random partition, putting $\lfloor n/2\rfloor$ random vertices in $A$ and the remaining $\lceil n/2\rceil$ in $B$. Now for each vertex $x$, at least half of the other vertices are in the opposite set. Thus if $xy$ is an edge, the probability that $xy$ goes between $A$ and $B$ is at least $1/2$. It follows that the average number of such edges is at least $e/2$, so there must be some partition that is at least this good.
Doing it that way, if $n=2k$ then for every vertex exactly $k$ of the other $2k-1$ are in the opposite set, and you get the "clear" improvement they suggest. (You can in fact get a similar improvement for odd $n$ too, but it needs an extra step.)
answered Sep 27, 2019 at 16:20
$\begingroup$
$\endgroup$
This is a comment, but I can't fit it in a comment box.
It's clear that if $e\neq0$, there must be strictly more than half the edges in $A\times B$, but I don't see how to get the explicit bound. By construction, every vertex in $A$ has at least half its neighbors in $B$, and vice versa. Suppose that exactly half the edges of $G$ belong to $A\times B$. Then any of $A$ has exactly half its neighbors in $B$, so we can move it to $B$ without changing the number of edges in $A\times B$. We can continue in this way until $A$ is empty. Then it is still the case half the edges are in $A\times B$, so $e=0$.
So if $e\neq0$, there must be a vertex $v$ that has more than half its neighbors in the other set. If the degree of $v$ is even then it has at least two more neighbors in the other set. If the degree of $v$ is odd, then there must be at least one more vertex of odd degree. If $e_1$ is the number of edges in $A\times B$ then we see that $$e_1\geq(e-e_1)+2\implies e_1\geq{e+2\over2},$$ but that's a long way short of the "clear" bound, and it doesn't use "$n$ is even."
answered Sep 27, 2019 at 15:40