随机一致超图的关于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))就是随机超图H_r(n,p)包含H-因子的一个紧的门槛函数.也就是说,存在两个常数c和C使得对任意p=p(n)=cn^(-1/α(H)),几乎所有的随机超图H_r(n,p)都不包含一个H-因子,对任意p=p(n)=Cn^(-1/α(H)),几乎所有的随机超图H_r(n,p)都包含一个H-因子.

Random Hypergraphs and Subset Systems

Suppose to toss an independent coin with equal probability of success and failure for each subset of [n] = {1, 2, ..., n}, and form the random hypergraph H(n) by taking as hyperedges the subsets with successful coin tosses. It is proved that H(n) is almost surely connected. By defining a graph G(S) according to a subset system S, it is shown that the intersecting problem is NP-complete.