Tree Embedding Problem for Digraphs.

Abstract:
The \textit{tree embedding problem} focuses on identifying the minimal conditions a graph $G$ must satisfy to ensure it contains all trees with $k$ edges. Here, a graph $G$ consists of a set $V$ of elements called vertices, and a set $E$ of (unordered) pairs of vertices, called edges. We say that a graph $G$ is a tree if, for any pair of vertices, there is exactly one path connecting them.

Erd\H{o}s and Sós conjectured that any graph $G$ with $n$ vertices and more than $(k-1)n/2$ edges contains every tree with $k$ edges. This conjecture has been generalized into the Antitree Conjecture by Addario-Berry et al., which states that every digraph $D$ with $n$ vertices and more than $(k-1)n$ arcs contains every antidirected tree with $k$ arcs. Here, a digraph $D$ consists of a set $V$ of vertices and a set $A$ of arcs (ordered pairs of vertices), and an antidirected tree is a tree in which the edges are directed so that each vertex has only incoming or outgoing arcs.

In this talk, we present a proof of the Antitree Conjecture for the case where the digraph $D$ does not contain certain orientations of the complete bipartite graph $K_{2,s}$, where $s = k/12$. Additionally, we explore a proof of this conjecture for antidirected caterpillars. This work is a collaboration with Maya Stein.mitted).

Posted on Oct 17, 2024 in Seminars, SIPo (Seminario de Investigadores Postdoctorales)