The paper tackles two long-standing open problems about a class of networks called "rearrangeable networks," which are switching networks designed to connect any set of inputs to any desired set of outputs without conflicts. Think of these as the routing architecture underlying telephone exchanges or data center switches. Researchers had proposed mathematical conjectures predicting how hard or easy it is to rearrange connections in certain structured networks built from simple repeated patterns called shuffle-exchange and Benes networks.
The first result disproves a conjecture known as the Benes inequality, which claimed that a network's rearrangeability cost is at most twice a simpler measure of its connectivity. The authors build explicit small network examples that violate this relationship by a wide margin, showing the gap between the two quantities can be arbitrarily large. Importantly, they also identify which additional conditions on a network would rescue the inequality, clarifying exactly why the conjecture fails and what would need to be true for a corrected version to hold.
The second result disproves the shuffle-exchange conjecture, which predicted that the minimum number of stages needed to build a rearrangeable shuffle-exchange network with alphabet size k and n stages follows the formula 2n minus 1. The authors prove that when k equals 3 (meaning three symbols instead of the classical binary case), the correct answer for n equals 3 is 6, not 5 as the conjecture would predict. This shows the conjecture, previously verified only for the binary case, breaks down as soon as you move beyond two symbols. The authors suggest that a revised formula of 3n minus 3 may be the correct replacement for larger alphabet sizes, pointing toward a new research direction for the field.