The full range of counterexamples to the dijoin conjecture

About 4 years old · traced to

Let LL and RR be oriented graphs, and let L→RL\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 ℓ,r∈N\ell,r\in\mathbb{N} with ℓ≥3\ell\geq 3 or r≥3r\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⁡(L→R)<ℓ+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.

References

Primary source

Noga Alon, Emil Powierski, Michael Savery, Alex Scott and Elizabeth Wilmer, “Invertibility of digraphs and tournaments”, arXiv:2212.11969 (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.