首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Perfect matchings in random uniform hypergraphs
Authors:Jeong Han Kim
Abstract:Let ??k(n, p) be the random k‐uniform hypergraph on V = n] with edge probability p. Motivated by a theorem of Erd?s and Rényi 7 regarding when a random graph G(n, p) = ??2(n, p) has a perfect matching, the following conjecture may be raised. (See J. Schmidt and E. Shamir 16 for a weaker version.) Conjecture. Let k|n for fixed k ≥ 3, and the expected degree d(n, p) = p(urn:x-wiley:10429832:media:RSA10093:tex2gif-stack-1). Then equation image (Erd?s and Rényi 7 proved this for G(n, p).) Assuming d(n, p)/n1/2 → ∞, Schmidt and Shamir 16 were able to prove that ??k(n, p) contains a perfect matching with probability 1 ? o(1). Frieze and Janson 8 showed that a weaker condition d(n, p)/n1/3 → ∞ was enough. In this paper, we further weaken the condition to equation image A condition for a similar problem about a perfect triangle packing of G(n, p) is also obtained. A perfect triangle packing of a graph is a collection of vertex disjoint triangles whose union is the entire vertex set. Improving a condition pcn?2/3+1/15 of Krivelevich 12 , it is shown that if 3|n and p ? n?2/3+1/18, then equation image © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 111–132, 2003
Keywords:
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号