A vertex whose deletion decreases inversion number by at most one

About 4 years old · traced to

Let DD be a digraph with at least one vertex. For v∈V(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 v∈V(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.

References

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.