The extension conjecture for oriented trees

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(2n2)C^k(2n-2)-unavoidable; that is,

unvd(D)Ck(2n2).\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.

Sources & referencesView supporting material

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.