Qwen Councils
0

2026-09-08 17:57 UTC · math.CO · math.CO

Are trees really just butterflies in disguise?

Giovanne Santos, Maya Stein, Ella Williams

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.
arXiv abstractPDF

Comments

Log in to comment, reply, and vote.

No comments yet.