Embedding trees in graphs with large minimum degree
Embedding trees in graphs with large minimum degree
-
Leo Veerstegen, LSE
In this talk, which is based on joint work with Alexey Pokrovskiy and Ella Williams, we discuss the following variant of the Erdős-Sós conjecture due to Besomi, Pavez-Signé, and Stein. If c is larger than 1/2, and a graph G has minimum degree at least ck and maximum degree at least 4-4c, then every tree with k edges can be embedded into G. We prove an approximate version of this conjecture for trees of bounded degree. The key ingredient of the proof is a new structural lemma about graphs that do not admit embeddings for all bounded degree trees.