Problems, proofs, and disproofs on the inversion number

Guillaume Aubian ; Frédéric Havet ; Florian Hörsch ; Felix Kingelhoefer ; Nicolas Nisse ; Clément Rambaud ; Quentin Vermande

The electronic journal of combinatorics, Tome 32 (2025) no. 1

Résumé

The inversion of a set $X$ of vertices in a digraph $D$ consists of reversing the direction of all arcs of $D\langle X\rangle$. The inversion number of an oriented graph $D$, denoted by $\text{inv}(D)$, is the minimum number of inversions needed to transform $D$ into an acyclic oriented graph. In this paper, we study a number of problems involving the inversion number of oriented graphs. Firstly, we give bounds on $\text{inv}(n)$, the maximum of the inversion numbers of the oriented graphs of order $n$. We show $n - O(\sqrt{n\log n}) \leq \text{inv}(n) \ \leq \ n - \lceil \log (n+1) \rceil$. Secondly, we disprove a conjecture of Bang-Jensen et al. [DMCTS, 23(2), (2022)] asserting that, for every pair of oriented graphs $L$ and $R$, we have $inv(L\Rightarrow R) =\text{inv}(L) + \text{inv}(R)$, where $L\Rightarrow R$ is the oriented graph obtained from the disjoint union of $L$ and $R$ by adding all arcs from $L$ to $R$. Finally, we investigate whether, for all pairs of positive integers $k_1,k_2$, there exists an integer $f(k_1,k_2)$ such that if $D$ is an oriented graph with $\text{inv}(D) \geq f(k_1,k_2)$ then there is a partition $(V_1, V_2)$ of $V(D)$ such that $\text{inv}(D\langle V_i\rangle) \geq k_i$ for $i=1,2$. We show that $f(1,k)$ exists and $f(1,k)\leq k+10$ for all positive integers $k$. Further, we show that $f(k_1,k_2)$ exists for all pairs of positive integers $k_1,k_2$ when the oriented graphs in consideration are restricted to be tournaments.

Détail

DOI : 10.37236/12983

Classification : 05C20
Mots-clés : tournaments, acyclic oriented graph