Recent results on well-balanced orientations

NEW

Problem: Reconstructed statement: for a finite set $V$, $d:2^V\to\mathbb Z_{\ge0}$ is symmetric, $d(\emptyset)=0$, and satisfies the standard connectivity-function inequalities

for all $X,Y\subseteq V$. Let

A pairing $M$ on $T_d$ is a perfect matching, and $d_M(X)$ counts matched pairs crossing $X$. The question asks whether, for every even-valued symmetric skew-supermodular $\hat R\le d$, there is $M$ with

Result: The statement is false.

Let $V=\mathbb F_2^3$. For every nonzero $a\in\mathbb F_2^3$ and $\epsilon\in\mathbb F_2$, let

Define $d:2^V\to\mathbb Z_{\ge0}$ by

Then $d$ is symmetric, $d(\emptyset)=0$, and $d(X)\equiv |X|\pmod2$. Hence $T_d=V$.

The function $d$ satisfies the two displayed inequalities. Indeed, with $h(X)=\min(|X|,8-|X|)$, $h$ is submodular and $d=h-2\mathbf 1_{\{X\text{ hyperplane}\}}$. If neither of $X,Y$ is a hyperplane, submodularity follows from that of $h$. If both are hyperplanes, they are equal, complementary, or meet in two points, and the inequality is immediate. If exactly $X$ is a hyperplane, put $a=|X\cap Y|$, $c=|V\setminus(X\cup Y)|$; a direct check using $g(t)=t$ for $t\le3$, $g(4)=2$, gives

Posimodularity follows from submodularity and symmetry.

Now take $\hat R\equiv0$, which is even-valued, symmetric, skew-supermodular, and satisfies $\hat R\le d$.

Let $M$ be any pairing of $V$, with pairs $\{x_i,y_i\}$, $i=1,\dots,4$. Set $z_i=x_i+y_i\neq0$. Since $\sum_{v\in\mathbb F_2^3}v=0$, we have $\sum_i z_i=0$. Every linear dependence among the $z_i$’s has even size, so there exists nonzero $a\in\mathbb F_2^3$ with

Thus the hyperplane $H=\{x:a\cdot x=0\}$ contains exactly one endpoint of every matched pair, so

But $H$ is one of the special hyperplanes, so $d(H)=2$. Therefore

contradicting the required inequality. Hence no such pairing exists.

Citation: Original question: Bernáth, Iwata, T. Király, Z. Király, Szigeti, “Recent results on well-balanced orientations,” Discrete Optimization 5 (2008), 663–676. The counterexample above is not taken from a known source.