The extension conjecture for oriented trees

About 2 years old · traced to

Let DD be a kk-extension of an oriented tree of order nn, meaning that there is a set of kk vertices whose deletion leaves the tree. Let unvd⁡(D)\operatorname{unvd}(D) denote unavoidability.

Extension conjecture. There is an absolute constant CC such that, for every integer kk, every kk-extension of an oriented tree of order nn is Ck(2n−2)C^k(2n-2)-unavoidable; that is,

unvd⁡(D)⩽Ck(2n−2).\operatorname{unvd}(D)\leqslant C^k(2n-2).

The source says this follows from the vertex-deletion conjecture together with Sumner's conjecture, so it is currently open with those conjectures. It concerns controlling the effect of adding finitely many vertices to an oriented tree.

References

Primary source

Pierre Aboulker, Frédéric Havet, William Lochet, Raul Lopes, Lucas Picasarri-Arrieta and Clément Rambaud, “Blow-ups and extensions of trees in tournaments”, arXiv:2410.23566 (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.