Blow-up closure of linear unavoidability

Conjecture 7 · 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 partial high confidence

Conjecture 7 asks whether the $k$-blow-up operation preserves linear unavoidability under a bounded maximum average degree condition. The source paper itself proves the conjecture for the special case where $\mathcal{F}$ is the family of oriented trees, establishing that $k$-blow-ups of oriented trees are linearly unavoidable. No subsequent paper resolving the full conjecture has been found in the literature as of May 2026.

Reviewer notes. The paper proves the conjecture for the family of oriented trees (a significant partial result). The bounded maximum average degree condition in the conjecture is noted as necessary, as demonstrated by a counterexample using disjoint unions of transitive tournaments. No follow-up paper addressing the full conjecture was found after searching author homepages and arXiv. Clément Rambaud's 2026 preprint concerns graph minors and is unrelated.

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

Conjecture. If $\cal F$ is linearly unavoidable and has bounded maximum average degree, then ${\cal F}[k]$ is also linearly unavoidable.

Context

This conjecture asks whether the $k$-blow-up operation preserves linear unavoidability. The bounded maximum average degree condition is necessary, as shown by an example using disjoint unions of transitive tournaments. The paper proves this conjecture holds for the family of 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