For all positive integers n and k, every digraph D on n vertices with more than (k-1)n arcs contains every antidirected tree T with k arcs as a subdigraph. Here, an antidirected tree is a directed tree in which every vertex is either a source or a sink.

Addario-Berry–Havet–Linhares Sales–Reed–Thomassé antidirected-tree conjecture

The conjecture asserts that a sufficiently dense digraph contains every antidirected tree of the corresponding order; for symmetric digraphs, it specializes to the Erdős–Sós conjecture. It was formulated by Addario-Berry, Havet, Linhares Sales, Reed, and Thomassé in 2011/2013.

Known results

Antidirected trees of diameter at most $3$ (Addario-Berry, Havet, Linhares Sales, Reed, and Thomassé, 2011).
Every antidirected caterpillar (2024 source).
Asymptotically, balanced bounded-degree antidirected trees of linear size in dense oriented graphs (Stein and Zárate-Guerén, January 16, 2024).
Antidirected paths in dense oriented graphs, asymptotically (2025 source).

September 2026 dense approximate progress

A September 2026 report on Are trees really just butterflies in disguise? says that a regularity-based embedding method establishes the conjecture approximately for two dense tree classes. This is claimed restricted progress, not a proof of the full conjecture.

Current status (as of September 2026): The conjecture is known for several restricted classes and now has a reported approximate result for two further dense classes, but its full statement remains open.

Addario-Berry–Havet–Linhares Sales–Reed–Thomassé antidirected-tree conjecture

Primary source

Additional references

Progress summary

Solutions 0