Packing perfect matchings in random hypergraphs

Asaf Ferber, Van VuRandom Struct. Algorithms 2018 · DOI

TL;DR

This paper introduces a new "online sprinkling" technique to efficiently find multiple edge-disjoint perfect matchings in random hypergraphs. The authors prove that for a specific class of random hypergraphs, they can find a near-optimal number of these matchings, significantly improving upon previous results. This work is crucial for understanding the structural properties of large random hypergraphs.

What Problem Does This Paper Address?

The paper tackles the problem of finding multiple edge-disjoint perfect matchings within a random hypergraph. A perfect matching in a $k$-uniform hypergraph is a set of edges where each vertex is covered by exactly one edge. Finding even a single perfect matching in random hypergraphs is a challenging problem, famously related to Shamir's Conjecture. While previous work has established conditions under which a single perfect matching appears, finding multiple edge-disjoint perfect matchings that cover a significant portion of the hypergraph's edges is a more complex question. The authors aim to show that for a standard random hypergraph model ($H_{n,p}^k$), one can pack a large number of these matchings, improving upon the density requirements established by Frieze and Krivelevich.

Methods

The core methodological contribution is the introduction of an "online sprinkling" technique. This method generates a random hypergraph incrementally, in stages. In each stage, a subset of potential edges is considered, and then each of these edges is included in the hypergraph with a certain probability. This allows for a more controlled construction of the desired structures.

The proof strategy involves two main phases:

  1. Phase 1: Building "almost spanning" structures. This phase uses a "nibbling" approach, where matchings are built incrementally by adding small sets of edges that are vertex-disjoint from previously chosen edges. This phase aims to find a large number of edge-disjoint matchings, each covering a significant fraction (but not all) of the vertices.
  2. Phase 2: Completing to perfect matchings. In this phase, the "almost spanning" matchings from Phase 1 are extended to full perfect matchings. This step heavily relies on a known result (from Johansson, Kahn, and Vu) that guarantees the existence of a perfect matching in a random hypergraph under certain conditions.

The authors also introduce a $k$-partite hypergraph model ($H_{n \times k, p}^k$) as a technical tool, which simplifies some aspects of the proof before relating it back to the original hypergraph model.

Datasets

Not discussed in the paper. The paper deals with theoretical models of random hypergraphs, not empirical datasets.

Key Insights and Ideas

  • Online Sprinkling: The novel "online sprinkling" technique offers a flexible way to construct complex structures within random graphs/hypergraphs by building them incrementally and controlling edge probabilities at each step. This is more powerful than simply querying edges independently for the entire graph at once.
  • Nibbling for Matchings: The adaptation of the "nibbling" technique, typically used in deterministic settings, to the random setting is a key idea for constructing the initial large matchings. The randomness of the hypergraph simplifies some aspects of the nibbling process.
  • Two-Phase Approach: The strategy of first finding "almost spanning" structures and then completing them to perfect matchings is a common theme in probabilistic combinatorics, but its successful application here to pack multiple matchings is significant.
  • Optimality of Probability Threshold: The paper demonstrates that the probability threshold for packing a near-optimal number of perfect matchings is essentially optimal, up to polylogarithmic factors, which is a strong theoretical result.

Key Results

The main quantitative result is Theorem 1.2: For a $k$-uniform random hypergraph $H_{n,p}^k$ with $k \ge 3$ and $p > \frac{\log^4 k n}{n^{k-1}}$, the hypergraph contains $(1 - o(1)) \frac{n^{k-1}p}{C(k)}$ edge-disjoint perfect matchings, where $C(k)$ is a constant depending on $k$. This number is asymptotically optimal for the given probability $p$. Theorem 1.4 provides a similar result for a $k$-partite hypergraph model.

Limitations and Future Work

  • Case k=2: The paper explicitly mentions that the case $k=2$ (standard graphs) is more complicated and requires different tools (generalizations of Hall's Theorem). The current technique is primarily for $k \ge 3$.
  • Polylogarithmic Factors: The proof strategy inherently introduces polylogarithmic factors in the probability threshold. While the authors believe the threshold is truly lower, their method doesn't achieve this exact optimality.
  • Dependence on Existing Results: The proof relies on a pre-existing result for finding a single perfect matching in random hypergraphs. It does not provide a new proof for that fundamental result.
  • Future Work: The authors suggest that their technique could be applied to finding other types of structures in random hypergraphs, and that more complicated applications will appear in follow-up papers. The extension to $k=2$ and the removal of polylogarithmic factors are natural avenues for future research.

Summary updated

BibTeX
@article{ferber2018packing,
  author = {Asaf Ferber and Van Vu},
  title = {{Packing perfect matchings in random hypergraphs}},
  journal = {Random Struct. Algorithms},
  year = {2018},
  doi = {10.1002/rsa.20745},
}
Figure