Non-uniform Cross-intersecting Families

Huajun Zhang; Jimeng Xiao; Qing Xiang; Zhen Jia

REVIEW 3 major objections 4 minor 1 cited by

Non-uniform Cross-intersecting Families

T0 review · 3 major / 4 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 For non-uniform cross-intersecting families, total size is maximized by a star or by one small-set family with all others containing that set.

desk verdict A genuinely new common generalization of cross-intersecting families results, with a coherent generating-set proof, but it relies on an unproved lexicographic-initial-segment theorem that referees should ask to be proved. read the letter →

arxiv 2411.18426 v1 pith:K4RKMSY7 submitted 2024-11-27 math.CO

Zhen Jia , Qing Xiang , Jimeng Xiao , Huajun Zhang This is my paper · ORCID

classification math.CO MSC 05D05

keywords non-emptycross-intersectingfamiliesnon-uniformErdős–Ko–Radotheoremgeneratingsetmethodshiftinglexicographicinitialsegmentsextremaltheorysumofsizes

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

This paper determines the exact largest total number of sets in $m$ non-empty cross-intersecting families when the families are non-uniform, meaning each family $\mathcal{F}_i$ may draw its sets from several prescribed sizes $R_i\subseteq[n]$ at once. The bound holds whenever $n\ge k_1+k_2$, where $k_1$ and $k_2$ are the two largest allowed sizes across all families. The maximum is the larger of two explicit candidates: either every family is a star at one fixed element, or one chosen family consists of all its sets meeting a fixed small set while every other family consists of sets containing that small set. The paper also gives a complete list of equality cases, including two boundary exceptions when $n=k_1+k_2$. This settles, in generalized form, an open problem posed by earlier work on non-uniform cross-intersecting families.

What carries the argument

The proof is carried by the generating-set method applied to monotone, left-compressed families. After a lex-initial reduction makes every uniform layer consist of its earliest sets in lexicographic order, the proof works with generating sets, the minimal subsets whose up-sets lie inside each family. For an extremal configuration, a boundary generating family at the largest extent $l$ is nonempty, and a pairing lemma forces any generating set of size $u$ in one family to combine with a generating set of size $l+1-u$ in another family so that the two sets partition $[l]$. Two replacement operations shift whole blocks of sets between the chosen family and the others, producing two inequalities on binomial products. Strict log-concavity of binomial coefficients makes those inequalities contradictory for any interior value of $l$, so the maximum must sit at an endpoint: $l=1$, giving the star bound, or $l=k_\gamma^{\min}$, giving the $\mathcal{M}_1/\mathcal{M}_2$ bound. The two boundary exceptions come from the equalities that arise when $n=k_1+k_2$.

What would settle it

A finite exhaustive search over all pairs of families with small parameters, such as $n=7, k_1=k_2=3$ or $n=8, k_1=4, k_2=3$, for a cross-intersecting pair whose lexicographic initial segments are not cross-intersecting would settle Theorem 2.3: a single such pair would refute the theorem and break the main proof's first reduction.

Watch

Extended reading notes

Core claim

The central theorem states that under $n\ge k_1+k_2$, $$\sum_{j=1}^{m}|\mathcal{F}_j|\le\max\left\{\sum_{j=1}^{m}|\mathcal{S}(n,R_j)|,\ \max_{\gamma}\left(|\mathcal{M}_1(n,R_\gamma,[k_\$gamma^{{\min}}$])|+\sum_{\$\alpha$\neq\gamma}|\mathcal{M}_2(n,R_\$\alpha$,[k_\$gamma^{{\min}}$])|\right)\right\},$$ where $\mathcal{S}(n,R)$ is the family of all sets in $\binom{[n]}{R}$ containing $1$, $\mathcal{M}_1(n,R,[k])$ is the family of all $R$-sets meeting $[k]$, $\mathcal{M}_2(n,R,[k])$ is the family of all $R$-sets containing $[k]$, and $k_\gamma^{\min}$ is the smallest size appearing in $R_j$ for $j\neq\gamma$. Equality holds exactly in four configurations: all families are stars at one element; one family is $\mathcal{M}_1$ anchored at $[k_\gamma^{\min}]$ and all others are $\mathcal{M}_2$ anchored at the same set; in the boundary case $n=k_1+k_2$ with two families of two different singleton sizes, one family consists of all sets of size $k_1$ except the complements of the sets in the other family; and when all $m\ge3$ families have the same singleton size $k$, all families coincide with the same extremal intersecting family of size $\binom{n-1}{k-1}$.

Load-bearing premise

The proof assumes that replacing each uniform layer of a cross-intersecting pair by its lexicographically first sets preserves the cross-intersecting property; this statement is cited to an unpublished manuscript and a doctoral thesis and is not proved in the paper.

Editorial extensions

If this is right

For any number $m\ge2$ of non-uniform families with prescribed size sets, the maximum total size is given by a closed formula and the extremal families are fully classified.
When every $R_i$ is the same singleton $\{k\}$, the theorem reduces to the earlier uniform bound for non-empty cross-intersecting families and reproduces its equality structure.
When each $R_i$ is a different singleton $\{k_i\}$, the theorem answers the previously open problem on non-uniform cross-intersecting families and covers the independently proved special cases of that problem.
The equality cases show two new extremal phenomena at $n=k_1+k_2$: a boundary complement-avoiding configuration for two families, and a common identical extremal family for three or more families of equal size.
The log-concavity contradiction establishes that no intermediate generating-set depth can be extremal, so the competition is genuinely only between the star and the two-center configurations.

Reading between the lines

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

If a cross-$t$-intersecting analogue of the lex-initial preservation theorem ever becomes available, the same generating-set machinery would likely resolve the open non-uniform cross-$t$ problem stated in the final section; the paper explicitly notes that no such analogue is known for $t\ge2$.
The theorem suggests that the essential extremal competition in non-uniform cross-intersecting problems is between a one-point star and an anchor set of size equal to the smallest allowed size outside the chosen family, a dichotomy reminiscent of the complete intersection theorem.
The equality flexibility in the $m=2$, $n=k_1+k_2$ boundary case indicates that the threshold $n\ge k_1+k_2$ is sharp: below that threshold the extremal shapes may be genuinely different and are not described by this theorem.
A natural testable extension is to search for the maximum at $n=k_1+k_2-1$ in small cases; finding a configuration that beats both the star and the two-center bounds would confirm that the stated threshold is necessary.

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

This is a solid paper that closes the natural multi-family version of Shi–Frankl–Qian's question, and it does so with a clean extremal characterization. The main theorem, for any number of families with arbitrary allowed sizes R_i under n≥k1+k2, gives the maximum sum as the max of the star bound and the two-center bounds, and characterizes equality. That is a genuine common generalization of the uniform m-family result and the m=2 non-uniform results, so it earns its place in the literature.

The proof uses the generating set method, adapted from Ahlswede–Khachatrian and the recent work of Li–Zhang. The core inequalities are standard log-concavity arguments, and the extremal analysis is careful. I checked the steps around the boundary generating sets and the 'shifting a generating set' arguments; they hang together. Lemma 3.1 is proved in the paper, which is good.

The main soft spot is exactly what you flagged: Theorem 2.3, which lets the authors reduce to lexicographic initial segments, is cited to an unpublished 1976 manuscript and a 2005 thesis. This theorem is load-bearing: without it, the first reduction collapses. It is probably true and standard, but the manuscript does not prove it or give a citable proof. A referee should ask the authors to include a proof or a published reference. This is a verification gap, not a counterexample.

The equality cases for n=k1+k2 are dispatched quickly, and there is a small notation glitch in case (iii) (the complement bar is easy to misread). That part deserves a bit more exposition, but I don't see a fatal flaw.

Net: the result is likely correct, the proof is a natural extension, and the paper is honest about its reliance on Theorem 2.3. I'd send it to review and ask for a proof of Theorem 2.3 and a fuller treatment of the equality cases. A serious reader in extremal set theory will want this in the literature.

Referee Report

3 major / 4 minor

Summary. The paper studies m non-empty cross-intersecting families F_1,...,F_m, where each F_i is contained in C([n],R_i) for a prescribed set R_i of admissible sizes. The main result, Theorem 1.6, gives the maximum of the sum of the family sizes when n is at least the sum of the two largest admissible sizes, and it characterizes all extremal configurations. The upper bound is the maximum of a star bound and a family of two-center bounds; the equality cases include all-star families, M1/M2 two-center constructions, and two special complement-pair and common-intersecting-family cases when n equals k1+k2. The proof combines shifting, lexicographic initial segments, and the generating-set method, extending earlier results of Shi-Frankl-Qian and others.

Significance. If the proof is correct, the result is a substantial common generalization: it answers Problem 1.5 of Shi, Frankl, and Qian and subsumes earlier uniform and non-uniform cross-intersecting results by different methods. The extremal characterization is complete and is stated with no free parameters. The generating-set machinery is applied in a way that yields a clean two-sided candidate bound. However, the proof depends at its first step on Theorem 2.3, a lexicographic initial-segment theorem cited only to an unpublished 1976 manuscript and a Ph.D. thesis; the manuscript gives no proof. Because this theorem is load-bearing, the significance of the paper is somewhat conditional until that gap is closed.

major comments (3)

[Section 2, Theorem 2.3] Theorem 2.3 is the first reduction used in the proof of Theorem 1.6: the proof opens with 'By Theorem 2.3, without loss of generality, we can assume that (F_j)_r is L-initial for all j and r.' The theorem is cited to [7], an unpublished 1976 manuscript, and to [12], a Ph.D. thesis, and no proof is supplied. Since every later step of the proof is built on this reduction, the correctness of the central claim is not independently verifiable from the manuscript as written. The authors should provide a full proof of Theorem 2.3 or replace these citations with a peer-reviewed published source. In addition, because Theorem 2.3 is stated only for two uniform families, the manuscript should justify how it yields the simultaneous L-initiality of all layers of m non-uniform families; a short inductive argument using the already-initial partner is needed.
[Section 3, Lemma 3.1] The assertion |(G_i)_u| = |(G_j)_{l+1-u}| is not established by the proof. For each E in (G_i)_u the argument constructs F = ([l]\E) ∪ {l} in (G_j)_{l+1-u}, which gives an injection in one direction only. The reverse direction is not shown. This equality is used later in the n = k1+k2 analysis, in particular to deduce m = 2, so the argument needs a bijective proof or a different derivation of the required cardinality relation.
[Section 3, proof of Theorem 1.6] The step 'Using n > k1 + k2, we know that each element in F_alpha ... contains 1' appears to exclude the case n = k1+k2, although the theorem is stated for n >= k1+k2. The argument actually works under the stated hypothesis n >= k1+k2 because n-1-a >= k1-1 for every admissible size a <= k2. Please correct the inequality and make explicit that the reduction is valid throughout the stated range; as written, the proof seems to leave the equality case n = k1+k2 outside this part of the argument.

minor comments (4)

[Theorem 1.6, case (iii)] The notation in case (iii) is confusing: the statement writes F1 = C([n],k1) \setminus \overline{F_2} and then says 'here \overline{F_2} is the complement of F_2.' Please define the complement family \overline{F_2} explicitly, e.g., \overline{F_2} = { [n]\B : B in F_2 }, so that the reader does not confuse it with the family F_2 itself.
[Section 1, definition of k_gamma^min] The definition 'k_gamma^min = min{x in R_j : j in [m] \ {gamma}}' is ambiguous because R_j varies with j. It should be written as min{ x : x in R_j for some j != gamma }, i.e., the minimum element of the union of the other R_j.
[Theorem 1.6, equality cases (i) and (ii)] When the star bound and a two-center bound are equal, both structures (i) and (ii) are extremal; the current 'if and only if' statement lists them as alternatives with overlapping hypotheses. It would be clearer to state explicitly that both extremal families occur in the case of equality between the two bounds.
[Section 3, Lemma 3.4] Lemma 3.4 is stated for n > k1+k2, but the main theorem also covers n = k1+k2. The equality discussion in the proof of Lemma 3.4 addresses this case, but the statement of the lemma should explicitly include the full range n >= k1+k2 or explain how the equality case is handled.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main bound is proved from external tools and the only self-cited lemma is proved in the paper.

full rationale

The derivation is self-contained in the relevant sense. The right-hand side of Theorem 1.6 is not a fitted quantity: it is the maximum of sizes of explicit candidate families (the stars S(n,R_j) and the two-center families M1/M2), and the proof supplies an upper bound via left-compression, lexicographic initial segments, generating sets, and log-concavity of binomial coefficients. Lemma 3.1, the only result explicitly said to be analogous to a result in [10], is given a full proof in the paper, so the conclusion is not imported from a self-citation. Theorem 2.3 is load-bearing, but it is cited to an independent unpublished manuscript and a PhD thesis; it is an external input rather than an output of this paper, so reliance on it is a verification-gap concern rather than circularity. No parameter is fitted and no derived quantity is defined in terms of the claimed answer. Therefore no circular step is present.

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

The theorem has no free parameters fitted to data. The central proof rests on standard tools from extremal set theory: lexicographic initialization (Theorem 2.3), monotone completion, log-concavity of binomial coefficients, and the generating set decomposition. No new entities are postulated.

assumptions (4)

standard math Theorem 2.3 (Hilton, Ou): if A and B are cross-intersecting, then their lexicographic initial segments A_L and B_L are also cross-intersecting.
Stated in Section 2 and used at the start of Section 3 to reduce arbitrary maximum families to L-initial families. Cited to an unpublished 1976 manuscript and a 2005 PhD thesis; no proof is included.
domain assumption Replacing a family by its up-set within C([n],R) preserves non-emptiness and cross-intersection and never decreases size.
Used implicitly at the start of Section 3 to assume all F_j are monotone. This is a standard monotonicity fact for cross-intersecting families.
standard math Binomial coefficients are log-concave: C(N,p)C(N,q) < C(N,p+1)C(N,q+1) when p+q+1 <= N.
Used in Case 1 of Section 3 and in Lemma 3.4 to obtain contradictions from inequalities (3) and (6).
standard math In lexicographic order on r-subsets, the first C(n-1,r-1) sets are exactly those containing the element 1.
Used in Section 3 to infer that an L-initial level of size at least C(n-1,r-1) contains every r-set containing 1, which drives the star-reduction argument.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Non-uniform Cross-intersecting Families." pith.science (2026). https://pith.science/paper/K4RKMSY7

@misc{pith2026241118426,
  author       = {Pith},
  title        = {Pith review of: Non-uniform Cross-intersecting Families},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/K4RKMSY7}},
  note         = {Machine review of arXiv:2411.18426}
}

abstract

Let $m\geq 2$, $n$ be positive integers, and $R_i=\{k_{i,1} >k_{i,2} >\cdots> k_{i,t_i}\}$ be subsets of $[n]$ for $i=1,2,\ldots,m$. The families $\mathcal{F}_1\subseteq \binom{[n]}{R_1},\mathcal{F}_2\subseteq \binom{[n]}{R_2},\ldots,\mathcal{F}_m\subseteq \binom{[n]}{R_m}$ are said to be non-empty cross-intersecting if for each $i\in [m]$, $\mathcal{F}_i\neq\emptyset$ and for any $A\in \mathcal{F}_i,B\in\mathcal{F}_j$, $1\leq i<j\leq m$, $|A\bigcap B|\geq1$. In this paper, we determine the maximum value of $\sum_{j=1}^{m}|\mathcal{F}_j|$ for non-empty cross-intersecting family $\mathcal{F}_1, \mathcal{F}_2,\ldots,\mathcal{F}_m$ when $n\geq k_1+k_2$, where $k_1$ (respectively, $k_2$) is the largest (respectively, second largest) value in $\{k_{1,1},k_{2,1},\ldots,k_{m,1}\}$. This result is a generalization of the results by Shi, Frankl and Qian \cite{shi2022non} on non-empty cross-intersecting families. Moreover, the extremal families are completely characterized.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Non-uniform pairwise cross $t$-intersecting families
math.CO 2025-08 unverdicted novelty 7.0 of 10

For m non-empty pairwise cross t-intersecting families, the sum of their sizes is at most max{sum_{k=t to n} binom(n,k) + m-1, m M(n,t)}, with a complete characterization of the extremal families.

Reference graph

Works this paper leans on

14 extracted references · 13 canonical work pages · cited by 1 Pith paper

[7]

A. J. Hilton. The Erd˝ os–Ko–Rado theorem with valency co nditions. Unpublished manuscript, 1976

work page 1976
[12]

Y. Ou. Maximum size t-cross-intersecting and intersecting famil ies with degree condi- tions. ProQuest LLC, Ann Arbor, MI, 2005. Thesis (Ph.D.)–West Vir ginia University

work page 2005
[1]

Ahlswede and L

R. Ahlswede and L. H. Khachatrian. The complete intersec tion theorem for systems of ﬁnite sets. European J. Combin. , 18(2):125–136, 1997

work page 1997
[2]

Borg and C

P. Borg and C. Feghali. The maximum sum of sizes of cross-i ntersecting families of subsets of a set. Discrete Math. , 345(11):Paper No. 112981, 4, 2022

work page 2022
[3]

Erd˝ os, C

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

1961
[4]

P. Frankl. The shifting technique in extremal set theory . In Surveys in combinatorics 1987 (New Cross, 1987) , volume 123 of London Math. Soc. Lecture Note Ser. , pages 81–110. Cambridge Univ. Press, Cambridge, 1987

work page 1987
[5]

Frankl, E

P. Frankl, E. L. L. Liu, J. Wang, and Z. Yang. Non-trivial t-intersecting separated families. Discrete Appl. Math. , 342:124–137, 2024

work page 2024
[6]

Gupta, Y

P. Gupta, Y. Mogge, S. Piga, and B. Sch¨ ulke. r-cross t-intersecting families via necessary intersection points. Bull. Lond. Math. Soc. , 55(3):1447–1458, 2023

work page 2023

Show all 14 references

[8]

A. J. W. Hilton and E. C. Milner. Some intersection theore ms for systems of ﬁnite sets. Quart. J. Math. Oxford Ser. (2) , 18:369–384, 1967

1967
[9]

Huang and Y

Y. Huang and Y. Peng. The maximum sum of sizes of non-empty pairwise cross intersecting families. arXiv:2306.03473, 2023

2023 arXiv
[10]

Li and H

A. Li and H. Zhang. On non-empty cross- t-intersecting families. J. Combin. Theory Ser. A , 210:Paper No. 105960, 2025

2025
[11]

S. Li, D. Liu, D. Song, and T. Yao. The maximum sum of sizes of non-empty cross t-intersecting families. Graphs Combin. , 40(5):Paper No. 103, 2024

2024
[13]

C. Shi, P. Frankl, and J. Qian. On non-empty cross-inter secting families. Combina- torica, 42(suppl. 2):1513–1525, 2022. 12

2022
[14]

Zhang and T

M. Zhang and T. Feng. A note on non-empty cross-intersec ting families. European J. Combin. , 120:Paper No. 103968, 12, 2024. 13

2024

Pith tools

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

[1] [7]

A. J. Hilton. The Erd˝ os–Ko–Rado theorem with valency co nditions. Unpublished manuscript, 1976

work page 1976

[2] [12]

Y. Ou. Maximum size t-cross-intersecting and intersecting famil ies with degree condi- tions. ProQuest LLC, Ann Arbor, MI, 2005. Thesis (Ph.D.)–West Vir ginia University

work page 2005

[3] [1]

Ahlswede and L

R. Ahlswede and L. H. Khachatrian. The complete intersec tion theorem for systems of ﬁnite sets. European J. Combin. , 18(2):125–136, 1997

work page 1997

[4] [2]

Borg and C

P. Borg and C. Feghali. The maximum sum of sizes of cross-i ntersecting families of subsets of a set. Discrete Math. , 345(11):Paper No. 112981, 4, 2022

work page 2022

[5] [3]

Erd˝ os, C

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

1961

[6] [4]

P. Frankl. The shifting technique in extremal set theory . In Surveys in combinatorics 1987 (New Cross, 1987) , volume 123 of London Math. Soc. Lecture Note Ser. , pages 81–110. Cambridge Univ. Press, Cambridge, 1987

work page 1987

[7] [5]

Frankl, E

P. Frankl, E. L. L. Liu, J. Wang, and Z. Yang. Non-trivial t-intersecting separated families. Discrete Appl. Math. , 342:124–137, 2024

work page 2024

[8] [6]

Gupta, Y

P. Gupta, Y. Mogge, S. Piga, and B. Sch¨ ulke. r-cross t-intersecting families via necessary intersection points. Bull. Lond. Math. Soc. , 55(3):1447–1458, 2023

work page 2023