Conjecture on the diameter of the Hurwitz graph of the symmetric group

About 14 years old · traced to

Let GT(n)G_T(n) be the Hurwitz graph whose vertices are reduced factorizations of the reverse permutation in SnS_n into transpositions, with edges given by local Hurwitz moves. Diameter conjecture. The diameter of GT(n)G_T(n) is

(n−12)+O(n).{n-1\choose 2}+O(n).

The preceding proposition gives an upper bound of 32(n−12)\frac{3}{2}{n-1\choose 2}, while the conjecture predicts the sharper leading term. Computations for n<8n<8 suggest the more precise value ⌊(n−1)2/2⌋−1\left\lfloor (n-1)^2/2 \right\rfloor-1, but this stronger formula is not asserted as the conjecture here.

References

Primary source

Ron M. Adin and Yuval Roichman, “On maximal chains in the non-crossing partition lattice”, arXiv:1201.4669 (2013).

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.