I Simposio de Postgrado 2023. Ingeniería, ciencias e innovación

I SIMPOSIO 2023 PACKING LARGE BALANCED TREES ABSTRACT We say that a graph H embeds in a graph G if there is a copy of H in G. A family of graphs H 1 ,…, H k packs in a graph G if there exist pairwise edge-disjoint embeddings of H 1 ,...,H k in G. The union of such embeddings is called a packing .The packing problem has a long history in combinatorics and related areas. For instance, Euler’s question from 1782 about the existence of orthogonal latin squares can be formulated as a graph decomposition problem. In this work, we are particularly interested in packing sequences of trees, which are connected graphs without cycles, into complete bipartite graphs. Within this context, Gyárfás raised in the 1970s the following question: does any sequence of n trees T 1 ,...,T n such that T i has i vertices pack into the complete graph on n vertices, K n ? Despite recent progress for some special families of trees, this question is still open. Balogh and Palmer proved, for n sufficiently large, that there exists a packing of any sequence of t = (n/4) 1/4 large trees T n ,...,T n-t+1 into K n+1 . In 2013, Hollingsworth presented a variant of Gyárfás’ conjecture to balanced trees. We say that a bipartite graph is balanced if it has a bipartition in which the both parts have the same cardinality . We present an approximate analogue of Balogh and Palmer’s result for Hollingsworth’s conjecture. More specifically, we prove that, for every γ > 0 and n sufficiently large, any family of n (1/2+ γ) balanced trees on 2(1 − γ)n vertices can be packed into the complete bipartite graph K n,n . Cristina G. Fernandes 1 , Tássio Naia 1 , GiovanneM. dos Santos 2* , Maya Stein 2 1 Instituto de Matemática e Estatística, Universidade de São Paulo. 2 Departamento de Ingeniería Matemática, Universidad de Chile. *Email: gsantos@dim.uchile.cl