= Hypergraph cut function
{title2=$f(S)=\sum_{e:\,e\cap S\ne\varnothing,\ e\setminus S\ne\varnothing}w(e)$}
For a <weighted hypergraph>, the <hypergraph cut function> totals the weights of <hyperedges> meeting both a <subset> and its complement. It is a <normalised set function> and a <symmetric set function>. With nonnegative weights it is a <nonnegative function> and a <submodular set function>. It is generally not a <monotone set function>: a single two-element <hyperedge> of weight one has cut value one on either <singleton>, but zero on the whole <ground set>.
\b[Proof of <submodularity> for nonnegative weights.] For one <hyperedge> $e$ of size at least two, let $q_e$ indicate whether it is split. Adding $x\notin e$ has zero <marginal increment>. For $x\in e$, with $x\notin S$, the <marginal increment> is $1$ if $S\cap(e\setminus\{x\})$ is empty, $-1$ if it equals $e\setminus\{x\}$, and zero otherwise. These values can only decrease under inclusion of $S$. Thus <diminishing returns> holds for $q_e$, and taking a nonnegative weighted sum preserves it. For a <singleton> or empty <hyperedge>, $q_e$ is identically zero. A negative-weight two-element <hyperedge> gives a counterexample to <submodularity>: its two <singleton> values sum to a negative number, while the values at their <union> and <intersection> are zero.
Back to article page
