Local and global proportionality

NEW

Problem: Reconstructed Conjecture 3: a finite digraph $D=(V,A)$ with nonempty out-neighbourhoods $N^+(v)$ is fully proportional iff it satisfies Woodall’s Theorem 4 covering condition. Here fully proportional means: for every red set $R\subseteq V$ and every $p$,

The Theorem 4 condition is the standard sufficient double-counting condition: there are nonnegative weights $a_v$, not all zero, such that every vertex of $V$ is covered equally often by the weighted out-neighbourhoods:

is independent of $x$. For the counterexample below all out-neighbourhoods have size $2$, so normalized and unnormalized formulations coincide.

Result: The conjecture is false.

Let $V=\{1,2,3,4,5,6\}$, and define a loopless $2$-out-regular digraph by

First, $D$ is fully proportional. Let $R\subseteq V$, $g=|R|/6$, and

We prove $\min_i\ell_i\le g$. If $|R|\le2$, then $R$ cannot meet all six pairs: if $5\notin R$, meeting $\{4,5\}$ and $\{3,5\}$ forces $3,4\in R$, missing $\{1,2\}$; if $5\in R$, one further vertex cannot meet all three pairs $\{1,6\},\{2,6\},\{1,2\}$. Hence some $\ell_i=0$.

If $3\le |R|<6$, either some $\ell_i=0$, or every pair meets $R$. In the latter case not every pair is contained in $R$, since their union is $V$; hence some $\ell_i=1/2\le |R|/6$. If $R=V$, equality holds. Thus $\min_i\ell_i\le |R|/6$ for all $R$, proving full proportionality.

Now suppose the Theorem 4 condition held, with common cover value $C$. The coverage equations are

From $a_1=C$ and $a_6=C$, the fifth equation gives $2C+a_4=C$, so $a_4=-C$. Since $a_4,C\ge0$, $C=0$, and then all $a_i=0$, contradiction. Therefore the Theorem 4 condition is not necessary.

Citation: Counterexample above. Source conjecture: D. R. Woodall, “Local and global proportionality,” Discrete Mathematics 102 (1992), 315–328, Conjecture 3.