 Hypergraph cut function

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.

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.