A reminder: this is today.
On 2025-02-24 07:20, Mykhaylo Tyomkyn wrote:
Dear all,
There will be a noon seminar this Thursday, 27 February, given by Ana Laura Trujillo. Please find the talk details below.
Best regards, Misha Tyomkyn.
The tree embedding problem for digraphs Ana Laura Trujillo Universidad de Chile February 27, 2025, 12:20 in S6
Abstract The tree embedding problem seeks to determine the minimal conditions a graph $G$ must satisfy to ensure it contains all trees with $k$ edges. A well-known conjecture by Erd\H{o}s and Sós states that any graph $G$ with $n$ vertices and more than $(k-1)n/2$ edges must contain every tree with $k$ edges. This conjecture was later extended by Addario-Berry et al. into the Antitree Conjecture, which asserts that any digraph $D$ with $n$ vertices and more than $(k-1)n$ arcs contains every antidirected tree with $k$ arcs.
In this talk, we present a proof of the Antitree Conjecture for the case where the digraph $D$ avoids certain orientations of the complete bipartite graph $K_{2,s}$, with $s = k/12$. Additionally, we discuss a proof of this conjecture for antidirected caterpillars. This is joint work with Maya Stein.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz