Exact extremal non-trivial cross-intersecting families

Biao Wu; Huajun Zhang

REVIEW 3 major objections 3 minor 19 references

Exact extremal non-trivial cross-intersecting families

T0 review · 3 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read This paper proves that, in the stated range, nontrivial cross-intersecting family products attain one of two explicit sharp bounds, with unique extremal structures.

desk verdict The ℓ > k result is a real extension and the early sections are solid, but Proposition 4.1 has a load-bearing flaw in its derivative analysis, so the main theorem is not proven as written. read the letter →

arxiv 2411.16091 v1 pith:T3KXK6OY submitted 2024-11-25 math.CO

Biao Wu , Huajun Zhang This is my paper · ORCID

classification math.CO MSC 05D0505A20

keywords cross-intersectingfamiliesnontrivialextremalproblemproductoffamilysizesshadowmethodsbinomialcoefficientinequalitiessize-sensitiveuniqueconfigurations

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

Two families $\mathcal{A}\subseteq \binom{[n]}{k}$ and $\mathcal{B}\subseteq \binom{[n]}{\ell}$ are cross-intersecting when every set in $\mathcal{A}$ meets every set in $\mathcal{B}$, and nontrivial when no single element lies in every member of $\mathcal{A}\cup\mathcal{B}$. The paper determines the exact extremal value of the product $|\mathcal{A}||\mathcal{B}|$ for nontrivial pairs, under the range $n\ge 2\ell>2k$ or $n>2\ell=2k$. There are exactly two extremal shapes up to isomorphism, giving two sharp closed-form upper bounds. The range of $n$ is best possible, and the size-sensitive inequalities proved along the way recover the known equal-size nontrivial extremal result.

What carries the argument

The proof has two layers. A family of size-sensitive inequalities is built from regular bipartite graphs whose two parts are adjacent layers of the disjointness graph on set families: when a pair is maximal, the neighbor ratio $|N(X)|/|X|$ is bounded below, which lets one replace a part of $\mathcal{B}$ and the corresponding part of $\mathcal{A}$ and compare the new product with the old. For the middle range of $|\mathcal{A}|$, the proof compresses to lexicographically initial families, then uses the shadow transform: from $|\mathcal{B}'|=\binom{x}{n-\ell-1}$ the analytic shadow bound yields $|\mathcal{A}'|\le \binom{n-2}{k-1}-\binom{x}{k-1}$, so $|\mathcal{A}||\mathcal{B}|$ is dominated by the polynomial $\varphi(x)$ in equation (12). The target is to show $\varphi(x)<\Gamma$ for every integer $x\in[n-\ell-1,n-4]$, where $\Gamma$ is the maximum of the two claimed bounds; endpoint checks are binomial-ratio estimates, and the interior is handled by a second-derivative argument that, as written, relies on an invalid concavity step. The equality analysis uses a uniqueness criterion for shadow equality to force the two extremal structures.

What would settle it

Evaluate $\varphi(x)-\Gamma$ for an admissible triple with $n\ge \ell^2$ and $n\ge 2\ell>2k$ at an interior point of $[n-\ell-1,n-4]$, for example $x=n-\ell-2$; if any value is nonnegative, Proposition 4.1's covering of the middle range fails. A finite check over small parameters, say $\ell\le 8$ and all permitted $k,n$, would settle whether the bound is true or false.

Watch

Extended reading notes

Core claim

Under the stated range, any nontrivial cross-intersecting pair must satisfy one of two inequalities: $|\mathcal{A}||\mathcal{B}| \le \bigl(\binom{n-1}{k-1}+\binom{n-2}{k-1}\bigr)\binom{n-2}{\ell-2}$, with equality only for $\mathcal{A}=\{A: 1\in A \text{ or } 2\in A\}$ and $\mathcal{B}=\{B: [2]\subseteq B\}$; or $|\mathcal{A}||\mathcal{B}| \le \bigl(\binom{n-1}{k-1}+1\bigr)\bigl(\binom{n-1}{\ell-1}-\binom{n-k-1}{\ell-1}\bigr)$, with equality only for $\mathcal{A}=\{A: 1\in A\}\cup\{[2,k+1]\}$ and $\mathcal{B}=\{B: 1\in B,\ B\cap[2,k+1]\ne\emptyset\}$, up to isomorphism. The dichotomy is exhaustive, so every nontrivial cross-intersecting pair falls under one of the two sharp bounds. The theorem also shows that the numerical range on $n$ is best possible, giving explicit examples just outside the range where the product exceeds both bounds.

Load-bearing premise

The middle-range inequality in Proposition 4.1 depends on the auxiliary polynomial $\varphi(x)$ staying strictly below the target maximum $\Gamma$ at every integer $x$ from $n-\ell-1$ to $n-4$; the written proof of that bound invokes a second-derivative argument that misstates the expansion of $\varphi''(x)$ and confuses a stationary point with an inflection point.

Editorial extensions

If this is right

If Theorem 1.5 is correct, the exact extremal product for nontrivial cross-intersecting families is known in the stated range, with two explicit extremal families up to isomorphism.
The range $n\ge 2\ell>2k$ or $n>2\ell=2k$ is sharp: just outside it, explicit examples beat both bounds, so the numerical condition is not an artifact of the method.
The size-sensitive inequalities proved here recover the known nontrivial extremal bound for the equal-size case, placing that earlier result inside the same framework.
The dichotomy gives a practical way to recognize extremality: compare $|\mathcal{A}|$ to the two thresholds and test membership in the two listed shapes.

Reading between the lines

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

A natural next step the authors do not take is to verify the polynomial bound $\varphi(x)<\Gamma$ computationally for small admissible parameter triples; since the interval of $x$ has length $O(\ell)$, the check is finite and could repair or refute the middle-range step.
If the polynomial bound is repaired, the same shadow-and-polynomial reduction may extend to the third extremal product or to nontrivial cross-intersecting families under weaker constraints on $n$.
The uniqueness proof suggests a stability statement: families whose product is close to the second extremum should be close, in symmetric difference, to one of the two displayed shapes; the paper does not prove such a statement.

Share X Bluesky LinkedIn Reddit HN

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

Short version: the paper's ℓ > k result is a genuine extension and the machinery is mostly sound, but Proposition 4.1 has a load-bearing flaw. I checked the step the stress-test flags, and it holds up.

The displayed formula for φ''(x) in Section 4.2 is not the true second derivative of the binomial polynomials. For binom(x,r), the actual second derivative involves all pairwise reciprocal products, 2Σ_{i

That said, the paper has real merit. The extremal constructions are explicit and the two candidate bounds are natural. The use of Mörs's equality criterion for uniqueness is elegant, and recovering Frankl–Kupavskii as a by-product is a useful consistency check. The citation pattern is fine; the self-citation to Wu–Xiong is used for context and recovery, not as a load-bearing input.

My guess is the overall claim is true and the gap is repairable, but the submitted text does not prove it. A serious referee should ask for a corrected proof of Proposition 4.1—specifically a correct second-derivative computation and a valid convexity or maximum argument. I would not desk-reject this; it deserves refereeing. But it should not be accepted in current form.

Referee Report

3 major / 3 minor

Summary. The paper studies the product size |A||B| of two cross-intersecting families A in C([n],k) and B in C([n],ell) under the nontriviality condition that the total intersection of all sets in A union B is empty. For n >= 2ell > 2k or n > 2ell = 2k, it claims two sharp upper bounds with unique extremal families, along with a sharpness example. The proof develops several size-sensitive inequalities in Section 3 and then, in Section 4, reduces the remaining middle range of |A| to a polynomial inequality phi(x) < Gamma. The authors state that the proof recovers results of Frankl and Kupavskii. The main theorem is thus a natural 'second extremal' complement to Matsumoto-Tokushige and Pyber.

Significance. If correct, the main theorem would settle a natural extremal problem for non-trivial cross-intersecting families in the ell > k range, giving explicit extremal configurations and a sharpness example. The paper draws on standard tools (Kruskal-Katona, Lovasz, Moers, Hilton) and the size-sensitive inequalities in Section 3 are potentially useful. However, the central proof depends on Proposition 4.1, whose written proof contains serious gaps in the analysis of the polynomial phi(x). These gaps are load-bearing: without them, the middle range of |A| is not covered and the main theorem is not established. The significance of the claimed result is therefore not realized by the submitted text.

major comments (3)

[Section 4.2, Eq. (12)] The displayed formula for phi''(x) is not the second derivative of the binomial-coefficient polynomial. For f(x) = binom(x,r), the correct second derivative is f(x)[(sum_{i=0}^{r-1} 1/(x-i))^2 - sum_{i=0}^{r-1} 1/(x-i)^2] = 2 f(x) sum_{0 <= i < j <= r-1} 1/((x-i)(x-j)). The expression printed in the proof contains only products of consecutive factors, omitting all cross terms. Consequently, the claim that phi''(x) > 0 for all x in the interval is unsupported, and the subsequent dichotomy in the proof has no valid basis.
[Section 4.2, proof of Proposition 4.1] The statement 'Let x0 be an arbitrary maximum element. So phi''(x0) = 0' is logically false. For a twice-differentiable function on an open interval, an interior maximum satisfies phi'(x0) = 0 and phi''(x0) <= 0; it need not be an inflection point with phi''(x0) = 0. The dichotomy 'either phi is convex on the whole interval or its maximum has zero second derivative' is therefore not established. Since the endpoint checks in Lemmas 4.4-4.7 do not control the interior (n-ell-1, n-5), the bound phi(x) < Gamma is left unproved for that interval.
[Section 4.2, proof of Proposition 4.1] The proof asserts that the Lovasz parameter x satisfies n-ell-1 <= x <= n-5 (or n-5 < x <= n-4 in the second case) without derivation. These bounds on x are load-bearing because the subsequent argument verifies phi(x) < Gamma only at the endpoints and attempts to control the interior by the invalid convexity step. A derivation of these bounds from the size hypotheses on |A| is needed; otherwise the interval over which phi is studied is not justified.

minor comments (3)

[Section 4.2] The symbol B prime is reused for the family {B in C([3,n],ell-1) : {1} union B in B} and later for the family of complements {[3,n]\B : B in B prime}. This notational clash makes the proof harder to follow and should be fixed.
[Section 4.2] There is a typographical inconsistency: the proof says 'n-5 < x <= n-4 for n <= ell^2', while Lemma 4.6 and the end of the proof use n >= ell^2. The intended condition appears to be n >= ell^2.
[Theorem 1.4] The text contains 'positive intgers'; it should read 'positive integers'.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the main inequalities are derived from standard external theorems; the only self-citation is contextual and non-load-bearing.

full rationale

The paper's central result, Theorem 1.5, is obtained through a chain of independent results: Theorem 3.7 and Corollary 3.6 are proved in Section 3 from Kruskal–Katona, Lovász, Mörs, and Hilton tools; Proposition 4.1 is proved separately via Lovász's shadow theorem and binomial-coefficient estimates. The extremal bound Γ is used only as a comparison constant, not as an assumed input. No parameter is fitted to the target quantity, and no intermediate inequality is defined in terms of the conclusion. The uniqueness argument in Proposition 4.2 invokes Mörs's uniqueness theorem and the cascade representation, not the theorem being proved. The only self-citation, Wu–Xiong [19], appears in the statement of the known k = ℓ theorem (Theorem 1.4) and is used for context or as an already-established external result; the new ℓ > k case does not reduce to it. Even if the k = ℓ case were imported from [19], that is an independent prior publication rather than a circular reuse of the present paper's assumptions. A separate correctness concern exists in Proposition 4.1's convexity argument for φ(x) < Γ: the claim that an interior maximum has zero second derivative is not valid in general, and the displayed expression for φ''(x) is not justified against the binomial polynomial. This is a rigor/correctness issue, not a circularity issue, and it does not raise the circularity score.

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

The proof rests entirely on established theorems: EKR, Pyber, Matsumoto–Tokushige, Kruskal–Katona, Lovász, Mörs, and Hilton. These are standard background, not ad hoc assumptions introduced for this paper. No new entities or fitted parameters appear.

assumptions (8)

standard math Erdős–Ko–Rado theorem (Theorem 1.1)
Used as baseline for intersecting families.
standard math Pyber's product bound (Theorem 1.2)
Sets the first-order extremal context for cross-intersecting families.
standard math Matsumoto–Tokushige uniqueness (Theorem 1.3)
Provides the top extremal bound and uniqueness that the present paper refines.
standard math Kruskal–Katona theorem (Theorem 2.1)
Used to control shadow sizes in Proposition 4.1 and Section 4.3.
standard math Lovász's binomial-coefficient bound (Theorem 2.2)
Extends shadow lower bounds to real-valued binomial coefficients.
standard math Mörs's uniqueness theorem for KK equality (Theorem 2.3)
Used in Section 4.3 to identify the unique shadow-minimizer.
standard math Mörs's cross-intersecting inequality (Theorem 2.4)
Applied in Theorem 2.4 and to split cases in the main proof.
standard math Hilton's lexicographic shifting lemma (Lemma 2.5)
Justifies the assumption that extremal families can be taken as lexicographic initial segments.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Exact extremal non-trivial cross-intersecting families." pith.science (2026). https://pith.science/paper/T3KXK6OY

@misc{pith2026241116091,
  author       = {Pith},
  title        = {Pith review of: Exact extremal non-trivial cross-intersecting families},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T3KXK6OY}},
  note         = {Machine review of arXiv:2411.16091}
}

abstract

Two families $\mathcal{A}$ and $\mathcal{B}$ of sets are called cross-intersecting if each pair of sets $A\in \mathcal{A}$ and $B\in \mathcal{B}$ has nonempty intersection. Let $\cal{A}$ and ${\cal B}$ be two cross-intersecting families of $k$-subsets and $\ell$-subsets of $[n]$. Matsumoto and Tokushige [J. Combin. Theory Ser. A 52 (1989) 90--97] studied the extremal problem of the size $|\cal{A}||\cal{B}|$ and obtained the uniqueness of extremal families whenever $n\ge 2 \ell\ge 2k$, building on the work of Pyber. This paper will explore the second extremal size of $|\cal{A}||\cal{B}|$ and obtain that if $\mathcal{A}$ and $\mathcal{B}$ are not the subfamilies of Matsumoto--Tokushige's extremal families, then, for $n\ge 2\ell >2k$ or $n> 2\ell=2k$, \begin{itemize} \item[1)]either $|\cal{A}||\cal{B}|\le \left({\binom{n-1}{k-1}}+{\binom{n-2 }{k-1}}\right){\binom{n-2}{\ell-2}}$ with the unique extremal families (up to isomorphism) \[\mbox{$\mathcal{A}=\{A\in {\binom{[n]}{k}}: 1\in A \: \rm{ or} \: 2\in A\}$ \quad and \quad $\mathcal{B}=\{B\in {\binom{[n]}{\ell}}: [2] \subseteq B\}$};\] \item[2)] or $|\cal{A}||\cal{B}|\le \left({\binom{n-1}{k-1}}+1\right)\left({\binom{n-1}{\ell-1}}-{\binom{n-k-1}{\ell-1}}\right)$ with the unique extremal families (up to isomorphism) \[\mbox{$\mathcal{A}=\{A\in {\binom{[n]}{k}}: 1\in A\}\cup \{[2,k+1] \}$\quad and \quad $\mathcal{B}=\{B\in {\binom{[n]}{\ell}}: 1\in B, B\cap [2,k+1]\neq \emptyset \}$.}\] \end{itemize} The bound ``$n\ge 2\ell >2k$ or $n> 2\ell=2k$" is sharp for $n$. To achieve the above results, we establish some size-sensitive inequalities for cross-intersecting families. As by-products, we will recover the main results of Frankl and Kupavskii [European J. Combin. 62 (2017) 263--271].

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[1]

M. Cao, M. Lu, B. Lv, K. Wang. Nearly extremal non-trivial cros s t-intersecting families and r-wise t-intersecting families. European J. Combin. 120 (2024), Paper No. 103958, 26 pp

work page 2024
[2]

D. E. Daykin. A simple proof of the Kruskal–Katona theorem. J. C ombin. Theory Ser. A 17 (1974) 252–253

work page 1974
[3]

Erd˝ os, C

P. Erd˝ os, C. Ko, R. Rado. Intersection theorems for system s of ﬁnite sets. Quart. J. Math. Oxf. 2(12) (1961) 313–320

work page 1961
[4]

P. Frankl. Old and new applications of Katona’s circle. European J. Combin. 95 (2021), 103339

work page 2021
[5]

Frankl, Z

P. Frankl, Z. F¨ uredi. A new short proof of the EKR theorem. J. Combin. Theory Ser. A 119 (2012) 1388–1390

work page 2012
[6]

F¨ uredi, K

Z. F¨ uredi, K. Hwang, P. M. Weichsel. A proof and generalizations of the Erd˝ os–Ko–Rado theorem using the method of linearly independent polynomials. in: Topics in Discr ete Mathematics, in: Algorithms Combin., vol. 26, Springer, Berlin, 2006, pp. 215–224

work page 2006
[7]

Frankl, A

P. Frankl, A. Kupavskii. A size-sensitive inequality for cross-inte rsecting families. European J. Com- bin. 62 (2017) 263–271

work page 2017
[8]

Frankl, N

P. Frankl, N. Tokushige. Invitation to intersection problems for ﬁnite sets. J. Combin. Theory Ser. A 144 (2016) 157–211

work page 2016

Show all 19 references

[9]

Frankl, N

P. Frankl, N. Tokushige. Extremal Problem for Finite Sets, Stud ent Mathematical Library 86. Amer. Math. Soc., Providence, RI, 2018

2018
[10]

A. J. W. Hilton. The Erd˝ os–Ko–Rado theorem with valency cond itions. Unpublished Manuscript, 1976

1976
[11]

G. O. H. Katona. Intersection theorems for systems of ﬁnite sets. Acta Math. Hungar. 15 (1964) 329–337. 18

1964
[12]

G. O. H. Katona. A theorem on ﬁnite sets. in: Theory of Graphs , Proceedings, Colloq. Tihany, Hungary, (1966) 187–207

1966
[13]

G. O. H. Katona, A simple proof of the Erd˝ os–Chao Ko–Rado th eorem, J. Combin. Theory Ser. B 13 (1972) 183–184

1972
[14]

J. B. Kruskal. The number of simplices in a complex. in: Mathematic al Optimization Techniques, Univ. of California Press, Berkeley, (1963) 251–278

1963
[15]

Lov´ asz, Problem 13.31, in: Combinatorial Problems and Exer cises, North Holland, 1979

L. Lov´ asz, Problem 13.31, in: Combinatorial Problems and Exer cises, North Holland, 1979

1979
[16]

Matsumoto, N

M. Matsumoto, 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

1989
[17]

M. M¨ ors. A generalization of a theorem of Kruskal. Graphs and Combinatorics, 1 (1985) 167–183

1985
[18]

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

1986
[19]

B. Wu, R. Xiong. A note on the maximum product-size of non-triv ial cross t-intersecting families. Discrete Math. 347 (2024), no.2, Paper No. 113783, 11 pp. 19

2024

Pith tools

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

[1] [1]

M. Cao, M. Lu, B. Lv, K. Wang. Nearly extremal non-trivial cros s t-intersecting families and r-wise t-intersecting families. European J. Combin. 120 (2024), Paper No. 103958, 26 pp

work page 2024

[2] [2]

D. E. Daykin. A simple proof of the Kruskal–Katona theorem. J. C ombin. Theory Ser. A 17 (1974) 252–253

work page 1974

[3] [3]

Erd˝ os, C

P. Erd˝ os, C. Ko, R. Rado. Intersection theorems for system s of ﬁnite sets. Quart. J. Math. Oxf. 2(12) (1961) 313–320

work page 1961

[4] [4]

P. Frankl. Old and new applications of Katona’s circle. European J. Combin. 95 (2021), 103339

work page 2021

[5] [5]

Frankl, Z

P. Frankl, Z. F¨ uredi. A new short proof of the EKR theorem. J. Combin. Theory Ser. A 119 (2012) 1388–1390

work page 2012

[6] [6]

F¨ uredi, K

Z. F¨ uredi, K. Hwang, P. M. Weichsel. A proof and generalizations of the Erd˝ os–Ko–Rado theorem using the method of linearly independent polynomials. in: Topics in Discr ete Mathematics, in: Algorithms Combin., vol. 26, Springer, Berlin, 2006, pp. 215–224

work page 2006

[7] [7]

Frankl, A

P. Frankl, A. Kupavskii. A size-sensitive inequality for cross-inte rsecting families. European J. Com- bin. 62 (2017) 263–271

work page 2017

[8] [8]

Frankl, N

P. Frankl, N. Tokushige. Invitation to intersection problems for ﬁnite sets. J. Combin. Theory Ser. A 144 (2016) 157–211

work page 2016