Past exam of the computer science course of the University of Oxford / 2023 / Combinatorial optimisation / 1 / d

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.

No. Take the hypergraph with $V=\{a,b\}$ and its single hyperedge $\{a,b\}$ of weight $1$. Then $\{a\}\subseteq V$ but $f(\{a\})=1>0=f(V)$, violating the monotone set function property. This example already has strictly positive weights.

No for arbitrary signed weights. Give the same single hyperedge weight $-1$. For $A=\{a\}$ and $B=\{b\}$,This directly violates the defining inequality for a submodular set function.

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$.