pith. sign in

arxiv: 2604.21588 · v1 · submitted 2026-04-23 · 🧮 math.CO · math.MG

Piercing all maximum cliques in hypergraphs

Andreas Holmsen , Attila Jung , Bal\'azs Keszegh , D\'aniel G. Simon , G\'abor Tardos This is my paper

Pith reviewed 2026-05-09 21:33 UTC · model grok-4.3

classification 🧮 math.CO math.MG
keywords hypergraphscliquespiercing numberuniform hypergraphsconjecture refutationHajnal theoremHelly theoremintersection theorems
0
0 comments X

The pith

Hypergraphs can have maximum cliques exceeding any fraction c<1 of their vertices while requiring arbitrarily many points to pierce all of them.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper refutes a conjecture extending a 1965 graph theorem to hypergraphs. In graphs, maximum cliques larger than half the vertices always share one common vertex. The authors build k-uniform hypergraphs for any k at least 3 where the largest cliques occupy more than c fraction of vertices for any c below 1, yet no fixed number t of vertices hits every such clique. This shows no single density threshold forces bounded piercing numbers in uniform hypergraphs. The work also poses a geometric version of the piercing question that invokes Helly's theorem.

Core claim

For every real number c less than 1 and every pair of integers k at least 3 and t at least 1, there exist k-uniform hypergraphs whose largest cliques have size strictly larger than c times the number of vertices, yet the collection of all such largest cliques has piercing number strictly larger than t. No fixed positive density therefore guarantees that the maximum cliques of a uniform hypergraph can be hit by a bounded number of vertices.

What carries the argument

Explicit constructions of k-uniform hypergraphs that achieve arbitrarily high relative size for their maximum cliques while forcing arbitrarily high piercing numbers on exactly those cliques.

If this is right

  • The classical Hajnal piercing property for graphs has no direct analogue in uniform hypergraphs at any constant density threshold.
  • Piercing numbers for the family of maximum cliques can be made arbitrarily large while the relative clique size approaches 1.
  • Any attempt to bound the piercing number of maximum cliques in k-uniform hypergraphs must depend on k or on additional structural assumptions beyond clique density.
  • The geometric piercing problem introduced in the paper, which asks for bounds under Helly-type intersection conditions, remains open.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The constructions may imply that piercing number grows at least linearly with uniformity k when clique density is held close to 1.
  • One could test whether random k-uniform hypergraphs with suitable edge probabilities exhibit the same separation between clique density and piercing number.
  • The geometric variant may connect to questions about the Helly number needed to guarantee a bounded piercing set in families of convex sets with large common intersections.

Load-bearing premise

The explicit constructions must truly produce hypergraphs in which the maximum cliques are both larger than any given fraction below 1 of the vertex set and collectively require more than any given fixed number of piercing vertices.

What would settle it

For k=3, t=2 and c=0.9, compute or verify in one of the constructed hypergraphs whether the largest clique size exceeds 90 percent of vertices while the smallest set intersecting every largest clique has size at least 3.

read the original abstract

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\'alv\"olgyi, 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 exist $k$-uniform hypergraphs $G$ whose maximum clique size exceeds $c|V(G)|$, yet the family of maximum size cliques of $G$ cannot be pierced by $t$ vertices. This demonstrates that no universal constant threshold guarantees bounded piercing number for maximum cliques in uniform hypergraphs. We discuss further questions concerning the relationship between clique size and piercing maximum cliques in hypergraphs, and introduce a geometric variant of the problem using Helly's Theorem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper refutes the conjecture of Jung, Keszegh, Pálvölgyi, and Yuditsky that an analogue of Hajnal's 1965 theorem holds for k-uniform hypergraphs: namely, that there exists some constant c < 1 such that any k-uniform hypergraph whose maximum clique exceeds c|V| has its maximum cliques pierceable by a bounded number of vertices. Instead, the authors prove that for every c < 1, every k ≥ 3, and every t ≥ 1, there exist k-uniform hypergraphs G with maximum clique size > c|V(G)| whose family of maximum cliques has piercing number > t. The refutation is obtained via explicit combinatorial constructions; the paper also poses further questions on the clique-piercing relationship and introduces a geometric variant invoking Helly's theorem.

Significance. If the constructions are correct, the result is a strong, parameter-free refutation showing that no universal constant threshold can guarantee bounded piercing numbers for maximum cliques in uniform hypergraphs, in sharp contrast to the graph case. The explicit constructions, together with direct combinatorial arguments establishing both the clique-size lower bound (> c|V|) and the piercing-number lower bound (> t) for arbitrary c, k, and t, constitute a robust negative answer that advances extremal hypergraph theory and motivates new questions.

minor comments (2)
  1. Section 3 (construction): a small concrete example for k=3 and t=1 would improve readability of the general construction.
  2. Section 5 (geometric variant): the application of Helly's theorem would benefit from one fully worked numerical example.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work, the assessment of its significance, and the recommendation to accept the manuscript. We are pleased that the explicit constructions and the strong refutation of the conjecture were viewed favorably.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper refutes the cited conjecture via explicit combinatorial constructions of k-uniform hypergraphs. Direct arguments establish both the clique-size lower bound (>c|V|) and the piercing-number lower bound (>t) without any reduction to self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The overlapping authors on the refuted conjecture do not create circularity, as the result is a disproof rather than an assumption of the prior claim. The derivation chain is self-contained against external combinatorial verification.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions of uniform hypergraphs, cliques, and piercing sets; no free parameters, new entities, or non-standard axioms are introduced in the abstract statement.

axioms (1)
  • standard math Standard definitions of k-uniform hypergraphs, cliques, and vertex piercing sets from combinatorial graph theory
    The entire claim is phrased in these classical terms without additional assumptions.

pith-pipeline@v0.9.0 · 5522 in / 1204 out tokens · 37443 ms · 2026-05-09T21:33:59.360333+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages

  1. [1]

    Intersection of Maximum Cliques , year =

    D\"om\"ot\"or P. Intersection of Maximum Cliques , year =

    work page

  2. [2]

    Canadian Journal of Mathematics , volume=

    A theorem on k-saturated graphs , author=. Canadian Journal of Mathematics , volume=. 1965 , publisher=

    work page 1965

  3. [3]

    The exact bound in the Erd

    Wilson, Richard M , journal=. The exact bound in the Erd. 1984 , publisher=

    work page 1984

  4. [4]

    Israel Journal of Mathematics , volume=

    Intersection patterns of convex sets , author=. Israel Journal of Mathematics , volume=. 1984 , publisher=

    work page 1984

  5. [5]

    2021 , issn =

    Note on sunflowers , journal =. 2021 , issn =. doi:https://doi.org/10.1016/j.disc.2021.112367 , url =

    work page doi:10.1016/j.disc.2021.112367 2021

  6. [6]

    1974 , issn =

    On finite -systems , journal =. 1974 , issn =. doi:https://doi.org/10.1016/0012-365X(74)90103-4 , url =

    work page doi:10.1016/0012-365x(74)90103-4 1974

  7. [7]

    Journal of the London Mathematical Society , volume=

    Intersection theorems for systems of sets , author=. Journal of the London Mathematical Society , volume=. 1960 , publisher=

    work page 1960

  8. [8]

    Discrete & Computational Geometry , volume=

    Nerve complexes of circular arcs , author=. Discrete & Computational Geometry , volume=. 2016 , publisher=

    work page 2016