Beneš Conjecture (graph-theoretic form)

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

An $\ell$-stage graph has ordered parts $V_1,\ldots,V_\ell$, with edges only between consecutive parts; parallel edges are allowed unless simplicity is required. A plain path uses one vertex from each part, from a source in $V_1$ to a target in $V_\ell$. The graph is externally connected if every source--target pair has a plain path. A mask is any bipartite multigraph on $V_1,V_\ell$ having at each endpoint the same degree as the stage graph. Rearrangeability means that every mask admits one plain path per edge with matching endpoints, all paths mutually edge-disjoint. The graph is straight if every internal vertex has equal numbers of edges to the previous and next parts. It is ordered if each part is linearly ordered. If an ordered two-stage graph $B$ has equal-sized parts, $B^m$ concatenates $m$ identical copies respecting these orders. Such powers are uniform. For positive $m$, let $F(B)$ and $R(B)$ be the least exponents for which $B^m$ is externally connected or rearrangeable, respectively, and set an unattained minimum equal to $\infty$.

Statement recorded in the supplied source.

Find sufficient conditions for a straight $\ell$-stage graph to be rearrangeable, including the straight uniform case. In particular, for every simple regular ordered two-stage graph $L$ and every $m\geq1$, does \[L^m\text{ externally connected}\quad\Longrightarrow\quad L^{2m}\text{ rearrangeable}?\] Equivalently, does $R(L)\leq2F(L)$ whenever $F(L)<\infty$? The stronger equality $R(L)=2F(L)$ is a distinct assertion. [S2]

Short English statement

Find criteria that guarantee routing every permitted end-to-end demand in a balanced layered graph, and test whether doubling an externally connected uniform simple regular network always suffices.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3110 (OPG-37210). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Beneš, Václav E., Beneš Conjecture (graph-theoretic form), Open Problem Garden, node 37210. Complete problem, discussion and bibliography (including mathematical image alt text). https://www.openproblemgarden.org/op/bene_conjecture_graph_theoretic_form_0.