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

$$d(X)+d(Y)\ge d(X\cap Y)+d(X\cup Y),\qquad d(X)+d(Y)\ge d(X\setminus Y)+d(Y\setminus X)$$

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

$$T_d=\{v\in V:d(\{v\})\text{ is odd}\}.$$

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

$$d_M(X)\le d(X)-\hat R(X)\quad\forall X\subseteq V.$$

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

$$H_{a,\epsilon}=\{x:a\cdot x=\epsilon\}.$$

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

$$d(X)= \begin{cases} 0,& |X|=0,8,\\ 1,& |X|=1,7,\\ 2,& |X|=2,6,\\ 3,& |X|=3,5,\\ 2,& |X|=4\text{ and }X=H_{a,\epsilon}\text{ for some }a,\epsilon,\\ 4,& |X|=4\text{ and }X\text{ is not such a hyperplane.} \end{cases}$$

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

$$d(X\cap Y)+d(X\cup Y)=g(a)+g(c)\le 2+h(Y)=d(X)+d(Y).$$

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

$$a\cdot z_i=1\quad\forall i.$$

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

$$d_M(H)=4.$$

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

$$d_M(H)=4>2=d(H)-\hat R(H),$$

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.