Bounded unvd ratio under vertex deletion

Conjecture 9 · 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 9 from arXiv:2410.23566 asserts that there exists a constant C such that unvd(D) ≤ C·unvd(D−v) for every acyclic digraph D and every vertex v, where unvd(D) is the smallest order of a tournament that contains D. The paper itself proves the special case C=2 when v is a source or sink (Proposition 1), but the general case remains open. No follow-up paper resolving the conjecture was found in a targeted web search covering the period 2024–2026.

Reviewer notes. The function unvd(D) is the smallest integer p such that D is contained in every tournament of order p. Conjecture 9 generalises Proposition 1 (source/sink case, C=2) to arbitrary vertices. The conjecture is intimately linked to Sumner's conjecture (Conjecture 4) and to Conjecture 10 on k-extensions of oriented trees: together, Conjectures 9 and 4 would imply Conjecture 10. The paper arXiv:2603.13955 found in the search concerns digraph subdivisions of C(k,ℓ) cycles and is unrelated. No follow-up was found; open with high confidence given the conjecture is recent (Oct 2024).

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

Conjecture. There exists a constant $C$ such that $\operatorname{unvd}(D)\leqslant C\cdot\operatorname{unvd}(D-v)$ for every acyclic digraph $D$ and for every vertex $v$ of $D$.

Context

This conjecture generalizes Proposition 1, which gives $\operatorname{unvd}(D)\leqslant 2\operatorname{unvd}(D-x)$ only when $x$ is a source or sink of $D$, to arbitrary vertices. Together with Sumner's Conjecture 4, it implies Conjecture 10 about $k$-extensions 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