Exponential unavoidability of tree k-extensions

Conjecture 10 · arXiv:2410.23566

arXiv Conjecture high confidence— first stated 2024-10-31

Authors: Pierre Aboulker, Frédéric Havet, William Lochet, Raul Lopes, Lucas Picasarri-Arrieta, Clément Rambaud

Status open high confidence

Conjecture 10 from arXiv:2410.23566 asserts the existence of an absolute constant C such that every k-extension of an oriented tree of order n is C^k(2n-2)-unavoidable. This would follow from Conjecture 9 (multiplicative stability under vertex addition) combined with Sumner's conjecture, but remains open. The paper itself establishes only a weaker bound of (2·3^{\binom{2k+2}{2}}·|V(F)|)-unavoidability (Corollary 25), with super-exponential dependence on k rather than the conjectured simple exponential C^k. No subsequent work resolving or further advancing this conjecture was found in the published literature.

Reviewer notes. No follow-up resolving or partially resolving Conjecture 10 was found after 5 web calls. The conjecture is implied by the still-open Conjecture 9 of the same paper together with the (also open) exact form of Sumner's conjecture. Lucas Picasarri-Arrieta's personal page and Clément Rambaud's arXiv listing show no 2025 papers on this topic.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. There is an absolute constant $C$ such that for every integer $k$, every $k$-extension of an oriented tree of order $n$ is $C^{k}(2n-2)$-unavoidable.

Context

This conjecture is implied by Conjecture 9 (multiplicative stability under vertex addition) together with Sumner's Conjecture 4 (that oriented trees are $(2n-2)$-unavoidable). The paper proves a weaker result in Corollary 25, establishing $(2\cdot 3^{\binom{2k+2}{2}}\cdot|V(F)|)$-unavoidability for $k$-extensions of sufficiently large oriented trees.

Source paper

Blow-ups and extensions of trees in tournaments
Pierre Aboulker, Frédéric Havet, William Lochet, Raul Lopes, Lucas Picasarri-Arrieta, Clément Rambaud · 2024-10-31
https://arxiv.org/abs/2410.23566