Packing perfect matchings in random hypergraphs

DOI10.1002/RSA.20745MaRDI QIDQ4642740zbMATH OpenOpenAlexFDO

Authors Asaf Ferber, Van Vu

Publication date 25 May 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.09492

zbMATH Keywords

hypergraphperfect matchingrandom graphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We introduce a new procedure for generating the binomial random graph/hypergraph models, referred to as emph{online sprinkling}. As an illustrative application of this method, we show that for any fixed integer $kgeq3$, the binomial $k$-uniform random hypergraph $H_{n,p}^k$ contains $$ edge-disjoint perfect matchings, provided $pgeqfraclo{g}^{C}n{n}^{k-1}$, where $C:=C(k)$ is an integer depending only on $k$. Our result for $N$ is asymptotically best optimal and for $p$ is optimal up to the $polylog(n)$ factor.

Recommendations

• Almost perfect matchings in random uniform hypergraphs
• Packing random graphs and hypergraphs
• Co-degrees resilience for perfect matchings in random hypergraphs
• Perfect packings in quasirandom hypergraphs. I.
• Perfect matchings in random s‐uniform hypergraphs

Cited in

(10)

• Dirac-type theorems in random hypergraphs
• Perfect fractional matchings in \(k\)-out hypergraphs
• Perfect packings in quasirandom hypergraphs. I.
• Perfect matchings in random s‐uniform hypergraphs
• Packing trees of unbounded degrees in random graphs
• Pseudorandom hypergraph matchings
• Packing random graphs and hypergraphs
• Perfect Packings in Quasirandom Hypergraphs II
• Packing loose Hamilton cycles
• Packing and counting arbitrary Hamilton cycles in random digraphs

This page was built for publication: Packing perfect matchings in random hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4642740)