Graph-theory open problems

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 solved high confidence

The conjecture is true: a support-plus-rank potential gives the lower bound 2n-3, matching the stated construction, and the current source note already reports a resolution.

Cited literature (1)

  • proof Short reachability networks (2022)
    See linked article · Existing literature or final source version

    The conjecture is true: a support-plus-rank potential gives the lower bound 2n-3, matching the stated construction, and the current source note already reports a resolution.

    Read the literature-status audit

Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: The proof below is self-contained; I have not independently verified the bibliographic attribution of the post-v1 proof.

Auto-reviewed 2026-08-31 with gpt-5.6-sol.

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

Related conjectures

  • implied by Exact formula for U_t(n) lazy transpositions disproved Verified in both PDFs (companion papers by the same four authors). In 2208.06629, U_t(n) is the minimum number of lazy transpositions in a (t,n)-shuffle, i.e. achieving t-uniformity on n points, and Problem 3 asks 'Does U_t(n) = tn - binom(t+1,2)?'. In 2208.06630, a 2-uniformity network is defined identically and Conjecture 1 states the minimum is 2n-3 = 2n - binom(3,2), exactly the t=2 instance of Problem 3's formula. An affirmative answer to the general problem at t=2 (t=n is already refuted by Theorem 2) is literally the target conjecture: implication by restriction. The DMTCS version of 2208.06630 footnotes that Conjecture 1 was later proven by Janzer, Johnson, Leader (2023), corroborating that the two quantities coincide.

View in the relation graph — relations are AI-reviewed, not formally verified.