= Solution
\b[With nonnegative weights, the <hypergraph cut function> is a <symmetric set function> and a <submodular set function>, but need not be a <monotone set function>.] The proofs of symmetry and failure of monotonicity in (i) and (ii) still apply.
For <submodularity>, write $f(S)=\sum_{e\in E}w(e)q_e(S)$, where $q_e(S)$ is the <indicator function> that $e$ meets both sides. Fix $x\notin S$. If $x\notin e$, its <marginal increment> is zero. If $x\in e$, let $m=|e|\geq2$ and $j=|S\cap(e\setminus\{x\})|$. Its <marginal increment> is
$$
\Delta_x q_e(S)=
\begin{cases}
1,&j=0,\\
0,&0<j<m-1,\\
-1,&j=m-1.
\end{cases}
$$
For $m=2$, the middle case is absent. As $S$ grows without acquiring $x$, $j$ can only increase, so these <marginal increments> can only decrease. Each $q_e$ therefore satisfies <diminishing returns>. Multiplying by $w(e)\geq0$ and summing preserves the inequality, proving <submodularity> of $f$.
Back to article page
