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


Almost perfect matchings in random uniform hypergraphs
Authors:Michael Krivelevich  
Affiliation:

Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, 69978, Israel

Abstract:We consider the following model Hr(n, p) of random r-uniform hypergraphs. The vertex set consists of two disjoint subsets V of size | V | = n and U of size | U | = (r − 1)n. Each r-subset of V × (r−1U) is chosen to be an edge of H ε Hr(n, p) with probability p = p(n), all choices being independent. It is shown that for every 0 < < 1 if P = (C ln n)/nr−1 with C = C() sufficiently large, then almost surely every subset V1 V of size | V1 | = (1 − )n is matchable, that is, there exists a matching M in H such that every vertex of V1 is contained in some edge of M.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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