$s$-almost cross-$t$-intersecting families for finite sets

Dehai Liu; Kaishun Wang; Tian Yao

REVIEW 2 major objections 4 minor 25 references

$s$-almost cross-$t$-intersecting families for finite sets

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For $k \geq t+1$ and sufficiently large $n$, every pair of $s$-almost cross-$t$-intersecting families that maximizes $|\mathcal{F}||\mathcal{G}|$ has $\mathcal{F}=\mathcal{G}$ equal to the full star $\mathcal{H}_1([n],W;k)$ about a fixed…

desk verdict Solid generalization of cross-t-intersecting extremal results for all t, with the main proof depending on an external sequence bound and unverified binomial estimates; worth a careful referee. read the letter →

arxiv 2506.21993 v1 pith:SQWYKJPP submitted 2025-06-27 math.CO

Dehai Liu , Kaishun Wang , Tian Yao This is my paper · ORCID

classification math.CO MSC 05D05

keywords extremalsettheorycross-t-intersectingfamiliess-almostErdős-Ko-RadotheoremHilton-Milnercoveringnumberproductofsizesstability

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper characterizes the exact pairs of families $\mathcal{F},\mathcal{G}\subseteq \binom{[n]}{k}$ that maximize the product of their sizes among all $s$-almost cross-$t$-intersecting pairs. For $k\geq t+1$ and $n\geq (t+1)(2(k-t+1)^2+7s)$, the unique maximum is attained when both families are the full star of all $k$-sets containing one fixed $t$-set $W$. The paper also describes the extremal structure when the two families are not cross-$t$-intersecting, giving two explicit shapes depending on whether the families live in $\binom{[n]}{t+1}$ or in larger $k$. A stability corollary then decides which of two competing extremal constructions wins when the common intersection of all sets in both families has size below $t$. The result matters because it settles the product version of the Erdős–Ko–Rado problem under a local, one-sided relaxation of the intersection condition.

What carries the argument

The load-bearing object is the $t$-covering number $\tau_t(\mathcal{F})$, the minimum size of a set $T$ that meets every member of $\mathcal{F}$ in at least $t$ points, together with the product bound $f_1(n,k,t,s,x)$ defined in (2.3). Lemma 2.3 bounds $|\mathcal{F}||\mathcal{G}|$ by $f_1$ evaluated at the two covering numbers whenever both are at most $k$; Lemma 2.4, using an external bound on alternating sequences of $k$-sets, handles the case where one covering number is at least $k+1$. These bounds force $\tau_t(\mathcal{F})=\tau_t(\mathcal{G})=t$ under the stated $n$ range, after which Lemma 2.5 shows the unique minimum $t$-covers coincide, giving the double-star conclusion.

What would settle it

Exhibit two $s$-almost cross-$t$-intersecting families $\mathcal{F},\mathcal{G}\subseteq\binom{[n]}{k}$ with $k\geq t+1$ and $n\geq (t+1)(2(k-t+1)^2+7s)$ whose product $|\mathcal{F}||\mathcal{G}|$ exceeds $\binom{n-t}{k-t}^2$; that directly refutes Theorem 1.1. Alternatively, check whether two alternating sequences of $k$-sets satisfying $|F_i\cap G_i|<t$ and $|F_i\cap G_j|\geq t$ for $j<i$ can have length greater than $\binom{2k-2t+2}{k-t+1}$; if so, Lemma 2.4 breaks.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: if $k\geq t+1$ and $n\geq (t+1)(2(k-t+1)^2+7s)$, and $\mathcal{F},\mathcal{G}\subseteq \binom{[n]}{k}$ are $s$-almost cross-$t$-intersecting with $|\mathcal{F}||\mathcal{G}|$ maximum, then there is a $t$-set $W$ such that $\mathcal{F}=\mathcal{G}=\mathcal{H}_1([n],W;k)$, the star of all $k$-sets containing $W$. Theorems 1.2 and 1.3 sharpen this for extremal pairs that fail to be cross-$t$-intersecting: when $k\geq t+2$, one family is a star with a specific slice of size $\binom{n-k-1}{k-t}-s$ removed, and the other is the same star with a set of size $\min\{t,s\}$ added; when $k=t+1$, two different shapes arise according to whether $t\geq s+2$ or $t\leq s+1$. Combining these with an earlier classification of nearly extremal cross-$t$-intersecting families yields a stability result that determines which extremal shape is optimal when the intersection of all members of both families has size less than $t$.

Load-bearing premise

The proof assumes $n$ is large enough that the full-star product beats every competitor; in particular, the external bound on alternating sequences of $k$-sets from [19] and the Section 7 inequalities must hold in the stated $n$ range, or the contradiction forcing both covering numbers to equal $t$ collapses.

Editorial extensions

If this is right

If the theorem is correct, the maximum product for large $n$ is exactly $\binom{n-t}{k-t}^2$, attained only by $\mathcal{F}=\mathcal{G}=\mathcal{H}_1([n],W;k)$.
Any extremal pair that is not cross-$t$-intersecting must be a star with a removed slice of size $\binom{n-k-1}{k-t}-s$ together with a small added block, so the extremal families are always close to a full star.
For $k=t+1$, the optimal non-cross-$t$-intersecting shape switches at the boundary $s=t-1$: one family is a singleton for $t\geq s+2$, and a small star around a $t$-set for $t\leq s+1$.
The stability corollary determines, under the condition that the common intersection of all sets in both families has size less than $t$, whether the star-with-surgery construction or the cross-intersecting pair $\mathcal{H}_1([n],Y;k)$ and $\mathcal{M}_1(Y;k,t)$ wins, depending on whether $k\geq 2t+1$ or $k\leq 2t$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the same covering-number machinery should extend to a two-parameter version where each family is allowed its own budget, $s_1$ and $s_2$; the extremal shapes would likely be stars with asymmetric removed slices.
Editorial inference: the threshold on $n$ is almost certainly not sharp, because the Section 7 inequalities use deliberately loose constants; a direct comparison of $g_1$, $g_2$, $g_3$, and $g_4$ could identify the true boundary for moderate $n$.
Editorial inference: the method and the extremal shapes should transfer to other ranked posets with a similar intersection notion, such as vector spaces, a direction the concluding remark already points toward.
Editorial inference: a testable quantitative consequence is that for fixed $k,t,s$ the product-maximizing pair should remain a double star for all $n$ beyond some much smaller threshold; searching for the smallest such $n$ by computer would either confirm the trend or reveal a new extremal family.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the short version: this paper completes the s-almost cross-t-intersecting characterization for all t, not just t=1. The extremal structures in Theorems 1.2 and 1.3 are new, and the stability results are a useful addition. It's a solid paper.

What's genuinely new: [13] gave the maximum product for t=1; [5] handled the cross-t-intersecting case. This paper does the complementary non-cross-t-intersecting case for all t and gives the full structure, including two nontrivial extremal families. The proof method—covering numbers plus a battery of binomial inequalities—is the right tool, and the exposition is clear.

The soft spots are exactly where the stress-test note points. Lemma 2.4 leans entirely on [19, Theorem 6], an alternating-sequence bound that is quoted but not reproduced, and the hypotheses (distinctness, n-range) are not checked against the constructed sequences. The Section 7 inequalities are long and are stated as verified computations without CAS support. These are the load-bearing dependencies for Theorem 1.1, so a referee should check them. I don't see any internal inconsistency, and the extremal examples do match the upper-bound products.

Minor point: Lemma 2.1 imports [5, Lemma 2.7] from one of the authors' group, but [5] is published, so that's not a real problem. The large-n hypotheses are explicit; yes, they're strong, but that's typical for this style of theorem.

Bottom line: this is a serious combinatorics paper that deserves a proper referee, not a desk reject. If you work in extremal set theory, cite it. I'd send it to review, with the instruction that the arithmetic and the [19] bound get a careful look.

Referee Report

2 major / 4 minor

Summary. The paper studies pairs of families F,G of k-subsets of an n-set that are s-almost cross-t-intersecting, meaning that each member of either family is t-disjoint from at most s members of the other family. The main results are as follows. Theorem 1.1 states that, for k ≥ t+1 and n ≥ (t+1)(2(k−t+1)^2+7s), the maximum product |F||G| is attained exactly by two copies of the full t-star H1([n],W;k). Theorems 1.2 and 1.3 classify the extremal pairs that are not cross-t-intersecting: one family is a star with a specified slice removed, the other is that star together with a small block, with the precise parameters depending on s, t, and k; the case k=t+1 is treated separately. Corollaries 6.2 and 6.3 use the non-cross-t-intersecting classification together with the external result [5, Theorem 1.2] to give a stability version under the condition that the common intersection of all members of F∪G has size less than t. The proofs are built on t-covering numbers, several auxiliary bounds on subfamilies, and a long collection of binomial inequalities assembled in Section 7.

Significance. If correct, the paper supplies a natural product-maximum analogue of the Erdős–Ko–Rado and Hilton–Milner line of results for a locally relaxed cross-intersection condition, and it does so in full structural detail rather than only with an extremal number. The extremal constructions are explicit and their product formulas match the upper bounds derived in the proofs, which is a real strength. The t-covering-number framework is appropriate, and the separation of the k=t+1 case in Theorem 1.3 is well matched to the different behaviour of the examples. The proofs are not machine-checked, but the chains of inequalities in Section 7 are written out in enough detail that I found no internal contradiction; the main risk is the dependence on one external theorem and on several delicate rational estimates, as detailed below. If those are verified, the paper gives a complete and convincing characterization.

major comments (2)

[Lemma 2.4 and Section 3] Lemma 2.4 is load-bearing for Theorem 1.1: the proof rules out the case τ_t(F) ≥ k+1 by applying the alternating-sequence bound m ≤ C(2k−2t+2, k−t+1) from [19, Theorem 6] to sequences F_i, G_i satisfying conditions (a) and (b). The manuscript does not state the exact formulation of [19, Theorem 6] or verify that its hypotheses are satisfied by the constructed sequences, in particular whether it requires the F_i and G_i to be distinct or imposes any condition on n beyond the ones already present. I request that the authors state the theorem explicitly and check those hypotheses; if [19, Theorem 6] carries any hidden n-dependence or distinctness condition, the contradiction in the τ_t ≥ k+1 case would fail.
[Section 7, Lemmas 7.2–7.6] The central product upper bounds ultimately rest on a sequence of delicate rational inequalities and monotonicity claims, including the bounds 7225/14112, 69803/112896, 2119/14112 in Lemma 7.4, the monotonicity of f3 in Lemma 7.5, and the comparison g1 < g4 in Lemma 7.6. I did not find a specific arithmetic error, but these estimates are described as routine computations and are load-bearing for Theorems 1.1, 1.2, and 1.3. Please provide either a CAS verification script or an expanded derivation of the critical inequalities so that the constants can be checked independently.

minor comments (4)

[Section 2, proof of Lemma 2.2] The phrase 'Repeated the process above' would be clearer if the induction invariant and the precise stopping rule for the chain H = H1 ⊊ H2 ⊊ ... ⊊ Hu were stated explicitly.
[Section 7, Lemma 7.6(ii)] In the display after (7.9), the polynomial expression is typeset as 'n2(7 − 2t) + 4n(2t2 − 5t − 2) ...'; please insert exponent and multiplication signs for readability.
[Introduction, Theorem 1.2] The normalization |F| ≤ |G| breaks the symmetry, but the paper does not explicitly say that the extremal description for |F| ≥ |G| is obtained by interchanging F and G; adding this sentence would prevent confusion.
[Section 7] The proposition [11, Proposition 1.6] is invoked repeatedly; stating its content once at the beginning of Section 7 would make the subsequent estimates easier to follow.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the main theorems are proved from stated hypotheses using independent external lemmas and explicit binomial estimates.

full rationale

The derivation chain is self-contained conditional on stated external results. Theorem 1.1 reduces the extremal product problem to proving (tau_t(F), tau_t(G))=(t,t) via two upper-bound regimes (Lemmas 2.3 and 2.4) and then compares these bounds with the lower bound from a star-star pair. The upper bounds are not fitted to the target; f1 and g1 are explicit closed-form binomial expressions and every comparison is proven in Section 7. Lemma 2.1 imports [5, Lemma 2.7] from a prior paper sharing author K. Wang, but that lemma is a general cross-t-intersecting local bound and is not equivalent to, nor does it presuppose, the present theorems; it does not by itself force the extremal structure. Similarly, Lemma 2.4 relies on [19, Theorem 6] about alternating set sequences, an independent published result with no overlap with the authors. The structural descriptions in Theorems 1.2 and 1.3 are obtained by applying these bounds and double-counting arguments, not by renaming examples or by assuming the conclusion. Corollaries 6.2 and 6.3 additionally invoke [5, Theorem 1.2], which is an external characterization of cross-t-intersecting extremal families and is used only to separate the cross-t-intersecting case. No fitted parameter is renamed as a prediction and no uniqueness claim is imported solely from self-citation. The external [19] bound and the Section 7 constants are correctness risks, not circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim rests on standard binomial arithmetic plus two external combinatorial lemmas. There are no free parameters fitted to data and no new postulated entities.

assumptions (3)

domain assumption External theorem [19, Theorem 6] gives the bound m ≤ C(2k−2t+2, k−t+1) for sequences of k-sets with properties (a) and (b) in Lemma 2.4.
Used in Lemma 2.4 to bound |F| when τt(G) ≥ k+1; load-bearing for the contradiction in Theorem 1.1.
domain assumption External lemma [5, Lemma 2.7] provides the local cross-t-intersecting bound |I_H| ≤ C(k−|H∩G|, t−|H∩G|) |I_R| used in Lemma 2.1.
Imported at the start of the proof of Lemma 2.1 to control the 'good' part of F; underpins Lemma 2.2 and all later covering-number bounds.
standard math External binomial-ratio estimates from [11, Proposition 1.6].
Used repeatedly in Section 7 to bound products of binomial coefficients.

how reviews work

0 comments

Cite this review

Pith. "Pith review of $s$-almost cross-$t$-intersecting families for finite sets." pith.science (2026). https://pith.science/paper/SQWYKJPP

@misc{pith2026250621993,
  author       = {Pith},
  title        = {Pith review of: $s$-almost cross-$t$-intersecting families for finite sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SQWYKJPP}},
  note         = {Machine review of arXiv:2506.21993}
}

abstract

Two families $\mathcal{F}$ and $\mathcal{G}$ of $k$-subsets of an $n$-set are called $s$-almost cross-$t$-intersecting if each member in $\mathcal{F}$ (resp. $\mathcal{G}$) is $t$-disjoint with at most $s$ members in $\mathcal{G}$ (resp. $\mathcal{F}$). In this paper, we characterize the $s$-almost cross-$t$-intersecting families with the maximum product of their sizes. Furthermore, we provide a corresponding stability result after studying the $s$-almost cross-$t$-intersecting families which are not cross-$t$-intersecting.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

[13]

Gerbner, N

D. Gerbner, N. Lemons, C. Palmer, D. P´ alv¨ olgyi, B. Patk´ os and V. Sz´ ecsi, Almost cross-intersecting and almost cross-sperner pairs of families of sets, Graphs Combin. 29 (2013) 489–498

work page 2013
[5]

M. Cao, M. Lu, B. Lv and 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
[19]

Properties of intersecting families of ordered sets

S.-I. Oum and S. Wee, A remark on the paper “Properties of intersecting families of ordered sets” by O. Einstein, Combinatorica 38 (2018) 1279–1284

work page 2018
[1]

Ahlswede and L.H

R. Ahlswede and L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Theory Ser. A 76 (1996) 121–138

work page 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. 22

work page 1997
[3]

Alishahi and A

M. Alishahi and A. Taherkhani, Extremal G-free induced subgraphs of Kneser graphs, J. Combin. Theory Ser. A 159 (2018) 269–282

work page 2018
[4]

Borg, The maximum product of weights of cross-intersecting families, J

P. Borg, The maximum product of weights of cross-intersecting families, J. Lond. Math. Soc. 94 (2016) 993–1018

work page 2016
[6]

Erd˝ os, C

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

work page 1961

Show all 25 references

[7]

Frankl, The Erd˝ os-Ko-Rado theorem is true forn = ckt, in: I

P. Frankl, The Erd˝ os-Ko-Rado theorem is true forn = ckt, in: I. Combinatorics (Ed.), Proc. Fifth Hungarian Colloq., Keszthey 1976, in: Colloq. Math. Soc. J´ anos Bolyai, vol. 18, North-Holland, 1978, pp. 365–375

1976
[8]

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

1978
[9]

Frankl and Z

P. Frankl and Z. F¨ uredi, Non-trivial intersecting families, J. Combin. Theory Ser. A 41 (1986) 150–153

1986
[10]

Frankl and A

P. Frankl and A. Kupavskii, Almost intersecting families, Electron. J. Combin. 28 (2021) #P2.7

2021
[11]

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
[12]

Gerbner, N

D. Gerbner, N. Lemons, C. Palmer, B. Patk´ os and V. Sz´ ecsi, Almost intersecting families of sets, SIAM J. Discrete Math. 26 (2012) 1657–1699

2012
[14]

Hilton and E

A. Hilton and E. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2) 18 (1967) 369–384

1967
[15]

L. Ji, D. Liu, K. Wang, T. Yao and S. Yu, s-almost t-intersecting families for vector spaces, arXiv: 2406.05840

arXiv
[16]

D. Liu, K. Wang and T. Yao, s-almost t-intersecting families for finite sets, arXiv: 2410.20185
[17]

D. Liu, J. Wang and T. Yao, s-almost cross-t-intersecting families for vector spaces, in preparation
[18]

Matsumoto and N

M. Matsumoto and N. Tokushige, The exact bound in the Erd˝ os-Ko-Rado theorem for cross-intersecting families, J. Combin. Theory Ser. A 52 (1989) 90–97. 23

1989
[20]

Pyber, A new generalization of the Erd˝ os-Ko-Rado theorem, J

L. Pyber, A new generalization of the Erd˝ os-Ko-Rado theorem, J. Combin. Theory Ser. A 43 (1986) 85–90

1986
[21]

Scott and E

A. Scott and E. Wilmer, Hypergraphs of bounded disjointness, SIAM J. Discrete Math. 28 (2014) 372–384

2014
[22]

Shan and J

Y. Shan and J. Zhou, Almost intersecting families for vector spaces, Graphs Combin. 40 (2024) Paper No. 62

2024
[23]

Tokushige, The eigenvalue method for cross t-intersecting families, J

N. Tokushige, The eigenvalue method for cross t-intersecting families, J. Algebraic Com- bin. 38 (2013) 653–662

2013
[24]

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
[25]

Zhang and B

H. Zhang and B. Wu, On a conjecture of Tokushige for cross- t-intersecting families, J. Combin. Theory Ser. B 171 (2025) 49–70. 24

2025

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [13]

Gerbner, N

D. Gerbner, N. Lemons, C. Palmer, D. P´ alv¨ olgyi, B. Patk´ os and V. Sz´ ecsi, Almost cross-intersecting and almost cross-sperner pairs of families of sets, Graphs Combin. 29 (2013) 489–498

work page 2013

[2] [5]

M. Cao, M. Lu, B. Lv and 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

[3] [19]

Properties of intersecting families of ordered sets

S.-I. Oum and S. Wee, A remark on the paper “Properties of intersecting families of ordered sets” by O. Einstein, Combinatorica 38 (2018) 1279–1284

work page 2018

[4] [1]

Ahlswede and L.H

R. Ahlswede and L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Theory Ser. A 76 (1996) 121–138

work page 1996

[5] [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. 22

work page 1997

[6] [3]

Alishahi and A

M. Alishahi and A. Taherkhani, Extremal G-free induced subgraphs of Kneser graphs, J. Combin. Theory Ser. A 159 (2018) 269–282

work page 2018

[7] [4]

Borg, The maximum product of weights of cross-intersecting families, J

P. Borg, The maximum product of weights of cross-intersecting families, J. Lond. Math. Soc. 94 (2016) 993–1018

work page 2016

[8] [6]

Erd˝ os, C

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

work page 1961