Recognition: 1 theorem link
· Lean TheoremSharp bounds for uniform union-free hypergraphs
Pith reviewed 2026-05-13 04:57 UTC · model grok-4.3
The pith
The maximum number of edges in an n-vertex t-union-free r-uniform hypergraph is determined asymptotically up to lower-order terms for almost all t and r at least 3.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Let U_t(n,r) denote the maximum number of edges in an n-vertex t-union-free r-uniform hypergraph. The paper shows that U_t(n,r) is determined asymptotically, up to a lower-order term, for almost all t greater than or equal to 3 and r greater than or equal to 3. The proof of the matching lower bound rests on the existence of near-optimal locally sparse induced hypergraph packings.
What carries the argument
The extremal function U_t(n,r) together with the auxiliary construction of near-optimal locally sparse induced hypergraph packings that supplies the lower bound.
If this is right
- The density of maximum t-union-free hypergraphs is now known to within lower-order fluctuations for most parameters.
- The same packing technique immediately yields constructions for related forbidden-union problems in uniform hypergraphs.
- Upper-bound methods developed here extend the earlier exact asymptotics known only for t equals 2.
- The locally sparse packings themselves become available as a reusable combinatorial object for other extremal questions.
Where Pith is reading between the lines
- The sharpened bounds can be substituted into coding-theory constructions to obtain families of codes with improved rate for union-free decoding.
- The packing existence result may transfer to hypergraph Turán problems that also require local sparsity.
- One could test the construction by computing explicit small-n examples for t=3, r=3 and comparing the observed edge count against the asymptotic formula.
Load-bearing premise
That near-optimal locally sparse induced hypergraph packings exist and can be used to build the claimed lower-bound constructions.
What would settle it
An explicit t-union-free r-uniform hypergraph on n vertices whose edge count exceeds the paper's predicted asymptotic expression by more than a lower-order term, for infinitely many n, would disprove the result.
read the original abstract
An $r$-uniform hypergraph is called $t$-union-free if any two distinct subsets of at most $t$ edges have distinct union. The study of union-free hypergraphs has multiple origins and a long history, dating back to the works of Kautz and Singleton (1964) in coding theory, Bollob\'as and Erd\H{o}s (1976) in combinatorics, and Hwang and S\'os (1987) in group testing. Let $U_t(n,r)$ denote the maximum number of edges in an $n$-vertex $t$-union-free $r$-uniform hypergraph. In this paper, we determine the asymptotic behavior of $U_t(n,r)$, up to a lower order term, for almost all $t\ge 3$ and $r\ge 3$. This significantly advances the understanding of this extremal function, as previously, only the asymptotics of $U_2(n,3)$ and $U_2(n,4)$ were known. As a key ingredient of our proof, we establish the existence of near-optimal locally sparse induced hypergraph packings, which is of independent interest.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript defines a t-union-free r-uniform hypergraph as one in which any two distinct collections of at most t edges have distinct unions. It introduces the extremal function U_t(n,r) as the maximum number of edges in an n-vertex example and claims to determine the asymptotic order of U_t(n,r) up to a lower-order term for almost all integers t ≥ 3 and r ≥ 3. The upper bound is derived from standard double-counting or deletion methods applied to unions of small edge sets; the matching lower bound is obtained by constructing near-optimal packings of induced subhypergraphs that remain t-union-free while satisfying local sparsity conditions (bounded codegrees on small vertex sets).
Significance. If correct, the result substantially extends the known asymptotics, which had previously been established only for the cases t=2 with r=3 and r=4. The auxiliary theorem establishing the existence of near-optimal locally sparse induced hypergraph packings is of independent interest and may find applications in other extremal packing problems in hypergraph theory and coding theory.
major comments (1)
- [Section 3 (packing construction)] The central lower-bound construction relies on the existence of near-optimal locally sparse induced packings that remain t-union-free. The manuscript must explicitly verify, for the stated density of almost all t,r, that the local sparsity condition (e.g., bounded codegrees) does not inadvertently create two distinct t-subsets with the same union; this verification is load-bearing for the matching asymptotic claim.
minor comments (3)
- [Abstract] The abstract states the result holds for 'almost all' t,r but does not quantify the exceptional set or the precise density of the main term; adding a brief explicit statement of the asymptotic formula (including the leading coefficient if known) would improve readability.
- [Section 1] Notation for the union operation and the precise definition of 'locally sparse' should be introduced once in Section 1 and used consistently thereafter to avoid ambiguity when the packing is invoked in the lower-bound argument.
- [Introduction] The historical references to Kautz-Singleton, Bollobás-Erdős, and Hwang-Sós are appropriate; confirm that the bibliography entries contain complete bibliographic data and that all cited works appear in the reference list.
Simulated Author's Rebuttal
We thank the referee for the careful reading, positive evaluation, and constructive comment. We address the major point below and will revise the manuscript accordingly.
read point-by-point responses
-
Referee: [Section 3 (packing construction)] The central lower-bound construction relies on the existence of near-optimal locally sparse induced packings that remain t-union-free. The manuscript must explicitly verify, for the stated density of almost all t,r, that the local sparsity condition (e.g., bounded codegrees) does not inadvertently create two distinct t-subsets with the same union; this verification is load-bearing for the matching asymptotic claim.
Authors: We agree that an explicit verification is necessary to make the argument fully transparent. In the current proof of the lower bound, the parameters for the locally sparse induced packings (in particular the bound on codegrees of small sets) are chosen strictly below the threshold that would allow two distinct t-collections to share the same union; this follows from a direct counting argument that mirrors the upper-bound deletion method and holds for the density regime of almost all t,r ≥ 3. We will add a short dedicated lemma (or expanded paragraph) in Section 3 that isolates this verification, including the precise inequality relating the codegree bound to the union-uniqueness condition. revision: yes
Circularity Check
No significant circularity; derivation self-contained
full rationale
The paper establishes matching upper and lower bounds on U_t(n,r) up to lower-order terms for most t,r ≥ 3. The upper bound relies on standard double-counting and deletion arguments applied to unions of edge sets. The lower bound is obtained by a new explicit construction of near-optimal locally sparse induced hypergraph packings that remain t-union-free; this auxiliary result is stated to be of independent interest and does not presuppose the target asymptotic. No equations reduce a claimed prediction to a fitted parameter by definition, no load-bearing step rests on a self-citation chain, and no ansatz or uniqueness theorem is imported from prior work by the same authors. The derivation is therefore independent of its own outputs.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.