The Degree Threshold for Covering with all the Connected $3$-Graphs with $3$ Edges

Yue Ma, Xinmin Hou, Zhi YinElectron. J. Comb 2025 · OpenReview

TL;DR

This paper tackles the problem of "covering" in hypergraphs, specifically determining the minimum degree a hypergraph needs to guarantee that every vertex is part of a specific small substructure (a "connected 3-graph with 3 edges"). The authors provide exact thresholds for all such substructures, completing a significant line of research in hypergraph theory.

What Problem Does This Paper Address?

In hypergraph theory, a fundamental question is understanding how the minimum degree of a hypergraph relates to its substructures. Specifically, this paper focuses on the "F-covering" problem: given a small hypergraph $F$, what is the minimum degree a larger hypergraph $H$ must have to guarantee that every vertex in $H$ belongs to at least one copy of $F$? This is quantified by $c_1(n, F)$, the minimum degree threshold for an $n$-vertex hypergraph to have an $F$-covering. Previous work had established these thresholds for a few specific hypergraphs, but a complete picture for all connected 3-graphs with 3 edges was missing. This paper aims to fill that gap.

Methods

The paper employs a combination of extremal graph theory techniques. For lower bounds, they construct specific hypergraphs that do not contain the target substructure $F$ despite having a high minimum degree, thus establishing a lower bound for $c_1(n, F)$. For upper bounds, they use proof by contradiction, assuming a hypergraph with a sufficiently high minimum degree does not have an $F$-covering and then deriving a contradiction using structural properties of hypergraphs and their link graphs. Key tools include:

  • Link Graphs: The "link graph" of a vertex $v$ in a $k$-uniform hypergraph $H$ is a $(k-1)$-uniform hypergraph formed by the neighbors of $v$. This is a standard technique for analyzing hypergraph properties.
  • Induction and Contradiction: Many proofs proceed by induction on the number of vertices or by assuming the opposite of what needs to be proven and deriving a logical inconsistency.
  • Combinatorial Arguments: Detailed case analysis and counting arguments are used to establish bounds and rule out specific configurations.
  • Known Theorems: The Tutte-Berge theorem is invoked in one of the proofs to bound the number of edges in certain subgraphs.

Datasets

Not discussed in the paper. This paper is a theoretical work in combinatorics and does not involve empirical data or datasets.

Key Insights and Ideas

  • Completing the Picture: The paper provides a complete set of degree thresholds for all connected 3-graphs with 3 edges. This is a significant achievement, as these structures represent the simplest non-trivial connected hypergraphs beyond single edges or pairs of edges.
  • $F_5$ as a Key Case: The generalized triangle $F_5$ is a central focus, and its exact degree threshold $c_1(F_5)$ is determined. This structure, with its specific edge configuration, presents unique challenges.
  • Variety of Thresholds: While many of the thresholds are linear in $n$ (e.g., $n-1$ or $n-2$), some exhibit more complex behavior, like $c_1(n, TP_3)$ which depends on $n \pmod 3$. This highlights the subtle differences in how these small hypergraphs embed.
  • Connection to Other Extremal Problems: The paper situates the covering problem within the broader landscape of hypergraph extremal problems, contrasting it with Turán problems (finding the maximum number of edges without a given subgraph) and tiling problems (finding vertex-disjoint copies of a subgraph).

Key Results

The paper determines the exact values of $c_1(n, F)$ for all connected 3-graphs $F$ with 3 edges. Specifically:

  • The asymptotic threshold for $F_5$ (the generalized triangle) is determined.
  • Exact values for $c_1(n, F)$ are found for $F \in \{LP_3, TP_3, GP_3, K_{1,1,3}, S_3, GS_3\}$. These values are often of the form $n-k$ for small constants $k$, or depend on $n \pmod 3$. For example:
  • $c_1(n, F_5) = \frac{1}{2}$ (asymptotic density).
  • $c_1(n, LP_3) = n-2$ for $n \ge 13$.
  • $c_1(n, TP_3)$ is $n-1$ if $n \equiv 1 \pmod 3$, and $n-2$ if $n \equiv 0, 2 \pmod 3$, for $n \ge 6$.
  • $c_1(n, K_{1,1,3}) = n-1$ for $n \ge 9$.
  • $c_1(n, S_3) = n-1$ for $n \ge 11$.
  • $c_1(n, GS_3) = \lceil \frac{n-1}{2} \rceil$ for $n \ge 13$.

Limitations and Future Work

  • Focus on 3-Graphs: The paper is exclusively focused on 3-uniform hypergraphs with 3 edges. The authors note that for 3-graphs with more than 3 edges, there are very few non-trivial exact results for $c_1(F)$. This suggests a broad avenue for future research.
  • 2-Degree Thresholds: While the paper focuses on 1-degree thresholds ($c_1$), it briefly mentions that 2-degree thresholds ($c_2$) for these small hypergraphs are often small constants. Investigating these further could be a direction for future work.
  • Generalizations: Extending these results to $r$-uniform hypergraphs with a fixed number of edges, or to different types of substructures, remains an open area.

Summary updated

Abstract

Given two $r$-uniform hypergraphs $F$ and $H$, we say that $H$ has an $F$-covering if every vertex in $H$ is contained in a copy of $F$. Let $c_{i}(n,F)$ be the least integer such that every $n$-vertex $r$-graph $H$ with $\delta_{i}(H)>c_i(n,F)$ has an $F$-covering. Falgas-Ravry, Markström and Zhao (Combin. Probab. Comput., 2021) asymptotically determined $c_1(n,K_{4}^{(3)-})$, where $K_{4}^{(3)-}$ is obtained by deleting an edge from the complete $3$-graph on $4$ vertices. Later, Tang, Ma and Hou (Electron. J. Combin., 2023) asymptotically determined $c_1(n,C_{6}^{(3)})$, where $C_{6}^{(3)}$ is the linear triangle, i.e. $C_{6}^{(3)}=([6],\{123,345,561\})$. In this paper, we determine $c_1(n,F_5)$ asymptotically, where $F_5$ is the generalized triangle, i.e. $F_5=([5],\{123,124,345\})$. We also determine the exact values of $c_1(n,F)$, where $F$ is any connected $3$-graph with $3$ edges and $F\notin\{K_4^{(3)-}, C_{6}^{(3)}, F_5\}$.
BibTeX
@article{ma2025degree,
  author = {Yue Ma and Xinmin Hou and Zhi Yin},
  title = {{The Degree Threshold for Covering with all the Connected $3$-Graphs with $3$ Edges}},
  journal = {Electron. J. Comb.},
  year = {2025},
  url = {https://openreview.net/forum?id=QbRuzrHtum},
}
Figure