Integer and fractional packing of families of graphs

Let $\mathcal{F}$ be a family of graphs. For a graph $G$, the {\em ${\cal F}-packing number}, denoted\nu_{{\cal F}}(G)$, is the maximum number of pairwise edge-disjoint elements of $\mathcal{F}$ in $G$. A function $\psi$ from the set of elements of $\mathcal{F}$ in $G$ to $[0,1]$ is a {\em fractional ${\cal F}-packing} ofG$if$\sum_{e \in H \in {\cal F}} {\psi(H)} \leq 1$foreach$e \in E(G). The {\em fractional{\cal F}-packing number}, denoted\nu^*{{\cal F}}(G)$,isdefinedtobethemaximumvalueof$\sum{H \in {{G} \choose {{\cal F}}}} \psi(H)$overallfractional${\cal F}$-packings$\psi$. Our main result is that ${\nu }_{\mathcal{F}}^{\ast }(G)-{\nu }_{\mathcal{F}}(G)=o(\mathrm{\mid }V(G){\mathrm{\mid }}^2)$. Furthermore, a set of ${\nu }_{\mathcal{F}}(G)-o(\mathrm{\mid }V(G){\mathrm{\mid }}^2)$ edge-disjoint elements of $\mathcal{F}$ in $G$ can be found in randomized polynomial time. For the special case $\mathcal{F}=\{H_0\}$ we obtain a significantly simpler proof of a recent difficult result of Haxell and R"odl \cite{HaRo} that ${\nu }_{H_0}^{\ast }(G)-{\nu }_{H_0}(G)=o(\mathrm{\mid }V(G){\mathrm{\mid }}^2)$.