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

Less than 1 year old · traced to

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‾]))≤t⋅diam⁡(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.

References

Primary source

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

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.