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

About 5 years old · traced to

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)≥⌊n−12⌋.\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.

References

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.

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.