WorksMathematics
Inverting Dependently Random Tournaments
Abstract
Let be the inversion index of the tournament . Answering a question of Behague, we show that does not even hold asymptotically.
Consider vertices, labelled by , and for every unordered pair , an arrow from to or an arrow from to . Such a vertex set and set of ordered pairs is known as a tournament [1]. If the relation defined by the set of arrows is transitive, it is a transitive tournament.
A fundamental result in the study of tournaments is that a Hamiltonian directed circuit is to be found in a tournament if and only if it is not a dijoin [2].
Definition 1. Let and be tournaments on and vertices. Their join is a tournament on vertices, corresponding to the vertices of and of , with arrows as in or and arrows from -vertices to -vertices.
For a subset , replacing the arrow with whenever is called an -inversion. To see an example, if and are the vertex sets of the and in their join , inverting , , and yields .
Definition 2. The least number of inversions required to reach a transitive tournament from the tournament is the inversion number of .
Similarly to the inversion of graphs, where non-edges are interchanged with edges [3], tournament inversion is intricately connected with linear algebra over [4].
We biject a sequence of vertex sets with an array of vectors , where the -th component of is 1 if and else 0. The arrow of is reversed by -inversion if and only if , so the formal dot product
indicates whether is reversed by these inversions.
For each , is there a tournament with inversion number ? The answer is yes: the -fold join of the 3-cycle . One reason is that the -vectors are linearly independent [4]. Such a non-elementary argument raised the question of whether the inversion number of a join is necessarily the sum of the individual inversion numbers [5]. As it turns out, if is even [6], but for every odd , there is a tournament with such that for all tournaments , unless is transitive [7].
In light of the trivial bounds
one could inquire into which possible values of can be achieved, depending on . By inspecting matrix rank, the lower bound cannot be attained if or is even and [8], [9]. While the joins of are a case of equality for the upper bound, it has not been known whether [10]. We disprove this.
Theorem 3. Let be a positive integer. Then there exist tournaments and such that , yet for .
Our proof relies on a probabilistic result from the related question of maximising across tournaments with vertices: for a uniformly random tournament , with probability tending to 1 as [11]. We remark that the greatest achieved by a deterministic , for arbitrarily large , is (a transitive tournament with its unique Hamilton path reversed) [12].
Proof of Theorem 3. Suppose that and are each tournaments with vertices. It is easy to show that their inversion number must be less than [5], but we assume there are column vectors and encoding inversions that change and into the increasing linear order, respectively. By introducing a dependency between the and , we shall make these inversions change into the lexicographic order . By the probabilistic method, we can guarantee .
Let the matrix with columns and be and , respectively. The arrow from vertex of to vertex of is reversed with parity , and so if , then in the aforementioned way. Hence, we require
Motivated by this, let be in upper triangular form, with for all and or for all with equal chance, independently. Since the determinant of is , it is invertible, so we can let .
By applying the inversions encoded by and to the increasing linear order, we obtain the dependently random tournaments and , respectively. However, and are uniformly random. Indeed, if , switching to reverses the arrows precisely of the pairs with . In particular, is reversed and is not reversed if . Hence, by double induction, all possible tournaments can arise for some value of , so each of the possible values of define a unique tournament. As for , the adjoints of over the diagonal are and on the diagonal are , which implies that is lower triangular with for all , but , so .
Since is uniformly random, with probability less than , and similarly for [11]. By the union bound, an instance of and exists for which , whilst .
This proof was found using an LLM and communicated by the self-funded author.
INDEPENDENT AUTHOR IN CAMBRIDGE, UNITED KINGDOM.
E-mail address: [email protected]
References
- [1]Belkhechine, H., Bouaziz, M., Boudabbous, I., Pouzet, M. Inversion dans les tournois. Comptes Rendus Mathematique 348 (13), 703-707, 2010.DOI
- [2]A. Ghouila-Houri. Une condition suffisante d’existence d’un circuit Hamiltonien. Comptes Rendus de l’Academie des Sciences Paris Série A-B 251, 495-497, 1960.
- [3]Buchanan, C., Purcell, C., Rombach, P. Subgraph complementation and minimum rank. The Electronic Journal of Combinatorics 29 (1), Article 1.38, 2022.DOI
- [4]Pouzet, M., Si Kaddour, H., Thatte, B. D. On the Boolean dimension of a graph and other related parameters. Discrete Mathematics and Theoretical Computer Science 23 (2), Article 5, 2022.
- [5]Bang-Jensen, J., Havet, F., da Silva, J. C. F. On the inversion number of oriented graphs. Discrete Mathematics and Theoretical Computer Science 23 (2), Article 8, 2022.
- [6]Lu, M., Wang, H., Yang, Y. The inversion number of dijoin and blow-up digraphs. Arxiv preprint, arXiv:2404.14937, 2024.arxiv.org/abs/2404.14937
- [7]Aubian, G., Havet, F., Hörsch, F., Kingelhofer, F., Nisse, N., Rambaud, C., Vermande, Q. Problems, proofs, and disproofs on the inversion number. The Electronic Journal of Combinatorics 32 (1), Article 1.42, 2025.arxiv.org/abs/2212.09188
- [8]Behague, N., Johnston, T., Morrison, N., Ogden, S. A note on inverting the dijoin of oriented graphs. The Electronic Journal of Combinatorics 32 (1), Article 1.44, 2025.DOI
- [9]Behague, N., Gaudart-Wifling, P. A case of the dijoin conjecture on inverting oriented graphs. Arxiv preprint, arXiv:2509.10232, 2025.arxiv.org/abs/2509.10232
- [10]Cameron et al. Problems from BCC30. Arxiv preprint, arXiv:2409.07216, 2024.arxiv.org/abs/2409.07216
- [11]Alon, N., Powierski, E., Savery, M., Scott, A., Wilmer, E. Invertibility of digraphs and tournaments. SIAM Journal on Discrete Mathematics 38 (1), 327-347, 2024.DOI
- [12]Mao, Y. The inversion number of a path-reversed tournament: Resolving a conjecture of Belkhechine, Bouaziz, Boudabbous, and Pouzet. Arxiv preprint, arXiv:2607.13829, July 2026.arxiv.org/abs/2607.13829