Completing Partial Packings of Bipartite Graphs

Abstract

Given a bipartite graph $H$ and an integer $n$, let $f(n;H)$ be the smallest integer such that, any set of edge disjoint copies of $H$ on $n$ vertices, can be extended to an $H$-design on at most $n+f(n;H)$ vertices. We establish tight bounds for the growth of $f(n;H)$ as $n\to \infty$. In particular, we prove the conjecture of Füredi and Lehel \cite{FuLe} that $f(n;H)=o(n)$. This settles a long-standing open problem.