The structure of graphs with Circular flow number 5 or more, and the complexity of their recognition problem

NEW

Problem: Reconstructed statement: in the setting of finite undirected graphs and modular flows in $\mathbb R/5\mathbb Z$, let $\mathrm{CP}_5(G_{u,v})$ be the open $5$-capacity of a two-terminal network $G_{u,v}$, and let

Problem 37 asks whether the 16 explicitly listed capacities in Section $\ref{>=5}$ of Esperet--Mazzuoccolo--Tarsi equal all of $GI_5$. This is supported by the paper’s definitions and by the sentence immediately before Problem 37 saying that they “systematically analyzed” $GI_5$.

Result: No. The list is incomplete.

Let $R_5=\mathbb R/5\mathbb Z$, and let $H=K_4-uv$, with terminals $u,v$ and the other vertices $a,b$. I claim

This set is one of the five capacities explicitly not in the paper’s 16-item list.

Orient $ua,ub,av,bv,ab$ as

and orient the added closing edge $e_0$ as $v\to u$. Since $(1,4)\subset R_5$ is symmetric, fixing this orientation loses no generality.

For $t\in R_5$, put $A=(1,4)$ and

A flow with $f(e_0)=t$ exists iff there are $x,z\in D_t$ with $x-z\in A$: indeed, taking

the vertex equations are equivalent to

Thus $x,z\in A$, $t-x,t-z\in A$, and $x-z\in A$. Conversely these conditions define such a flow.

Represent $t\in[0,5)$. A direct computation gives

For $x,z\in(1,4)$, one has $x-z\in(1,4)\pmod 5$ iff $|x-z|>1$. The sets $D_2=(3,4)$ and $D_3=(1,2)$ contain no two points at distance $>1$, so $2,3\notin\mathrm{CP}_5(H_{u,v})$. In every other case above, $D_t$ contains two points at distance $>1$, so $t\in\mathrm{CP}_5(H_{u,v})$.

Hence $\mathrm{CP}_5(H_{u,v})=R_5\setminus\{2,3\}$, proving $R_5\setminus\{2,3\}\in GI_5$ but not in the listed 16 capacities.

Moreover, since $GI_5$ is closed under intersection, intersecting this new capacity with the five listed capacities containing $\{2,3\}$ yields all five omitted members of $SI_5$. Thus, in fact, $GI_5=SI_5$.

Verification audit: the counterexample is a finite simple two-terminal graph, so no extra graph-theoretic assumptions are used; the strict open interval condition is checked exactly; and the conclusion directly negates the proposed completeness of the Section $\ref{>=5}$ list.

Citation: Problem and definitions: L. Esperet, G. Mazzuoccolo, M. Tarsi, “The structure of graphs with Circular flow number 5 or more, and the complexity of their recognition problem,” Journal of Combinatorics 7(2) (2016), 453–479; arXiv:1501.03774, Problem 37. The counterexample above is not cited as a known literature result.