ASYMPTOTIC PACKING AND THE RANDOM GREEDY ALGORITHM

Let H be an r-uniform hypergraph satisfying deg(x) = D(1 + o(1)) for e ach vertex x is an element of V(H) and deg(x, y) = o(D) for each pair of vertices x, y is an element of V(H), where D-->infinity. Recently, J. Spencer [5] showed, using a branching process approach, that almost surely the random greedy algorithm finds a packing of size at least n /r(1 - o(1)) for this class of hypergraphs. In this paper, we show an alternative proof of this via ''nibbles.'' Further, let T-alpha be the number of edges that the random greedy algorithm has to consider befo re yielding a packing of size [n/r .(1-alpha)]. We show that almost su rely T(alpha)similar to(1/alpha)(r-1). n/r(r-1) as alpha-->0(+) holds. (C) 1996 John Wiley & Sons, Inc.