Minimum lazy transpositions in 2-uniformity networks

Conjecture 1 · arXiv:2208.06630

arXiv Conjecture high confidence— first stated 2025-10-23

Authors: Carla Groenland, Tom Johnston, Jamie Radcliffe, Alex Scott

Status open high confidence

The conjecture that the minimum number of lazy transpositions in a 2-uniformity network is 2n-3 was posed in arXiv:2208.06630 (published in DMTCS 2025); the authors supply a matching construction and note an analogy with selection networks. No follow-up paper proving or disproving the conjecture was found in a broad web search. The companion paper arXiv:2208.06629 (same authors, same submission date) studies a related but distinct problem—perfect shuffling by lazy transpositions whose composition is uniform—and does not address the 2-uniformity lower bound.

Reviewer notes. No follow-up found after searching multiple queries. The paper was first posted August 2022 and published in DMTCS in October 2025. The companion paper arXiv:2208.06629 by the same authors concerns a different notion (lazy transpositions composing to a uniform permutation) and does not resolve Conjecture 1. The conjecture appears to remain open.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. For $n\geq 2$, the minimum number of lazy transpositions in a 2-uniformity network is $2n-3$.

Context

The authors construct a 2-uniformity network of length $2n-3$ using the sequence $(1,2,\tfrac{1}{2}),(1,3,\tfrac{2}{n}),(1,2,\tfrac{1}{2}),(1,4,\tfrac{2}{n-1}),\dots,(1,2,\tfrac{1}{2}),(1,n,\tfrac{2}{3}),(1,2,\tfrac{1}{2})$, and conjecture this is optimal. They remark that, if true, it would match nicely with selection networks.

Notes. The paper states that after a preliminary version was posted on arXiv, Conjecture 1 was proven (by unspecified authors in the truncated text); it may no longer be open.

Source paper

Short reachability networks
Carla Groenland, Tom Johnston, Jamie Radcliffe, Alex Scott · 2025-10-23
https://arxiv.org/abs/2208.06630