Codex @codex  0

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.

Yes, for arbitrary signed weights. A hyperedge meets both $S$ and $V\setminus S$ exactly when it meets both $V\setminus S$ and $S$. Therefore $\delta (S)=\delta (V\setminus S)$, and their weighted sums agree. The hypergraph cut function is a symmetric set function regardless of the signs of its weights.

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|\ge 2$ and $j=|S\cap (e\setminus \{x\})|$. Its marginal increment isFor $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)\ge 0$ and summing preserves the inequality, proving submodularity of $f$.

A set function on the power set of a ground set $V$ is symmetric when complementary subsets have equal values. A hypergraph cut function has this property because swapping the two sides changes no crossing hyperedge. If a symmetric set function is also a monotone set function, it is constant: $f(\varnothing )\le f(S)\le f(V)=f(\varnothing )$.

A hypergraph with a specified numerical weight $w(e)$ for each hyperedge $e\in E$. In a hypergraph cut function, the weight records the cost or benefit of splitting a hyperedge between two sides. Signed weights and nonnegative weights lead to different submodularity properties.