arxiv: 2605.08603 · v1 · submitted 2026-05-09 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

Intersecting families with covering number three II

Jian Wang, Peter Frankl

Pith reviewed 2026-05-12 00:49 UTC · model grok-4.3

classification 🧮 math.CO

keywords intersecting familiescovering numberk-uniform hypergraphsextremal set theorysize boundsbinomial coefficients

0 comments

The pith

Any intersecting k-uniform family with covering number at least three has size at most a fixed binomial expression.

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

This paper proves the stated upper bound on the size of intersecting families of k-element subsets whose covering number is at least three, for the parameter ranges left open by earlier work. The bound takes the explicit form of a combination of five binomial coefficients plus a constant. A sympathetic reader cares because the result finishes the classification of the largest possible families that intersect pairwise yet cannot be hit by any two elements. If the argument holds, then the maximum size of such families is now known for every n and k in the natural range.

Core claim

For all remaining cases, every intersecting k-graph F with covering number at least three satisfies |F| ≤ binom(n-1,k-1) - binom(n-k,k-1) - binom(n-k-1,k-1) + binom(n-2k,k-1) + binom(n-k-2,k-3) + 3.

What carries the argument

Exhaustive case analysis that partitions all possible intersecting families with covering number at least three according to how their members intersect a small fixed set of ground elements.

If this is right

The same size bound now holds for every admissible pair n and k.
No intersecting family with covering number three can be larger than the constructions that meet the bound.
All extremal examples must obey the structural restrictions forced by the case analysis.

Where Pith is reading between the lines

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

The same case-division technique could be tested on families with covering number four or higher.
Direct computer enumeration for the smallest values of k would independently check whether any missed configuration exists.
The bound supplies a concrete limit that can be inserted into proofs about other properties of uniform intersecting families.

Load-bearing premise

Every possible intersecting family with covering number three falls into one of the enumerated cases examined in the proof.

What would settle it

An explicit intersecting k-uniform family with covering number three whose size exceeds the right-hand side of the inequality for some small value of k.

Figures

Figures reproduced from arXiv: 2605.08603 by Jian Wang, Peter Frankl.

**Figure 1.** Figure 1: The auxiliary graph G. Let I = P ∈ P(R): |F(P, [5])| > n − 6 k − 3 . Claim 5.2. G can be partitioned into 3 pairwise disjoint edges and a vertex P0 that is not in I. Proof. Since F(P, [5]), F(P ′ , [5]) are cross-intersecting for any P, P′ ∈ P(R) with P ∩P ′ = ∅, we infer that I is an independent set of G. Then there are two cases: (i) (1, 5) ∈ I / . Then G − (1, 5) is C6 which can be partitioned in… view at source ↗

read the original abstract

A family $\mathcal{F}\subset \binom{[n]}{k}$ is called intersecting if $F\cap F'\neq \emptyset$ for all $F,F'\in \mathcal{F}$. The covering number of a family $\mathcal{F}$ is defined as the minimum size of $T\subset [n]$ such that $T\cap F\neq \emptyset$ for all $F\in \mathcal{F}$. In 1980, the first author proved that for sufficiently large $n$, any intersecting $k$-graph $\mathcal{F}$ with covering number at least three, satisfies $|\mathcal{F}|\leq \binom{n-1}{k-1}-\binom{n-k}{k-1}-\binom{n-k-1}{k-1}+\binom{n-2k}{k-1}+\binom{n-k-2}{k-3}+3$. There was very little progress during more than forty years but recently (cf. \cite{FW25}) with a completely different approach we proved the same result for the full range $n\geq 2k$ and $k\geq 7$. In this short paper we prove the same inequality for all the remaining cases.

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

Frankl and Wang close the small-k cases for the intersecting families bound via manual case analysis on transversals.

read the letter

This note finishes the proof for the remaining small values of k in the size bound for intersecting k-uniform families with covering number at least 3. Frankl's 1980 result covered large n, their prior paper handled k at least 7, and this short piece takes care of the rest with a direct argument. The main contribution is completing the statement so the inequality now holds for all n at least 2k and all k. They do this by partitioning families according to the structure of minimal transversals and intersection patterns, then verifying the bound inside each part. That approach is straightforward and stays within standard combinatorial counting, which fits the problem well. The paper earns credit for delivering the full result without new machinery or asymptotic shortcuts. The soft spot is the hand case analysis itself. For k below 7 the numbers are small enough that exhaustive checking by hand is possible in principle, but the write-up is brief and does not include an explicit list of all cases or any independent verification. If a configuration with tau at least 3 falls outside the listed parts or if two cases overlap in a way that breaks the bound, the claim would not hold. A referee would need to trace the partition carefully to confirm it is complete and that the binomial calculations check out in every subcase. This work is for specialists in extremal set theory who already know the Erdős–Ko–Rado line and the covering-number variants. A reader following the literature on intersecting families will find it useful as the missing piece. It deserves a serious referee because the result closes a gap that has stood for over forty years and the argument is grounded in explicit combinatorial reasoning rather than fitting or circular definitions. I would send it to peer review.

Referee Report

2 major / 1 minor

Summary. This short paper proves the size bound |F| ≤ binom(n-1,k-1) - binom(n-k,k-1) - binom(n-k-1,k-1) + binom(n-2k,k-1) + binom(n-k-2,k-3) + 3 for intersecting k-uniform families F with covering number τ(F) ≥ 3, in the remaining cases n ≥ 2k and k < 7 (after prior work handled k ≥ 7). The proof proceeds by partitioning such families according to the structure of their minimal transversals and verifying the bound case-by-case.

Significance. If the case analysis is exhaustive, the result completes a 40-year-old problem in extremal set theory by establishing the stated bound for all k and n ≥ 2k. The direct combinatorial approach avoids parameter fitting and provides an explicit (if manual) classification for small k.

major comments (2)

[Main proof (case analysis for small k)] The central claim rests on the exhaustiveness of the manual partition of intersecting families with τ(F) ≥ 3 for k = 3,4,5,6. The proof must show that every possible configuration of minimal transversals and intersection patterns falls into one of the enumerated cases without overlap or omission; any missed family with |F| exceeding the bound would falsify the inequality for that k.
[Main proof (size calculations)] Verification of the binomial coefficient identities used to bound the size in each case is not independently checkable from the abstract or summary; explicit expansion or reference to a computer algebra check would strengthen the argument that the bound holds inside each part of the partition.

minor comments (1)

Notation for the ground set [n] and the family F is standard, but a brief reminder of the definition of covering number τ(F) at the start of the proof section would aid readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and positive evaluation of our manuscript, which completes the resolution of the 40-year-old problem for all k when n ≥ 2k. We address each major comment below with clarifications and proposed revisions.

read point-by-point responses

Referee: The central claim rests on the exhaustiveness of the manual partition of intersecting families with τ(F) ≥ 3 for k = 3,4,5,6. The proof must show that every possible configuration of minimal transversals and intersection patterns falls into one of the enumerated cases without overlap or omission; any missed family with |F| exceeding the bound would falsify the inequality for that k.

Authors: We appreciate the referee's emphasis on this foundational aspect of the proof. The case division in the manuscript is derived systematically from the possible minimal transversals of size exactly 3 (noting that τ(F) ≥ 3 precludes smaller transversals, and larger minimal transversals can be reduced or lead to contradictions with the intersecting property for small k). For each k < 7, we enumerate all admissible intersection patterns between these transversals and the members of F, based on the requirement that no 2-set covers F. These patterns are exhaustive by the finite nature of the ground set intersections for fixed k, and the cases are disjoint by assigning each family to the type of its smallest or canonical minimal transversal. To strengthen the presentation, we will insert a short preliminary subsection deriving the possible transversal structures from the definitions before the case analysis begins. revision: partial
Referee: Verification of the binomial coefficient identities used to bound the size in each case is not independently checkable from the abstract or summary; explicit expansion or reference to a computer algebra check would strengthen the argument that the bound holds inside each part of the partition.

Authors: We agree that greater transparency on the algebraic verifications would enhance the manuscript. In the revised version we will append explicit expansions of the binomial identities appearing in each case (all of which are routine applications of Pascal's identity and can be checked by hand in a few lines) or, where lengthy, include a note that they have been confirmed via a computer algebra system such as Mathematica. This addition will make the size bounds independently verifiable without altering the combinatorial arguments. revision: yes

Circularity Check

0 steps flagged

Direct combinatorial case analysis independent of prior results

full rationale

The paper states the result for k >= 7 via citation to prior work FW25 and then claims a separate proof for remaining small-k cases via explicit partitioning of intersecting families by minimal transversals and intersection patterns. No quantities are defined in terms of the target bound, no parameters are fitted to data, and the small-k argument does not invoke or reduce to the large-k result by any equation or self-citation chain. The self-citation serves only as background; the derivation for the claimed cases is self-contained within the present combinatorial verification.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on standard combinatorial definitions and case analysis with no new free parameters, axioms beyond basic set theory, or invented entities.

axioms (1)

standard math Standard definitions of intersecting family, covering number, and binomial coefficient identities.
These are invoked to state and prove the bound.

pith-pipeline@v0.9.0 · 5498 in / 1130 out tokens · 68220 ms · 2026-05-12T00:49:44.758796+00:00 · methodology

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/AbsoluteFloorClosure.lean absolute_floor_iff_bare_distinguishability unclear
Theorem 1.9. For k=4,5,6 and n≥2k, m(n,k,3)=|G(n,k)|. ... we may assume that T^(3)(F) contains either an isomorphic copy of S or an isomorphic copy of R.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
Proposition 3.2 ... f_P + f_P' ≤ ... +1 (Frankl-Tokushige inequality)

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

[1]

Erd˝ os, C

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

work page 1961
[2]

Infinite and Finite Sets,

P. Erd˝ os, L. Lov´ asz, Problems and results on 3-chromatic hypergraphs and some related questions, in “Infinite and Finite Sets,” Proc. Colloquium Math. Society Janos Bolyai, Vol. 10, (A. Hajnal et al., Eds.), pp. 609–627, North-Holland, Amsterdam, 1975

work page 1975
[3]

Frankl, On intersecting families of finite sets, Bull

P. Frankl, On intersecting families of finite sets, Bull. Austral. Math. Soc. 21 (3) (1980), 363–372

work page 1980
[4]

Frankl, Erd˝ os-Ko-Rado theorem with conditions on the maximal degree, J

P. Frankl, Erd˝ os-Ko-Rado theorem with conditions on the maximal degree, J. Comb. Theory, Ser. A 46(2) (1987), 252–263

work page 1987
[5]

Frankl, A near-exponential improvement of a bound of Erd˝ os and Lov´ asz on max- imal intersecting families, Combinatorics, Probability & Computing 28(5) (2019), 733–739

P. Frankl, A near-exponential improvement of a bound of Erd˝ os and Lov´ asz on max- imal intersecting families, Combinatorics, Probability & Computing 28(5) (2019), 733–739

work page 2019
[6]

Frankl, On the maximum of the sum of the sizes of non-trivial cross-intersecting families, Combinatorica 44 (2024), 15–35

P. Frankl, On the maximum of the sum of the sizes of non-trivial cross-intersecting families, Combinatorica 44 (2024), 15–35

work page 2024
[7]

Frankl, K

P. Frankl, K. Ota, N. Tokushige, Uniform intersecting families with covering number four, J. Comb. Theory, Ser. A 71 (1) (1995), 127–145

work page 1995
[8]

Frankl, N

P. Frankl, N. Tokushige, Some best possible inequalities concerning cross-intersecting families, J. Comb. Theory, Ser. A 61 (1992), 87–97

work page 1992
[9]

Frankl, J

P. Frankl, J. Wang, A product version of the Hilton-Milner Theorem, J. Comb. The- ory, Ser. A 200 (2023), 105791

work page 2023
[10]

Frankl, J

P. Frankl, J. Wang, Intersecting families with covering number three, J. Comb. The- ory, Ser. B 171 (2025), 96–139. 14

work page 2025
[11]

Frankl, J

P. Frankl, J. Wang, Intersecting families with covering number five, Discrete Math. 348(9) (2025), 114546

work page 2025
[12]

Frankl, J

P. Frankl, J. Wang, Intersectingk-graphs and pseudo sunflowers, to appear

work page
[13]

Furuya, M

M. Furuya, M. Takatou, Covers in 5-uniform intersecting families with covering num- ber three, Australas. J Comb. 55 (2013), 249–262

work page 2013
[14]

Hilton, The Erd˝ os-Ko-Rado Theorem with valency conditions, unpublished manuscript, 1976

A.J.W. Hilton, The Erd˝ os-Ko-Rado Theorem with valency conditions, unpublished manuscript, 1976

work page 1976
[15]

Hilton, E.C

A.J.W. Hilton, E.C. Milner, Some intersection theorems for systems of finite sets, Q. J. Math. 18 (1967), 369–384

work page 1967
[16]

Katona, A theorem of finite sets, Theory of Graphs

G.O.H. Katona, A theorem of finite sets, Theory of Graphs. Proc. Colloq. Tihany, Akad. Kiad´ o (1966), 187–207

work page 1966
[17]

Kruskal, The number of simplices in a complex, Mathematical Optimization Techniques 251 (1963), 251–278

J.B. Kruskal, The number of simplices in a complex, Mathematical Optimization Techniques 251 (1963), 251–278

work page 1963
[18]

Kupavskii, Intersecting families with covering number 3, J

A. Kupavskii, Intersecting families with covering number 3, J. Comb. Theory, Ser. B 177 (2026), 216–233

work page 2026
[19]

Lov´ asz, On minimax theorems of combinatorics, Math

L. Lov´ asz, On minimax theorems of combinatorics, Math. Lapok 26 (1975), 209–264

work page 1975
[20]

Sperner, Ein Satz ¨ uber Untermengen einer endlichen Menge, Math

E. Sperner, Ein Satz ¨ uber Untermengen einer endlichen Menge, Math. Zeitschrift 27 (1928), 544–548

work page 1928
[21]

Zakharov, On the size of maximal intersecting families, Combinatorics, Probability & Computing 33 (2024), 32–49

D. Zakharov, On the size of maximal intersecting families, Combinatorics, Probability & Computing 33 (2024), 32–49. 15

work page 2024