The maximum and minimum degree of the random r-uniform r-partite hypergraphs

详细信息    查看全文

• 作者：Ai-lian Chen ; Hao Li ; Fu-ji Zhang
• 关键词：maximum degree ; minimum degree ; degree distribution ; random uniform hypergraphs
• 刊名：Acta Mathematicae Applicatae Sinica, English Series
• 出版年：2016
• 出版时间：October 2016
• 年：2016
• 卷：32
• 期：4
• 页码：867-874
• 全文大小：219 KB
• 刊物主题：Applications of Mathematics; Math Applications in Computer Science; Theoretical, Mathematical and Computational Physics;
• 出版者：Institute of Applied Mathematics, Chinese Academy of Sciences and Chinese Mathematical Society
• ISSN：1618-3932
• 卷排序：32

文摘

In this paper we consider the random r-uniform r-partite hypergraph model H(n₁, n₂, ···, n_r; n, p) which consists of all the r-uniform r-partite hypergraphs with vertex partition {V₁, V₂, ···, V_r} where |V_i| = n_i = n_i(n) (1 ≤ i ≤ r) are positive integer-valued functions on n with n₁ +n₂ +···+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₁, n₂, ···, n_r; n, p) with probability p = p(n), all choices being independent. Let $${\Delta _{{V_1}}} = {\Delta _{{V_1}}}\left( H \right)$$ and $${\delta _{{V_1}}} = {\delta _{{V_1}}}\left( H \right)$$ be the maximum and minimum degree of vertices in V₁ of H, respectively; $${X_{d,{V_1}}} = {X_{d,{V_1}}}\left( H \right),{Y_{d,{V_1}}} = {Y_{d,{V_1}}}\left( H \right)$$, $${Z_{d,{V_1}}} = {Z_{d,{V_1}}}\left( H \right)and{Z_{c,d,{V_1}}} = {Z_{c,d,{V_1}}}\left( H \right)$$ be the number of vertices in V₁ 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₁, n₂, ···, n_r; n, p), $${X_{d,{V_1}}},{Y_{d,{V_1}}},{Z_{d,{V_1}}}and{Z_{c,d,{V_1}}}$$ 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₁, n₂, ···, n_r; n, p), $$\mathop {\lim }\limits_{n \to \infty } P\left( {{\Delta _{{V_1}}} = D\left( n \right)} \right) = 1$$? What is the range of p such that a.e., H_p ∈ H (n₁, n₂, ···, n_r; n, p) has a unique vertex in V₁ with degree $${\Delta _{{V_1}}}\left( {{H_p}} \right)$$? Both answers are p = o (log n₁/N), where $$N = \mathop \prod \limits_{i = 2}^r {n_i}$$. The corresponding problems on $${\delta _{{V_i}}}\left( {{H_p}} \right)$$ also are considered, and we obtained the answers are p ≤ (1 + o(1))(log n₁/N) and p = o (log n₁/N), respectively.Keywordsmaximum degreeminimum degreedegree distributionrandom uniform hypergraphsSupported 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.