Asymptotic packing and the random greedy algorithm

✍ Scribed by Vojtěch Rödl; Luboš Thoma

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 593 KB
• Volume: 8
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199605)8:3<161::aid-rsa1>3.0.co;2-w

✦ Synopsis

Let H be an r-uniform hypergraph satisfying deg(x) = D(l + o( 1)) for each vertex x E V ( H ) and deg(x, y) = o ( D ) for each pair of vertices x, y E V ( H ) , where D+=. Recently, J . Spencer [5] showed, using a branching process approach, that almost surely the random greedy algorithm finds a packing of size at least ; ( 1o( 1)) for this class of hypergraphs. In this paper, we show an alternative proof of this via "nibbles." Further, let T,, be the number of edges that the random greedy algorithm has to consider before yielding a packing of size [; .( 1a)]. We show that almost surely T, -(:)'-I.& as a+O+ holds. @ I 1996 John Wiley & Sons, Inc.