Linear saturation numbers of Berge-$C_3$ and Berge-$C_4$

Cynthia Wang, Junxue ZhangarXiv 2023 · DOI · arXiv

Abstract: The linear saturation number $sat^{lin}_k(n,\mathcal{F})$ of a family of hypergraphs $\mathcal{F}$ is the minimum number of hyperedges in an $n$-vertex linear $k$-uniform hypergraph that contains no member of $\mathcal{F}$, but where the addition of any new hyperedge (preserving linearity) creates a copy of some hypergraph in $\mathcal{F}$. This paper proves that $sat^{lin}_k(n, \text{Berge-}C_t) \ge \lfloor \frac{n-1}{k-1} \rfloor$ for any integers $k, t \ge 3$, with equality holding for $t=3$. Additionally, the authors provide upper bounds for $sat^{lin}_3(n, \text{Berge-}C_4)$ and establish lower bounds for the number of hyperedges in disconnected Berge-$C_4$-saturated linear 3-uniform hypergraphs.

Introduction

In extremal graph theory, standard problems often focus on the maximum number of edges a graph can have without containing a specific forbidden subgraph. Saturation problems explore the opposite end of the spectrum: determining the minimum number of edges such that a graph is "maximal" with respect to the absence of a forbidden structure. Adding any missing edge to a saturated graph must create at least one copy of the forbidden subgraph.

This paper investigates these properties within the context of linear $k$-uniform hypergraphs. A hypergraph is linear if any two of its hyperedges share at most one vertex. The forbidden structures studied here are Berge cycles, which generalize cycles to the hypergraph setting. While extremal numbers for Berge cycles have been linked to classical problems like the (6,3)-problem, their saturation numbers have remained largely unexplored until this work.

Methodology

The research employs a combination of combinatorial proofs and explicit structural constructions. A central technique is the use of bipartite mapping, where hypergraphs are represented as bipartite graphs to apply established results from graph connectivity and path theory.

To derive upper bounds for Berge-$C_4$ saturation, the authors utilize a recursive gluing method. This involves defining small, saturated "seed" hypergraphs and merging them at specific "cut vertices" to build larger $n$-vertex hypergraphs while maintaining the saturation property. This iterative process is demonstrated in the sequence of hypergraphs $T_i$ shown below.

Recursive construction of saturated hypergraphs $T_i$

Another critical concept is Berge-$P_3$-connectivity. A hypergraph is considered Berge-$P_3$-connected if every pair of non-adjacent vertices is connected by a Berge path of length 3. This structural property ensures that the addition of any valid new hyperedge will complete a Berge cycle of length 4, satisfying the saturation condition.

Key Results

The authors establish several foundational results for the linear saturation of Berge cycles:

  • Universal Lower Bound: For any $k$-uniform linear hypergraph and any Berge cycle of length $t \ge 3$, the linear saturation number is at least $\lfloor \frac{n-1}{k-1} \rfloor$.
  • Exact Value for Triangles: For Berge-$C_3$, the saturation number is proven to be exactly $\lfloor \frac{n-1}{k-1} \rfloor$, settling the problem for the simplest cycle case. This structure typically resembles a collection of "stars."
  • Bounds for Quadrilaterals: For Berge-$C_4$ in 3-uniform hypergraphs, the authors provide an upper bound that scales approximately as $\frac{5n}{6}$. These bounds are derived from complex saturated structures such as $T'$ and $T^*$.
Saturated hypergraphs $T'$ and $T^*$ used for $C_4$ bounds
  • Disconnected Components: For disconnected Berge-$C_4$-saturated hypergraphs, the paper establishes a lower bound of $e(H) \ge \frac{2n}{3} - 4$, indicating that the edge density requirements may shift if connectivity is not enforced.

Conclusion and Future Work

This work provides the first systematic bounds for the linear saturation numbers of Berge cycles. While the results for Berge-$C_3$ are definitive for all $k$, the findings for Berge-$C_4$ are primarily focused on 3-uniform hypergraphs. Future research directions include generalizing the $C_4$ upper bounds for larger $k$, determining exact saturation values for cycles of length $t > 4$, and further exploring the structural differences between connected and disconnected saturated hypergraphs.

Summary updated

Abstract

The linear saturation number $sat^{lin}_k(n,\mathcal{F})$ (linear extremal number $ex^{lin}_k(n,\mathcal{F})$) of $\mathcal{F}$ is the minimum (maximum) number of hyperedges of an $n$-vertex linear $k$-uniform hypergraph containing no member of $\mathcal{F}$ as a subgraph, but the addition of any new hyperedge such that the result hypergraph is still a linear $k$-uniform hypergraph creates a copy of some hypergraph in $\mathcal{F}$. Determining $ex_3^{lin}(n$, Berge-$C_3$) is equivalent to the famous (6,3)-problem, which has been settled in 1976. Since then, determining the linear extremal numbers of Berge cycles was extensively studied. As the counterpart of this problem in saturation problems, the problem of determining the linear saturation numbers of Berge cycles is considered. In this paper, we prove that $sat^{lin}_k$($n$, Berge-$C_t)\ge \big\lfloor\frac{n-1}{k-1}\big\rfloor$ for any integers $k\ge3$, $t\ge 3$, and the equality holds if $t=3$. In addition, we provide an upper bound for $sat^{lin}_3(n,$ Berge-$C_4)$ and for any disconnected Berge-$C_4$-saturated linear 3-uniform hypergraph, we give a lower bound for the number of hyperedges of it.
BibTeX
@misc{wang2023linear,
  author = {Cynthia Wang and Junxue Zhang},
  title = {{Linear saturation numbers of Berge-$C\_3$ and Berge-$C\_4$}},
  year = {2023},
  eprint = {2306.06435},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.06435},
}
Figure