Havet–Horsch–Rambaud lexicographic-product conjecture for inversion diameter

From papers

Let GG be a graph and let tt be a positive integer. Denote by G[Kt]G[\overline{K_t}] the lexicographic product obtained by replacing each vertex of GG with an independent set of size tt, and write I(G)I(G) for the inversion graph and diam(I(G))\operatorname{diam}(I(G)) for its diameter.

Havet–Horsch–Rambaud's lexicographic-product conjecture. For every graph GG and every positive integer tt,

diam(I(G[Kt]))tdiam(I(G)).\operatorname{diam}(I(G[\overline{K_t}]))\le t\cdot\operatorname{diam}(I(G)).

The conjecture predicts that lexicographic blow-ups by independent sets increase inversion diameter by at most the blow-up factor. It is presented as a proposed general bound, and no resolution is supplied 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

Jiawen Bo, Anqi Li, Xiaopan Lian and Xin Yan, “Edge-Number Bounds for the Inversion Diameter of Graphs”, arXiv:2606.17974 (2026).

Solutions 0

No solutions have been posted yet.