Beneš and Shuffle-Exchange Counterexamples

Przemek Chojecki

We give explicit counterexamples to two rearrangeability conjectures for shuffle-type networks. First, for every $N\ge 2$ we construct a simple $N$-regular ordered two-stage graph $…