Hypergraph saturation for the bow tie
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917762428829696 |
|---|---|
| author | Cambie, Stijn Salia, Nika |
| author_facet | Cambie, Stijn Salia, Nika |
| contents | Erdős and Sós initiated the study of the maximum size of a $k$-uniform set system, for $k \geq 4$, with no singleton intersections $50$ years ago. In this work, we investigate the dual problem: finding the minimum size of a $k$-uniform hypergraph with no singleton intersections, such that adding any missing hyperedge forces a singleton intersection. These problems, known as saturation and semi-saturation, are typically challenging. Our focus is on an elementary-to-state case in the line of work by Erdős, Füredi and Tuza. We establish tight linear bounds for $k=4$, marking one of the first non-obvious cases with such a bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16758 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hypergraph saturation for the bow tie Cambie, Stijn Salia, Nika Combinatorics 05C35, 05C65, 05C70 Erdős and Sós initiated the study of the maximum size of a $k$-uniform set system, for $k \geq 4$, with no singleton intersections $50$ years ago. In this work, we investigate the dual problem: finding the minimum size of a $k$-uniform hypergraph with no singleton intersections, such that adding any missing hyperedge forces a singleton intersection. These problems, known as saturation and semi-saturation, are typically challenging. Our focus is on an elementary-to-state case in the line of work by Erdős, Füredi and Tuza. We establish tight linear bounds for $k=4$, marking one of the first non-obvious cases with such a bound. |
| title | Hypergraph saturation for the bow tie |
| topic | Combinatorics 05C35, 05C65, 05C70 |
| url | https://arxiv.org/abs/2408.16758 |