Jung–Keszegh–Pálvölgyi–Yuditsky conjecture on piercing maximum hypergraph cliques

From papers

Let [n]={1,,n}[n]=\{1,\ldots,n\}, let ([n]k)\binom{[n]}{k} denote the family of kk-element subsets of [n][n], and let H([n]k)\mathcal{H}\subset\binom{[n]}{k} be a kk-uniform hypergraph. Write v(H)v(\mathcal{H}) for its number of vertices and ω(H)\omega(\mathcal{H}) for the size of its largest clique.

Jung–Keszegh–Pálvölgyi–Yuditsky conjecture. For all k2k\geq2 there exists a constant ck<1c_k<1 such that, whenever

ω(H)>ckv(H),\omega(\mathcal{H})>c_kv(\mathcal{H}),

the maximum-size cliques of H\mathcal{H} 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 c<1c<1, k3k\geq3, and t1t\geq1, there are kk-uniform hypergraphs with maximum clique size exceeding cc times the number of vertices whose maximum cliques cannot be pierced by tt 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

No solutions have been posted yet.