Tree embeddings

Tree embeddings

-
Maya Stein , U. Chile
Fine Hall 224

There are several conjectures trying to relate the average/minimum/median degree of a graph with it having all trees of a certain size as subgraphs. One example is the Erdos-Sos conjecture, and another is the Loebl-Komlos-Sos conjecture. We will give a short overview of what is known for these conjectures and then investigate a new conjecture in the same direction. The new conjecture (due to Havet, Wood, Reed and Stein) says that a minimum degree of 2k/3 together with a maximum degree of k should be enough for having all trees of size k as subgraphs. The results we present are joint work with Havet, Reed and Wood, and with Reed.