PERFECT FRACTIONAL MATCHINGS IN RANDOM HYPERGRAPHS

Given an r-uniform hypergraph H = (V, E) on \V\ = n vertices, a real-v alued function f:E-,R(+) is called a perfect fractional matching if Si gma(upsilon is an element of e) f(e) less than or equal to 1 for all u psilon is an element of V and Sigma(e is an element of E) f(e) = n/r. Considering a random r-uniform hypergraph process of n vertices, we sh ow that with probability tending to 1 as n --> infinity, at the very m oment t(0) when the last isolated vertex disappears, the hypegraph H-t 0 has a perfect fractional matching. This result is clearly best possi ble. As a consequence, we derive that if p(n) = (ln n + w(n))/ [GRAPHI CS] where w(n) is any function tending to infinity with n, then with p robability tending to 1 a random r-uniform hypergraph on n vertices wi th edge probability p has a perfect fractional matching. Similar resul ts hold also for random r-partite hypergraphs. (C) 1996 John Wiley & S ons, Inc.