Bang-Jensen et al.'s dijoin conjecture for inversion number

For digraphs without loops, parallel edges, or 22-cycles, let LL and RR be oriented graphs. The dijoin LRL\Rightarrow R is formed from their disjoint union by adding an arc uvuv for every uV(L)u\in V(L) and vV(R)v\in V(R). The inversion number inv(D)\operatorname{inv}(D) is the minimum size of a family of vertex subsets whose successive inversions make DD acyclic.

Bang-Jensen et al.'s dijoin conjecture. For oriented graphs LL and RR,

inv(LR)=inv(L)+inv(R).\operatorname{inv}(L\Rightarrow R)=\operatorname{inv}(L)+\operatorname{inv}(R).

The conjecture is trivial when one of the two inversion numbers is zero and is known when their sum is at most 33, as well as when both are 22. It is false in general: counterexamples were independently found by Alon et al. and Aubian et al.

Sources & referencesView supporting material

Primary source

Haozhe Wang, Yuxuan Yang and Mei Lu, “The inversion number of dijoins and blow-up digraphs”, arXiv:2404.14937 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.