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

Threshold Functions for H-factors in Random Uniform Hypergraphs

作　　者：陈爱莲[1] 

机构地区：[1]厦门大学数学科学学院,福建厦门361005

出　　处：《数学研究》2008年第4期384-387,共4页Journal of Mathematical Study

基　　金：partially supported by NNSF of china(60373012)

摘　　要：假设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-因子.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 5（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） = en-1/α（H）, almost surely Hr（n,p） does not contain aa H-factor, whereas for p = p（n） = cn-1/α（H）, almost surely Hr（n, p） contains an H-factor （provided h divides n ）.

关 键 词：随机一致超图 门槛函数 因子 

分 类 号：O157.5[理学—数学]