The full range of counterexamples to the dijoin conjecture

From papers

Let LL and RR be oriented graphs, and let LRL\rightarrow R be their dijoin. The dijoin conjecture asserts that its inversion number equals the sum of the inversion numbers of the factors.

Dijoin counterexample-range conjecture. For all ,rN\ell,r\in\mathbb{N} with 3\ell\geq 3 or r3r\geq 3, there exist oriented graphs LL and RR such that

inv(L)=,inv(R)=r,\operatorname{inv}(L)=\ell,\qquad \operatorname{inv}(R)=r,

and

inv(LR)<+r.\operatorname{inv}(L\rightarrow R)<\ell+r.

The paper has counterexamples with one inversion number equal to 33 and explains an equivalent formulation using tournaments, but the general assertion remains conjectural.

Progress summary

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

Sources & referencesView supporting material

Primary source

Noga Alon, Emil Powierski, Michael Savery, Alex Scott and Elizabeth Wilmer, “Invertibility of digraphs and tournaments”, arXiv:2212.11969 (2024).

Solutions 0

No solutions have been posted yet.