REVIEW 5 minor 59 references
A peeling-and-t-cover method determines the largest cross t-intersecting set families and their t-diversity for large n.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · grok-4.5
2026-07-12 03:19 UTC pith:LI3X4B4C
load-bearing objection Solid combinatorial paper that actually delivers the natural t≥2 max-min, product, and diversity extensions of the classical Hilton–Milner / Mörs–Füredi / Frankl results, with a usable fingerprint+t-cover method and explicit (if quadratic) n-thresholds.
A unified approach to cross-intersection problems with applications to Hilton--Milner type theorems and stability
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For k≥t+2≥4 and n larger than a quadratic threshold in k and t, every pair of cross t-intersecting k-uniform families with no common t-set satisfies min{|F|,|G|}≤ max{|A(n,k,t)|,|H(n,k,t)|}, with equality only for the classical Hilton–Milner pairs or the Ahlswede–Khachatrian family A(Z). Parallel statements hold for the product |F||G| and for the new t-diversity measure.
What carries the argument
The fingerprint iteration: starting from a maximal cross t-intersecting pair, one repeatedly replaces each family by a fingerprint of its minimal t-covers of successive sizes; the resulting layers are small by spread estimates, and the terminal fingerprint is simple enough that classical t-cover degree bounds finish the proof.
Load-bearing premise
All main theorems need n to grow at least quadratically with k (or linearly in (k-t) times a polynomial in t); the degree bounds fail once n drops below roughly (k-t)^{2}.
What would settle it
Exhibit, for some fixed t≥2 and infinitely many k, a pair of cross t-intersecting k-uniform families on n=O(kt) elements whose min-size strictly exceeds both |A(n,k,t)| and |H(n,k,t)|.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops a unified combinatorial framework for cross t-intersecting families, combining an iterative fingerprint algorithm (inspired by Kupavskii–Zakharov peeling) with the t-cover method. For k-subsets of [n] it proves, under explicit quadratic n-thresholds, a max-min theorem (Thm 1.5) generalizing Mörs–Füredi, a product Hilton–Milner theorem with equality characterization that improves Frankl–Wang (Thm 1.7), and several t-diversity stability results (Thms 1.10, 1.12, 1.14), the last of which gives a large-n form of a conjecture of Ellis–Keller–Lifshitz and a t-analogue of Frankl’s degree theorem. A product EKR statement for weakly (r,t)-spread families (Thm 1.3) is also obtained and applied to signed sets and k-partitions.
Significance. The work supplies the first systematic treatment of cross t-intersecting problems for t≥2 that yields both extremal sizes and structural characterizations, together with a natural t-diversity parameter that unifies several stability statements. The fingerprint algorithm is flexible enough to recover classical Hilton–Milner theorems as special cases and to produce new product and diversity results under fully explicit n-conditions. The proofs are self-contained combinatorial arguments; all binomial inequalities are derived rather than black-boxed, and equality cases are completely classified. The quadratic n-thresholds are a genuine limitation (already noted by the authors in §5.2), but they do not undermine the correctness of the theorems as stated.
minor comments (5)
- The n-thresholds appearing in Theorems 1.5, 1.7, 1.10 and 1.12 (the constants 30, 15, 18, 7, 10, …) are obtained by successive crude estimates; a short remark collecting the precise places where each constant is forced would help the reader track possible improvements.
- In the statement of Conjecture 1 the authors already note a minor slip in the printed formulation of Ellis–Keller–Lifshitz; it would be cleaner to restate the corrected form once and then refer only to that version.
- Lemma 3.5 lists three concrete pairs of 2-uniform families; a one-line verification that these pairs are indeed cross t-intersecting antichains of minimal t-covers would make the subsequent case analysis easier to follow.
- The applications in §5.1 (signed sets, k-partitions) are short and correct, but the precise range of q or n for which the classical EKR thresholds are improved could be highlighted more explicitly.
- A few typographical inconsistencies appear (e.g., “crosst-intersecting” versus “cross t-intersecting”, occasional missing spaces around “t-cover”). These are purely cosmetic.
Circularity Check
No circularity: pure combinatorial derivation from definitions of cross t-intersection, maximality and the fingerprint algorithm; extremal constructions are exhibited independently and proved optimal under explicit n-thresholds.
full rationale
The paper develops an iterative fingerprint algorithm (Section 2) that produces sequences of minimal t-covers from a maximal cross t-intersecting pair, then applies elementary union bounds, binomial estimates (Lemmas 3.1–3.2) and the classical t-cover degree bound (Lemma 3.3) to control the sizes of successive layers. All main theorems (1.5, 1.7, 1.10, 1.12, 1.14) are proved by exhaustive case analysis on the termination index N of the algorithm, comparing the resulting size or diversity bounds against the independently defined constructions A(Z), H(X,K,L) and L(X,U,V). Equality cases are characterized by forcing the fingerprints to coincide with those of the constructions. No parameter is fitted to data; no uniqueness theorem is imported from the authors’ prior work as a hidden premise; the self-citations (to their earlier t-cover paper on partitions) appear only as applications of the new Theorem 1.3. The quadratic n-thresholds are explicit hypotheses of the statements and are used transparently in the estimates; they do not create a definitional loop. The derivation is therefore self-contained and non-circular.
Axiom & Free-Parameter Ledger
free parameters (1)
- n-threshold constants (30, 15, 18, 7, 10, …) =
e.g. 30, 15, 18, 7, 10
axioms (4)
- standard math Classical Erdős–Ko–Rado theorem (Theorem 1.1) and Hilton–Milner / Ahlswede–Khachatrian non-trivial intersection theorems for the comparison constructions A and H.
- domain assumption A pair of cross t-intersecting families may be enlarged to a maximal pair without decreasing sizes or t-diversities.
- domain assumption Weak (r,t)-spreadness of the ambient family implies the degree bounds needed for the product EKR (Theorem 1.3).
- ad hoc to paper Lemma 3.3 (t-cover size bound) holds whenever n≥(k−t+1)(ℓ−t+1)+t.
invented entities (2)
-
fingerprint of a cross t-intersecting pair
no independent evidence
-
t-diversity γ_t(F)
no independent evidence
Cite this review
Pith. "Pith review of A unified approach to cross-intersection problems with applications to Hilton--Milner type theorems and stability." pith.science (2026). https://pith.science/paper/LI3X4B4C
@misc{pith2026260703315,
author = {Pith},
title = {Pith review of: A unified approach to cross-intersection problems with applications to Hilton--Milner type theorems and stability},
year = {2026},
howpublished = {\url{https://pith.science/paper/LI3X4B4C}},
note = {Machine review of arXiv:2607.03315}
}
read the original abstract
We develop a new approach to cross-intersection problems in extremal set theory. The method builds on the iterative procedure introduced by Kupavskii and Zakharov (2024) and the $t$-cover method. It provides a flexible framework for deriving extremal and stability results for cross $t$-intersecting families. Our approach applies to a variety of combinatorial objects. As an application, we prove a product version of the seminal Erd\H{o}s--Ko--Rado theorem for sufficiently spread set systems. Two families $\mathcal{F}$ and $\mathcal{G}$ of $k$-subsets of $[n]$ are called cross $t$-intersecting if $|F\cap G|\geq t$ for all $F\in\mathcal{F}$ and $G\in\mathcal{G}$. We determine the families maximizing $\min\{|\mathcal{F}|, |\mathcal{G}|\}$ for large $n$ and all $t\ge2$, generalizing results of M\"{o}rs (1985) and F\"{u}redi (1995) for cross $1$-intersecting families. We then determine the families maximizing $|\mathcal{F}||\mathcal{G}|$ under the condition $\max\{|\cap_{F\in\mathcal{F}}F|,|\cap_{G\in\mathcal{G}}G|\}<t$ for large $n$. This improves the bound obtained by Frankl and Wang (2024), and provides a characterization of extremal configurations. For a family $\mathcal{F}$ of subsets of $[n]$, we introduce its $t$-diversity $\gamma_t(\mathcal{F})$, defined as the minimum number of sets from $\mathcal{F}$ not containing a fixed $t$-subset. This serves as a natural generalization of the important notion of diversity for $t=1$. We obtain a stability result via $\gamma_t$, and determine the maximum of $\min\{\gamma_t(\mathcal{F}),\gamma_t(\mathcal{G})\}$ for cross $t$-intersecting families $\mathcal{F}$ and $\mathcal{G}$. These yield new results for $t$-intersecting families, including a stability theorem towards a conjecture of Ellis, Keller and Lifshitz (2019), which may also be regarded as a $t$-intersection version, for large $n$, of an influential theorem of Frankl (1987).
Figures
Reference graph
Works this paper leans on
-
[1]
Ahlswede and L.H
R. Ahlswede and L.H. Khachatrian, The complete nontrivial-intersection theorem for sys- tems of finite sets, J. Combin. Theory Ser. A 76 (1996) 121–138
1996
-
[2]
Ahlswede and L.H
R. Ahlswede and L.H. Khachatrian, The complete intersection theorem for systems of finite sets, European J. Combin. 18 (1997) 125–136
1997
-
[3]
Alweiss, S
R. Alweiss, S. Lovett, K. Wu, J. Zhang, Improved bounds for the sunflower lemma, Ann. of Math. 194 (3) (2021) 795–815
2021
-
[4]
Balogh and D
J. Balogh and D. Mubayi, A new short proof of a theorem of Ahlswede and Khachatrian, J. Combin. Theory Ser. A 115 (2008) 326–330
2008
-
[5]
Blokhuis, A
A. Blokhuis, A. Brouwer, A. Chowdhury, P. Frankl, T. Mussche, B. Patk´ os and T. Sz˝ onyi, A Hilton–Milner theorem for vector spaces, Electron. J. Combin. 17 (2010) #R71
2010
-
[6]
Bollob´ as and I
B. Bollob´ as and I. Leader, An Erd˝ os–Ko–Rado theorem for signed sets, Comput. Math. Appl. 34 (1997) 9–13
1997
-
[7]
Borg, Ont-intersecting families of signed sets and permutations, Discrete Math
P. Borg, Ont-intersecting families of signed sets and permutations, Discrete Math. 309 (2009) 3310–3317
2009
-
[8]
Borg and I
P. Borg and I. Leader, Multiple cross-intersecting families of signed sets, J. Combin. Theory Ser. A 117 (2010) 583–588
2010
-
[9]
M. Cao, B. Lv and K. Wang, The structure of large non-trivialt-intersecting families of finite sets, European J. Combin. 97 (2021) 103373
2021
-
[10]
M. Cao, M. Lu, B. Lv and K. Wang, Nearly extremal non-trivial crosst-intersecting families andr-wiset-intersecting families, European J. Combin. 120 (2024) 103958
2024
-
[11]
Deza and P
M. Deza and P. Frankl, The Erd˝ os–Ko–Rado theorem–22 years later, SIAM J. Algebraic Discrete Methods 4 (1983) 419–431
1983
-
[12]
Dinur and E
I. Dinur and E. Friedgut, Intersecting families are essentially contained in juntas, Combin. Probab. Comput. 18 (2009) 107–122
2009
-
[13]
Ellis, N
A. Ellis, N. Keller and N. Lifshitz, Stability versions of Erd˝ os–Ko–Rado type theorems via isoperimetry, J. Eur. Math. Soc. 21 (2019) 3857–3902
2019
-
[14]
Ellis, Intersection problems in extremal combinatorics: theorems, techniques and ques- tions old and new, in: Surveys in Combinatorics 2022, in: London Math
D. Ellis, Intersection problems in extremal combinatorics: theorems, techniques and ques- tions old and new, in: Surveys in Combinatorics 2022, in: London Math. Soc. Lecture Note Ser., vol. 481, Cambridge Univ. Press, Cambridge, 2022, pp. 115–173
2022
-
[15]
Ellis, N
D. Ellis, N. Keller and N. Lifshitz, Stability for the complete intersection theorem, and the forbidden intersection problem of Erd˝ os and S´ os, J. Eur. Math. Soc. 26 (2024) 1611–1654
2024
-
[16]
Erd˝ os, C
P. Erd˝ os, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxf. 2 (12) (1961) 313–320
1961
-
[17]
Erd˝ os and L.A
P.L. Erd˝ os and L.A. Sz´ ekely, Erd˝ os–Ko–Rado theorems of higher order, in: I. Alth¨ ofer, N. Cai, G. Dueck, L. Khachatrian, M.S. Pinsker, A. S´ ark¨ ozy, I. Wegener and Z. Zhang (Eds.), Numbers, Information and Complexity, Springer US, Boston, MA, 2000, 117–124
2000
-
[18]
Frankl, The Erd˝ os–Ko–Rado theorem is true forn=ckt, in: Combinatorics, Vol
P. Frankl, The Erd˝ os–Ko–Rado theorem is true forn=ckt, in: Combinatorics, Vol. I, Proc. Fifth Hungarian Colloq., Keszthely, 1976, in: Colloq. Math. Soc. J´ anos Bolyai, vol. 18, North-Holland, 1978, 365–375
1976
-
[19]
Frankl, On intersecting families of finite sets, J
P. Frankl, On intersecting families of finite sets, J. Combin. Theory Ser. A 24 (1978) 146– 161. 43
1978
-
[20]
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. Combin. Theory Ser. A 46 (1987) 252–263
1987
-
[21]
Frankl, The shifting technique in extremal set theory, in: Surveys in Combinatorics, in: London Math
P. Frankl, The shifting technique in extremal set theory, in: Surveys in Combinatorics, in: London Math. Soc. Lecture Note Ser., vol. 123, Cambridge Univ. Press, Cambridge, 1987, pp. 81–110
1987
-
[22]
Frankl, Antichains of fixed diameter, Moscow J
P. Frankl, Antichains of fixed diameter, Moscow J. Combin. Number Theory 7 (2017) 189– 219
2017
-
[23]
Frankl, Maximum degree and diversity in intersecting hypergraphs, J
P. Frankl, Maximum degree and diversity in intersecting hypergraphs, J. Combin. Theory Ser. B 144 (2020) 81–94
2020
-
[24]
Frankl and Z
P. Frankl and Z. F¨ uredi, Beyond the Erd˝ os–Ko–Rado theorem, J. Combin. Theory Ser. A 56 (1991) 182–194
1991
-
[25]
Frankl and A
P. Frankl and A. Kupavskii, Sharp results concerning disjoint cross-intersecting families, European J. Combin. 86 (2020) 103089
2020
-
[26]
Frankl and A
P. Frankl and A. Kupavskii, Diversity, J. Combin. Theory Ser. A 182 (2021) 105468
2021
-
[27]
P. Frankl and A. Kupavskii, The Hajnal and Rothschild problem, arXiv:2502.06699
-
[28]
Frankl and N
P. Frankl and N. Tokushige, Invitation to intersection problems for finite sets, J. Combin. Theory Ser. A 144 (2016) 157–211
2016
-
[29]
Frankl and N
P. Frankl and N. Tokushige, Extremal Problems for Finite Sets, American Mathematical Society, 2018
2018
-
[30]
Frankl and J
P. Frankl and J. Wang, A product version of the Hilton–Milner theorem, J. Combin. Theory Ser. A 200 (2023) 105791
2023
-
[31]
Frankl and J
P. Frankl and J. Wang, A product version of the Hilton–Milner–Frankl theorem, Sci. China Math. 67 (2024) 455–474
2024
-
[32]
Frankl and J
P. Frankl and J. Wang, Improved bounds on the maximum diversity of intersecting families, European J. Combin. 118 (2024) 103885
2024
-
[33]
P. Frankl and J. Wang, A product version of the Hilton–Milner theorem II, arXiv:2605.09246
-
[34]
F¨ uredi, Cross-intersecting families of finite sets, J
Z. F¨ uredi, Cross-intersecting families of finite sets, J. Combin. Theory Ser. A 72 (1995) 332–339
1995
-
[35]
Godsil and K
C. Godsil and K. Meagher, Erd˝ os–Ko–Rado Theorems: Algebraic Approaches, Cambridge University Press, 2015
2015
-
[36]
Hajnal and B
A. Hajnal and B. Rothschild, A generalization of the Erd˝ os–Ko–Rado theorem on finite set systems, J. Combin. Theory Ser. A 15 (1973), 359–362
1973
-
[37]
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
1976
-
[38]
Hilton, An intersection theorem for a collection of families of subsets of a finite set, J
A.J.W. Hilton, An intersection theorem for a collection of families of subsets of a finite set, J. Lond. Math. Soc. (2) 15 (1977) 369–376
1977
-
[39]
Hilton and E.C
A.J.W. Hilton and E.C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxf. 2 (18) (1967) 369–384
1967
-
[40]
Huang, Two extremal problems on intersecting families, European J
H. Huang, Two extremal problems on intersecting families, European J. Combin. 76 (2019) 1–9
2019
-
[41]
Keevash, Shadows and intersections: Stability and new proofs, Adv
P. Keevash, Shadows and intersections: Stability and new proofs, Adv. Math. 218 (2008) 1685–1703. 44
2008
-
[42]
Keevash and E
P. Keevash and E. Long, Stability for vertex isoperimetry in the cube, J. Combin. Theory Ser. B 145 (2020) 113–144
2020
-
[43]
P. Keevash, N. Lifshitz, E. Long and D. Minzer, Global hypercontractivity and its applica- tions, arXiv:2103.04604
-
[44]
Keevash, N
P. Keevash, N. Lifshitz, E. Long and D. Minzer, Forbidden intersections for codes, J. Lond. Math. Soc. (2) 108 (2023) 2037–2083
2023
-
[45]
Keevash, N
P. Keevash, N. Lifshitz, E. Long and D. Minzer, Hypercontractivity for global functions and sharp thresholds, J. Amer. Math. Soc. 37 (2024) 245–279
2024
-
[46]
N. Keller, A. Kupavskii, N. Lifshitz and O. Sheinfeld, A complete intersection theorem for large permutation groups, arXiv:2607.00318
-
[47]
Keller and N
N. Keller and N. Lifshitz, The junta method for hypergraphs and the Erd˝ os–Chv´ atal simplex conjecture, Adv. Math. 392 (2021) 107991
2021
-
[48]
Keller, D
N. Keller, D. Minzer, E. Long and O. Sheinfeld, Ont-intersecting families of permutations, Adv. Math. 445 (2024) 109650
2024
-
[49]
Kupavskii, Diversity of uniform intersecting families, European J
A. Kupavskii, Diversity of uniform intersecting families, European J. Combin. 74 (2018) 39–47
2018
-
[50]
Kupavskii, An almost completet-intersection theorem for permutations
A. Kupavskii, An almost completet-intersection theorem for permutations. arXiv:2405.07843
-
[51]
Kupavskii, Erd˝ os–Ko–Rado type results for partitions via spread approximations, Eu- ropean J
A. Kupavskii, Erd˝ os–Ko–Rado type results for partitions via spread approximations, Eu- ropean J. Combin. 132 (2026) 104288
2026
-
[52]
Kupavskii and D
A. Kupavskii and D. Zakharov, Regular bipartite graphs and intersecting families, J. Com- bin. Theory Ser. A 155 (2018) 180–189
2018
-
[53]
Kupavskii and D
A. Kupavskii and D. Zakharov, Spread approximations for forbidden intersections problems, Adv. Math. 445 (2024) 109653
2024
-
[54]
Lemons and C
N. Lemons and C. Palmer, The unbalance of set systems, Graphs Combin. 24 (2008) 361– 365
2008
-
[55]
M¨ ors, A generalization of a theorem of Kruskal, Graphs Combin
M. M¨ ors, A generalization of a theorem of Kruskal, Graphs Combin. 1 (N1) (1985) 167–183
1985
-
[56]
Saengrungkongka, extremalt-intersecting families of permutations for larget, arXiv:2605.26051
P. Saengrungkongka, extremalt-intersecting families of permutations for larget, arXiv:2605.26051
-
[57]
Wen and B
J. Wen and B. Lv, Erd˝ os–Ko–Rado theorem and Hilton–Milner type theorem fork- partitions, J. Combin. Theory Ser. A 223 (2026) 106219
2026
-
[58]
Wilson, The exact bound in the Erd˝ os–Ko–Rado theorem, Combinatorica 4 (1984) 247–257
R.M. Wilson, The exact bound in the Erd˝ os–Ko–Rado theorem, Combinatorica 4 (1984) 247–257
1984
-
[59]
T. Yao, B. Lv and K. Wang, Large non-trivialt-intersecting families of signed sets, Aus- tralas. J. Combin. 89 (2024) 32–48. 45
2024
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.