The all-kk counterexample conjecture for dijoin additivity

About 4 years old · traced to

For an integer k≥3k\geq3, let TkT_k be a tournament and let RR be an oriented graph; Tk⇒RT_k\Rightarrow R denotes their dijoin, formed by adding all arcs from TkT_k to RR.

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

inv⁡(Tk⇒R)<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 k≥3k\geq3 and conjectures that the same phenomenon holds for even integers. Thus the remaining content concerns even kk.

References

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.