Combinatorical and Algebraic Structures Seminar
Session details
| Date: | 2.12.2014 |
| Speaker: | Diana Piguet, FAV, Západočeská univerzita v Plzni |
| Title: | An approximate version of the tree packing conjecture for bounded degree graphs |
| Abstract: | (spoluautoři: Julia Böttcher, Jan Hladký, and Anusch Taraz) A family of graphs packs into a graph $G$ if there exist pairwise edge-disjoint copies of its members in $G$. In 1976 Gyárfás has made the following conjecture: any family of trees $\{T_i, i\in[n]\}$ with $|V(T_i)|=i$ packs into the complete graph $K_n$. Another conjecture about packing trees in complete graphs was made by Ringel back in 1963 and reads as follows: any $2n + 1$ identical copies of any tree of order $n + 1$ pack into $K_{2n+1}$. We prove a theorem that implies asymptotic versions of both conjectures for the class of trees with bounded maximal degree. The core of the proof is a random process controlled by the nibble method. |
Return to index.
last update: 27.9.2007, webmaster: Petr Ambrož