The all-kk counterexample conjecture for dijoin additivity

For an integer k3k\geq3, let TkT_k be a tournament and let RR be an oriented graph; TkRT_k\Rightarrow R denotes their dijoin, formed by adding all arcs from TkT_k to RR.

The all-kk dijoin counterexample conjecture. For any k3k\geq3, there is a tournament TkT_k with inv(Tk)=k\operatorname{inv}(T_k)=k such that

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

for all RR with inv(R)1\operatorname{inv}(R)\geq1.

The paper proves this statement for every odd integer k3k\geq3 and conjectures that the same phenomenon holds for even integers. Thus the remaining content concerns even kk.

Sources & referencesView supporting material

Primary source

Guillaume Aubian, Frédéric Havet, Florian Hörsch, Felix Klingelhoefer, Nicolas Nisse, Clément Rambaud and Quentin Vermande, “Problems, proofs, and disproofs on the inversion number”, arXiv:2212.09188 (2022).

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.