{"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","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-02","reactions":{}}