Empaquetamiento óptimo de árboles de grado máximo acotado.

Abstract:

En 1976, Gyárfás y Lehel conjeturaron que si T_1,…, T_n es una secuencia de árboles tal que T_i tiene i vértices, entonces el grafo completo en n vértices K_n tiene una descomposición en T_1,…, T_n. Recientemente, Joos, Kim, Kühn y Osthus [1] probaron esta conjetura para árboles de grado máximo acotado. En este seminario vamos a estudiar las técnicas utilizadas en la demostración de este resultado. En especial, veremos una aplicación del método de absorción iterativo.

[1] Felix Joos, Jaehoon Kim, Daniela Kühn, Deryk Osthus, Optimal packings of bounded degree trees. J. Eur. Math. Soc. 21 (2019), no. 12, pp. 3573–3647

Posted on Nov 22, 2022 in Seminario de Grafos, Seminars