Perfect fractional matchings in random hypergraphs

Given an r ‐uniform hypergraph H = ( V, E ) on | V | = n vertices, a real‐valued function f : E → R + is called a perfect fractional matching if Σ v ϵ e f ( e ) ≤ 1 for all v ϵ V and Σ e ϵ E f ( e ) = n/r . Considering a random r ‐uniform hypergraph process of n vertices, we show that with probability tending to 1 as n → infinity, at the very moment t 0 when the last isolated vertex disappears, the hypergraph H t 0 has a perfect fractional matching. This result is clearly best possible. As a consequence, we derive that if p ( n ) = (ln n + w ( n ))/ ${{n-1}\choose{r-1}}$ , where w ( n ) is any function tending to infinity with n , then with probability tending to 1 a random r ‐uniform hypergraph on n vertices with edge probability p has a perfect fractional matching. Similar results hold also for random r ‐partite hypergraphs. © 1996 John Wiley & Sons, Inc.