PreprintCC BY 4.0arXiv
Are trees really just butterflies in disguise?
Abstract
As a generalisation of the Erdős-Sós conjecture about graphs, Addario-Berry, Havet, Linhares Sales, Reed and Thomassé conjectured that every digraph on n vertices with more than (k−1)n arcs contains every antidirected tree with k arcs. We prove a dense, approximate version of this for trees with bounded maximum degree, as well as for trees whose layers are evenly distributed. We use a regularity based approach, centred around finding a copy of a given tree in the blow up of a caterpillar.
Related
- Gauss-Manin Connection in Disguise: Holomorphic Anomaly Equations and Higher Genus Real Gromov-Witten Invariants
- Unrolled gradients in disguise: bridging interpolation-based and Jacobian regularization for stable neural dynamics
- Gauss-Manin connection in disguise: limiting periods and quasi-Jacobi forms
- How Deep Are Deep GPs, Really? A Sharp Threshold and a Non-Gaussian Limit for Compositional GPs
- Every finite group admits a just finite presentation
BibTeX
@misc{santos2026trees,
title = {{Are trees really just butterflies in disguise?}},
author = {Giovanne Santos and Maya Stein and Ella Williams},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09142},
eprint = {2609.09142},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09142},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Are trees really just butterflies in disguise?
AU - Giovanne Santos
AU - Maya Stein
AU - Ella Williams
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.09142
UR - https://arxiv.org/abs/2609.09142
AB - As a generalisation of the Erdős-Sós conjecture about graphs, Addario-Berry, Havet, Linhares Sales, Reed and Thomassé conjectured that every digraph on n vertices with more than (k−1)n arcs contains every antidirected tree with k arcs. We prove a dense, approximate version of this for trees with bounded maximum degree, as well as for trees whose layers are evenly distributed. We use a regularity based approach, centred around finding a copy of a given tree in the blow up of a caterpillar.
ER -