Search
next up previous
Next: Felix Lazebnik - On Up: Extremal Combinatorics / Combinatoire Previous: Jerrold Griggs - Extremal

Penny Haxell - Integer and fractional packings in dense graphs



PENNY HAXELL, University of Waterloo, Waterloo, Ontario  N2L 3G1, Canada
Integer and fractional packings in dense graphs


Let H0 be any fixed graph. For a graph G we define $\nu_{H_0}(G)$to be the maximum size of a set of pairwise edge-disjoint copies of H0 in G. We say a function $\psi$ from the set of copies of H0in G to [0,1] is a fractional H0-packing of G if $\sum_{H\ni e}\psi(H)\leq 1$ for every edge e of G. Then $\nu_{H_0}^\ast(G)$ is defined to be the maximum value of $\sum_{H\in{G\choose{H_0}}}\psi(H)$ over all fractional H0-packings $\psi$ of G. We show that $\nu_{H_0}^\ast(G)-\nu_{H_0}(G)=o(\vert V(G)\vert^2)$ for all graphs G. (Joint work with V. Rödl.)