Search

Let be any fixed graph. For a graph G we define to be the maximum size of a set of pairwise edge-disjoint copies of in G. We say a function from the set of copies of in G to [0, 1] is a fractional -packing of G if for every edge e of G. Then is defined to be the maximum value of over all fractional -packings of G. We show that for all graphs G.

For 00, there exists a real constantC=C(l, η), such that almost every random graphG n, p withp=p(n)≥Cn −1+1/2l satisfiesG n,p→1/2+η C 2l+1. In particular, for any fixedl≥1 and η>0, this result implies the existence of very sparse graphsG withG →1/2+η C 2l+1.