Directed-tree extremal bounds in Eulerian digraphs
Follow the latest progress by email.
Does a finite loopless Eulerian digraph with n vertices and more than (t−1)n arcs contain every orientation of every t-edge tree? Repeated ordered arcs are excluded, but pairs of opposite arcs are allowed.
Why it matters and what counts as progress
Why it matters: A sharp directed embedding theorem extends tree-extremal reasoning while distinguishing opposite arcs from repeated ordered arcs.
What counts as progress: Prove the sharp oriented-tree embedding threshold or determine which Eulerian or arc assumptions can be relaxed.
How the problem developed
- 1959 · Theorem [1]
Paul Erdős and Tibor Gallai Proved the classical extremal bound for undirected paths, a precursor to the tree question but not a directed Eulerian result.
- 10 Sept 2026 · Theorem claim [2]
Dhruv Mubayi and Jacques Verstraëte, with GPT-6 Astra The manuscript claims every n-vertex Eulerian digraph with more than (t−1)n arcs contains every oriented tree with t edges, and states the bound is sharp.
AI contribution
Erdős-Sós for digraphs
Every finite loopless Eulerian digraph with no repeated ordered arc, including digraphs with opposite arcs, contains every orientation of every t-edge tree when it has n vertices and more than (t−1)n arcs. Complete bidirected graph unions show the bound is sharp.
Sources
Website timeline
Publication dates and editorial changes.