Minimum transpositions in t-reachable networks
Problem 1 · arXiv:2208.06630
Status open high confidence
Problem 1 from arXiv:2208.06630 asks for the minimum number of transpositions in a t-reachable network, including the special case of star transpositions of the form (1,·). The paper (published in DMTCS, November 2025) settles the t=2 case exactly and gives an upper bound of (2+o_t(1))n transpositions for fixed t>=3, but the true asymptotics for large t remain open; a gap between upper and lower bounds also persists in the star-transposition setting. No follow-up paper resolving either variant was found in the indexed literature.
Reviewer notes. The paper appeared in Discrete Mathematics & Theoretical Computer Science, vol. 27:3, Combinatorics (DOI: 10.46298/dmtcs.12454), published 4 November 2025. A companion manuscript 'Perfect shuffling with fewer lazy transpositions' by Groenland and Johnston is hosted on Alex Scott's webpage but its arXiv preprint status and exact bearing on Problem 1 could not be confirmed within the 5-call budget. The sole verified citing paper (arXiv:2210.13286, Janzer–Johnson–Leader 2022) concerns lazy random transpositions and uniform mixing, not the deterministic t-reachable network problem. No resolution of the open asymptotics for t>=3 or the star-transposition gap was found.
Context
The authors determine the exact minimum for $t=2$ (Theorem 2) and give an upper bound of $(2+o_t(1))n$ transpositions for fixed $t\geq 3$, but the asymptotics remain open for large $t$. Lower bounds for star-transposition $t$-reachable networks are also given, but a gap between upper and lower bounds remains even in that restricted setting.
Source paper
Short reachability networks
Carla Groenland, Tom Johnston, Jamie Radcliffe, Alex Scott · 2025-10-23
https://arxiv.org/abs/2208.06630