Unlabelled inversion diameter conjecture for complete graphs

About 2 years old · traced to

Let KnK_n be the complete graph on nn vertices, and let U(Kn)\mathcal{U}(K_n) be its unlabelled inversion graph, obtained by identifying vertices of the inversion graph corresponding to isomorphic orientations. Unlabelled inversion diameter conjecture.

diam⁡(U(Kn))⩽n−⌈log⁡(n+1)⌉.\operatorname{diam}(\mathcal{U}(K_n))\leqslant n-\lceil\log(n+1)\rceil.

The bound is motivated by the known upper bound for the eccentricity of the transitive tournament in the unlabelled inversion graph. The source gives asymptotic lower and upper bounds but does not establish this conjectured inequality.

References

Primary source

Frédéric Havet, Florian Hörsch and Clément Rambaud, “Diameter of the inversion graph”, arXiv:2405.04119 (2024).

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.