随机一致超图的关于H-因子的门槛函数

假设H和H（分别是具有h个顶点和n个顶点的r一致超图．我们称一个具有n/h个分支，且每个分支都同构于H的H的生成子图为H的一个H-因子．记α（H） = max{｜E′｜/｜V′｜-1 ｜}，其中的最大值取遍H的所有满足｜V’｜〉1的子超图（V’，E′）．δ（H）表示超图H的最小度．在本文中，我们证明了如果δ（H）〈α（H），那么P=p（n）=n-1／α（H）就是随机超图Hr（n，P）包含．H-因子的一个紧的门槛函数．也就是说，存在两个常数c和C使得对任意P=p（n）=cn-1／α（H），几乎所有的随机超图Hr（n，P）都不包含一个H-因子，对任意P=p（n）=cn-1／α（H），几乎所有的随机超图Hr（n，P）都包含一个H-因子．

Threshold Functions for H-factors in Random Uniform Hypergraphs

Let H be a fixed r-uniform hypergraph on h vertices and H a r-uniform hypergraph on n vertices. An H-factor of H is a spanning subhypergraph of H consisting of n/h vertex disjoint copies of H. The fractional arboricity of H is α(H) = max{|E'|/|V'|-1}, where the maximum is taken over all subhypergraphs (V', E') of H with |V'| > 1. Let δ(H) denote the minimum degree of vertices of H, where the degree of a vertex is the number of edges adjacent to it. In this paper we show that if δ(H) < α(H) then p = p(n) =n-1/α(H) is a sharp threshold function for the property that the random r-uniform hypergraph Hr(n,p) contains an H-factor, i. e. there are two positive constants c and C so that for p = p(n) = cn-1/α(H), almost surely Hr(n,p) does not contain an H-factor, whereas for p = p(n) =Cn-1/α(H), almost surely Hr(n,p) contains an H-factor (provided h divides n).