Pith.

Combinatorics · arXiv:2610.22021 v1 · submitted 15 Oct 2026 · 24 references

The asymptotic Erdős–Frankl–Füredi cover-free conjecture

Xinqi Huang, Hong Liu

The paper says

“In 1985, Erdős, Frankl and Füredi conjectured that the threshold T(r) for the existence of an r-cover-free family with more members than points satisfies T(r) = (1 + o(1))r2. We confirm this conjecture by proving T(r) ≥ r2 + r + 2 for every r ≥ 1.”

from the abstract

Pith says

Machine review · deepseek-v4-flash · 16 Oct 2026 · what was read was not recorded · not checked by a person

It can be wrong. Challenge this review or reply to it.

A genuine proof of the Erdős–Frankl–Füredi threshold conjecture, with a new pseudo-private pair technique; the proof is intricate and worth a careful referee, but I found no load-bearing flaw. This line is wrong

5 minor

How often objections from reviews like this one are right: not yet measured

Are you an author? What you can do.

Not checked: figures, code, what the 24 references say.

5 minor objections

The paper says, at §2, Claim 2.8, definition of J_i

Pith says: minor objection 1 of 5

As printed, J_i is defined as the set of vertex-pairs α with f_i(α)∈E(G'_i−z_i), without requiring α itself to be an edge of G'_i. Under this literal reading, P_i={α∈J_i: α∩L_i=∅} can contain pairs that are not edges of G(H_i); such pairs need not be non-private pairs of A, so P_i need not be a pseudo-private collection in the sense of Definition 2.4, and the later assertion that every pair in ∪_{A∈B} P_A is non-private would not follow.

more of objection 1

The intended definition is evidently J_i={α∈E(G'_i−z_i): f_i(α)∈E(G'_i−z_i)}; equation (2) and the estimates (3)–(5) are consistent with that reading. I therefore treat this as a local notational correction, but the authors should fix the definition and re-verify the surrounding paragraph.

The paper says, at §2, Lemma 2.6 display

Pith says: minor objection 2 of 5

The displayed lower bound in Lemma 2.6 is rendered ambiguously as r(r+1)+16 over 6, while the proof concludes with (r(r+1)+1)/6 and Lemma 2.5's derivation uses the same constant. The authors should ensure that every instance of this constant is the intended (r(r+1)+1)/6.

show 3 more

The paper says, at §2, Fact 2.3 proof

Pith says: minor objection 3 of 5

The proof of Fact 2.3(2) states that the members of F_A are nonempty; this deserves one sentence of justification, namely that B\A=∅ would give B⊆A and hence a cover of B by the single other member A, contradicting r-cover-freeness for r≥2.

The paper says, at §1, paragraph on earlier bounds

Pith says: minor objection 4 of 5

In the sentence quoting Shangguan and Ge's bound, the expression '0.86n^2' should be '0.86r^2'.

The paper says, at AI usage statement

Pith says: minor objection 5 of 5

The AI usage note refers to 'Theorem 2.6'; the theorem being discussed appears to be Lemma 2.6. This should be corrected for consistency.

How the review went

3 readings by deepseek-v4-flash · 16 Oct 2026

  1. Reader holds up confidence moderate
  2. Editor wrote the verdict above 14 s · 12,551 tokens read, 1,399 written
  3. Referee minor revision: 5 minor 11 min 47 s · 12,038 tokens read, 53,457 written

Not run on this paper: the skeptic, the simulated authors' defence.

Pith did not check this review's objections against the paper.

The review in full

The review in brief, machine-written

Short version: this looks like the real thing. The paper proves T(r) ≥ r² + r + 2 for every r, which, together with the affine-plane construction giving T(r) ≤ (1+o(1))r², settles the 1985 Erdős–Frankl–Füredi conjecture. The previous general lower bound was about 0.86r², so this is a substantial jump, not an incremental cleanup.

What is actually new is the method. The pseudo-private pair notion, the C₄-free auxiliary bipartite graph, and the component-level construction in Lemma 2.6 are not repackaged known tools. The paper also correctly notes that the frameproof-code thresholds follow directly from Theorem 1.2 via existing relations; that is a genuine corollary, not an overclaim.

I worked through the main steps the way the reader did: Fact 2.3, the double counting in Lemma 2.5, the decomposition in Lemma 2.6, inequality (6), and the final quadratic minimization. I agree there are no fitted parameters and no circularity. The only external load-bearing result is Stehlík's theorem, which is published and appears to be used in exactly the setting for which it is stated. The induction step in Fact 2.3(2) also checks out.

Soft spots: the proof is long and the local claims in Lemma 2.6 are delicate. The compensating-pair construction depends on the partition supplied by Stehlík's theorem, so that import is the natural place for a referee to focus. I did not machine-check the inequalities, and for a proof this intricate that would be the only way to get from moderate to high confidence. A minor point: the authors state in their concluding remarks that the stronger conjecture T(r) ≥ (r+1)² remains open, which is honest and should stay in the paper.

Who is this for? Extremal combinatorists and coding theorists working on cover-free families, superimposed codes, and frameproof codes. A coding theorist can use the threshold result directly; a combinatorialist will be interested in the pseudo-private pair method as a reusable technique.

My recommendation: send it to peer review. It deserves a serious referee, with the specific assignment of checking Lemma 2.6 and the application of Stehlík's theorem. I expect it to survive, but this is a proof that needs line-by-line verification, not a quick skim.

The referee's report

If correct, the paper resolves a 1985 conjecture of Erdős, Frankl and Füredi and improves the best general lower bound from roughly 0.86r^2 to the asymptotic truth. The proof is self-contained apart from the quoted Stehlík theorem, the constants are uniform for all r, and no fitted parameters or post hoc exclusions appear. The result also has immediate consequences for the frameproof-code thresholds studied in [11] and [24], as the paper explains. The finite version T(r)≥(r+1)^2 is not proved, so the paper does not claim sharpness of the affine-plane construction beyond the asymptotic regime. I checked the Stehlík application, the component decomposition, the C4-free double counting, and the final algebra; the line of argument is coherent and the cited theorem is used within its stated hypotheses.

Pith's reading of the paper (a machine's summary, not the authors')

An r-cover-free family is a collection of subsets of an n-element ground set with the property that no member is contained in the union of any r other members. The family of all singletons always has n members, so the interesting question is when a larger family can exist. The affine plane construction shows that for every r one can build such a family with more than n members once n is about r squared. Erdős, Frankl and Füredi conjectured in 1985 that this is the truth up to lower-order terms.

The paper proves the missing lower bound: if n is at most r squared plus r plus 2, an r-cover-free family on n points can never have more than n members. The proof argues by contradiction with a minimal counterexample. Each member has size between r+1 and 2r-1. The authors count pairs of points lying inside family members, with a pair called private when it belongs to exactly one member. If every member had the minimum possible number of private pairs, a simple count would contradict the assumed size of the ground set. The difficulty is that some members, called bad, have too few private pairs.

For bad members the paper selects additional non-private pairs, called pseudo-private, in a way that controls how often the same pair can be reused. A bipartite graph recording which bad members selected which pairs is C4-free, which gives the overlap bound needed to compensate the deficits. Inside each bad member, a structural theorem of Stehlík decomposes the ground set into two-element blocks and larger blocks, and a local counting argument produces the required pseudo-private pairs. Combining these pieces yields the theorem.

Core claim. Theorem 1.2: For every r >= 1, we have T(r) >= r^2 + r + 2. Since the affine-plane construction gives T(r) <= (1+o(1)) r^2, this confirms Conjecture 1.1, T(r) = (1+o(1)) r^2.

The premise it rests on. Lemma 2.2 imports Stehlík's theorem: for each connected critical down-set H_i with covering number t_i, deleting any maximum-degree vertex z_i leaves a partition of V_i minus z_i into t_i-1 members of H_i, each of size at least two. All of the local structure in Lemma 2.6, including the matching M_i, the sets U_i and W_i, and the bounds in Claims 2.7 and 2.8, is built on this partition. If the cited theorem does not apply to H_i as defined, or its statement is misread, the compensating pair count in Lemma 2.6 collapses.

Check this review

Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.

How often reviews like this one are right

Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.

How often objections from reviews like this one are right: not yet measured

Every value above, in the review's public record (JSON)

Reviews by people

This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

Abstract

In 1985, Erdős, Frankl and Füredi conjectured that the threshold T(r) for the existence of an r-cover-free family with more members than points satisfies T(r) = (1 + o(1))r2. We confirm this conjecture by proving T(r) ≥ r2 + r + 2 for every r ≥ 1.

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-10-16

The authors' main claim, as the classifier picked it out 1.00

“We confirm this conjecture by proving $T(r)\ge r^2+r+2$ for every $r\ge1$.”

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.05 · states limitation 0.08 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.98 · compares with prior results 0.49 · mentions code or data availability 0.01

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
In 1985, Erd{\H{o}}s, Frankl and F{\"u}redi conjectured that the threshold $T(r)$ for the existence of an $r$-cover-free family with more members than points satisfies $T(r)=(1+o(1))r^2$. background 1.00 0.03 0.04 speculative 0.74
We confirm this conjecture by proving $T(r)\ge r^2+r+2$ for every $r\ge1$. result 0.87 0.97 0.96 asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00

What was examined, and what was not

Sources read

  • arXiv listing abstract v1

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-16: 1 request, 2,373 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

Figures (2)
Figure 2 of the paper
Figure 2. 1: The local construction. Only selected edges are shown.

Showing 1 of the paper's 2 figures. Figures are the authors', reproduced from the paper.

References (24)
  1. [11] G. Ge, C. Shangguan, and X. Wang. Some intriguing upper bounds for separating hash families. Science China Mathematics, 62(2):269–282, 2019 on Pith
  2. [24] Y. Zhao and X. Zhang. Improved upper bounds for wide-sense frameproof codes.IEEE Transactions on Information Theory, 70(12):8636–8646, 2024. 9 on Pith
  3. [1] A. Z. Abdi and N. H. Bshouty. Lower bounds for cover-free families.The Electronic Journal of Combinatorics, 23(2):P2.45, 2016 on Pith
  4. [2] S. R. Blackburn. Frameproof codes.SIAM Journal on Discrete Mathematics, 16(3):499–510, 2003 on Pith
  5. [3] D. Boneh and J. Shaw. Collusion-secure fingerprinting for digital data.IEEE Transactions on Information Theory, 44(5):1897–1905, 1998. Earlier version in CRYPTO 1995 on Pith
  6. [4] N. H. Bshouty and A. Gabizon. Almost optimal cover-free families. InAlgorithms and Complexity (CIAC 2017), volume 10236 ofLecture Notes in Computer Science, pages 140–151. Springer, 2017 on Pith
  7. [5] T.-W. Chao, X. Huang, and H. Liu. Asymptotics of the Brown–Erd˝ os–S´ os problem at integer exponents.arXiv:2609.38115, 2026 on PithPith's reviewarXiv
  8. [6] H.-B. Chen and F. K. Hwang. Exploring the missing link among d-separable, d-separable and d-disjunct matrices.Discrete Applied Mathematics, 155(5):662–664, 2007 on Pith
  9. [7] A. G. D’yachkov and V. V. Rykov. A survey of superimposed code theory.Problems of Control and Information Theory, 12(4):229–242, 1983 on Pith
  10. [8] 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.Journal of Combinatorial Theory, Series A, 33(2):158–166, 1982 on Pith
  11. [9] P. Erd˝ os, P. Frankl, and Z. F¨ uredi. Families of finite sets in which no set is covered by the union ofrothers.Israel Journal of Mathematics, 51(1–2):79–89, 1985. 8 on Pith
  12. [10] Z. F¨ uredi. Onr-cover-free families.Journal of Combinatorial Theory, Series A, 73(1):172–173, 1996 on Pith
  13. [12] S. H. Huang and F. K. Hwang. When is individual testing optimal for nonadaptive group testing? SIAM Journal on Discrete Mathematics, 14(4):540–548, 2001 on Pith
  14. [13] T. B. Idalino and L. Moura. Embedding cover-free families and cryptographical applications. Advances in Mathematics of Communications, 13(4):629–643, 2019 on Pith
  15. [14] T. B. Idalino and L. Moura. A survey of cover-free families: Constructions, applications, and generalizations. In C. J. Colbourn and J. H. Dinitz, editors,New Advances in Designs, Codes and Cryptography, volume 86 ofFields Institute Communications, pages 195–239. Springer, 2024 on Pith
  16. [15] W. H. Kautz and R. C. Singleton. Nonrandom binary superimposed codes.IEEE Transactions on Information Theory, 10(4):363–377, 1964 on Pith
  17. [16] M. Liu, Z. Ma, and C. Shangguan. Near optimal probabilistic constructions of frameproof codes. IEEE Transactions on Information Theory, 71(6):4137–4144, 2025 on Pith
  18. [17] J. Pieprzyk, H. Wang, and C. Xing. Multiple-time signature schemes against adaptive chosen message attacks. In M. Matsui and R. J. Zuccherato, editors,Selected Areas in Cryptography (SAC 2003), volume 3006 ofLecture Notes in Computer Science, pages 88–100. Springer, 2004 on Pith
  19. [18] M. Ruszink´ o. On the upper bound of the size of ther-cover-free families.Journal of Combinatorial Theory, Series A, 66(2):302–310, 1994 on Pith
  20. [19] C. Shangguan and G. Ge. New bounds on the number of tests for disjunct matrices.IEEE Transactions on Information Theory, 62(12):7518–7521, 2016 on Pith
show 4 more
  1. [20] M. Stehl ´ ık. Minimal connectedτ -critical hypergraphs.Graphs and Combinatorics, 22(3):421–426, 2006 on Pith
  2. [21] D. R. Stinson, T. van Trung, and R. Wei. Secure frameproof codes, key distribution patterns, group testing algorithms and related structures.Journal of Statistical Planning and Inference, 86(2):595–617, 2000 on Pith
  3. [22] D. R. Stinson and R. Wei. Generalized cover-free families.Discrete Mathematics, 279(1–3):463– 477, 2004 on Pith
  4. [23] D. R. Stinson, R. Wei, and L. Zhu. Some new bounds for cover-free families.Journal of Combinatorial Theory, Series A, 90(2):224–234, 2000 on Pith
Cited by 1 Pith paper

Reviewed papers on Pith that cite this one. The full citation record

  1. A proof of the strong Erd\H{o}s--Frankl--F\"uredi cover-free conjecture math.CO · Oct 2026

Challenges and discussion

Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.

No comments yet.

Sign in to comment