arxivmath.COcs.NI2026-07-02
Beneš and Shuffle-Exchange Counterexamples
We give explicit counterexamples to two rearrangeability conjectures for shuffle-type networks. First, for every $N\ge2$ we construct a simple $N$-regular ordered two-stage graph $L_N$ with $F(L_N)=2$ and $R(L_N)\ge N$, refuting the graph-theoretic Beneš inequality $R(L)\le2F(L)$…