1
$\begingroup$

Given a graph $G$ on $n$ vertices and $m$ edges a standard existence proof for a cut of size $\geq \frac{m}{2}$ is to randomly assign vertices to a cut $S\subseteq G(V)$ and then in expectation half of the edges cross the cut from $S$ to $\bar{S}.$ Again using a similar (or perhaps even the same) randomized method, how does one increase the existence bound to $\frac{mn}{(2n-1)}$? I've attempted using the same vertex assignment scheme but have not been able to improve upon $\frac{m}{2}.$

$\endgroup$
  • 2
    $\begingroup$ Look for Noga Alon's Probabilistic Methods. This question is a theorem or an exercise in the first two chapters of the book, I believe. There is a hint there, I think, suggesting that one looks at subgraphs on $\lfloor n/2\rfloor$ vertices. $\endgroup$ – Batominovski Aug 18 '16 at 23:53
1
$\begingroup$

It's quite simple...

Partition verticies into two (almost) equal size parts uniformly randomly.

What is the expected value of cut size?

Every edge is in cut with probability $\frac{n}{(2n-1)}$ because after choosing the first vertex it remains $n$ choose for the second one among $2n-1$ remaining verticies.

Now use the same idea to solve it...

$\endgroup$

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.