{"id":"482e9cb2-f161-416b-a8bd-1b242a2ba00f","arxiv_id":"2411.18426","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper determines the maximum total size of m non-empty pairwise cross-intersecting families with arbitrary allowed set sizes when n is at least the sum of the two largest allowed sizes, and characterizes all extremal families.","lead":"This paper finds the maximum possible total number of sets in several families of subsets of a finite set, under the rule that any two sets from different families must share at least one element, and where each family may contain sets of several different sizes. It generalizes earlier results to any number of families and to arbitrary allowed set sizes, and it describes all structures that achieve the maximum.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.3 is load-bearing and unproved: the entire reduction to L-initial families depends on it, with only an unpublished 1976 manuscript and a 2005 thesis cited; a self-contained proof is needed.","rationale":"The proof is coherent conditional on Theorem 2.3. I checked the main reductions: the simultaneous use of Theorem 2.3 on each pair of levels is legitimate because lexicographic initial segments are defined independently for each family and the theorem applies pairwise; the monotone and left-compressed reductions are compatible; the generating-set lemmas are internally consistent; and the binomial log-concavity inequalities appear valid under n >= k1+k2. The weakest point is exactly the unproved compression theorem, which the reader's weakest_assumption also identifies. I found no counterexample and no circular argument. Because the theorem is essential and not proved in the paper, I would accept only conditional on adding a proof or a citable peer-reviewed reference for Theorem 2.3; this does not amount to rejection.","tokens_in":12472,"tokens_out":30801,"duration_ms":283252,"concrete_test":"Enumerate all cross-intersecting pairs (A,B) for n <= 8 and all k1,k2, and check whether their lexicographic initial segments A_L and B_L are always cross-intersecting; if no counterexample appears, obtain or write a complete proof of Theorem 2.3 from the shifting literature and include it in the paper, or replace the unpublished citations with a peer-reviewed reference. This settles whether the initial reduction step is sound.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Theorem 1.6 opens with: \"By Theorem 2.3, without loss of generality, we can assume that (F_j)_r is L-initial for all j in [m] and r in R_j.\" Theorem 2.3 is a two-family compression result for uniform lexicographic initial segments, and every later step—the choice of {1} in G_gamma, the generating-set lemmas, and the extremal classification—is built on this reduction. The paper does not prove Theorem 2.3; it cites [7], an unpublished 1976 manuscript, and [12], a Ph.D. thesis. If the theorem were false or misstated, the main theorem would collapse. The theorem is probably true and standard, but because the manuscript makes it load-bearing without proof or a peer-reviewed citation, the correctness of the central argument is not independently verifiable from the paper alone. This is a verification gap rather than a demonstrated counterexample.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12617,"tokens_out":18974,"duration_ms":170414,"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":[{"comment":"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":"Section 2, Theorem 2.3"},{"comment":"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":"Section 3, Lemma 3.1"},{"comment":"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.","section":"Section 3, proof of Theorem 1.6"}],"minor_comments":[{"comment":"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":"Theorem 1.6, case (iii)"},{"comment":"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.","section":"Section 1, definition of k_gamma^min"},{"comment":"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":"Theorem 1.6, equality cases (i) and (ii)"},{"comment":"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.","section":"Section 3, Lemma 3.4"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is likely correct, but the verification gap around Theorem 2.3 is real: the theorem is cited to an unpublished manuscript and a thesis, and the proof of the main result collapses without it. I would be willing to accept after the authors add a self-contained proof of Theorem 2.3 (or a published reference) and clarify the multi-family reduction. The cardinality equality in Lemma 3.1 also needs a proof. These are fixable within the scope of the manuscript, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nThe 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.\n\nNet: 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.","headline":"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.","tokens_in":13205,"tokens_out":4333,"would_cite":true,"duration_ms":37861,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["non-empty cross-intersecting families","non-uniform families","Erdős–Ko–Rado theorem","generating set method","shifting method","lexicographic initial segments","extremal set theory","sum of sizes"],"falsifier":"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.","tokens_in":12233,"feed_emoji":"🧩","tokens_out":12801,"duration_ms":107337,"temperature":0.7,"pith_summary":"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.","feed_headline":"Two shapes maximize cross-intersecting family size","feed_subtitle":"For any number of non-uniform set families, the exact bound is a star or a small-set anchor.","key_machinery":"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$.","core_discovery":"The central theorem states that under $n\\ge k_1+k_2$,\n$$\\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\\},$$\nwhere $\\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}$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the generating-set method and the basic properties of generating families used throughout the proof.","marker":"[1]"},{"why":"One of the two cited sources for Theorem 2.3, the lex-initial preservation step on which the reduction to L-initial families depends.","marker":"[7]"},{"why":"The other cited source for Theorem 2.3; the paper does not prove this theorem, so this reference carries the reduction.","marker":"[12]"},{"why":"The uniform case that the main theorem generalizes and the source of the open problem answered here.","marker":"[13]"},{"why":"The earlier two-family non-uniform result with all sizes up to prescribed bounds, used as a comparison point and motivating baseline.","marker":"[2]"},{"why":"Provides the analogue of the boundary-generating-family lemma that drives the pairing argument in the proof.","marker":"[10]"},{"why":"One of the independent proofs of the singleton-uniform inequality that Theorem 1.6 contains as a special case.","marker":"[9]"},{"why":"The other independent proof of that inequality, giving the comparison point for the new general bound.","marker":"[14]"}],"fun_headline_variants":["Two shapes maximize cross-intersecting sums","Stars or small-set anchors cap family size","Exact max for non-uniform cross-intersecting families","Cross-intersecting families: best is star or anchor","Optimal non-uniform cross-intersecting families found"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Two shapes maximize cross-intersecting sums","Stars or small-set anchors cap family size","Exact max for non-uniform cross-intersecting families","Cross-intersecting families: best is star or anchor","Optimal non-uniform cross-intersecting families found"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000291,"raw_usage":{"total_tokens":1818,"prompt_tokens":1182,"completion_tokens":636,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":798,"completion_tokens_details":{"reasoning_tokens":562}},"tokens_in":798,"tokens_out":636,"duration_ms":5774,"temperature":1.0,"reasoning_tokens":562,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:14:29.482665+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Ahlswede and L","cited_arxiv_id":null,"evidence_quote":"Supplies the generating-set method and the basic properties of generating families used throughout the proof."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"One of the two cited sources for Theorem 2.3, the lex-initial preservation step on which the reduction to L-initial families depends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The other cited source for Theorem 2.3; the paper does not prove this theorem, so this reference carries the reduction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The uniform case that the main theorem generalizes and the source of the open problem answered here."},{"cited_title":"Borg and C","cited_arxiv_id":null,"evidence_quote":"The earlier two-family non-uniform result with all sizes up to prescribed bounds, used as a comparison point and motivating baseline."},{"cited_title":"Li and H","cited_arxiv_id":null,"evidence_quote":"Provides the analogue of the boundary-generating-family lemma that drives the pairing argument in the proof."},{"cited_title":"Non-empty pairwise cross-intersecting families","cited_arxiv_id":"2306.03473","evidence_quote":"One of the independent proofs of the singleton-uniform inequality that Theorem 1.6 contains as a special case."},{"cited_title":"Zhang and T","cited_arxiv_id":null,"evidence_quote":"The other independent proof of that inequality, giving the comparison point for the new general bound."}],"review_version":1}