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


Packing perfect matchings in random hypergraphs
Abstract:We introduce a new procedure for generating the binomial random graph/hypergraph models, referred to as online sprinkling. As an illustrative application of this method, we show that for any fixed integer urn:x-wiley:10429832:media:rsa20745:rsa20745-math-0001, the binomial urn:x-wiley:10429832:media:rsa20745:rsa20745-math-0002‐uniform random hypergraph urn:x-wiley:10429832:media:rsa20745:rsa20745-math-0003 contains urn:x-wiley:10429832:media:rsa20745:rsa20745-math-0004 edge‐disjoint perfect matchings, provided urn:x-wiley:10429832:media:rsa20745:rsa20745-math-0005, where urn:x-wiley:10429832:media:rsa20745:rsa20745-math-0006 is an integer depending only on urn:x-wiley:10429832:media:rsa20745:rsa20745-math-0007. Our result for urn:x-wiley:10429832:media:rsa20745:rsa20745-math-0008 is asymptotically optimal and for urn:x-wiley:10429832:media:rsa20745:rsa20745-math-0009 is optimal up to the urn:x-wiley:10429832:media:rsa20745:rsa20745-math-0010 factor. This significantly improves a result of Frieze and Krivelevich.
Keywords:Perfect matching  hypergraph  random graphs
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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