Id: arxiv/2607.15296 Url: https://arxiv.org/abs/2607.15296 Tags: math.CO, cs.NI Score: 0 Title: Beneš and Shuffle-Exchange Counterexamples Domain: math.CO Source: arxiv Authors: Przemek Chojecki Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-02 Page: https://delphi.science/r/arxiv/2607.15296 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)$ and its partition-stabilizer form as stated on Open Problem Garden. We retain the sharp cut obstruction, exact mask-composition identity, exact middle criterion, first nontrivial-level result, and balanced-middle sufficient condition that explain which extra hypotheses can replace mere external connectivity. Second,…