Exponential flows in 3-edge-connected oriented graphs

Conjecture 1.10 · arXiv:2005.09767

arXiv Conjecture high confidence— first stated 2020-05-19

Authors: Matt DeVos, Rikke Langhede, Bojan Mohar, Robert Šámal

Status open medium confidence

Conjecture 1.10 from arXiv:2005.09767 asserts an exponential lower bound $c^n$ on the number of $\Gamma$-connected flows for every abelian group $\Gamma$ with $|\Gamma| \geq 6$. The source paper itself proves this for all groups of size $\geq 8$ (Theorem 1.9) and establishes only a superpolynomial (but sub-exponential) bound for $\mathbb{Z}_6$ (Theorem 1.11), leaving $\mathbb{Z}_6$ and $\mathbb{Z}_7$ open. No subsequent paper resolving the conjecture for these two groups was found in five targeted web searches across the literature through May 2026; the paper remains at a single arXiv version with no revision signalling a resolution.

Reviewer notes. No follow-up paper resolving the conjecture for |Γ| = 6 or 7 was found. The conjecture is roughly 6 years old as of the review date, which is long enough that absence of evidence is somewhat suspicious but the two open cases (Z_6 and Z_7) are notoriously hard; confidence is set to medium rather than high. The sole internal reference candidate (2409.18220) was a false positive on the fuzz match.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. There exists a fixed constant $c > 1$ so that the following holds. For every 3-edge-connected oriented graph $G = (V, E)$ of order $n$, every abelian group $\Gamma$ with $|\Gamma| \geq 6$, and every $f : E \to \Gamma$, there exist at least $c^n$ flows $\phi : E \to \Gamma$ with $\phi(e) \neq f(e)$ for every $e \in E$.

Context

Theorem 1.9 establishes an explicit exponential lower bound on the number of $\Gamma$-connected flows for groups of size $k \geq 8$, but yields only the existence of a single flow for $k = 6, 7$. The authors attribute this gap to a shortcoming of their techniques and conjecture the exponential bound holds for all abelian groups of size at least 6. Theorem 1.9 confirms the conjecture for all groups except $\mathbb{Z}_6$ and $\mathbb{Z}_7$; Theorem 1.11 gives a superpolynomial (but not exponential) lower bound for $\mathbb{Z}_6$.

Source paper

Many flows in the group connectivity setting
Matt DeVos, Rikke Langhede, Bojan Mohar, Robert Šámal · 2020-05-19
https://arxiv.org/abs/2005.09767 PDF source