On fractional K ‐factors of random graphs

Let K be a graph on r vertices and let G = ( V , E ) be another graph on ∣ V ∣ = n vertices. Denote the set of all copies of K in G by . A non‐negative real‐valued function f : → ℝ + is called a fractional K ‐factor if ∑ K : v ∈ K ∈ f ( K ) ≤ 1 for every v ∈ V and ∑ K ∈ f ( K ) = n / r . For a non‐empty graph K let d ( K ) = e ( K )/ v ( K ) and d (1) ( K ) = e ( K )/( v ( K ) ‐ 1). We say that K is strictly K 1 ‐balanced if for every proper subgraph K ′ ⊊ K , d (1) ( K ′ ) < d (1) ( K ). We say that K is imbalanced if it has a subgraph K ′ such that d ( K ′ ) > d ( K ). Considering a random graph process $\widetilde{G}$ on n vertices, we show that if K is strictly K 1 ‐balanced, then with probability tending to 1 as n → ∞ , at the first moment τ 0 when every vertex is covered by a copy of K , the graph ${\widetilde{G}}_{\tau_0}$ has a fractional K ‐factor. This result is the best possible. As a consequence, if K is K 1 ‐balanced, we derive the threshold probability function for a random graph to have a fractional K ‐factor. On the other hand, we show that if K is an imbalanced graph, then for asymptotically almost every graph process there is a gap between τ 0 and the appearance of a fractional K ‐factor. We also introduce and apply a criteria for perfect fractional matchings in hypergraphs in terms of expansion properties. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007