Minimum length of 2-uniformity networks

About 4 years old · traced to

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 n≥2n\geq 2, the conjecture is

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

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

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.