Société mathématique du Canada
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.)


© Société mathématique du Canada, 2020 :