betaFeedback

WorksMathematics

Inverting Dependently Random Tournaments

Abstract

Let inv(T)\text{inv}(T) be the inversion index of the tournament TT. Answering a question of Behague, we show that inv(T1→T2)=inv(T1)+inv(T2)\text{inv}(T_1\to T_2)=\text{inv}(T_1)+\text{inv}(T_2) does not even hold asymptotically.

Consider nn vertices, labelled by [n]={1,2,…,n}[n] = \{1, 2, \ldots, n\}, and for every unordered pair {i,j}⊂[n]\{i, j\} \subset[n], an arrow (i,j)(i, j) from ii to jj or an arrow (j,i)(j, i) from jj to ii. 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 T1T_1 and T2T_2 be tournaments on n1n_1 and n2n_2 vertices. Their join T1→T2T_1 \to T_2 is a tournament on n1+n2n_1 + n_2 vertices, corresponding to the vertices of T1T_1 and of T2T_2, with arrows as in T1T_1 or T2T_2 and arrows from T1T_1-vertices to T2T_2-vertices.

For a subset X⊆[n]X \subseteq[n], replacing the arrow (i,j)(i, j) with (j,i)(j, i) whenever {i,j}⊂X\{i, j\} \subset X is called an XX-inversion. To see an example, if X1X_1 and X2X_2 are the vertex sets of the T1T_1 and T2T_2 in their join T1→T2T_1 \to T_2, inverting X1X_1, X2X_2, and X1∪X2X_1 \cup X_2 yields T2→T1T_2 \to T_1.

Definition 2. The least number of inversions required to reach a transitive tournament from the tournament TT is the inversion number inv⁡(T)\operatorname{inv}(T) of TT.

Similarly to the inversion of graphs, where non-edges are interchanged with edges [3], tournament inversion is intricately connected with linear algebra over F2\mathbb{F}_2 [4].

We biject a sequence of vertex sets X1,…,XkX_1,\ldots,X_k with an array of nn vectors (vi)i=1n(\mathbf{v}_i)_{i=1}^n, where the tt-th component of vi∈F2k\mathbf{v}_i \in\mathbb{F}_2^k is 1 if i∈Xti \in X_t and else 0. The arrow of {i,j}\{i,j\} is reversed by XtX_t-inversion if and only if (vi)t(vj)t=1(\mathbf{v}_i)_t(\mathbf{v}_j)_t=1, so the formal dot product

vi⋅vj=∑t=1k(vi)t(vj)t\mathbf{v}_i \cdot\mathbf{v}_j = \sum_{t=1}^{k}(\mathbf{v}_i)_t(\mathbf{v}_j)_t

indicates whether (i,j)(i,j) is reversed by these kk inversions.

For each nn, is there a tournament with inversion number nn? The answer is yes: the nn-fold join of the 3-cycle C3C_3. One reason is that the F2\mathbb{F}_2-vectors vi\mathbf{v}_i 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, inv⁡(T→C3)=inv⁡(T)+1\operatorname{inv}(T \to C_3)=\operatorname{inv}(T)+1 if inv⁡(T)\operatorname{inv}(T) is even [6], but for every odd k≥3k \ge3, there is a tournament TkT_k with inv⁡(Tk)=k\operatorname{inv}(T_k)=k such that for all tournaments T′T', inv⁡(Tk→T′)<k+inv⁡(T′)\operatorname{inv}(T_k \to T') < k+\operatorname{inv}(T') unless T′T' is transitive [7].

In light of the trivial bounds

max⁡{inv⁡(T1),inv⁡(T2)}≤inv⁡(T1→T2)≤inv⁡(T1)+inv⁡(T2),\max\{\operatorname{inv}(T_1),\operatorname{inv}(T_2)\} \le\operatorname{inv}(T_1 \to T_2) \le\operatorname{inv}(T_1)+\operatorname{inv}(T_2),

one could inquire into which possible values of inv⁡(T1→T2)\operatorname{inv}(T_1 \to T_2) can be achieved, depending on (inv⁡(T1),inv⁡(T2))(\operatorname{inv}(T_1),\operatorname{inv}(T_2)). By inspecting matrix rank, the lower bound cannot be attained if inv⁡(T1),inv⁡(T2)≥2\operatorname{inv}(T_1),\operatorname{inv}(T_2) \ge2 or inv⁡(T1)\operatorname{inv}(T_1) is even and inv⁡(T2)=1\operatorname{inv}(T_2)=1 [8], [9]. While the joins of C3C_3 are a case of equality for the upper bound, it has not been known whether inv⁡(T1→T2)=inv⁡(T1)+inv⁡(T2)−O(1)\operatorname{inv}(T_1 \to T_2)=\operatorname{inv}(T_1)+\operatorname{inv}(T_2)-O(1) [10]. We disprove this.

Theorem 3. Let nn be a positive integer. Then there exist tournaments T1T_1 and T2T_2 such that inv⁡(T1→T2)≤n\operatorname{inv}(T_1 \to T_2) \le n, yet inv⁡(Tm)=n−o(n)\operatorname{inv}(T_m)=n-o(n) for m=1,2m=1,2.

Our proof relies on a probabilistic result from the related question of maximising inv⁡(T)\operatorname{inv}(T) across tournaments TT with nn vertices: for a uniformly random tournament TT, inv⁡(T)≥n−2nlog⁡2n\operatorname{inv}(T) \ge n-\sqrt{2n\log_2 n} with probability tending to 1 as n→∞n \to\infty [11]. We remark that the greatest inv⁡(T)\operatorname{inv}(T) achieved by a deterministic TT, for arbitrarily large nn, is ⌊n−12⌋\left\lfloor\frac{n-1}{2}\right\rfloor (a transitive tournament with its unique Hamilton path reversed) [12].

Proof of Theorem 3. Suppose that TT and SS are each tournaments with nn vertices. It is easy to show that their inversion number must be less than nn [5], but we assume there are column vectors v1,…,vn\mathbf{v}_1,\ldots,\mathbf{v}_n and u1,…,un\mathbf{u}_1,\ldots,\mathbf{u}_n encoding nn inversions that change TT and SS into the increasing linear order, respectively. By introducing a dependency between the vi\mathbf{v}_i and uj\mathbf{u}_j, we shall make these inversions change T→ST \to S into the lexicographic order n+1<1<n+2<2<⋯<nn+1 < 1 < n+2 < 2 < \cdots< n. By the probabilistic method, we can guarantee inv⁡(T),inv⁡(S)=n−o(n)\operatorname{inv}(T),\operatorname{inv}(S)=n-o(n).

Let the matrix with columns vi\mathbf{v}_i and uj\mathbf{u}_j be AA and BB, respectively. The arrow from vertex ii of TT to vertex jj of SS is reversed with parity vi⋅uj\mathbf{v}_i \cdot\mathbf{u}_j, and so if vi⋅uj=1i≥j\mathbf{v}_i \cdot\mathbf{u}_j=1_{i\geq j}, then inv⁡(T→S)≤n\operatorname{inv}(T \to S) \leq n in the aforementioned way. Hence, we require

ATB=(1i≥j)i,j=:L.A^{T}B=(1_{i\geq j})_{i,j}=:L.

Motivated by this, let AA be in upper triangular form, with Aii=1A_{ii}=1 for all i∈[n]i\in[n] and Aij=0A_{ij}=0 or Aij=1A_{ij}=1 for all i<ji<j with equal chance, independently. Since the determinant of ATA^{T} is 11, it is invertible, so we can let B=(AT)−1LB=(A^{T})^{-1}L.

By applying the inversions encoded by AA and BB to the increasing linear order, we obtain the dependently random tournaments TT and SS, respectively. However, TT and SS are uniformly random. Indeed, if i<ni<n, switching AinA_{in} to 1−Ain1-A_{in} reverses the arrows precisely of the pairs {j,n}\{j,n\} with Aij=1A_{ij}=1. In particular, {i,n}\{i,n\} is reversed and {j,n}\{j,n\} is not reversed if j<ij<i. Hence, by double induction, all 2(n2)2^{\binom{n}{2}} possible tournaments TT can arise for some value of AA, so each of the 2(n2)2^{\binom{n}{2}} possible values of AA define a unique tournament. As for SS, the adjoints of (AT)−1(A^{T})^{-1} over the diagonal are 00 and on the diagonal are 11, which implies that BB is lower triangular with Bii=1B_{ii}=1 for all i∈[n]i\in[n], but A=(LB−1)TA=(LB^{-1})^{T}, so B∼AB\sim A.

Since TT is uniformly random, inv⁡(T)<n−O(nlog⁡n)\operatorname{inv}(T)<n-O(\sqrt{n\log n}) with probability less than 12\frac{1}{2}, and similarly for SS [11]. By the union bound, an instance of TT and SS exists for which inv⁡(T),inv⁡(S)≥n−O(nlog⁡n)\operatorname{inv}(T),\operatorname{inv}(S)\geq n-O(\sqrt{n\log n}), whilst inv⁡(T→S)≤n\operatorname{inv}(T\to S)\leq n. □\square

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. [1]Belkhechine, H., Bouaziz, M., Boudabbous, I., Pouzet, M. Inversion dans les tournois. Comptes Rendus Mathematique 348 (13), 703-707, 2010.DOI
  2. [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. [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. [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. [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. [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. [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. [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. [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. [10]Cameron et al. Problems from BCC30. Arxiv preprint, arXiv:2409.07216, 2024.arxiv.org/abs/2409.07216
  11. [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. [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

Paper details

vlnc:W_s8rp2svv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents