Piercing all maximum cliques in hypergraphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.21588
curl -X POST /api/v1/records/arxiv/2604.21588/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.21588/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'