Polynomial unavoidability in bounded average degree digraphs

Problem 6 · 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 6 from arXiv:2410.23566 asks whether for each positive real α there exists a polynomial P_α bounding unvd(D) for every digraph with maximum average degree at most α. The question is motivated by Fox, He, and Wigderson's result (arXiv:2105.02383) establishing that acyclic digraphs with bounded maximum degree are not linearly unavoidable, with unavoidability growing as n^{Ω(Δ^{2/3}/log^{5/3}Δ)}. No paper resolving the polynomial question or providing a counterexample was found in the literature as of May 2026.

Reviewer notes. No follow-up found in indexed literature. The Fox–He–Wigderson result (arXiv:2105.02383, 'Ramsey numbers of sparse digraphs', Israel J. Math. 2024) rules out linear unavoidability for bounded-degree acyclic digraphs but leaves the polynomial question open; Problem 6 asks about bounded maximum average degree, a condition weaker than bounded maximum degree, so the Fox–He–Wigderson lower bounds do not directly answer it.

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

Problem. Let $\alpha$ be a positive real number. Does there exist a polynomial $P_{\alpha}$ such that $\operatorname{unvd}(D)\leqslant P_{\alpha}(|V(D)|)$ for every digraph with maximum average degree at most $\alpha$?

Context

Fox, He, and Wigderson showed that acyclic digraphs with bounded maximum degree are not linearly unavoidable, ruling out linear bounds. This problem asks whether the weaker polynomial unavoidability still holds for digraphs with bounded maximum average degree, and is complemented by the second question of which families of such digraphs are linearly unavoidable.

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