Packing large balanced trees into bipartite graphs

Abstract

We prove that for every ${\hat{I}}^3>0$ there exists $n_0\in \mathbb{N}$ such that for every $n\ge n_0$ any family of up to $\lfloor n^{\frac{1}{2}+{\hat{I}}^3}\rfloor$ trees having at most $(1-{\hat{I}}^3)n$ vertices in each bipartition class can be packed into $K_{n,n}$. As a tool for our proof, we show an approximate bipartite version of the Komlós-Sárközy-Szemerédi Theorem, which we believe to be of independent interest.