Jung–Keszegh–Pálvölgyi–Yuditsky conjecture on piercing maximum hypergraph cliques
Let , let denote the family of -element subsets of , and let be a -uniform hypergraph. Write for its number of vertices and for the size of its largest clique.
Jung–Keszegh–Pálvölgyi–Yuditsky conjecture. For all there exists a constant such that, whenever
the maximum-size cliques of can be hit with a single point.
The conjecture proposed a hypergraph analogue of Hajnal's graph theorem, asserting that sufficiently large maximum cliques force a common piercing vertex. It is refuted in the source: for every , , and , there are -uniform hypergraphs with maximum clique size exceeding times the number of vertices whose maximum cliques cannot be pierced by vertices.
References
- Andreas Holmsen, Attila Jung, Balázs Keszegh, Dániel G. Simon and Gábor Tardos, “Piercing all maximum cliques in hypergraphs”, arXiv:2604.21588 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.