Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.18455 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915756079316992 |
|---|---|
| author | Chen, Yihan He, Jialin Xie, Tianying |
| author_facet | Chen, Yihan He, Jialin Xie, Tianying |
| contents | The saturation number $\text{sat}_r(n,\mathcal{F})$ is the minimum number of hyperedges in an $r$-uniform $\mathcal{F}$-saturated hypergraph on $n$ vertices. We determine this parameter for $3$-uniform Berge-$K_4$ hypergraphs, proving that $\text{sat}_3(n,\text{Berge-}K_4)=n$ for $n =5,7,8$ and $n\ge 96$, while $\text{sat}_3(6,\text{Berge-}K_4)=5$. This resolves a problem posed by English, Kritschgau, Nahvi, and Sprangel~\cite{EKNS2024} for large $n.$ Using a computer search, we classify all extremal hypergraphs for $5\le n\le 8.$ For $n\geq 96$, we further show the existence of many non-isomorphic extremal families. Our approach synthesizes structural insights with computational power. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_18455 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Saturation numbers for $3$-uniform Berge-$K_4$ Chen, Yihan He, Jialin Xie, Tianying Combinatorics The saturation number $\text{sat}_r(n,\mathcal{F})$ is the minimum number of hyperedges in an $r$-uniform $\mathcal{F}$-saturated hypergraph on $n$ vertices. We determine this parameter for $3$-uniform Berge-$K_4$ hypergraphs, proving that $\text{sat}_3(n,\text{Berge-}K_4)=n$ for $n =5,7,8$ and $n\ge 96$, while $\text{sat}_3(6,\text{Berge-}K_4)=5$. This resolves a problem posed by English, Kritschgau, Nahvi, and Sprangel~\cite{EKNS2024} for large $n.$ Using a computer search, we classify all extremal hypergraphs for $5\le n\le 8.$ For $n\geq 96$, we further show the existence of many non-isomorphic extremal families. Our approach synthesizes structural insights with computational power. |
| title | Saturation numbers for $3$-uniform Berge-$K_4$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2601.18455 |