Aubian et al.'s universal counterexample conjecture for dijoin inversion

Let LL and RR be oriented graphs, let LRL\Rightarrow R denote their dijoin, and let inv(D)\operatorname{inv}(D) denote the inversion number of an oriented graph DD.

Aubian et al.'s conjecture. For every integer k3k\ge 3, there exists a tournament TkT_k with

inv(Tk)=k\operatorname{inv}(T_k)=k

such that, for every oriented graph RR with inv(R)1\operatorname{inv}(R)\ge 1,

inv(TkR)<k+inv(R).\operatorname{inv}(T_k\Rightarrow R)<k+\operatorname{inv}(R).

The claim extends Aubian et al.'s proved construction for odd k3k\ge3 to all k3k\ge3; the supplied text gives no resolution of the even case.

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.