The Maximum and Minimum Degree of the Random r-uniform r-partite Hypergraphs

Ai-lian CHEN^{1}, Hao LI^{2}, Fu-ji ZHANG^{3}

1 College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China;
2 Laboratoire de Recherche en Informatique, UMR 8623, C. N. R. S. -Université de Paris-sud, 91405-Orsay cedex, France;
3 School of Mathematical Sciences, Xiamen University, Xiamen 361005, China

In this paper we consider the random r-uniform r-partite hypergraph model H(n_{1},n_{2},…,n_{r}; n,p) which consists of all the r-uniform r-partite hypergraphs with vertex partition {V_{1}, V_{2},…, V_{r}} where |V_{i}|=n_{i}=n_{i}(n) (1≤i≤r) are positive integer-valued functions on n with n_{1}+n_{2}+…+n_{r}=n, and each r-subset containing exactly one element in V_{i} (1≤i≤r) is chosen to be a hyperedge of H_{p}∈H (n_{1},n_{2},…,n_{r}; n,p) with probability p=p(n), all choices being independent. Let Δ_{V1}=Δ_{V1}(H) and δ_{V1}=δ_{V1}(H) be the maximum and minimum degree of vertices in V_{1} of H, respectively; X_{d,V1}=X_{d,V1}(H), Y_{d,V1}=Y_{d,V1}(H), Z_{d,V1}=Z_{d,V1}(H) and Z_{c,d,V1}=Z_{c,d,V1}(H) be the number of vertices in V_{1} of H with degree d, at least d, at most d, and between c and d, respectively. In this paper we obtain that in the space H(n_{1},n_{2},…,n_{r}; n,p), X_{d,V1}, Y_{d,V1}, Z_{d,V1}, and Z_{c,d,V1} all have asymptotically Poisson distributions. We also answer the following two questions. What is the range of p that there exists a function D(n) such that in the space H(n_{1},n_{2},…,n_{r}; n,p),P(Δ_{V1}=D(n))=1? What is the range of p such that a.e., H_{p}∈H(n_{1},n_{2},…,n_{r}; n,p) has a unique vertex in V_{1} with degree Δ_{V1}(H_{p})? Both answers are p=o (log n_{1}/N), where N=n_{i}. The corresponding problems on δ_{V1}(H_{p}) also are considered, and we obtained the answers are p≤(1+o(1))(log n_{1}/N) and p=o(log n_{1}/N), respectively.

Supported in part by the National Natural Science Foundation of China under Grant No. 11401102, 11271307 and 11101086, Fuzhou university of Science and Technology Development Fund No. 2014-XQ-29.

Ai-lian CHEN,Hao LI,Fu-ji ZHANG. The Maximum and Minimum Degree of the Random r-uniform r-partite Hypergraphs[J]. Acta Mathematicae Applicatae Sinica, English Serie, 2016, 32(4): 867-874.