Unavoidability rate of k-extensions in tournaments

Problem 12 · arXiv:2410.23566

arXiv Problem 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

Problem 12 asks for the minimum function $f$ such that every $k$-extension of every forest of order $n$ is $(2^{f(k)}\cdot n)$-unavoidable in tournaments. As of the source paper (October 2024), the gap between the quadratic upper bound $f(k)\leq\binom{2k+2}{2}$ (Corollary 25) and the linear lower bound from Proposition 28 remains open. No follow-up paper resolving or narrowing this gap was found in a search of the literature up to May 2026.

Reviewer notes. No follow-up found. The problem is recent (October 2024) and the wide web search covering author homepages (Lucas Picasarri-Arrieta's site, Clément Rambaud's DBLP) returned no paper addressing the gap between the linear lower bound and the quadratic upper bound on $f$. Status open with high confidence.

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

Problem. What is the minimum function $f$ such that every $k$-extension of every forest of order $n$ is $(2^{f(k)}\cdot n)$-unavoidable?

Context

This is the analogue of Problem 8 for extensions rather than blow-ups. Corollary 25 gives $f(k)\leqslant\binom{2k+2}{2}$ (quadratic upper bound), while Proposition 28 shows that the unavoidability of some $k$-extensions of the arcless digraph on $n$ vertices is $2^{k}n-o(n)$, giving a linear lower bound on $f$.

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