Vertex degree sums for rainbow matchings in 3-uniform hypergraphs

Haorui Liu, Mei Lu, Yan Wang, Yi ZhangarXiv 2025 · DOI · arXiv

TL;DR

This paper proves that the "rainbow" version of a key theorem in hypergraph theory is asymptotically true. It shows that if you have a collection of 3-uniform hypergraphs where the sum of degrees for any two adjacent vertices is sufficiently high, you can always find a perfect matching that picks exactly one edge from each hypergraph.

What Problem Does This Paper Address?

In graph theory, a "matching" is a set of edges that don't share any vertices. A "perfect matching" is one that covers every single vertex in the graph. While these concepts are well-understood for standard graphs, they become significantly more complex in hypergraphs, where an "edge" can contain three or more vertices (in this paper, exactly three, known as a 3-uniform hypergraph).

The authors specifically tackle the rainbow matching problem. Imagine you have $n/3$ different hypergraphs defined on the same set of $n$ vertices. A rainbow matching is a set of disjoint edges where each edge comes from a different hypergraph in your collection.

Previous work by Zhang, Zhao, and Lu established the minimum degree sum of two adjacent vertices (vertices that share an edge) required to guarantee a perfect matching in a single hypergraph. This paper investigates whether that same threshold—or something very close to it—guarantees a rainbow perfect matching across a family of hypergraphs.

Methods

The proof relies on a sophisticated "absorbing method," a staple in modern extremal combinatorics. The key steps include:

  1. Reduction to a 4-Graph: The authors transform the problem of finding a rainbow matching in 3-uniform hypergraphs into a problem of finding a standard perfect matching in a specific type of 4-uniform hypergraph. They create a new vertex set $Q$ representing the indices of the hypergraphs and a set $P$ representing the original vertices. An edge in this new 4-graph consists of one "index" vertex and three "content" vertices.
  2. The Absorbing Lemma: They prove the existence of a small "absorbing matching." This is a set of edges that can be rearranged to "absorb" any small, leftover set of vertices into a perfect matching.
  3. Fractional and Almost Perfect Matchings: Using probabilistic tools (like Chernoff and Janson inequalities) and the Pippenger-Spencer Theorem, they show that the hypergraph contains an "almost" perfect matching that leaves only a tiny fraction of vertices uncovered.
  4. Completion: Finally, they use the absorbing matching created in step 2 to soak up the few remaining vertices, resulting in a full rainbow perfect matching.

Datasets

Not applicable. This is a theoretical mathematical research paper; no external datasets or empirical benchmarks were used. The "evaluation" consists of rigorous logical proofs.

Key Insights and Ideas

  • The Power of Adjacency: Unlike many results that look at the minimum degree of a single vertex, this paper focuses on the degree sum of adjacent vertices. This is an "Ore-type" condition, named after Øystein Ore, who pioneered this approach for Hamilton cycles in graphs.
  • Asymptotic Tightness: The authors prove the result for a degree sum of $(\frac{2}{3} + \delta)n^2$. This is considered "asymptotically tight" because it mirrors the $\frac{2}{3}n^2$ threshold found for single hypergraphs, with only a small error term ($\delta$) required for the rainbow setting.
  • Bridging Rainbow and Partite Problems: The most elegant conceptual move is the conversion of the "rainbow" requirement into a structural property of a higher-order (4-uniform) hypergraph. This allows the authors to use powerful existing tools designed for partite hypergraphs.

Key Results

  • Theorem 3 (Main Result): For any $\delta > 0$ and a sufficiently large $n$ divisible by 3, if a family of $n/3$ hypergraphs $F_i$ satisfies the condition that $deg(u) + deg(v) > (\frac{2}{3} + \delta)n^2$ for any two adjacent vertices $u, v$, then the family admits a rainbow perfect matching.
  • This result confirms that the rainbow version of the Zhang-Zhao-Lu theorem holds true as $n$ approaches infinity.

Limitations and Future Work

  • Asymptotic vs. Exact: The paper provides an asymptotic result (valid for "sufficiently large $n$"). The authors explicitly pose Problem 2, which asks for the exact threshold (without the $\delta$ term). Finding the exact bound remains an open challenge.
  • Uniformity: The study is limited to 3-uniform hypergraphs. While the authors mention that similar logic has been applied to 4-graphs in other contexts, a generalized theory for $k$-uniform hypergraphs using this specific degree-sum condition is a potential avenue for future research.
  • Isolated Vertices: The current proof assumes the hypergraphs have no isolated vertices. Relaxing or further exploring this constraint could be interesting for sparse hypergraph theory.

Summary updated

Abstract

Let $n \in 3\mathbb{Z}$ be sufficiently large. Zhang, Zhao and Lu proved that if $H$ is a 3-uniform hypergraph with $n$ vertices and no isolated vertices, and if $deg(u)+deg(v) > \frac{2}{3}n^2 - \frac{8}{3}n + 2$ for any two vertices $u$ and $v$ that are contained in some edge of $H$, then $ H $ admits a perfect matching. In this paper, we prove that the rainbow version of Zhang, Zhao and Lu's result is asymptotically true. More specifically, let $δ> 0$ and $ F_1, F_2, \dots, F_{n/3} $ be 3-uniform hypergraphs on a common set of $n$ vertices. For each $ i \in [n/3] $, suppose that $F_i$ has no isolated vertices and $deg_{F_i}(u)+deg_{F_i}(v) > \left( \frac{2}{3} + δ\right)n^2$ holds for any two vertices $u$ and $v$ that are contained in some edge of $F_i$. Then $ \{ F_1, F_2, \dots, F_{n/3} \} $ admits a rainbow matching. Note that this result is asymptotically tight.
BibTeX
@misc{liu2025vertex,
  author = {Haorui Liu and Mei Lu and Yan Wang and Yi Zhang},
  title = {{Vertex degree sums for rainbow matchings in 3-uniform hypergraphs}},
  year = {2025},
  eprint = {2503.14968},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2503.14968},
  howpublished = {arXiv},
}

Loading related content...

Figure