Unlabelled inversion diameter conjecture for complete graphs

From papers

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))nlog(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.

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

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

Solutions 0

No solutions have been posted yet.