Minimum length of 2-uniformity networks

From papers

A 2-uniformity network is a network of lazy transpositions whose output permutation is uniformly distributed on every subset of two positions; let U2(n)U_2(n) denote the minimum length of such a network on nn positions. For n2n\geq 2, the conjecture is

U2(n)=2n3.U_2(n)=2n-3.

This is motivated by an explicit family of 2-uniformity networks of length 2n32n-3; the conjecture asserts that no shorter sequences exist. Its status is left open in the source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Carla Groenland, Tom Johnston, Jamie Radcliffe and Alex Scott, “Short reachability networks”, arXiv:2208.06630 (2025).

Solutions 0

No solutions have been posted yet.