Piercing all maximum cliques in hypergraphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914502248759296 |
|---|---|
| author | Holmsen, Andreas Jung, Attila Keszegh, Balázs Simon, Dániel G. Tardos, Gábor |
| author_facet | Holmsen, Andreas Jung, Attila Keszegh, Balázs Simon, Dániel G. Tardos, Gábor |
| contents | Graphs whose maximum clique size exceeds half of the total number of vertices satisfy a classical property: the family of their maximum sized cliques can be pierced by a single vertex. This result dates back to a 1965 theorem by Hajnal. Motivated by this theorem, Jung, Keszegh, Pálvölgyi, and Yuditsky recently conjectured that an analogous result should hold for hypergraphs of larger uniformity, with an appropriate constant replacing the threshold $1/2$.
In this paper we refute this conjecture in a strong form. We show that for any constant $c<1$ and integers $k\ge 3$ and $t\ge 1$, there exist $k$-uniform hypergraphs $G$ whose maximum clique size exceeds $c|V(G)|$, yet the family of maximum size cliques of $G$ cannot be pierced by $t$ vertices. This demonstrates that no universal constant threshold guarantees bounded piercing number for maximum cliques in uniform hypergraphs.
We discuss further questions concerning the relationship between clique size and piercing maximum cliques in hypergraphs, and introduce a geometric variant of the problem using Helly's Theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_21588 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Piercing all maximum cliques in hypergraphs Holmsen, Andreas Jung, Attila Keszegh, Balázs Simon, Dániel G. Tardos, Gábor Combinatorics Metric Geometry 05C65 (Primary), 05C69, 52A35, 05D10 (Secondary) Graphs whose maximum clique size exceeds half of the total number of vertices satisfy a classical property: the family of their maximum sized cliques can be pierced by a single vertex. This result dates back to a 1965 theorem by Hajnal. Motivated by this theorem, Jung, Keszegh, Pálvölgyi, and Yuditsky recently conjectured that an analogous result should hold for hypergraphs of larger uniformity, with an appropriate constant replacing the threshold $1/2$. In this paper we refute this conjecture in a strong form. We show that for any constant $c<1$ and integers $k\ge 3$ and $t\ge 1$, there exist $k$-uniform hypergraphs $G$ whose maximum clique size exceeds $c|V(G)|$, yet the family of maximum size cliques of $G$ cannot be pierced by $t$ vertices. This demonstrates that no universal constant threshold guarantees bounded piercing number for maximum cliques in uniform hypergraphs. We discuss further questions concerning the relationship between clique size and piercing maximum cliques in hypergraphs, and introduce a geometric variant of the problem using Helly's Theorem. |
| title | Piercing all maximum cliques in hypergraphs |
| topic | Combinatorics Metric Geometry 05C65 (Primary), 05C69, 52A35, 05D10 (Secondary) |
| url | https://arxiv.org/abs/2604.21588 |