A directed Erdős-Sós theorem for Eulerian digraphs
The Erdős-Sós conjecture, proved in 2026, says that a graph on vertices with more than edges contains every tree with edges. The directed analogue asks for the arc bound forcing an Eulerian digraph on vertices to contain every oriented tree with edges. No tight bound was known, even for directed paths. Does more than arcs suffice?
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Extremal graph theory
- Posed by
- Not posed under a name; the directed analogue of the Erdős-Sós conjecture, with tight bounds previously unknown even for directed paths
- Year posed
- —
- Years open
- —
- Solved
- 2026-09-10
- Model
- GPT-6 Astra
- Vendor
- OpenAI
- Collaborators
- Dhruv Mubayi, Jacques Verstraëte
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 20 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The abstract states it directly: "The result was proved by GPT-6 Astra." The authors supplied the problem and the write-up.
Verification
Checked here on 22 September 2026 against arXiv:2609.10987: the abstract states that every Eulerian digraph on vertices with more than arcs contains every oriented tree with edges, that the bound is sharp for each fixed oriented tree by disjoint unions of complete bidirected graphs, and that tight bounds were not previously known even for directed paths. It is described there as a directed analogue of the recently proved Erdős-Sós conjecture, which this catalog records as erdos-problem-548. The mathematics was not checked here; twelve days old, no referee.