Sharp bounds for uniform union-free hypergraphs

Chenyang Zhang; Chong Shangguan; Miao Liu

arxiv: 2605.11949 · v2 · submitted 2026-05-12 · 🧮 math.CO

Sharp bounds for uniform union-free hypergraphs

Miao Liu , Chong Shangguan , Chenyang Zhang This is my paper

Pith reviewed 2026-05-14 20:54 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C65

keywords union-free hypergraphsextremal hypergraph theoryhypergraph packingsasymptotic boundscombinatorial coding theorygroup testing

0 comments

The pith

The asymptotic maximum edge count in t-union-free r-uniform hypergraphs is now determined 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.

A t-union-free r-uniform hypergraph on n vertices requires that the unions of any two distinct collections of at most t edges are all different. U_t(n,r) measures the largest possible number of edges in such a hypergraph. The paper shows that this quantity follows a specific asymptotic formula, correct except for lower-order terms, across nearly every pair of integers t greater than or equal to 3 and r greater than or equal to 3. Prior work had settled only the special cases where t equals 2 and r equals 3 or 4. The argument rests on proving the existence of near-optimal locally sparse induced hypergraph packings.

Core claim

We determine the asymptotic behavior of U_t(n,r), up to a lower order term, for almost all t≥3 and r≥3. This is achieved by establishing the existence of near-optimal locally sparse induced hypergraph packings as the key ingredient.

What carries the argument

near-optimal locally sparse induced hypergraph packings, which serve as the extremal constructions that match the upper bounds on the size of t-union-free hypergraphs

If this is right

The union-free property now yields tighter maximum code sizes in the coding-theory setting introduced by Kautz and Singleton.
Group-testing schemes obtain improved identification bounds from the new values of U_t(n,r).
The classical extremal results of Bollobás-Erdős and Hwang-Sós extend to higher uniformity parameters.
Locally sparse induced packings of this form become available as tools for other forbidden-subconfiguration problems.

Where Pith is reading between the lines

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

The same packing technique may yield asymptotics for union-free hypergraphs under relaxed uniformity or intersection conditions.
Small-n computational enumeration could check whether the asymptotic formula holds exactly for the first few unsettled pairs t and r.
These constructions suggest a route to analogous results for union-closed families or other set-system extremal functions.

Load-bearing premise

The existence of near-optimal locally sparse induced hypergraph packings whose density is high enough to saturate the upper bound.

What would settle it

An explicit t-union-free r-uniform hypergraph on n vertices whose edge count exceeds the claimed asymptotic upper bound for some fixed t and r at least 3, or a proof that no such packing can reach the required density.

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.

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.

Desk Editor's Note private letter to a colleague

This paper settles the asymptotic order of U_t(n,r) for almost all t,r >=3 via a new packing construction, but the lower bound hinges on verifying that construction reaches the target density.

read the letter

The punchline is that they give the first asymptotic determination of the maximum edges in a t-union-free r-uniform hypergraph for the generic range t>=3 and r>=3. Only the two small cases t=2 with r=3 or 4 were known before, so this covers the bulk of the parameter space and ties together results from coding theory, extremal combinatorics, and group testing. The upper bound looks standard from the abstract, and the advance comes from matching it with a lower bound built on near-optimal locally sparse induced packings. That construction is presented as the main new ingredient and of independent interest. The paper does a clean job stating the result up to lower-order terms and situating it against the classical references like Kautz-Singleton and Bollobas-Erdos. The soft spot is exactly where the stress test points: the lower bound requires the packings to be both dense enough and locally sparse uniformly across the relevant t and r. If the construction only gets within a constant factor or loses the sparsity condition on small sets, the asymptotics would not match. Since the full proof is in the manuscript, the question is whether the error terms and the packing lemma are handled tightly enough to close the gap without extra logarithmic losses. Minor issues like citation density or notation are not a problem here. This is for readers already working in union-free or separating systems; someone outside the area will need the background but can still extract the main theorem. It is worth sending to a serious referee because the claim is precise, the prior gap was real, and the packing technique may have other uses even if small adjustments are needed.

Referee Report

2 major / 2 minor

Summary. The paper determines the asymptotic behavior of U_t(n,r), the maximum number of edges in an n-vertex t-union-free r-uniform hypergraph, up to a lower-order term, for almost all t ≥ 3 and r ≥ 3. This is achieved by establishing matching upper and lower bounds, with the key new ingredient being the existence of near-optimal locally sparse induced hypergraph packings.

Significance. If the result holds, it constitutes a substantial advance in extremal combinatorics for union-free hypergraphs, extending the previously known asymptotics (only for U_2(n,3) and U_2(n,4)) to almost all parameters t,r ≥ 3. The construction of locally sparse packings is of independent interest and may apply to other packing and extremal problems in hypergraph theory.

major comments (2)

[§3] §3 (Construction of packings): The lower bound on U_t(n,r) relies on the packings achieving density (1-o(1)) times the target extremal density with local sparsity holding uniformly for all induced subhypergraphs on at most t vertices. The error-term analysis must be checked to confirm the o(1) term is small enough to close the gap with the upper bound for the full range of almost all t,r ≥ 3.
[§4] §4 (Upper bound proof): The upper bound argument uses the packing lemma to control the number of edges; it is not clear from the write-up whether the local sparsity condition is preserved under the random sampling or deletion steps used to obtain the induced packing, which could affect the constant factors in the asymptotic.

minor comments (2)

[Definition 1.1] Notation for the union-free condition in Definition 1.1 could be clarified by explicitly stating whether the subsets of edges are required to be of size exactly t or at most t.
[Figure 1] Figure 1 (packing illustration) has overlapping labels that reduce readability; consider separating the vertex sets more clearly.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and the detailed comments on Sections 3 and 4. We have carefully reviewed the concerns regarding the error terms in the lower bound construction and the preservation of local sparsity in the upper bound proof. Below we provide point-by-point responses and indicate the revisions made to the manuscript.

read point-by-point responses

Referee: [§3] §3 (Construction of packings): The lower bound on U_t(n,r) relies on the packings achieving density (1-o(1)) times the target extremal density with local sparsity holding uniformly for all induced subhypergraphs on at most t vertices. The error-term analysis must be checked to confirm the o(1) term is small enough to close the gap with the upper bound for the full range of almost all t,r ≥ 3.

Authors: We appreciate the referee's attention to the error-term analysis. In our construction of the near-optimal locally sparse induced hypergraph packings, we employ a random greedy algorithm where the density is (1 - o(1)) times the target, and the local sparsity condition is enforced uniformly over all potential induced subhypergraphs on at most t vertices by bounding the failure probabilities using Chernoff bounds and union bounds over the relevant range. We have added an expanded subsection in §3 detailing the calculations, which confirm that for almost all t, r ≥ 3 (specifically, when log t = o(log n / log log n) or similar regimes implicit in the 'almost all' statement), the o(1) term is sufficiently small to match the upper bound up to lower-order terms. This verification ensures the asymptotic determination holds. revision: yes
Referee: [§4] §4 (Upper bound proof): The upper bound argument uses the packing lemma to control the number of edges; it is not clear from the write-up whether the local sparsity condition is preserved under the random sampling or deletion steps used to obtain the induced packing, which could affect the constant factors in the asymptotic.

Authors: Thank you for pointing out this potential ambiguity in the write-up. The packing lemma is applied after a random sampling step with deletion probability chosen to be o(1), and we argue that the local sparsity is preserved because any induced subhypergraph on t vertices in the sampled version inherits the sparsity from the original packing with high probability, up to a multiplicative (1 - o(1)) factor. We have revised §4 to include a new auxiliary lemma (Lemma 4.3) that rigorously shows the preservation under these operations, ensuring that the constant factors in the asymptotic remain unaffected. The upper bound thus matches the lower bound as claimed. revision: yes

Circularity Check

0 steps flagged

No significant circularity; asymptotics derived from independent packing existence result

full rationale

The paper claims to determine the asymptotic behavior of U_t(n,r) up to lower-order terms for almost all t,r ≥ 3 by proving matching upper and lower bounds. The lower bound rests on a new construction establishing existence of near-optimal locally sparse induced hypergraph packings, presented explicitly as a key ingredient of independent interest. No equations, self-definitions, fitted parameters renamed as predictions, or self-citation chains are visible that would reduce the claimed asymptotics to tautological inputs by construction. The derivation chain is self-contained against external benchmarks, with the packing result serving as genuine new content rather than a renaming or imported uniqueness theorem from the authors' prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no free parameters, axioms, or invented entities are specified or quantified in the provided text.

pith-pipeline@v0.9.0 · 5500 in / 1078 out tokens · 30632 ms · 2026-05-14T20:54:22.953700+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat recovery and embed_injective unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

we establish the existence of near-optimal locally sparse induced hypergraph packings... Lemma 3.1... C-free matching M ⊆ H

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

45 extracted references · 45 canonical work pages · 1 internal anchor

[1]

N. Alon, P. Frankl, H. Huang, V. R¨ odl, A. Ruci´ nski, and B. Sudakov. Large matchings in uniform hyper- graphs and the conjectures of erd˝ os and samuels.J. Combin. Theory Ser. A, 119(6):1200–1215, 2012

work page 2012
[2]

W. G. Brown. On graphs that do not contain a thomsen graph.Can. Math. Bull., 9(3):281–285, 1966

work page 1966
[3]

Delcourt and L

M. Delcourt and L. Postle. Finding an almost perfect matching in a hypergraph avoiding forbidden sub- matchings.arXiv:2204.08981, 2022

work page arXiv 2022
[4]

Delcourt and L

M. Delcourt and L. Postle. The limit in the (k+ 2, k)-problem of Brown, Erd˝ os and S´ os exists for allk≥2. Proc. Amer. Math. Soc., 152(5):1881–1891, 2024

work page 2024
[5]

A. G. D’yachkov, I.V. Vorobyev, N.A. Polyanskii, and V.Yu. Shchukin. Bounds on the rate of superimposed codes. In2014 IEEE Int. Symp. Inf. Theory, pages 2341–2345, 2014

work page 2014
[6]

P. Erd˝ os. Some recent progress on extremal problems in graph theory. InProc. Sixth SE Conf. Comb. Graph Theory Comput, volume No. XIV ofCongress. Numer., pages 3–14. Utilitas Math., Winnipeg, MB, 1975

work page 1975
[7]

P. Erd˝ os. Problems and results in combinatorial analysis. InProc. Eighth SE Conf. Comb. Graph Theory Comput., volume XIX ofCongressus Numerantium, pages 3–12. Utilitas Mathematica, 1977

work page 1977
[8]

Erd˝ os and T

P. Erd˝ os and T. Gallai. On maximal paths and circuits of graphs.Aeta Math. Acad. Sci. Hung, 10:337–356, 1959

work page 1959
[9]

Erd˝ os, C

P. Erd˝ os, C. Ko, and R. Rado. Intersection theorems for systems of finite sets.Quart. J. Math. Oxford, 12(2):313–320, 1961

work page 1961
[10]

Erd˝ os, A

P. Erd˝ os, A. R´ enyi, and V. T. S´ os. On a problem of graph theory.Studia Sci. Math. Hungar, 1(4):215–235, 1966

work page 1966
[11]

P. Erd˝ os. A problem on independentr-tuples.Ann. Univ. Sci. Budapest. E¨ otv¨ os Sect. Math, 8(93-95):2, 1965

work page 1965
[12]

Erd˝ os, P

P. Erd˝ os, P. Frankl, and Z. F¨ uredi. Families of finite sets in which no set is covered by the union of two others.J. Combin. Theory Ser. A, 33(2):158–166, 1982

work page 1982
[13]

Erd˝ os, P

P. Erd˝ os, P. Frankl, and Z. F¨ uredi. Families of finite sets in which no set is covered by the union ofrothers. Israel J. Math., 51(1-2):79–89, 1985

work page 1985
[14]

P. Frankl. Improved bounds for Erd˝ os’ matching conjecture.J. Combin. Theory Ser. A, 120(5):1068–1072, 2013

work page 2013
[15]

P. Frankl. On the maximum number of edges in a hypergraph with given matching number.Discrete Appl. Math., 216:562–581, 2017

work page 2017
[16]

P. Frankl. Proof of the Erd˝ os matching conjecture in a new range.Isr. J. Math., 222:421–430, 2017

work page 2017
[17]

Frankl and Z

P. Frankl and Z. F¨ uredi. Union-free families of sets and equations over fields.J. Number Theory, 23(2):210– 218, 1986

work page 1986
[18]

Frankl and Z

P. Frankl and Z. F¨ uredi. Colored packing of sets. InCombinatorial design theory, volume 149 ofNorth- Holland Math. Stud., pages 165–177. North-Holland, Amsterdam, 1987

work page 1987
[19]

Frankl and Z

P. Frankl and Z. F¨ uredi. A new extremal property of Steiner triple-systems.Discrete Math., 48(2):205–212, 1984

work page 1984
[20]

Frankl and A

P. Frankl and A. Kupavskii. The Erd˝ os matching conjecture and concentration inequalities.J. Combin. Theory Ser. B, 157:366–400, 2022. 13

work page 2022
[21]

Frankl and V

P. Frankl and V. R¨ odl. Near perfect coverings in graphs and hypergraphs.European J. Combin., 6(4):317– 326, 1985

work page 1985
[22]

F¨ uredi and M

Z. F¨ uredi and M. Ruszink´ o. Uniform hypergraphs containing no grids.Adv. Math., 240:302–324, 2013

work page 2013
[23]

Glock, F

S. Glock, F. Joos, J. Kim, M. K¨ uhn, and L. Lichev. Conflict-free hypergraph matchings.J. Lond. Math. Soc., 109(5):e12899, 2024

work page 2024
[24]

Glock, F

S. Glock, F. Joos, J. Kim, M. K¨ uhn, L. Lichev, and O. Pikhurko. On the (6, 4)-problem of Brown, Erd˝ os, and S´ os.Proc. Am. Math. Soc. Ser. B, 11(17):173–186, 2024

work page 2024
[25]

Glock, J

S. Glock, J. Kim, L. Lichev, O. Pikhurko, and S. Sun. On the (k+ 2, k)-problem of Brown, Erd˝ os and S´ os fork= 5,6,7.arXiv preprint arXiv:2403.04474, 2024

work page arXiv 2024
[26]

Improved Probabilistic Lower Bounds for Separable Matrices

D. Goshkoder, N. Polyanskii, and I. Vorobyev. Efficient combinatorial group testing: Bridging the gap between union-free and disjunctive codes.arXiv preprint arXiv:2401.16540, 2024

work page internal anchor Pith review Pith/arXiv arXiv 2024
[27]

F. K. Hwang and V. T. S´ os. Non-adaptive hypergeometric group testing.Studia Sci. Math. Hungar, 22(1- 4):257–263, 1987

work page 1987
[28]

T. B. Idalino and L. Moura. A survey of cover-free families: constructions, applications, and generalizations. InInternational Conference on New Advances in Designs, Codes and Cryptography, pages 195–239. Springer, 2022

work page 2022
[29]

Katona, T

G. Katona, T. Nemetz, and M. Simonovits. On a problem of Tur´ an in the theory of graphs.Mat. Lapok, 15:228–238, 1964

work page 1964
[30]

Kautz and R

W. Kautz and R. Singleton. Nonrandom binary superimposed codes.IEEE Trans. Inform. Theory, 10(4):363–377, 1964

work page 1964
[31]

D. J. Kleitman. Maximal number of subsets of a finite set nokof which are pairwise disjoint.Journal of Combinatorial Theory, 5(2):157–163, 1968

work page 1968
[32]

Kolupaev and A

D. Kolupaev and A. Kupavskii. Erd˝ os matching conjecture for almost perfect matchings.Discrete Math, 346(4):113304, 2023

work page 2023
[33]

Kov´ ari, V

T. Kov´ ari, V. S´ os, and P. Tur´ an. On a problem of K. Zarankiewicz. InColloq. Math., volume 3, pages 50–57. Polska Akademia Nauk. Instytut Matematyczny PAN, 1954

work page 1954
[34]

Letzter and A

S. Letzter and A. Sgueglia. On a problem of Brown, Erd˝ os and S´ os.arXiv e-prints, pages arXiv–2312, 2023

work page 2023
[35]

Ma and T

J. Ma and T. Yang. On extremal numbers of the triangle plus the four-cycle.Forum Math. Sigma, 13:e154, 2025

work page 2025
[36]

W. Mantel. Problem 28 (solution by h. gouwentak, w. mantel, j. teixeira de mattes, f. schuh and w. a. wythoff).Wiskundige Opgaven, 10:60–61, 1907

work page 1907
[37]

R. R. Martin and B. Patk´ os. A Note on the Erd˝ os Matching Conjecture.Studia Sci. Math. Hungar., 62(1):63–69, 2025

work page 2025
[38]

Pikhurko and S

O. Pikhurko and S. Sun. On the quadratic 8-edge case of the Brown-Erd˝ o-S´ os problem.arXiv preprint arXiv:2506.01739, 2025

work page arXiv 2025
[39]

Pippenger and J

N. Pippenger and J. Spencer. Asymptotic behavior of the chromatic index for hypergraphs.J. Combin. Theory Ser. A, 51(1):24–42, 1989

work page 1989
[40]

I. Reiman. ¨Uber ein problem von K. Zarankiewicz.Acta. Math. Hung., 9(3-4):269–273, 1958

work page 1958
[41]

V. R¨ odl. On a packing and covering problem.European J. Combin., 6(1):69–78, 1985. 14

work page 1985
[42]

Shangguan and I

C. Shangguan and I. Tamo. New Tur´ an exponents for two extremal hypergraph problems.SIAM J. Discrete Math., 34(4):2338–2345, 2020

work page 2020
[43]

Shangguan and I

C. Shangguan and I. Tamo. Sparse hypergraphs with applications to coding theory.SIAM J. Discrete Math., 34(3):1493–1504, 2020

work page 2020
[44]

Vorobyev

I. Vorobyev. Fast decoding of union-free codes. In2021 XVII International Symposium ”Problems of Redundancy in Information and Control Systems” (REDUNDANCY), pages 106–109, 2021

work page 2021
[45]

Y. Zhao. Probabilistic methods in combinatorics.Draft available at https://yufeizhao.com/pm/, 2022. A Proof of Theorem 1.1,1≤a≤t−1 This section proves the lower bound onU t+1(n, tk−a) for 1≤a≤t−1 stated in Theorem 1.1. Let t≥2,k≥2, and 1≤a≤t−1 be fixed integers. It suffices to prove that, apart from the cases U3(n,2k−1),U t+1(n, t+ 1),U t+1(n, t+ 2), andU...

work page 2022

[1] [1]

N. Alon, P. Frankl, H. Huang, V. R¨ odl, A. Ruci´ nski, and B. Sudakov. Large matchings in uniform hyper- graphs and the conjectures of erd˝ os and samuels.J. Combin. Theory Ser. A, 119(6):1200–1215, 2012

work page 2012

[2] [2]

W. G. Brown. On graphs that do not contain a thomsen graph.Can. Math. Bull., 9(3):281–285, 1966

work page 1966

[3] [3]

Delcourt and L

M. Delcourt and L. Postle. Finding an almost perfect matching in a hypergraph avoiding forbidden sub- matchings.arXiv:2204.08981, 2022

work page arXiv 2022

[4] [4]

Delcourt and L

M. Delcourt and L. Postle. The limit in the (k+ 2, k)-problem of Brown, Erd˝ os and S´ os exists for allk≥2. Proc. Amer. Math. Soc., 152(5):1881–1891, 2024

work page 2024

[5] [5]

A. G. D’yachkov, I.V. Vorobyev, N.A. Polyanskii, and V.Yu. Shchukin. Bounds on the rate of superimposed codes. In2014 IEEE Int. Symp. Inf. Theory, pages 2341–2345, 2014

work page 2014

[6] [6]

P. Erd˝ os. Some recent progress on extremal problems in graph theory. InProc. Sixth SE Conf. Comb. Graph Theory Comput, volume No. XIV ofCongress. Numer., pages 3–14. Utilitas Math., Winnipeg, MB, 1975

work page 1975

[7] [7]

P. Erd˝ os. Problems and results in combinatorial analysis. InProc. Eighth SE Conf. Comb. Graph Theory Comput., volume XIX ofCongressus Numerantium, pages 3–12. Utilitas Mathematica, 1977

work page 1977

[8] [8]

Erd˝ os and T

P. Erd˝ os and T. Gallai. On maximal paths and circuits of graphs.Aeta Math. Acad. Sci. Hung, 10:337–356, 1959

work page 1959

[9] [9]

Erd˝ os, C

P. Erd˝ os, C. Ko, and R. Rado. Intersection theorems for systems of finite sets.Quart. J. Math. Oxford, 12(2):313–320, 1961

work page 1961

[10] [10]

Erd˝ os, A

P. Erd˝ os, A. R´ enyi, and V. T. S´ os. On a problem of graph theory.Studia Sci. Math. Hungar, 1(4):215–235, 1966

work page 1966

[11] [11]

P. Erd˝ os. A problem on independentr-tuples.Ann. Univ. Sci. Budapest. E¨ otv¨ os Sect. Math, 8(93-95):2, 1965

work page 1965

[12] [12]

Erd˝ os, P

P. Erd˝ os, P. Frankl, and Z. F¨ uredi. Families of finite sets in which no set is covered by the union of two others.J. Combin. Theory Ser. A, 33(2):158–166, 1982

work page 1982

[13] [13]

Erd˝ os, P

P. Erd˝ os, P. Frankl, and Z. F¨ uredi. Families of finite sets in which no set is covered by the union ofrothers. Israel J. Math., 51(1-2):79–89, 1985

work page 1985

[14] [14]

P. Frankl. Improved bounds for Erd˝ os’ matching conjecture.J. Combin. Theory Ser. A, 120(5):1068–1072, 2013

work page 2013

[15] [15]

P. Frankl. On the maximum number of edges in a hypergraph with given matching number.Discrete Appl. Math., 216:562–581, 2017

work page 2017

[16] [16]

P. Frankl. Proof of the Erd˝ os matching conjecture in a new range.Isr. J. Math., 222:421–430, 2017

work page 2017

[17] [17]

Frankl and Z

P. Frankl and Z. F¨ uredi. Union-free families of sets and equations over fields.J. Number Theory, 23(2):210– 218, 1986

work page 1986

[18] [18]

Frankl and Z

P. Frankl and Z. F¨ uredi. Colored packing of sets. InCombinatorial design theory, volume 149 ofNorth- Holland Math. Stud., pages 165–177. North-Holland, Amsterdam, 1987

work page 1987

[19] [19]

Frankl and Z

P. Frankl and Z. F¨ uredi. A new extremal property of Steiner triple-systems.Discrete Math., 48(2):205–212, 1984

work page 1984

[20] [20]

Frankl and A

P. Frankl and A. Kupavskii. The Erd˝ os matching conjecture and concentration inequalities.J. Combin. Theory Ser. B, 157:366–400, 2022. 13

work page 2022

[21] [21]

Frankl and V

P. Frankl and V. R¨ odl. Near perfect coverings in graphs and hypergraphs.European J. Combin., 6(4):317– 326, 1985

work page 1985

[22] [22]

F¨ uredi and M

Z. F¨ uredi and M. Ruszink´ o. Uniform hypergraphs containing no grids.Adv. Math., 240:302–324, 2013

work page 2013

[23] [23]

Glock, F

S. Glock, F. Joos, J. Kim, M. K¨ uhn, and L. Lichev. Conflict-free hypergraph matchings.J. Lond. Math. Soc., 109(5):e12899, 2024

work page 2024

[24] [24]

Glock, F

S. Glock, F. Joos, J. Kim, M. K¨ uhn, L. Lichev, and O. Pikhurko. On the (6, 4)-problem of Brown, Erd˝ os, and S´ os.Proc. Am. Math. Soc. Ser. B, 11(17):173–186, 2024

work page 2024

[25] [25]

Glock, J

S. Glock, J. Kim, L. Lichev, O. Pikhurko, and S. Sun. On the (k+ 2, k)-problem of Brown, Erd˝ os and S´ os fork= 5,6,7.arXiv preprint arXiv:2403.04474, 2024

work page arXiv 2024

[26] [26]

Improved Probabilistic Lower Bounds for Separable Matrices

D. Goshkoder, N. Polyanskii, and I. Vorobyev. Efficient combinatorial group testing: Bridging the gap between union-free and disjunctive codes.arXiv preprint arXiv:2401.16540, 2024

work page internal anchor Pith review Pith/arXiv arXiv 2024

[27] [27]

F. K. Hwang and V. T. S´ os. Non-adaptive hypergeometric group testing.Studia Sci. Math. Hungar, 22(1- 4):257–263, 1987

work page 1987

[28] [28]

T. B. Idalino and L. Moura. A survey of cover-free families: constructions, applications, and generalizations. InInternational Conference on New Advances in Designs, Codes and Cryptography, pages 195–239. Springer, 2022

work page 2022

[29] [29]

Katona, T

G. Katona, T. Nemetz, and M. Simonovits. On a problem of Tur´ an in the theory of graphs.Mat. Lapok, 15:228–238, 1964

work page 1964

[30] [30]

Kautz and R

W. Kautz and R. Singleton. Nonrandom binary superimposed codes.IEEE Trans. Inform. Theory, 10(4):363–377, 1964

work page 1964

[31] [31]

D. J. Kleitman. Maximal number of subsets of a finite set nokof which are pairwise disjoint.Journal of Combinatorial Theory, 5(2):157–163, 1968

work page 1968

[32] [32]

Kolupaev and A

D. Kolupaev and A. Kupavskii. Erd˝ os matching conjecture for almost perfect matchings.Discrete Math, 346(4):113304, 2023

work page 2023

[33] [33]

Kov´ ari, V

T. Kov´ ari, V. S´ os, and P. Tur´ an. On a problem of K. Zarankiewicz. InColloq. Math., volume 3, pages 50–57. Polska Akademia Nauk. Instytut Matematyczny PAN, 1954

work page 1954

[34] [34]

Letzter and A

S. Letzter and A. Sgueglia. On a problem of Brown, Erd˝ os and S´ os.arXiv e-prints, pages arXiv–2312, 2023

work page 2023

[35] [35]

Ma and T

J. Ma and T. Yang. On extremal numbers of the triangle plus the four-cycle.Forum Math. Sigma, 13:e154, 2025

work page 2025

[36] [36]

W. Mantel. Problem 28 (solution by h. gouwentak, w. mantel, j. teixeira de mattes, f. schuh and w. a. wythoff).Wiskundige Opgaven, 10:60–61, 1907

work page 1907

[37] [37]

R. R. Martin and B. Patk´ os. A Note on the Erd˝ os Matching Conjecture.Studia Sci. Math. Hungar., 62(1):63–69, 2025

work page 2025

[38] [38]

Pikhurko and S

O. Pikhurko and S. Sun. On the quadratic 8-edge case of the Brown-Erd˝ o-S´ os problem.arXiv preprint arXiv:2506.01739, 2025

work page arXiv 2025

[39] [39]

Pippenger and J

N. Pippenger and J. Spencer. Asymptotic behavior of the chromatic index for hypergraphs.J. Combin. Theory Ser. A, 51(1):24–42, 1989

work page 1989

[40] [40]

I. Reiman. ¨Uber ein problem von K. Zarankiewicz.Acta. Math. Hung., 9(3-4):269–273, 1958

work page 1958

[41] [41]

V. R¨ odl. On a packing and covering problem.European J. Combin., 6(1):69–78, 1985. 14

work page 1985

[42] [42]

Shangguan and I

C. Shangguan and I. Tamo. New Tur´ an exponents for two extremal hypergraph problems.SIAM J. Discrete Math., 34(4):2338–2345, 2020

work page 2020

[43] [43]

Shangguan and I

C. Shangguan and I. Tamo. Sparse hypergraphs with applications to coding theory.SIAM J. Discrete Math., 34(3):1493–1504, 2020

work page 2020

[44] [44]

Vorobyev

I. Vorobyev. Fast decoding of union-free codes. In2021 XVII International Symposium ”Problems of Redundancy in Information and Control Systems” (REDUNDANCY), pages 106–109, 2021

work page 2021

[45] [45]

Y. Zhao. Probabilistic methods in combinatorics.Draft available at https://yufeizhao.com/pm/, 2022. A Proof of Theorem 1.1,1≤a≤t−1 This section proves the lower bound onU t+1(n, tk−a) for 1≤a≤t−1 stated in Theorem 1.1. Let t≥2,k≥2, and 1≤a≤t−1 be fixed integers. It suffices to prove that, apart from the cases U3(n,2k−1),U t+1(n, t+ 1),U t+1(n, t+ 2), andU...

work page 2022