A vertex whose deletion decreases inversion number by at most one

Let DD be a digraph with at least one vertex. For vV(D)v\in V(D), write D{v}D-\{v\} for the digraph obtained by deleting vv and all incident edges.

Vertex-deletion conjecture. There exists vV(D)v\in V(D) such that

inv(D{v})inv(D)1.\operatorname{inv}(D-\{v\})\geq\operatorname{inv}(D)-1.

Equivalently, the general bound inv(D)inv(D{v})+2\operatorname{inv}(D)\leq\operatorname{inv}(D-\{v\})+2 cannot be tight for every vertex of the same digraph. The supplied text gives no resolution.

Sources & referencesView supporting material

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.