Belkhechine et al.'s lower-bound conjecture for the inversion number

From papers

For every positive integer nn, let

inv(n)=max{inv(D)D is an oriented graph of order n}.\operatorname{inv}(n)=\max\{\operatorname{inv}(D)\mid D\text{ is an oriented graph of order }n\}.

Here inv(D)\operatorname{inv}(D) is the minimum number of inversions needed to transform DD into an acyclic oriented graph.

Belkhechine et al.'s inversion-number conjecture.

inv(n)n12.\operatorname{inv}(n)\geq\left\lfloor\frac{n-1}{2}\right\rfloor.

This strengthens the elementary counting lower bound given immediately before it and asserts that the logarithmic loss in that bound is unnecessary. The source does not state a resolution.

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

Guillaume Aubian, Frédéric Havet, Florian Hörsch, Felix Klingelhoefer, Nicolas Nisse, Clément Rambaud and Quentin Vermande, “Problems, proofs, and disproofs on the inversion number”, arXiv:2212.09188 (2022).

Additional references

2 papers in this index state this conjecture (2021–2022). The statement above is taken from the most recent of them; the others are arXiv:2105.04137.

Solutions 0

No solutions have been posted yet.