Jung–Keszegh–Pálvölgyi–Yuditsky conjecture on piercing maximum hypergraph cliques
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
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).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.