Belkhechine et al.'s lower-bound conjecture for the inversion number
Belkhechine et al.'s lower-bound conjecture for the inversion number
For every positive integer , let
Here is the minimum number of inversions needed to transform into an acyclic oriented graph.
Belkhechine et al.'s inversion-number conjecture.
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
Sign in to submit a solution.
No solutions have been posted yet.