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

Less than 1 year old · traced to

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 k≥2k\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, k≥3k\geq3, and t≥1t\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.

References

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).

Progress summary

Never refreshed

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.