Optimal constant for tree blow-up unavoidability

Problem 8 · 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 8 asks for the infimum of all constants C such that for every large enough n, the k-blow-up of every oriented tree of order n is (C^k · kn)-unavoidable. The paper establishes via Theorem 18 an upper bound of the form 2^(10+18k) · kn, which the authors acknowledge is far from tight; the maximum average degree of the k-blow-up of a tree of order n (equal to 2k − 2k/n) together with Proposition 2 gives a lower bound showing the optimal exponent is 2^Θ(k) · kn, but the precise constant C remains open. No follow-up paper resolving the exact infimum was found in the literature.

Reviewer notes. No follow-up found. The problem is recent (October 2024). The paper itself establishes that the optimal unavoidability constant is of the form 2^Θ(k) · kn, narrowing the question to the base of the exponential, but the infimum of C in C^k · kn is not yet determined. Lucas Picasarri-Arrieta's 2025 publications do not include a follow-up on this specific problem.

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

Problem. What is the infimum of all the constants $C$ such that for every large enough integer $n$, the $k$-blow-up of every oriented tree of order $n$ is $(C^{k}\cdot kn)$-unavoidable?

Context

The paper proves in Theorem 18 that the $k$-blow-up of an oriented tree of order $n$ is $(2^{10+18k}\cdot kn)$-unavoidable, but this upper bound is acknowledged to be far from tight. The maximum average degree of the $k$-blow-up of a tree provides a lower bound via Proposition 2.

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