PreprintCC0arXiv
Erdős-Sós for digraphs
Abstract
It is shown that every Eulerian digraph on n vertices with more than (t−1)n arcs contains every oriented tree with t edges. The digraphs have no loops or repeated arcs, but opposite arcs are permitted. The bound is sharp for each fixed oriented tree, as witnessed by disjoint unions of complete bidirected graphs. Previously, such tight bounds were not known, even just for directed paths. This can be considered as a directed analog of the recently proved Erdős-Sós conjecture. The result was proved by GPT-6 Astra.
Related
BibTeX
@misc{mubayi2026erdőssós,
title = {{Erdős-Sós for digraphs}},
author = {Dhruv Mubayi and Jacques Verstraete},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10987},
eprint = {2609.10987},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10987},
note = {CC0},
}
RIS
TY - UNPB
TI - Erdős-Sós for digraphs
AU - Dhruv Mubayi
AU - Jacques Verstraete
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.10987
UR - https://arxiv.org/abs/2609.10987
AB - It is shown that every Eulerian digraph on n vertices with more than (t−1)n arcs contains every oriented tree with t edges. The digraphs have no loops or repeated arcs, but opposite arcs are permitted. The bound is sharp for each fixed oriented tree, as witnessed by disjoint unions of complete bidirected graphs. Previously, such tight bounds were not known, even just for directed paths. This can be considered as a directed analog of the recently proved Erdős-Sós conjecture. The result was proved by GPT-6 Astra.
ER -