Are trees really just butterflies in disguise?
Giovanne Santos, Maya Stein, Ella Williams
Source 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 vertices with more than arcs contains every antidirected tree with 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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.