<p>Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w_e)_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e.
$$M^+=\max\limits_{(U_1,U_2)}\left\{\sum_{e=\{u,v\}\in E\,:\,u\in U_1,v\in U_2}w_e\ :\ U_1\cup U_2=V,\ U_1\cap U_2=\emptyset\right\},$$ 
$$M^-=\min\limits_{(U_1,U_2)}\left\{\sum_{e=\{u,v\}\in E\,:\,u\in U_1,v\in U_2}w_e\ :\ U_1\cup U_2=V,\ U_1\cap U_2=\emptyset\right\}.$$ 
I'm interested in possible ratios between the difference $M^+-M^-$ and $\sum_{e\in E}\lvert w_e\rvert$. From Corollary 3.7 in the paper <a href="http://link.springer.com/article/10.1007/s10107-012-0606-z" rel="nofollow noreferrer">Some results on the strength of multilinear functions</a> it follows that $M^+-M^-\geqslant\frac{1}{n-1}\sum_{e\in E}\lvert w_e\rvert$. Taking complete bipartite graphs and choosing the weights independently and uniformly at random from $\{\pm 1\}$ we find that there are graphs with $M^+-M^-=o(1)\sum_{e\in E}\lvert w_e\rvert$.</p>

<ol>
<li>Are there better lower bounds known? Maybe under additional assumptions on the weight fun (for instance if $w_e\in\{1,-1\}$ for all $e$)?</li>
<li>What are known constructions with $M^+-M^-\leqslant f(n)\sum_{e\in E}\lvert w_e\rvert$ for some "small" function $f$? For instance, can we replace the $o(1)$ in the random construction by $O(1/n)$?</li>
</ol>

<p>Cross posted on <a href="https://mathoverflow.net/q/182510">MO</a>.</p>

CC BY-SA 3.0
2014-10-07T17:56:21.810Z
If we have, say, a line graph (or a cycle) with all equal weights, then isn't the difference zero? Or I'm missing something.
usul
CC BY-SA 3.0
2014-10-07T18:12:32.400Z
@usul A path is bipartite: you can cut all the edges. So the difference is not zero, it's $n-2$ for an $n$-node path.
Sasho Nikolov
CC BY-SA 3.0
2014-10-07T18:23:25.383Z
The random construction you describe gives $M^+ - M^- = O(n^{3/2})$ and the sum of the absolute values of the weights is $n(n-1)/2$. So $f(n) = O(1/\sqrt{n})$.
Sasho Nikolov
CC BY-SA 3.0
2014-10-08T06:32:25.190Z
FYI, you're not supposed to simultaneously cross-post: http://meta.cstheory.stackexchange.com/a/231/5038.  A standard guideline would be to only cross-post on here and MO if you get no answer on the original site after a week or so.
D.W.
<graph-theory><co.combinatorics><optimization>
lower bound for difference between max cut and min cut
Thomas Kalinowski
# lower bound for difference between max cut and min cut

(Asked by: username_0 on 2014-10-06)

Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w\_e)\_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e.
$$M^+=\max\limits\_{(U\_1,U\_2)}\left\{\sum\_{e=\{u,v\}\in E\,:\,u\in U\_1,v\in U\_2}w\_e\ :\ U\_1\cup U\_2=V,\ U\_1\cap U\_2=\emptyset\right\},$$
$$M^-=\min\limits\_{(U\_1,U\_2)}\left\{\sum\_{e=\{u,v\}\in E\,:\,u\in U\_1,v\in U\_2}w\_e\ :\ U\_1\cup U\_2=V,\ U\_1\cap U\_2=\emptyset\right\}.$$
I'm interested in possible ratios between the difference $M^+-M^-$ and $\sum\_{e\in E}\lvert w\_e\rvert$. From Corollary 3.7 in the paper [Some results on the strength of multilinear functions](http://link.springer.com/article/10.1007/s10107-012-0606-z) it follows that $M^+-M^-\geqslant\frac{1}{n-1}\sum\_{e\in E}\lvert w\_e\rvert$. Taking complete bipartite graphs and choosing the weights independently and uniformly at random from $\{\pm 1\}$ we find that there are graphs with $M^+-M^-=o(1)\sum\_{e\in E}\lvert w\_e\rvert$.

1. Are there better lower bounds known? Maybe under additional assumptions on the weight fun (for instance if $w\_e\in\{1,-1\}$ for all $e$)?
2. What are known constructions with $M^+-M^-\leqslant f(n)\sum\_{e\in E}\lvert w\_e\rvert$ for some "small" function $f$? For instance, can we replace the $o(1)$ in the random construction by $O(1/n)$?

Cross posted on [MO](https://mathoverflow.net/q/182510).

**Tags:** graph-theory, co.combinatorics, optimization

> **Comments:**
> **username_1**: If we have, say, a line graph (or a cycle) with all equal weights, then isn't the difference zero? Or I'm missing something.  
> **username_2**: @username_1 A path is bipartite: you can cut all the edges. So the difference is not zero, it's $n-2$ for an $n$-node path.  
> **username_2**: The random construction you describe gives $M^+ - M^- = O(n^{3/2})$ and the sum of the absolute values of the weights is $n(n-1)/2$. So $f(n) = O(1/\sqrt{n})$.  
> **username_3**: FYI, you're not supposed to simultaneously cross-post: http://meta.cstheory.stackexchange.com/a/231/5038.  A standard guideline would be to only cross-post on here and MO if you get no answer on the original site after a week or so.  

---

## 0 answers

