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₀ when the last isolated vertex disappears, the hypergraph H_t0 has a perfect fractional matching. This result is clearly best possible. As a consequence, we derive that if p(n) = (ln n + w(n))/ , 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.