Exact Minimum Codegree Thresholds for $K_4^-$-Covering and $K_5^-$-Covering

Lei Yu, Xinmin Hou, Yue Ma, Boyuan LiuElectron. J. Comb 2020 · OpenReview

TL;DR

This paper tackles a problem in hypergraph theory: finding the minimum "codegree" (a measure of how connected vertices are to edges) required to guarantee that a hypergraph contains a specific substructure (a "covering"). The authors precisely determine these thresholds for two specific substructures, $K_4^-$ and $K_5^-$, resolving an open problem and providing exact formulas.

What Problem Does This Paper Address?

Imagine you have a collection of sets (a hypergraph), where each set has exactly three elements (a 3-graph). We're interested in whether this collection "covers" all its vertices. A hypergraph $H$ has an $F$-covering if we can find copies of a smaller hypergraph $F$ within $H$ such that every vertex in $H$ belongs to at least one of these copies of $F$.

The core question is: how "dense" does $H$ need to be to guarantee an $F$-covering? Specifically, the paper focuses on the minimum codegree, denoted $\delta_2(H)$, which is the minimum number of edges a pair of vertices shares. The authors define $c_2(n, F)$ as the maximum codegree a hypergraph on $n$ vertices can have without containing an $F$-covering. If a hypergraph has a codegree greater than $c_2(n, F)$, it's guaranteed to have an $F$-covering.

Previous work by Falgas-Ravry and Zhao established bounds for $c_2(n, K_4^-)$ and $c_2(n, K_5^-)$, where $K_t^-$ represents a complete $t$-vertex 3-graph with one edge removed. However, these were only bounds, leaving an open problem to find the exact values. This paper aims to close that gap.

Methods

The paper employs a constructive approach. To determine the exact value of $c_2(n, F)$, the authors need to do two things:

  1. Prove an upper bound: Show that any hypergraph with a codegree higher than a certain value must contain an $F$-covering. This is often done by leveraging existing theorems, like Theorem 1.1 in this paper, which relates the codegree threshold to the existence of an $F$-covering.
  2. Construct a counterexample: Build a specific hypergraph that has a codegree equal to that certain value but does not contain an $F$-covering. This demonstrates that the threshold cannot be any lower.

For their constructions, the authors utilize:

  • Blow-ups of graphs: They take known graphs (like cycles and complete bipartite graphs) and "blow them up" by replacing each vertex with a set of vertices. This allows them to control the density and structure of the resulting hypergraph.
  • Link graphs: For a vertex $x$ in a 3-graph $H$, the link graph $H(x)$ is a 2-graph (a standard graph) formed by the neighbors of $x$. Analyzing the properties of $H(x)$ is crucial for understanding how $x$ can be covered by copies of $F$.
  • Careful case analysis: The problem's dependence on $n$ modulo 6 requires breaking down the constructions and proofs into several cases based on the remainder of $n$ when divided by 6.

Datasets

Not discussed in the paper. The paper deals with theoretical constructions of hypergraphs rather than empirical evaluation on datasets.

Key Insights and Ideas

  • The power of codegree: The research highlights how a seemingly simple local property like the minimum codegree can have profound global implications for the existence of substructures within hypergraphs.
  • Constructing "just enough" density: The key to finding the exact threshold is to construct hypergraphs that are almost dense enough to force an $F$-covering but just miss the mark. This requires intricate constructions that precisely balance the number of edges.
  • Leveraging graph theory tools: The use of blow-ups and link graphs demonstrates how techniques from standard graph theory can be adapted and extended to study more complex hypergraph structures.
  • The role of modular arithmetic: The dependence of the exact threshold on $n \pmod 6$ is a common theme in extremal hypergraph theory, suggesting deep structural properties related to divisibility.

Key Results

The paper successfully determines the exact values for $c_2(n, K_4^-)$ and $c_2(n, K_5^-)$, resolving an open problem. Specifically:

  • For $K_4^-$: The paper proves Theorem 1.4, stating $c_2(n, K_4^-) = \lfloor \frac{2n}{3} \rfloor$. This resolves Problem 1.3 from a previous work.
  • For $K_5^-$: The paper proves Theorem 1.5, stating $c_2(n, K_5^-) = \lfloor \frac{2n-2}{3} \rfloor$. This completes Theorem 1.2 from a previous work.

These results provide precise thresholds for when a 3-graph with a certain minimum codegree is guaranteed to contain a $K_4^-$ or $K_5^-$ covering.

Limitations and Future Work

  • Specific substructures: The results are exact for $K_4^-$ and $K_5^-$. The paper's methods might be adaptable to other specific hypergraphs, but a general theory for arbitrary $F$ remains a significant challenge.
  • Generalization to $k$-graphs: This paper focuses on 3-graphs. Extending these results to $k$-graphs for $k > 3$ would be a natural next step, likely involving more complex constructions and analysis.
  • Other covering properties: The paper focuses on $F$-covering. Investigating thresholds for other types of hypergraph coverings or packings could be fruitful.
  • Asymptotic vs. Exact: While this paper provides exact values, much of the field still relies on asymptotic results. Finding exact thresholds for a wider range of hypergraphs is a continuing area of research.

Summary updated

Abstract

Given two $3$-graphs $F$ and $H$, an $F$-covering of $H$ is a collection of copies of $F$ in $H$ such that each vertex of $H$ is contained in at least one copy of them. Let $c_2(n,F)$ be the minimum integer $t$ such that every 3-graph with minimum codegree greater than $t$ has an $F$-covering. In this note, we answer an open problem of Falgas-Ravry and Zhao (SIAM J. Discrete Math., 2016) by determining the exact value of $c_2(n, K_4^-)$ and $c_2(n, K_5^-)$, where $K_t^-$ is the complete $3$-graph on $t$ vertices with one edge removed.
BibTeX
@article{yu2020exact,
  author = {Lei Yu and Xinmin Hou and Yue Ma and Boyuan Liu},
  title = {{Exact Minimum Codegree Thresholds for $K\_4^-$-Covering and $K\_5^-$-Covering}},
  journal = {Electron. J. Comb.},
  year = {2020},
  url = {https://openreview.net/forum?id=AKmqCiXxpf},
}
Figure