On the failure of additivity of inversion numbers for dijoins
Abstract
Let D be an oriented graph. For X ⊆ V(D), the inversion of X in D is the oriented graph that is obtained via changing the direction of all edges which have both endpoints in X. The inversion number of D, inv(D), is the minimum number of inversions necessary in order to remove all cycles from D. A dijoin D1 → D2 is the oriented graph obtained by taking disjoint copies of D1,D2 and adding edges from all v ∈ V(D1) to each u ∈ V(D2). It was conjectured by Bang-Jensen, da Silva and Havet that inv(D1 → D2) = inv(D1) + inv(D2) for all D1, D2. This was disproved by simultaneous constructions of various D1, D2 with inv(D1 → D2) = inv(D1)+inv(D2)−1. However, no known constructions achieved more than this gain of 1. Moreover, all of the constructions exploit a gap of 1 between inv(D) and the minimum rank of a family of related matrices, a gap that can never be more than 1, suggesting that perhaps something close to the original conjecture might be true. We prove that in fact additivity fails badly. In particular, for all ε>0 we show that there exist tournaments D1, D2 with arbitrarily large inversion numbers such that inv(D1 → D2) ≤ (1/2 +ε)(inv(D1)+inv(D2)).
Related
- ADDITIVITY AXIOM FOR THE TORSION FORMS AND HIGHER CHEEGER-MÜLLER/BISMUT-ZHANG THEOREM
- Playing with additivity conditions in multiplicative functions
- Singularising quantum channels preserving kappa-additivity
- A sphere-product counterexample to the additivity of homology nilpotency
- A constructive violation of additivity of minimum output von Neumann entropy
BibTeX
@misc{behague2026failure,
title = {{On the failure of additivity of inversion numbers for dijoins}},
author = {Natalie Behague and Jack Cromwell},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13798},
eprint = {2610.13798},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13798},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - On the failure of additivity of inversion numbers for dijoins
AU - Natalie Behague
AU - Jack Cromwell
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.13798
UR - https://arxiv.org/abs/2610.13798
AB - Let D be an oriented graph. For X ⊆ V(D), the inversion of X in D is the oriented graph that is obtained via changing the direction of all edges which have both endpoints in X. The inversion number of D, inv(D), is the minimum number of inversions necessary in order to remove all cycles from D. A dijoin D_1 → D_2 is the oriented graph obtained by taking disjoint copies of D_1,D_2 and adding edges from all v ∈ V(D_1) to each u ∈ V(D_2). It was conjectured by Bang-Jensen, da Silva and Havet that inv(D_1 → D_2) = inv(D_1) + inv(D_2) for all D_1, D_2. This was disproved by simultaneous constructions of various D_1, D_2 with inv(D_1 → D_2) = inv(D_1)+inv(D_2)−1. However, no known constructions achieved more than this gain of 1. Moreover, all of the constructions exploit a gap of 1 between inv(D) and the minimum rank of a family of related matrices, a gap that can never be more than 1, suggesting that perhaps something close to the original conjecture might be true. We prove that in fact additivity fails badly. In particular, for all ε>0 we show that there exist tournaments D_1, D_2 with arbitrarily large inversion numbers such that inv(D_1 → D_2) ≤ (1/2 +ε)(inv(D_1)+inv(D_2)).
ER -