# 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

► To cite this version:

Guillaume Aubian, Frédéric Havet, Florian Hörsch, Felix Kingelhoefer, Nicolas Nisse, et al. Problems, Proofs, and Disproofs on the Inversion Number. The Electronic Journal of Combinatorics, 2025, 32 (1), 10.37236/12983. hal-04994897

HAL Id: hal-04994897

https://inria.hal.science/hal-04994897v1

Submitted on 18 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Problems, proofs, and disproofs on the inversion number

Guillaume Aubian<sup>a</sup>

Frédéric Havet<sup>b</sup>

Florian Hörsch<sup>c</sup>

Felix Klingelhoefer<sup>d</sup>

Nicolas Nisse<sup>e</sup>

Clément Rambaud<sup>f</sup>

Quentin Vermande<sup>g</sup>

Submitted: Apr 30, 2024; Accepted: Jan 18, 2025; Published: Mar 14, 2025

© The authors. Released under the CC BY-ND license (International 4.0).

## Abstract

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}) \le \text{inv}(n) \le n - \lfloor \log(n+1) \rfloor$. Secondly, we disprove a conjecture of Bang-Jensen et al. [3] asserting that, for every pair of oriented graphs $L$ and $R$, we have $\text{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) \ge 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) \ge k_i$ for $i = 1, 2$. We show that $f(1, k)$ exists and $f(1, k) \le 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.

**Mathematics Subject Classifications:** 05C20

<footnote><sup>a</sup>Université de Paris, CNRS, IRIF, Paris, France and DIENS, École normale supérieure, CNRS, PSL University, Paris, France (guillaume.aubian@gmail.com)</footnote>

<footnote><sup>b</sup>Université Côte d'Azur, CNRS, Inria, I3S, Sophia Antipolis, France (frederic.havet@inria.fr)</footnote>

<footnote><sup>c</sup>CISPA Saarbrücken, Germany (florian.hoersch@cispa.de)</footnote>

<footnote><sup>d</sup>Université Grenoble Alpes, Grenoble, France (fel.klingel@gmail.com)</footnote>

<footnote><sup>e</sup>Université Côte d'Azur, CNRS, Inria, I3S, Sophia Antipolis, France (nicolas.nisse@inria.fr)</footnote>

<footnote><sup>f</sup>Université Côte d'Azur, CNRS, Inria, I3S, Sophia Antipolis, France and DIENS, cole normale supérieure, CNRS, PSL University, Paris, France (clement.rambaud@inria.fr)</footnote>

<footnote><sup>g</sup>Université Côte d'Azur, CNRS, Inria, I3S, Sophia Antipolis, France and DIENS, École normale supérieure, CNRS, PSL University, Paris, France (quentin.vermande@inria.fr)</footnote>
# 1 Introduction

Notation not given below is consistent with [4]. We denote by $[k]$ the set $\{1, 2, \dots, k\}$. The notation log refers to the logarithm to the base 2. A **digraph** $D$ is a pair $(V, A)$ where $V$ is a finite set and $A$ is a set of pairs of distinct elements of $V$. If for every distinct $u, v \in V$, at most one of the pairs $uv$ and $vu$ is in $A$, then we say that $D$ is an **oriented graph**. Furthermore, if for every distinct $u, v \in V$, exactly one of the pairs $uv$ and $vu$ is in $A$, then we say that $D$ is a **tournament**

Let $D$ be an oriented graph. The **inversion** of a set $X$ of vertices of $D$ consists of reversing the direction of all arcs of $D\langle X\rangle$. We say that we **invert** $X$ in $D$. The resulting oriented graph is denoted by $\text{Inv}(D; X)$. If $(X_i)_{i \in I}$ is a family of subsets of $V(D)$, then $\text{Inv}(D; (X_i)_{i \in I})$ is the oriented graph obtained after inverting the $X_i$ one after another. Observe that this is independent of the order in which we invert the $X_i$: $\text{Inv}(D; (X_i)_{i \in I})$ is obtained from $D$ by reversing the arcs such that an odd number of the $X_i$ contain its two end-vertices. A **de recycling family** of an oriented graph $D$ is a family $(X_i)_{i \in I}$ of subsets of $V(D)$ such that $\text{Inv}(D; (X_i)_{i \in I})$ is acyclic. 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, that is, the minimum cardinality of a de recycling family.

The inversion number of oriented graphs was first introduced by Belkhechine et al. in [7]. They studied oriented graphs with large inversion number. For any positive integer $n$, let $\text{inv}(n) = \max\{\text{inv}(D) \mid D \text{ oriented graph of order } n\}$. Since the inversion number is non-increasing with respect to edge deletion, we have $\text{inv}(n) = \max\{\text{inv}(T) \mid T \text{ tournament of order } n\}$. In the following, we give some basic bounds on $\text{inv}(n)$.

**Remark 1.** $\text{inv}(n) \le \text{inv}(n-1) + 1$ for all positive integer $n$.

*Proof.* Let $T$ be a tournament of order $n$. Pick a vertex $x$ of $T$. Observe that $x$ is a sink in $T' = \text{Inv}(T; N_T^+[x] \cup x)$. This yields $\text{inv}(T') = \text{inv}(T' - x) \le \text{inv}(n-1)$. Hence $\text{inv}(T) \le \text{inv}(n-1) + 1$. $\square$

Every oriented graph on at most two vertices is acyclic, so $\text{inv}(1) = \text{inv}(2) = 0$. Every tournament of order at most 4 has a cycle arc-transversal of size at most 1, so $\text{inv}(3) = \text{inv}(4) = 1$ since it is enough to reverse this single arc (see Theorem 6). As observed by Belkhechine et al. [6], every tournament of order at most 6 has inversion number at most 2. This observation and Remark 1 yield

$$ \text{inv}(n) \le n - 4 \quad \text{for all } n \ge 6. \qquad (1) $$

Moreover, Belkhechine et al. [7] observed that since there are $n!$ labelled transitive tournaments of order $n$, the number of labelled tournaments of order $n$ with inversion number less than $p$ is at most $n!2^{n(p-1)}$, while there are $2^{\frac{n(n-1)}{2}}$ labelled tournaments of order $n$. It follows that for all positive integers $n$ and $p$ such that $2^{\frac{n(n-1)}{2}} > n!2^{n(p-1)}$, there is a tournament $T$ of order $n$ such that $\text{inv}(T) \ge p$. Hence, for every positive integer $n$, we have
$$ \mathrm{inv}(n) \geq \frac{n-1}{2} - \log n. \qquad (2) $$

However, Belkhechine et al. [6] conjectured that Equation (2) is not tight.

**Conjecture 2** (Belkhechine et al. [6]). $\mathrm{inv}(n) \geq \lfloor \frac{n-1}{2} \rfloor$.

Their conjecture was motivated by their conviction that some explicit tournament of order $n$ has inversion number at least $\lfloor \frac{n-1}{2} \rfloor$. Let $Q_n$ be the tournament obtained from the transitive tournament by reversing the arcs of its unique directed hamiltonian path $(v_1, v_2, \dots, v_n)$.

**Conjecture 3** (Belkhechine et al. [6]). $\mathrm{inv}(Q_n) = \lfloor \frac{n-1}{2} \rfloor$.

The first main contribution of this article is an improvement of both the upper and the lower bound on $\mathrm{inv}(n)$. With a rather simple argument we improve the upper bound.

**Theorem 4.** For every positive integer $n$, we have $\mathrm{inv}(n) \leq n - \lceil \log(n+1) \rceil$.

Next, we improve the lower bound using some more involved probabilistic techniques. More precisely, considering a random tournament of order $n$, we show the following result.

**Theorem 5.** $\mathrm{inv}(n) \geq n - 2\sqrt{n \log n}$ for $n$ sufficiently large.

Observe that for $n$ sufficiently large, Theorem 5 confirms Conjecture 2 and even establishes a much stronger bound. The proofs of Theorems 4 and 5 can be found in Section 2.

A cycle transversal (resp. cycle arc-transversal) in a digraph $D$ is a set of vertices (resp. arcs) whose deletion results in an acyclic digraph. We wish to remark that cycle transversals and cycle arc-transversals are sometimes also referred to in the literature as feedback vertex sets and feedback arcs sets, respectively. The cycle transversal number (resp. cycle arc-transversal number) is the minimum size of a cycle transversal (resp. cycle arc-transversal) of $D$ and is denoted by $\tau(D)$ (resp. $\tau'(D)$). As observed in [3], the inversion number is bounded by the cycle arc-transversal number and twice the cycle transversal number.

**Theorem 6** (Bang-Jensen et al. [3]). $\mathrm{inv}(D) \leq \tau'(D)$ and $\mathrm{inv}(D) \leq 2\tau(D)$ for every oriented graph $D$.

A natural question is to ask whether these bounds are tight or not.

We denote by $\vec{C}_3$ the directed cycle of length 3, and by $TT_n$ the transitive tournament of order $n$. The vertices of $TT_n$ are $v_1, \dots, v_n$ and its arcs $\{v_i v_j \mid i < j\}$. The lexicographic product of a digraph $D$ by a digraph $H$ is the digraph $D[H]$ with vertex set $V(D) \times V(H)$ and arc set $A(D[H]) = \{(a, x)(b, y) \mid ab \in A(D), \text{ or } a = b \text{ and } xy \in A(H)\}$. It can be seen as blowing up each vertex of $D$ by a copy of $H$. Using boolean dimension, Pouzet et al. [8] proved the following.
**Theorem 7** (Pouzet et al. [8]). $\text{inv}(TT_n[\vec{C}_3]) = n$.

Since $\tau'(TT_n[\vec{C}_3]) = n$, this shows that the inequality $\text{inv}(D) \le \tau'(D)$ of Theorem 6 is tight.

Pouzet asked for an elementary proof of Theorem 7. Let $L$ and $R$ be two oriented graphs. The **dijoin** from $L$ to $R$, denoted by $L \Rightarrow R$, is the oriented graph obtained from the disjoint union of $L$ and $R$ by adding all arcs from $L$ to $R$. Observe that $TT_n[\vec{C}_3] = \vec{C}_3 \Rightarrow TT_{n-1}[\vec{C}_3]$. Hence one way to prove Theorem 7 would be to prove that $\text{inv}(\vec{C}_3 \Rightarrow T) = \text{inv}(T) + 1$ holds for every tournament $T$. First inverting $\text{inv}(L)$ subsets of $V(L)$ to make $L$ acyclic and then inverting $\text{inv}(R)$ subsets of $V(R)$ to make $R$ acyclic, makes $L \Rightarrow R$ acyclic. Therefore $\text{inv}(L \Rightarrow R) \le \text{inv}(L) + \text{inv}(R)$. Bang-Jensen et al. [3] conjectured that equality always holds.

**Conjecture 8** (Bang-Jensen et al. [3]). For any two oriented graphs, $L$ and $R$, $\text{inv}(L \Rightarrow R) = \text{inv}(L) + \text{inv}(R)$.

Bang-Jensen et al. [3] showed that the inequality $\text{inv}(D) \le 2\tau(D)$ of Theorem 6 is tight for $\tau(D) \in \{1, 2\}$ and conjectured the following.

**Conjecture 9** (Bang-Jensen et al. [3]). For every positive integer $n$, there exists an oriented graph $D$ such that $\tau(D) = n$ and $\text{inv}(D) = 2n$.

This conjecture would also be implied by Conjecture 8.

Moreover, Bang-Jensen et al. [3] proved that deciding whether a given digraph $D$ has inversion number at most 1 is NP-complete. Together with Conjecture 8, this would imply the following conjecture posed in [3].

**Conjecture 10** (Bang-Jensen et al. [3]). Deciding whether a given digraph $D$ has inversion number at most $k$ is NP-complete for any fixed positive integer $k$.

Bang-Jensen et al. [3] proved that Conjecture 8 holds when $\text{inv}(L) \le 1$ and $\text{inv}(R) \le 2$, and when $\text{inv}(L) = \text{inv}(R) = 2$ and both $L$ and $R$ are strongly connected. Unfortunately, in Section 3, we disprove Conjecture 8. More precisely, we show the following result:

**Theorem 11.** For every odd integer $k \ge 3$, there is a tournament $T_k$ with $\text{inv}(T_k) = k$ such that $\text{inv}(T_k \Rightarrow R) \le k + \text{inv}(R) - 1$ for every oriented graph $R$ with $\text{inv}(R) \ge 1$.

A celebrated conjecture of Alon [1] states that for any two positive integers $k_1, k_2$, there is a minimum integer $f(k_1, k_2)$ such that, for any digraph $D$ with minimum out-degree $f(k_1, k_2)$, there is a partition $(V_1, V_2)$ of $V(D)$ such that the minimum out-degree of the subdigraph induced by $V_i$ is at least $k_i$ for each $i = 1, 2$. It is natural to ask whether an Alon-type result holds for the inversion number.

**Conjecture 12.** For every two positive integers $k_1, k_2$, there exists an integer $f(k_1, k_2)$ such that every oriented graph $D$ with $\text{inv}(D) \ge f(k_1, k_2)$ admits a partition $(V_1, V_2)$ of $V(D)$ such that $\text{inv}(D\langle V_i \rangle) \ge k_i$ for $i = 1, 2$.
An oriented graph is **intercyclic** if it does not have two vertex-disjoint directed cycles. Bang-Jensen et al. [3] proved that intercyclic oriented graphs have inversion number at most 4. This implies that $f(1, 1)$ exists and $f(1, 1) \le 5$.

In an attempt to approach Conjecture 12, we give two partial results. Firstly, we show that an analogous statement holds when we restrict the oriented graphs in consideration to be tournaments.

**Theorem 13.** For every two positive integers $k_1, k_2$, there exists an integer $f_T(k_1, k_2)$ such that every tournament $T$ with $\text{inv}(T) \ge f_T(k_1, k_2)$ admits a partition $(V_1, V_2)$ of $V(T)$ such that $\text{inv}(T\langle V_i \rangle) \ge k_i$ for $i = 1, 2$.

Secondly, we show that the statement holds when restricting one of the two parameters to be 1. More concretely, we show the following result.

**Theorem 14.** For every positive integer $k$ and for every oriented graph $D$ with $\text{inv}(D) \ge k+10$, there is a partition $(V_1, V_2)$ of $V(D)$ satisfying $\text{inv}(D\langle V_1 \rangle) \ge k$ and $\text{inv}(D\langle V_2 \rangle) \ge 1$.

The proofs of Theorems 13 and 14 can be found in Section 4.

We conclude this work in Section 5, by proposing directions for further research on the topic.

First, since the lower bound on $\text{inv}(n)$ of Theorem 5 is obtained by random tournaments, we explore possible explicit constructions of tournaments with large inversion number. Theorem 7 yields tournaments of order $n$ with inversion number $\lfloor n/3 \rfloor$. Explicit constructions of tournaments with larger inversion number are not known. Proving (or approaching) Conjecture 3 would give one. Let us describe another construction. Let $D$ be an oriented graph. We denote by $\Delta(D)$ the oriented graph obtained from $D$ by adding two new vertices $u, v$, adding all the arcs from $V(D)$ to $u$, adding the arc $uv$, and adding all arcs from $v$ to $V(D)$. We believe that iterating this construction yields tournaments with large inversion number.

**Conjecture 15.** $\text{inv}(\Delta^k(TT_1)) = \text{inv}(\Delta^k(TT_2)) = k + 1$.

In Subsection 5.1, we consider this conjecture. In particular, in Theorem 29, we prove that $\text{inv}(\Delta^{k-1}(TT_2)) \ge k/2 - 1$.

Finally, in Subsection 5.2, we present some problems raised by the disproof of Conjecture 8.

**Note added** Almost simultaneously with the release of this paper, Alon, Powierski, Savery, Scott, and Wilmer announced independent work [2] on some of the problems we address here. Specifically, they show upper and lower bounds on $\text{inv}(n)$ of forms similar to those of Theorems 4 and 5. They also disprove Conjecture 8, but only provide one counterexample. In addition, they prove Conjectures 9 and 10.
## 2 Maximum inversion number of an oriented graph of order $n$

This section is dedicated to improving the bounds on inv($n$). More particularly, we prove Theorems 4 and 5.

We first give the proof of Theorem 4 which we recall.

**Theorem 4.** For every positive integer $n$, we have $\text{inv}(n) \le n - \lfloor \log(n+1) \rfloor$.

*Proof.* As observed above, it suffices to prove the statement for tournaments. We proceed by induction on $n$, the result holding trivially when $n=1$.

Let $T$ be a tournament on $n$ vertices for some $n \ge 2$. Now consider a vertex $u$. Without loss of generality, we may assume that $d_T^-(u) \le \lfloor \frac{n-1}{2} \rfloor$. Let $v_1, \dots, v_{d_T^-(u)}$ be an arbitrary ordering of $N_T^-(u)$. For every $i \in [d_T^-(u)]$, let $X_i = \{v_i\} \cup N_{T_{i-1}}^-(v_i) \setminus \{v_j \mid j < i\}$ where $T_{i-1} = \text{Inv}(T; (X_j)_{j \in [i-1]})$. Observe that after inverting $X_i$, $v_i$ dominates all the vertices of $\{v_j \mid j > i\} \cup \{u\} \cup N_T^+(u)$, and $u$ dominates $N_T^+(u)$. Hence it remains to apply the induction hypothesis to make the subtournament induced by $N_T^+(u)$ acyclic. In total, we used at most

$$ \left\lfloor \frac{n-1}{2} \right\rfloor + \left\lfloor \frac{n-1}{2} \right\rfloor - \log \left( \left\lfloor \frac{n-1}{2} \right\rfloor + 1 \right) = n - \log \left( 2 \left\lfloor \frac{n-1}{2} \right\rfloor + 2 \right) \\ \le n - \log(n+1) $$

inversions. This proves the theorem. $\square$

The proof of Theorem 5 is based on probabilistic methods and heavily relies on properties of a certain random matrix over the unique field $\mathbb{F}_2$ on two elements 0 and 1. All the matrices considered in this paper are over this field, and for a matrix $M$, we denote by rk($M$) its rank over $\mathbb{F}_2$. A significant part of the technicalities of the proof is included in the following lemma.

**Lemma 16.** Let $n \ge 1$ be a positive integer and let $x_1, \dots, x_n \in \mathbb{F}_2$. Let $M$ be a matrix in $\mathbb{F}_2^{n \times n}$ chosen uniformly at random among all symmetric matrices whose diagonal entries are $x_1, \dots, x_n$. Then for every $r \in \{0, \dots, n\}$, we have

$$ \Pr[\text{rk}(M) \le n - r] \le 2^{-\frac{1}{2}(r^2 - 4r)} $$

*Proof.* For $i \in \{0, \dots, n\}$, let $M_i$ be the submatrix of $M$ which is restricted to the first $i$ rows and columns. Observe that $M_n = M$. Further, we define random variables $X_i$, $i = 0, \dots, n$ where $X_i = i - \text{rk}(M_i)$.

**Claim 17.** For every $i \in \{0, \dots, n-1\}$, we have $X_i - 1 \le X_{i+1} \le X_i + 1$.

*Proof of claim.* As $M_i$ is a submatrix of $M_{i+1}$ with one row and one column less than $M_{i+1}$, we have $\text{rk}(M_i) \le \text{rk}(M_{i+1}) \le \text{rk}(M_i)+2$. By definition, $X_{i+1} = X_i+1-\text{rk}(M_{i+1})+\text{rk}(M_i)$, so $X_i - 1 \le X_{i+1} \le X_i + 1$. $\diamond$
**Claim 18.** For any $i \in \{1, \dots, n-1\}$ and $r \in \{1, \dots, i\}$, we have

$$ \Pr[X_{i+1} = r-1 | X_i = r] = 1 - 2^{-r} $$

and

$$ \Pr[X_{i+1} \ge r | X_i = r] = 2^{-r}. $$

*Proof of claim.* Suppose that $X_i = r$, so $rk(M_i) = i - r$. First let $M'_i$ be the submatrix of $M$ restricted to the first $i+1$ rows and $i$ columns. Observe that the vector space spanned by the rows of $M_i$ is of dimension $i-r$ and hence contains $2^{i-r}$ vectors. Further, the last row of $M'_i$ is chosen uniformly at random among $2^i$ vectors. We hence obtain $\Pr[\mathrm{rk}(M'_i) = \mathrm{rk}(M_i)] = \frac{2^{i-r}}{2^i} = 2^{-r}$ and $\Pr[\mathrm{rk}(M'_i) = \mathrm{rk}(M_i) + 1] = 1 - 2^{-r}$.

If $rk(M'_i) = rk(M_i)$, then $rk(M_{i+1}) \le rk(M_i)+1$, and so $X_{i+1} \ge X_i = r$. Now consider the case $rk(M'_i) = rk(M_i) + 1$. Due to the symmetry of the matrix, we then obtain that the last column vector of $M_{i+1}$ is not spanned by the column vectors of $M'_i$. Hence $rk(M_{i+1}) = rk(M'_i) + 1 = rk(M_i) + 2$ yielding

$$ \begin{aligned} X_{i+1} &= (i+1) - \mathrm{rk}(M_{i+1}) \\ &= (i+1) - (\mathrm{rk}(M_i) + 2) \\ &= i - \mathrm{rk}(M_i) - 1 \\ &= X_i - 1. \end{aligned} \quad \diamond $$

**Claim 19.** For any $i \in \{1, \dots, n\}$ and $r \in \{0, \dots, i\}$, we have $\Pr[X_i \ge r] \le 2^{-\frac{1}{2}(r^2-4r)}$.

*Proof of claim.* We proceed by induction on $i$. The statement clearly holds for $i=1$. We now suppose that the statement holds for all integers up to some $i$ and show it also holds for $i+1$. For $r \le 4$, we have $\Pr[X_i \ge r] \le 1 \le 2^{-\frac{1}{2}(r^2-4r)}$. We may hence suppose from now on that $r \ge 5$. By induction, Claims 17 and 18 we obtain

$$ \begin{aligned} \Pr[X_{i+1} \ge r] &= \Pr[X_{i+1} \ge r \text{ and } X_i \ge r+1] + \Pr[X_{i+1} \ge r \text{ and } X_i = r] \\ &\quad + \Pr[X_{i+1} \ge r \text{ and } X_i = r-1] \\ &\le \Pr[X_i \ge r+1] + \Pr[X_{i+1} \ge r | X_i = r] \Pr[X_i = r] \\ &\quad + \Pr[X_{i+1} \ge r | X_i = r-1] \Pr[X_i = r-1] \\ &\le \Pr[X_i \ge r+1] + 2^{-r} \Pr[X_i = r] + 2^{-(r-1)} \Pr[X_i = r-1] \\ &\le 2^{-\frac{1}{2}((r+1)^2-4(r+1))} + 2^{-(r-1)} \Pr[X_i \ge r-1] \\ &= 2^{-\frac{1}{2}((r+1)^2-4(r+1))} + 2^{-(r-1)} 2^{-\frac{1}{2}((r-1)^2-4(r-1))} \\ &= 2^{-\frac{1}{2}((r^2-4r)+(2r-3))} + 2^{-\frac{1}{2}((r^2-4r)+3)} \\ &\le 2^{-\frac{1}{2}(r^2-4r)} (2^{-\frac{1}{2}(2r-3)} + 2^{-\frac{3}{2}}) \\ &\le 2^{-\frac{1}{2}(r^2-4r)} (2^{-\frac{7}{2}} + 2^{-\frac{3}{2}}) \\ &\le 2^{-\frac{1}{2}(r^2-4r)}. \end{aligned} \quad \diamond $$
The lemma now follows by applying Claim 19 to $i = n$. □

For a tournament $T$ with vertex set $[n]$ and a permutation $\sigma$ of $[n]$, we denote by $\text{inv}_\sigma(T)$ the minimum number of inversions needed to transform $T$ into a transitive tournament with acyclic ordering $\sigma$. Observe that $\text{inv}(T) = \min_\sigma \text{inv}_\sigma(T)$. We also denote by $M_\sigma(T)$ the symmetric matrix in $\mathbb{F}_2^{n \times n}$ all of whose diagonal entries are 0 and which has a 0 in a cell $(i, j)$ if and only if the arc between $i$ and $j$ is oriented according to $\sigma$. Finally, we say that a matrix is a diagonal matrix if all its off-diagonal entries are 0 and we let $\mathbb{D}_2^{n \times n}$ be the set of diagonal matrices in $\mathbb{F}_2^{n \times n}$.

**Lemma 20.** Let $T$ be a tournament on $[n]$ and let $\sigma$ be a permutation of $[n]$. Then

$$ \text{inv}_{\sigma}(T) \ge \min_{D \in \mathbb{D}_2^{n \times n}} \text{rk}(M_{\sigma}(T) + D). $$

*Proof.* Suppose $\text{inv}_\sigma(T) = k$ and that $\mathcal{X} = (X_\ell)_{\ell \in [k]}$ is a decycling family such that $\text{Inv}(T; \mathcal{X})$ is the transitive tournament with acyclic ordering $\sigma$. For every $\ell \in [k]$, let $M_\ell$ be the matrix with cell $(i, j)$ having value 1 if and only if both $i$ and $j$ are in $X_\ell$. Then if $D$ is the diagonal $n \times n$ matrix whose value at cell $(i, i)$ equal 1 if and only if $i$ is in an odd number of sets in $\mathcal{X}$, we have

$$ M_{\sigma}(T) + D = M_1 + \dots + M_k. $$

Note that the column $j$ of each $M_\ell$ is either the null vector (if $j \notin X_\ell$) or the indicator vector of $X_\ell$ (if $j \in X_\ell$). Hence each $M_\ell$ has rank at most 1. Thus

$$ \text{rk}(M_{\sigma}(T) + D) \le \text{rk}(M_1) + \dots + \text{rk}(M_k) \le k $$

and the result follows. □

We are now ready to proceed to the proof of Theorem 5, which we recall.

**Theorem 5.** $\text{inv}(n) \ge n - 2\sqrt{n \log n}$ for $n$ sufficiently large.

*Proof.* Let $n$ be a positive integer and let $r \in [n]$ to be determined later. Let $T$ be a tournament with vertex set $[n]$ taken uniformly at random. Observe that for any fixed permutation $\sigma$ of $[n]$, the matrix $M_\sigma(T)$ follows the uniform law in the set of symmetric matrices in $\mathbb{F}_2^{n \times n}$ with diagonal constant to 0. Hence, by Lemma 16, for any fixed diagonal $n \times n$ matrix $D$ we have

$$ \Pr[\text{rk}(M_{\sigma}(T) + D) \le n - r] \le 2^{-\frac{1}{2}(r^2 - 4r)}. $$

and so by Lemma 20 and the Union Bound

$$ \begin{aligned} \Pr[\text{inv}(T) \le n - r] & \le \sum_{\sigma} \sum_{D \in \mathbb{D}_2^{n \times n}} \Pr[\text{rk}(M_{\sigma}(T) + D) \le n - r] \\ & \le n! 2^n 2^{-\frac{1}{2}(r^2 - 4r)} \\ & \le 2^n \log n + n - \frac{1}{2}(r^2/2 - 4r) \\ & < 1 \end{aligned} $$
if $n \log n + n - \frac{1}{2}(r^2 - 4r) < 0$. This last condition holds if $r > 2 + \sqrt{2(n \log n + n + 2)}$. As a consequence, for every positive integer $n$, there exists a tournament of order $n$ with inversion number at least $n - (2 + \sqrt{2(n \log n + n + 2)})$ and so $\text{inv}(n) \ge n - 2\sqrt{n \log n}$ for all sufficiently large integers $n$. $\square$

### 3 Inversion number and dijoin

In this section, we disprove Conjecture 8. We need the following lemmas.

**Lemma 21.** Let $k \ge 3$ be an odd integer. There is a tournament $T_k$ such that $\text{inv}(T_k) = k$ and there are disjoint sets $A_1, \dots, A_{k-1}$ such that $(A_1, \dots, A_{k-1}, \bigcup_{i=1}^{k-1} A_i)$ is a decycling family of $T_k$.

*Proof.* Let $k \ge 3$ be an odd integer and $N = 4^{k-1} + 1$. For every $i \in [k-1]$, let $A_i = \{a_i^1, \dots, a_i^N\}$ and $A'_i = \{a_i^{1'}, \dots, a_i^{N'}\}$ be sets of vertices and define an ordering $<$ on these vertices by

$$a_1^1 < a_1^{1'} < a_1^2 < a_1^{2'} < \dots < a_1^N < a_1^{N'} < a_2^1 < \dots < a_{k-1}^N < a_{k-1}^{N'}.$$

We define $T_k$ as the tournament with vertex set $V(T_k) = \bigcup_{i=1}^{k-1} (A_i \cup A'_i)$, in which the arc between two vertices is oriented according to $<$ (i.e., $xy$ is an arc if and only if $x < y$), except the ones of the form $a_i^j a_{i'}^{j'}$ for $i \neq i'$ which are oriented opposite to $<$. In other words, $T_k$ is obtained from the transitive tournament with hamiltonian path $(a_1^1, a_1^{1'}, a_1^2, a_1^{2'}, \dots, a_1^N, a_1^{N'}, a_2^1, \dots, a_{k-1}^N, a_{k-1}^{N'})$ by reversing all the arcs between the different $A_i$. See Figure 1.

<figure><img src="image_2.png" /><figcaption>Figure 1: The tournament $T_3$ of Lemma 21.</figcaption></figure>

It is straightforward to check that $(A_1, \dots, A_{k-1}, \bigcup_{i=1}^{k-1} A_i)$ is a decycling family of $T_k$. Now we show that $\text{inv}(T_k) \ge k$.

Suppose for a contradiction that there is a smaller decycling family $\mathcal{X}$ of $T_k$. Possibly adding empty sets, we may suppose that $\mathcal{X} = (X_1, \dots, X_{k-1})$ for some $X_1, \dots, X_{k-1} \subseteq$
$V(T_k)$. For every vertex $x$ in $T_k$, its **indicator vector** with respect to $\mathcal{X}$ is the vector $\mathbf{x} = (x_1, \dots, x_{k-1}) \in \mathbb{F}_2^{k-1}$ such that $x_i = 1$ if $x \in X_i$ and $x_i = 0$ otherwise.

For every $i \in [k-1]$ and $j \in [N]$, let $\mathbf{v}_i^j$ and $\mathbf{v}_i^{j'}$ be the indicator vectors of $a_i^j$ and $a_i^{j'}$ respectively. By the Pigeonhole Principle, for every $i \in [k-1]$, there exist distinct indices $j, j' \in [N]$ such that $j < j'$, $\mathbf{v}_i^j = \mathbf{v}_i^{j'}$ and $\mathbf{v}_i^{j'} = \mathbf{v}_i^{j'}$.

Set $\alpha_i^1 = a_i^j$, $\alpha_i^2 = a_i^{j'}$, $\alpha_i^{1'} = a_i^{j'}$, $\alpha_i^{2'} = a_i^{j'}$, $\tilde{A}_i = \{\alpha_i^1, \alpha_i^2\}$, $\mathbf{v}_i = \mathbf{v}_i^j = \mathbf{v}_i^{j'}$, $\tilde{A}_i' = \{\alpha_i^{1'}, \alpha_i^{2'}\}$ and $\mathbf{v}_i' = \mathbf{v}_i^{j'} = \mathbf{v}_i^{j'}$. We also define $\mathbf{u}_i = \mathbf{v}_i + \mathbf{v}_i'$ for every $i \in [k-1]$. We will now extract several constraints on the vectors $\mathbf{u}_i$.

We denote by $\cdot$ the scalar product in $\mathbb{F}_2^{k-1}$. Note that $\mathbf{u} \cdot \mathbf{u} = \mathbf{1} \cdot \mathbf{u}$ for every vector $\mathbf{u} \in \mathbb{F}_2^{k-1}$, where $\mathbf{1} \in \mathbb{F}_2^{k-1}$ is the vector constant to 1.

**Claim 22.** For every $i \in [k-1]$, $\mathbf{u}_i \cdot \mathbf{u}_i = 0$.

*Proof of claim.* First consider the triplet $(\alpha_i^1, \alpha_i^{1'}, \alpha_i^{2'})$. Observe that the arcs between the pairs $\{\alpha_i^1, \alpha_i^{1'}\}$ and $\{\alpha_i^{1'}, \alpha_i^{2'}\}$ are inverted exactly $\sum_{\ell=1}^{k-1} v_{i,\ell}v_{i,\ell'}$ times, and the arc between the pair $\alpha_i^1\alpha_i^{2'}$ has been inverted exactly $\sum_{\ell=1}^{k-1} v_{i,\ell}$ times. But as $\{\alpha_i^1, \alpha_i^{1'}, \alpha_i^{2'}\}$ induces originally a $TT_3$, and must finish as a $TT_3$, we deduce that these quantities must be equal modulo 2. In other words $\sum_{\ell=1}^{k-1} (v_{i,\ell}v_{i,\ell'} + v_{i,\ell}) \equiv 0 \mod 2$, which can be rewritten $\mathbf{v}_i \cdot (\mathbf{v}_i' + \mathbf{v}_i) = 0$.

Similarly, by considering the triplet $(\alpha_i^{1'}, \alpha_i^1, \alpha_i^{2'})$, we deduce the constraint $\mathbf{v}_i' \cdot (\mathbf{v}_i' + \mathbf{v}_i) = 0$. Then we deduce from the last two equalities

$$ \mathbf{u}_i \cdot \mathbf{u}_i = 0, \text{ for all } i \in [k-1]. \quad \diamond $$

**Claim 23.** For every distinct $i_1, i_2 \in [k-1]$, $\mathbf{u}_{i_1} \cdot \mathbf{u}_{i_2} = 1$.

*Proof of claim.* Consider the triplets in $\tilde{A}_{i_1} \times \tilde{A}_{i_1}' \times \tilde{A}_{i_2}$ for distinct $i_1, i_2 \in [k+1]$. Observe that there is always an arc from $\tilde{A}_{i_1}$ to $\alpha_{i_1}'$, and an arc from $\alpha_{i_1}'$ to $\tilde{A}_{i_1}$. Further observe that all arcs between $\tilde{A}_{i_1}$ and $\tilde{A}_{i_2}$ are oriented in the same direction in $\mathrm{Inv}(D, \mathcal{X})$. As $\mathrm{Inv}(D, \mathcal{X})$ is acyclic, this yields that in $\mathrm{Inv}(D, \mathcal{X})$, we have either $(\tilde{A}_{i_1} \cup \tilde{A}_{i_1}') \Rightarrow \tilde{A}_{i_2}$ or $\tilde{A}_{i_2} \Rightarrow (\tilde{A}_{i_1} \cup \tilde{A}_{i_1}')$. Therefore, the number of times the arcs from $\tilde{A}_{i_1}'$ to $\tilde{A}_{i_2}$ are inverted plus the number of times the arcs from $\tilde{A}_{i_2}$ to $\tilde{A}_{i_1}$ are inverted must be odd. Hence $\mathbf{v}_{i_1}' \cdot \mathbf{v}_{i_2} + \mathbf{v}_{i_2}' \cdot \mathbf{v}_{i_1} = 1$. Similarly, by considering the triplets in $\tilde{A}_{i_1} \times \tilde{A}_{i_1}' \times \tilde{A}_{i_2}'$, we get $\mathbf{v}_{i_1}' \cdot \mathbf{v}_{i_2} + \mathbf{v}_{i_2}' \cdot \mathbf{v}_{i_1} = 0$. Summing these two equalities we obtain

$$ \mathbf{u}_{i_1} \cdot \mathbf{u}_{i_2} = 1 \quad \text{for all } i_1, i_2 \in [k-1] \text{ such that } i_1 \neq i_2. \quad \diamond $$

Now consider the matrix $U \in \mathbb{F}_2^{(k-1) \times (k-1)}$ with column number $i$ being $\mathbf{u}_i$. Claims (22) and (23) yield

$$ U^{\top} \cdot U = \begin{pmatrix} 0 & (1) \\ \cdot\cdot\cdot & \\ (1) & 0 \end{pmatrix} = M \quad (3) $$

where $M$ is the $(k-1) \times (k-1)$ matrix with a 1 in every cell, except in the diagonal which is constant to 0. As $k$ is odd, we have $M^2 = I_{k-1}$. Thus $M$ has rank $k-1$,
and every solution $U$ to (3) is invertible. We will construct a solution $U'$ with a line equal to 0, which is a contradiction. To do so, observe that in any solution $U$ to (3), for every column $i_1$, adding $\mathbf{1}$, the vector constant to 1, to this column yields a new solution. Indeed, if $\mathbf{u}_{i_1} \cdot \mathbf{u}_{i_1} = \mathbf{1} \cdot \mathbf{u}_{i_1} = 0$, $\mathbf{u}_{i_2} \cdot \mathbf{u}_{i_2} = \mathbf{1} \cdot \mathbf{u}_{i_2} = 0$ and $\mathbf{u}_{i_1} \cdot \mathbf{u}_{i_2} = 1$, then $(\mathbf{u}_{i_1} + \mathbf{1}) \cdot (\mathbf{u}_{i_1} + \mathbf{1}) = 0 + 0 + 0 + \mathbf{1} \cdot \mathbf{1} = 0$ (because $k-1$ is even) and $(\mathbf{u}_{i_1} + \mathbf{1}) \cdot \mathbf{u}_{i_2} = 1 + 0$. Now consider $U'$ obtained from $U$ by adding the vector $\mathbf{1}$ to every column starting by a 1. This gives a solution to (3) with the first row being the vector $\mathbf{0}$, which contradicts the fact that every solution to (3) has full rank.

This contradiction shows that there is no decycling family of length $k-1$ for $T_k$, and so $\mathrm{inv}(T_k) \ge k$. □

We are now ready to give the proof of Theorem 11, which we recall.

**Theorem 11.** For every odd integer $k \ge 3$, there is a tournament $T_k$ with $\mathrm{inv}(T_k) = k$ such that $\mathrm{inv}(T_k \Rightarrow R) \le k + \mathrm{inv}(R) - 1$ for every oriented graph $R$ with $\mathrm{inv}(R) \ge 1$.

*Proof.* Let $T_k$ be as in Lemma 21 with decycling family $(A_1, \dots, A_{k-1}, \bigcup_{i=1}^{k-1} A_i)$. Let $(X_1, \dots, X_p)$ be a decycling family of $R$ with $p = \mathrm{inv}(R)$. One easily checks that

$$ \left( A_1 \cup X_1, \dots, A_{k-1} \cup X_1, \bigcup_{i=1}^{k-1} A_i \cup X_1, X_2, \dots, X_p \right) $$

is a decycling family of $T_k \Rightarrow R$. □

# 4 Splitting into two digraphs with large inversion number

In this section, we give partial positive answers to Conjecture 12 by proving Theorems 13 and 14.

In order to prove Theorem 13, we need the following result of Belkhechine et al. [6].

**Lemma 24.** Let $D$ be an oriented graph and let $x \in V(D)$. Then $\mathrm{inv}(D) \le \mathrm{inv}(D-x)+2$.

We also need a theorem of Belkhechine et al. [6] on inversion-critical tournaments. Let $k$ be a positive integer. A tournament $T$ is **k-inversion-critical** if $\mathrm{inv}(T) = k$ and $\mathrm{inv}(T-x) < k$ for all $x \in V(T)$. We denote by $\mathcal{IC}_k$ the set of $k$-inversion-critical tournaments.

**Theorem 25 (Belkhechine et al. [7]).** For any positive integer $k$, the set $\mathcal{IC}_k$ is finite.

We are now ready to give the proof of Theorem 13, which we recall.

**Theorem 13.** For every two positive integers $k_1, k_2$, there exists an integer $f_T(k_1, k_2)$ such that every tournament $T$ with $\mathrm{inv}(T) \ge f_T(k_1, k_2)$ admits a partition $(V_1, V_2)$ of $V(T)$ such that $\mathrm{inv}(T\langle V_i \rangle) \ge k_i$ for $i = 1, 2$.
*Proof.* For every positive integer $k$, let $p(k)$ be the maximum order of a tournament in $\mathcal{IC}_{k+1} \cup \mathcal{IC}_k$. Such a number exists, by Theorem 25.

We set $f_T(k_1, k_2) = k_2 + 2p(k_1)$.

Let $T$ be a tournament with $\text{inv}(T) \ge f_T(k_1, k_2)$. By Lemma 24, $T$ has a subtournament $T_1$ in $\mathcal{IC}_{k_1+1} \cup \mathcal{IC}_{k_1}$. We have $\text{inv}(T_1) \in \{k_1, k_1+1\}$ and $|V(T_1)| \le p(k_1)$. Set $T_2 = T - T_1$. By Lemma 24, $\text{inv}(T) \le \text{inv}(T_2) + 2p(k_1)$, so $\text{inv}(T_2) \ge k_2$. Hence $(V(T_1), V(T_2))$ is the desired partition. $\square$

We now proceed to the proof of Theorem 14. In fact, we shall prove the following result which directly implies Theorem 14.

**Theorem 26.** Let $D$ be a non-acyclic oriented graph. Then $D$ contains a directed cycle $C$ such that $\text{inv}(D-C) \ge \text{inv}(D) - 10$.

*Proof.* As $D$ is not acyclic, we can choose a shortest directed cycle $C = (v_1, \dots, v_p, v_1)$ in $D$. Set $a = \lfloor p/3 \rfloor$, $b = p - 3a$. Let $Y_1 = \{v_{3i-2} \mid 1 \le i \le a\}$, $Y_2 = \{v_{3i-1} \mid 1 \le i \le a\}$, and $Y_3 = \{v_{3i} \mid 1 \le i \le a\}$, and let $B = V(C) \setminus (Y_1 \cup Y_2 \cup Y_3)$. Note that $|B| = b \le 2$.

First invert a minimum decycling family $\mathcal{X}$ of $D-C$. For any $i \in \{1,2,3\}$, let $Z_i = N^+(Y_i) \setminus C$. Observe that there is no arc from $Z_i$ to $Y_i$ for otherwise $D$ would contain a shorter directed cycle than $C$. Therefore, after inverting $Y_i \cup Z_i$ and $Z_i$, we have all the arcs between $Y_i$ and $Z_i$ directed towards $Y_i$. Hence after doing at most six inversions (two for each $i$) all the arcs between $V(D) \setminus V(C)$ and $Y_1 \cup Y_2 \cup Y_3$ are directed towards $Y_1 \cup Y_2 \cup Y_3$. If $b=0$, then inverting any arc of $C$, we get a decycling family of $D$ of size $\text{inv}(D-C)+7$. Therefore $\text{inv}(D-C) \ge \text{inv}(D)-7$. If not, then $D\langle Y_1 \cup Y_2 \cup Y_3 \rangle$ is acyclic, so $\mathcal{X} \cup \bigcup_{i=1}^3 \{Y_i \cup Z_i, Z_i\}$ is a decycling family of $D-B$. Hence $\text{inv}(D-B) \le \text{inv}(D-C)+6$. Thus, by Lemma 24, $\text{inv}(D) \le \text{inv}(D-B) + 2|B| \le \text{inv}(D-C) + 10$. $\square$

# 5 Further research

## 5.1 Explicit construction of tournaments with large inversion number

The lower bound $n - 2\sqrt{n \log n}$ on $\text{inv}(n)$ is given by a random tournament. It would be interesting to have explicit constructions of tournaments with large inversion number. Theorem 7 provides tournaments of order $n$ with inversion number $\lfloor n/3 \rfloor$. Explicit constructions of tournaments of order $n$ with inversion number larger than $\lfloor n/3 \rfloor$ are not known. An option would be to prove Conjecture 3. Another one is to prove Conjecture 15, which we recall.

**Conjecture 27.** $\text{inv}(\Delta^k(TT_1)) = \text{inv}(\Delta^k(TT_2)) = k+1$.

With the aid of a computer, we verified this conjecture for $k \le 5$. A natural way to prove it would be to prove the following extension: For any digraph $D$, $\text{inv}(\Delta(D)) = \text{inv}(D)+1$. Unfortunately, this does not hold, even for tournaments. Consider for example the rotative $R_5$ tournament on five vertices $v_1, \dots, v_5$ in which $v_i \to v_j$ if and only if $j-i \mod 5 \in \{1,2\}$. Let $uv$ be the arc of $\Delta(R_5) - V(R_5)$. Setting $X = \{v_2, v_4\}$ and
$\overline{X} = \{v_1, v_3, v_5\}$, one easily checks that $\mathrm{inv}(R_5) = 2$ and $(X, \overline{X})$ is a decycling family of $R_5$. Thus $(X \cup \{v\}, \overline{X} \cup \{v\})$ is a decycling family of $\Delta(R_5)$. Hence $\mathrm{inv}(\Delta(R_5)) = \mathrm{inv}(R_5) = 2$. However the statement holds for oriented graphs with inversion number at most 1.

**Proposition 28.** If $\mathrm{inv}(D) \le 1$, then $\mathrm{inv}(\Delta(D)) = \mathrm{inv}(D) + 1$.

*Proof.* The result holds trivially when $\mathrm{inv}(D) = 0$.

Assume now $\mathrm{inv}(D) = 1$. Clearly, $\mathrm{inv}(\Delta(D)) \le \mathrm{inv}(D) + 1$. Suppose for a contradiction that there is a decycling set $X$ of $\Delta(D)$. Then $X \cap V(D)$ is a non-empty strict subset of $V(D)$ for otherwise inverting $X$ would either entirely reverse $D$ or leave it unchanged. In both cases, a directed cycle would remain, a contradiction. So there is a vertex $x \in X \cap V(D)$ and a vertex $y \in V(D) \setminus X$. Let $uv$ be the arc of $\Delta(D) - D$. By definition in $\Delta(D)$, for any $x \in V(D)$, $xu$ and $vx$ are arcs in $\Delta(D)$. If $X \cap \{u, v\} = \emptyset$, then $(u, v, x, u)$ is a directed 3-cycle in $\mathrm{Inv}(D; X)$. If $X \cap \{u, v\} = \{u, v\}$, then $(v, u, x, v)$ is a directed 3-cycle in $\mathrm{Inv}(D; X)$. If $|X \cap \{u, v\}| = 1$, then $(u, v, y, u)$ is a directed 3-cycle in $\mathrm{Inv}(D; X)$. In all cases, we get a contradiction, so $\mathrm{inv}(\Delta(D)) = 2 = \mathrm{inv}(D) + 1$. $\square$

**Theorem 29.** $\mathrm{inv}(\Delta^{k-1}(TT_2)) \ge k/2 - 1$.

*Proof.* Let $D_k = \Delta^{k-1}(TT_2)$. We write $V(D_k) = \{a_1, b_1, a_2, b_2, \dots, a_k, b_k\}$, with $a_ib_i$ being the arc of $D_i - D_{i-1}$. Let $\ell = \mathrm{inv}(D_k)$ and let $\mathcal{X} = (X_1, \dots, X_\ell)$ be a decycling family for $D_k$. For every $i \in [k]$, we denote by $v_i$ (resp. $w_i$) the vector in $\mathbb{F}_2^\ell$ with coordinates number $j$ being 1 if and only if $a_i \in X_j$ (resp. $b_i \in X_j$). Consider the matrices $V$ with columns $v_i$ and $W$ with columns $w_i$. Let $M$ be the matrix defined by $M = (m_{ij}) = V^\top W + I_k \in \mathbb{F}_2^{k \times k}$ where $I_k$ denotes the identity matrix of size $k$.

**Claim 30.** $M$ contains no submatrices $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ and $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$.

*Proof of claim.* Note that $m_{ij}$ represents the inversion of the arc $b_j a_i$ in $\mathrm{Inv}(D_k; \mathcal{X})$: if $m_{ij} = 1$, then $a_ib_j \in A(\mathrm{Inv}(D_k; \mathcal{X}))$, and if $m_{ij} = 0$, then $b_j a_i \in A(\mathrm{Inv}(D_k; \mathcal{X}))$. Hence if there were a submatrix $\begin{pmatrix} m_{i_1j_1} & m_{i_1j_2} \\ m_{i_2j_1} & m_{i_2j_2} \end{pmatrix}$ equal to $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ (resp. $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$), then $a_{i_2}b_{j_1}a_{i_1}b_{j_2}a_{i_2}$ (resp. $a_{i_1}b_{j_1}a_{i_2}b_{j_2}a_{i_1}$) would be a directed 4-cycle in $\mathrm{Inv}(D_k; \mathcal{X})$, a contradiction. $\diamond$

We will now show using this claim that $V^\top W = M + I$ has rank at least $\lceil \frac{k}{2} \rceil - 1$, which will imply $\mathrm{inv}(D_k) = \ell \ge \lceil \frac{k}{2} \rceil - 1$. As $M$ contains no submatrices $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ and $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$, the columns of $M$ are ordered by inclusion. By sorting the columns (and the rows with the same order) according to this ordering, we can now suppose that each row is of the form $1 \dots 10 \dots 0$. Let $n_i$ be the number of 1 in the row number $i$. If $|\{i \in [k] \mid n_i \ge i\}| \ge k/2$, then the rows in $M + I + (1)_{i,j}$ with indices in $\{i \in [k] \mid n_i \ge i\}$ are linearly independent, and as $(1)_{i,j}$ has rank 1, $M + I$ has rank at least $\frac{k}{2} - 1$. Here, $(1)_{i,j}$ denotes the $k \times k$ matrix constant to 1. Otherwise, $|\{i \in [k] \mid n_i \ge i\}| < k/2$ and the rows with indices in $\{i \in [k] \mid n_i < i\}$ in $M + I$ are linearly independent. In both cases, $\mathrm{rk}(M + I) = \mathrm{rk}(V^\top W) \ge k/2 - 1$ and so $\mathrm{inv}(D_k) \ge k/2 - 1$. $\square$
## 5.2 Inversion number and dijoin

Corollary 11 shows that for any odd integer $k \ge 3$, there is a tournament $T_k$ with $\text{inv}(T_k) = k$ such that $\text{inv}(T_k \Rightarrow R) < k + \text{inv}(R)$ for all $R$ with $\text{inv}(R) \ge 1$. We conjecture that the same statement also holds for even integers.

**Conjecture 31.** For any $k \ge 3$, there is a tournament $T_k$ with $\text{inv}(T_k) = k$ such that $\text{inv}(T_k \Rightarrow R) < k + \text{inv}(R)$ for all $R$ with $\text{inv}(R) \ge 1$.

During the submission process of this paper, Conjecture 31 has been disproved by Wang et al.[9] who showed the following.

**Theorem 32 (Wang et al.[9]).** Let $k \ge 2$ be an even integer. For all oriented graphs $L$ and $R$ with $\text{inv}(L) = k$ and $\text{inv}(R) = 1$, we have $\text{inv}(L \Rightarrow R) = \text{inv}(R \Rightarrow L) = \text{inv}(L) + \text{inv}(R) = k + 1$.

The disproof of Conjecture 8 also raises the question to which extent approximate versions of this conjecture could be true. For any two non-negative integers $\ell$ and $r$, let $\text{minv}(\ell, r) = \min\{\text{inv}(L \Rightarrow R) \mid \text{inv}(L) = \ell \text{ and } \text{inv}(R) = r\}$.

**Problem 33.** Determine $\text{minv}(\ell, r)$ for all $\ell$ and $r$.

We clearly have $\max\{\ell, r\} \le \text{minv}(\ell, r) \le \ell + r$ and Corollary 11 shows that the upper bound is often not tight. Is the lower bound tight ?

A first problem is the following.

**Problem 34.** Does there exist a non-acyclic oriented graph $D$ such that $\text{inv}(D \Rightarrow D) = \text{inv}(D)$ ?

During the submission process of this paper, Problem 34 has been answered in the negative by Behague et al. [5] who proved the following.

**Theorem 35 (Behague et al. [5]).** Let $D_1$ and $D_2$ be oriented graphs such that $\text{inv}(D_1) = \text{inv}(D_2) \ge 1$. Then $\text{inv}(D_1 \Rightarrow D_2) > \text{inv}(D_1)$.

A different direction for further research is motivated by the following observation. Every non-acyclic tournament $T$ contains a directed 3-cycle. Therefore $TT_n[T]$ contains $TT_n[\vec{C}_3]$, and so $\text{inv}(TT_n[T]) \ge \text{inv}(TT_n[\vec{C}_3]) = n$. This raises the question of the following generalization of Theorem 7.

**Problem 36.** What is the maximum function $h$ such that $\text{inv}(TT_n[T]) \ge h(\text{inv}(T), n)$ for every tournament $T$ ?

## Acknowledgements

This work was partially supported by the french Agence Nationale de la Recherche under contract Digraphs ANR-19-CE48-0013-01. It started at a workshop at Maison Clment, Les Plantiers, devoted to digraphs problems; we would like to express our thanks to Pierre Aboulker for organizing it (jointly with the second author). Also, we wish to thank Pierre Charbit, Julien Duron, and Emeric Gioan, who worked with us during the workshop and later.
References

[1] N. Alon. Disjoint directed cycles. *Journal of Combinatorial Theory, Series B*, 68(2):167–178, 1996.

[2] N. Alon, E. Powierski, M. Savery, A. Scott, and E. Wilmer. Invertibility of digraphs and tournaments. *SIAM Journal on Discrete Mathematics*, 38(1):327–347, 2024. [arXiv:2212.11969](https://arxiv.org/abs/2212.11969)

[3] J. Bang-Jensen, J. C. F. da Silva, and F. Havet. On the inversion number of oriented graphs. *Discrete Mathematics & Theoretical Computer Science*, 23(2), 2022. [arXiv:2105.04137](https://arxiv.org/abs/2105.04137)

[4] J. Bang-Jensen and G. Z. Gutin. *Digraphs: theory, algorithms and applications*. Springer-Verlag, London, 2009.

[5] N. Behague, T. Johnston, N. Morrison, and S. Ogden. A note on the invertibility of oriented graphs, 2024. [arXiv:2404.10663](https://arxiv.org/abs/2404.10663)

[6] H. Belkhechine, M. Bouaziz, I. Boudabbous, and M. Pouzet. Inversions in tournaments. *unpublished*.

[7] H. Belkhechine, M. Bouaziz, I. Boudabbous, and M. Pouzet. Inversion dans les tournois. *Comptes Rendus Mathematique*, 348(13-14):703–707, 2010. [arXiv:1007.2103](https://arxiv.org/abs/1007.2103)

[8] M. Pouzet, H. Si Kaddour, and B. Thatte. On the boolean dimension of a graph and other related parameters. *Discrete Mathematics & Theoretical Computer Science*, 23, 2022. [arXiv:2105.00206](https://arxiv.org/abs/2105.00206)

[9] H. Wang, Y. Yang, and M. Lu. The inversion number of dijoins and blow-up digraphs, 2024. [arXiv:2404.14937](https://arxiv.org/abs/2404.14937)