Non-uniform pairwise cross t-intersecting families
Pith reviewed 2026-05-18 21:36 UTC · model grok-4.3
The pith
m non-empty pairwise cross t-intersecting families have total size at most the larger of the full collection of sets of size at least t plus m minus 1, or m times the size of a maximum single t-intersecting family.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Let n ≥ t ≥ 1. If A1, A2, …, Am are non-empty subsets of the power set of [n] that are pairwise cross t-intersecting, then the sum of their sizes is at most the maximum of sum_{k=t to n} binom(n,k) plus m minus 1 and m times M(n,t), where M(n,t) denotes the maximum size of a single non-uniform t-intersecting family. The paper supplies a complete characterization of all families attaining this bound.
What carries the argument
The explicit upper bound max{sum_{k=t}^n binom(n,k) + m - 1, m M(n,t)} together with the generating set method and pushing-pulling method used to prove it and classify the extremals.
If this is right
- When m equals 1 the bound collapses to the classical maximum size of a single non-uniform t-intersecting family.
- When m equals 2 the bound recovers the earlier theorem of Frankl and Wong on two cross t-intersecting families.
- The extremal constructions are either the collection of all sets of size at least t with one extra set added to each of m-1 of the families, or m identical copies of a maximum single t-intersecting family.
- The same bound and characterization apply uniformly for every m ≥ 1 and every n ≥ t.
Where Pith is reading between the lines
- The same methods may extend directly to families with unequal intersection thresholds between different pairs.
- Computer enumeration for small n and t can test whether any additional extremal families exist beyond those characterized.
- The bound supplies a concrete limit that could be used to estimate the combined size of multiple codes whose pairwise intersections satisfy a minimum distance condition.
- Weighted or measure-theoretic versions of the same statement might follow by replacing cardinality with a suitable weight function.
Load-bearing premise
The generating set method combined with the pushing-pulling method is enough to obtain both the stated upper bound and the full characterization for every positive integer m.
What would settle it
Exhibit m pairwise cross t-intersecting families whose sizes sum to more than the maximum of the two quantities in the bound, or produce a family that meets the bound but lies outside the listed extremal types.
read the original abstract
Let $ n\geqslant t\geqslant 1$ and $ \mathcal{A}_1, \mathcal{A}_2, \ldots, \mathcal{A}_m \subseteq 2^{[n]}$ be non-empty families. We say that they are pairwise cross $t$-intersecting if $|A_i\cap A_j|\geqslant t$ holds for any $A_i\in \mathcal{A}_i$ and $A_j\in \mathcal{A}_j$ with $i\neq j$. In the case where $m=2$ and $\mathcal{A}_1=\mathcal{A}_2$, determining the maximum size $M(n,t)$ of a non-uniform $t$-intersecting family of sets over $[n]$ was solved by Katona (1964), and enhanced by Frankl (2017), and recently by Li and Wu (2024). In this paper, we establish the following upper bound: if $ \mathcal{A}_1, \mathcal{A}_2, \ldots, \mathcal{A}_m \subseteq 2^{[n]}$ are non-empty pairwise cross $t$-intersecting families, then $$ \sum_{i=1}^m |\mathcal{A}_i| \leqslant \max \left\{ \sum_{k=t} ^{n}\binom{n}{k} + m - 1, \, m M(n, t) \right\}. $$ Furthermore, we provide a complete characterization of the extremal families that achieve the bound. Our result not only generalizes an old result of Katona (1964) for a single family, but also extends a theorem of Frankl and Wong (2021) for two families. Moreover, our result could be viewed as a non-uniform version of a recent theorem of Li and Zhang (2025). The key in our proof is to utilize the generating set method and the pushing-pulling method together.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that for n ≥ t ≥ 1 and m non-empty families A1, …, Am ⊆ 2^[n] that are pairwise cross t-intersecting, the sum of their sizes is at most max{ ∑_{k=t}^n binom(n,k) + m − 1, m M(n,t) }, where M(n,t) is the maximum size of a single non-uniform t-intersecting family. It also supplies a complete characterization of all families attaining this bound, obtained via the generating-set method followed by a pushing-pulling argument.
Significance. The result generalizes Katona’s 1964 theorem (m=1) and the Frankl–Wong 2021 theorem (m=2) while providing a non-uniform counterpart to the recent Li–Zhang 2025 uniform result. The proof techniques handle arbitrary m without hidden restrictions on n or t, and the exhaustive equality-case analysis confirms the two extremal constructions (one large family plus m−1 singletons, and m copies of a maximum t-intersecting family) are the only ones that achieve the bound.
minor comments (2)
- [Theorem statement] In the statement of the main theorem (presumably Theorem 1.1 or 2.1), the two quantities inside the max should be labeled explicitly for quick reference when the characterization is discussed later.
- [Section on extremal families] A short table or diagram illustrating the two extremal constructions for small values (e.g., n=4, t=2, m=3) would improve readability of the equality-case analysis.
Simulated Author's Rebuttal
We thank the referee for their positive assessment of the manuscript, accurate summary of the main result, and recommendation to accept. The report correctly identifies the generalization of Katona's theorem for m=1, the Frankl-Wong result for m=2, and the connection to the uniform Li-Zhang theorem.
Circularity Check
No significant circularity; derivation relies on standard external methods
full rationale
The paper derives the stated bound and extremal characterization for m pairwise cross t-intersecting families by applying the generating set method combined with the pushing-pulling method. These are standard techniques in extremal set theory, independent of the present work. The result generalizes prior theorems (Katona 1964, Frankl-Wong 2021, Li-Zhang 2025) without reducing the central inequality or equality cases to self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations whose validity depends on the current paper. The single-family quantity M(n,t) is invoked as an external benchmark from prior literature, and the proof's case analysis for the two extremal constructions is presented as exhaustive and self-contained against the pairwise cross t-intersecting condition.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard properties of binomial coefficients and set intersections hold for all n and t.
Reference graph
Works this paper leans on
-
[1]
R. Ahlswede, L. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Theory Ser. A 76 (1996) 121–138
work page 1996
-
[2]
R. Ahlswede, L. Khachatrian, The complete intersection theorem for systems of finite sets, European J. Combin. 18 (1997) 125–136
work page 1997
-
[3]
R. Ahlswede, L. Khachatrian, A pushing-pulling method: new proofs of intersection theo- rems, Combinatorica 19 (1) (1999) 1–15
work page 1999
-
[4]
R. Ahlswede, L. Khachatrian, Katona’s intersection theorem: Four proofs, Combinatorica 25 (1) (2005) 105–110
work page 2005
- [5]
-
[6]
B. Bollob´ as, Combinatorics: Set systems, hypergraphs, families of vectors and combinatorial probability. Cambridge University Press, Cambridge, 1986. (see page 98)
work page 1986
-
[7]
P. Borg, C. Feghali, The maximum sum of sizes of cross-intersecting families of subsets of a set, Discrete Math. 345 (2022) 112981
work page 2022
-
[8]
M. Cao, B. Lv, K. Wang, The structure of large non-trivial t-intersecting families of finite sets, European J. Combin. 97 (2021) 103373
work page 2021
-
[9]
M. Cao, M. Lu, B. Lv, K. Wang, Nearly extremal non-trivial cross t-intersecting families and r-wise t-intersecting families, European J. Combin. 120 (2024) 103958
work page 2024
-
[10]
P. Erd˝ os, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Q. J. Math. 2 (1961) 313–320
work page 1961
-
[11]
Filmus, The weighted complete intersection theorem, J
Y. Filmus, The weighted complete intersection theorem, J. Combin. Theory Ser. A 151 (2017) 84–101
work page 2017
-
[12]
Frankl, The Erd˝ os–Ko–Rado theorem is true forn = ckt, Proc
P. Frankl, The Erd˝ os–Ko–Rado theorem is true forn = ckt, Proc. Fifth Hung. Comb. Coll., North-Holland, Amsterdam, 1978, pp. 365–375. 13
work page 1978
-
[13]
Frankl, The shifting technique in extremal set theory, Surveys in Combinatorics 123 (1987) 81–110
P. Frankl, The shifting technique in extremal set theory, Surveys in Combinatorics 123 (1987) 81–110
work page 1987
-
[14]
Frankl, A stability result for the Katona theorem, J
P. Frankl, A stability result for the Katona theorem, J. Combin. Theory Ser. B 122 (2017) 869–876
work page 2017
-
[15]
Frankl, A stability result for families with fixed diameter, Combin
P. Frankl, A stability result for families with fixed diameter, Combin. Probab. Comput. 26 (2017) 506–516
work page 2017
-
[16]
P. Frankl, On the maximum of the sum of the sizes of non-trivial cross-intersecting families, Combinatorica 44 (1) (2024) 15–35
work page 2024
- [17]
- [18]
-
[19]
Frankl, N.Tokushige, Some inequalities concerning cross-intersecting families, Combin
P. Frankl, N.Tokushige, Some inequalities concerning cross-intersecting families, Combin. Probab. Comput. 7 (3) (1998) 247–260
work page 1998
- [20]
- [21]
- [22]
-
[23]
P. Frankl, J. Wang, On r-wise t-intersecting uniform families, Combinatorica 45, 44 (2025), https://doi.org/10.1007/s00493-025-00166-y
- [24]
- [25]
- [26]
- [27]
- [28]
- [29]
- [30]
- [31]
- [32]
-
[33]
Katona, Intersection theorems for systems of finite sets, Acta Math
G. Katona, Intersection theorems for systems of finite sets, Acta Math. Hungar. 15 (1964) 329–337
work page 1964
-
[34]
A. Li, H. Zhang, On non-empty cross- t-intersecting families, J. Combin. Theory Ser. A 210 (2025) 105960
work page 2025
-
[35]
Y. Li, B. Wu, Stabilities for non-uniform t-intersecting families, Electron. J. Combin. 31 (4) (2024) #P4.3
work page 2024
-
[36]
Liu, The maximum sum of the sizes of cross-intersecting separated families, AIMS Math
E. Liu, The maximum sum of the sizes of cross-intersecting separated families, AIMS Math. 8 (12) (2023) 30910–30921
work page 2023
-
[37]
C. Shi, P. Frankl, J. Qian, On non-empty cross-intersecting families, Combinatorica 42 (2) (2022) 1513–1525
work page 2022
-
[38]
Wang, On systems of finite sets with constraints on their unions and intersections, J
D. Wang, On systems of finite sets with constraints on their unions and intersections, J. Combin. Theory, Ser. A 23 (3) (1977) 344–348
work page 1977
-
[39]
J. Wang, Developments of the shifting method in extremal set theory, (2025), available on the Researchgate, https://www.researchgate.net/publication/392500018
-
[40]
J. Wang, H. Zhang, Nontrivial independent sets of bipartite graphs and cross-intersecting families, J. Combin. Theory Ser. A 120 (2013) 129–141
work page 2013
-
[41]
Wilson, The exact bound in the Erd˝ os–Ko–Rado theorem, Combinatorica 4 (1984) 247– 257
R. Wilson, The exact bound in the Erd˝ os–Ko–Rado theorem, Combinatorica 4 (1984) 247– 257
work page 1984
-
[42]
Y. Wu, L. Feng, Y. Li, A result for hemi-bundled cross-intersecting families, Adv. in Appl. Math. 169 (2025) 102912
work page 2025
- [43]
- [44]
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.