Alon's partition conjecture for inversion number

For an oriented graph DD and a vertex subset ViV_i, write DViD\langle V_i\rangle for the subdigraph induced by ViV_i; let inv(D)\operatorname{inv}(D) denote inversion number.

Alon's inversion-number partition conjecture. For every two positive integers k1,k2k_1,k_2, there exists an integer f(k1,k2)f(k_1,k_2) such that every oriented graph DD with

inv(D)f(k1,k2)\operatorname{inv}(D)\geq f(k_1,k_2)

admits a partition (V1,V2)(V_1,V_2) of V(D)V(D) satisfying

inv(DVi)kifor i=1,2.\operatorname{inv}(D\langle V_i\rangle)\geq k_i\quad\text{for }i=1,2.

This asks for an inversion-number analogue of Alon's minimum-out-degree partition conjecture: sufficiently large global inversion number should force both parts to retain prescribed inversion complexity. The source does not state a resolution.

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.