OpenAlex ·
Are trees really just butterflies in disguise?
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.09142
- Original
- Read it at the publisher
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
A $(\log n)^{1/4}$ Bound for the Komlós Problem
Subexponential Approximation of the Permanent in Deterministic Polynomial Time
Sharp Metric Cotype Inequalities for $L_1$ via Nonlinear Cut Smoothing
Infinite Families of Counterexamples to a Conjecture of Liu and Qian and a Refined Inverse Theorem for Restricted Sumsets in $\mathbb{Z}_p$
Sharp edge-spectral supersaturation for odd cycles
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.