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 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$.
- Are there better lower bounds known? Maybe under additional assumptions on the weight function (for instance if $w_e\in\{1,-1\}$ for all $e$)?
- 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 cstheory
