{"id":"15dbb993-1a3a-4608-bc7c-c48c7a781a17","arxiv_id":"1908.05983","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Exact Turán numbers are determined for k disjoint s-cliques and r-cliques in r-partite s-uniform hypergraphs, and for counting s-cliques in kK_r-free r-partite graphs, under explicit size conditions.","lead":"This paper works out the exact maximum number of edges a multi-part hypergraph can have while avoiding k disjoint complete clusters, in three related problem settings. It matters to combinatorics because it generalizes known graph theorems to hypergraphs and connects to the Erdős matching conjecture, a long-standing open problem.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader identified the shifting/stable-world machinery as the weakest assumption. I examined Lemma 2.2 closely and found its proof complete: the argument that at most one edge in a shifted matching is new, and the replacement step yielding a larger matching in the original graph, is valid. Termination by a decreasing integer potential is also valid. The only real gap is the unstated exclusion of t=0 before dividing in Lemma 2.3, which is immediately resolved by the strict inequality (2.1) and therefore does not threaten the proof. I also checked the long case analysis of Lemma 2.3, the induction recurrences of Theorem 1.3, and the LP arguments of Theorems 1.4-1.6; no internally inconsistent step surfaced. The paper's mathematics appears correct, with minor presentational issues only, so the reader's CONDITIONAL verdict does not need to be changed on the basis of a load-bearing concern.","tokens_in":23084,"tokens_out":54585,"duration_ms":462054,"concrete_test":"Independently re-derive equation (2.12) from (2.10) and (2.1) for the r=s+1 case of Lemma 2.3, verifying the cancellation and the final bound n ≤ s^2 k/2 + s^2(s-2)k^2 ≤ s^3k^2. If the cancellation or the final inequality fails, the balanced base case of Theorem 1.3 would be unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing flaw found in the central argument. Theorem 1.3 relies on Lemma 2.2, and the proof of that lemma is correct for the r-partite partial order: in a (k+1)-matching of the shifted graph, at most one edge can be new, and replacing its u with v yields a matching of size k+1 in the original graph. Termination of iterative shifting via the strictly decreasing potential g is valid. The t=0 division in Lemma 2.3 Case 2 is an exposition gap rather than a logical gap: when t=0, strict inequality (2.1) immediately contradicts the bound |Γ(T0)|≤(k-1)binom(r-1,s-1)n^{s-1}. The algebra in Cases 2.1 and 2.2 checks out, including the improved r=s+1 estimate. The WLOG choice i=r in the inductive step of Theorem 1.3 is justified by symmetry and re-sorting of parts after deleting a vertex. The probabilistic arguments in Theorems 1.4-1.6 and their LP bounds are also consistent. The only issues are presentational: unstated handling of t=0, a stronger-than-needed abstract condition, and typos.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper determines three Turán-type extremal numbers for vertex-disjoint cliques in r-partite s-uniform hypergraphs. Its central result, Theorem 1.3, gives the exact value of ex_s(K_{n_1,\\ldots,n_r}^{(s)}, kK_s^{(s)}) for sufficiently large n_1, with the extremal construction consisting of all edges that touch a fixed (k-1)-subset of the first part. The companion Theorems 1.4--1.6 determine ex_s(K_{n_1,\\ldots,n_r}^{(s)}, kK_r^{(s)}) for k ≤ n_1 and the generalized Turán number ex(K_{n_1,\\ldots,n_r}, K_s, kK_r) under two sets of conditions. The proofs combine shifting/stability arguments, a decomposition of the complete r-partite r-graph into matchings, a probabilistic linear-programming argument, and a rainbow-matching bound imported from Glebov--Sudakov--Szabó. The paper also supplies a self-contained proof of the previously unpublished Theorem 1.1 of De Silva--Heysse--Young in an appendix.","tokens_in":23032,"tokens_out":16305,"duration_ms":148049,"significance":"If correct, the results give exact multipartite analogues of the Erdős matching conjecture in a substantial range, and they unify several previously known graph results: Theorem 1.3 specializes to Theorem 1.1 when s=2 and to Lemma 2.1 when s=r, and Theorem 1.4 recovers the r-uniform case. These external consistency checks are a genuine strength, as are the self-contained proofs of the shifting lemma and of Theorem 1.1. The probabilistic LP method is elegant and likely useful beyond this paper. I checked the boundary cases s=2 and s=r, the LP optimality argument, and the recurrences in the induction steps, and the algebra is internally consistent. The main concern is a missing t=0 case in the proof of Lemma 2.3; it is local and repairable, but it is load-bearing for Theorem 1.3 and the written proof is incomplete at that point.","major_comments":[{"comment":"The proof divides by t after combining inequality (2.1) with the bounds (2.2) and (2.7): inequality (2.3) is obtained from the preceding display by dividing by t, and inequality (2.8) is similarly obtained by dividing by t. However t = ν(H \\setminus T_0) may be zero, in which case these divisions are invalid and the displayed conclusions become 0 ≤ 0. This is not a purely cosmetic issue, because (2.3) and (2.8) are the steps that produce the required contradiction. The authors should add a short separate treatment of t=0: in that case Claim 4 gives ν(H \\setminus X) = 0, and since Y is nonempty, no edge of H \\setminus X can contain a vertex of Y; hence every edge of H intersects X, so |Γ(T0)| ≤ |X| binom(r-1,s-1) n^{s-1} = (k-1) binom(r-1,s-1) n^{s-1}, contradicting (2.1). This repair is straightforward, but the proof as written is incomplete.","section":"Section 2, Lemma 2.3, Case 2"}],"minor_comments":[{"comment":"The statement defines a = w_{M+1}(b-M), but if b ≥ N then M = N and w_{N+1} is undefined. In the applications one has b < binom(r,s), so the intended range is sufficient, but the lemma should explicitly assume b < N or handle the boundary case separately.","section":"Section 3, Lemma 3.1"},{"comment":"The abstract states the condition n_1 ≥ s^3 k^2 + sr for Theorem 1.3, whereas the theorem itself only requires n_1 ≥ s^3 k + sr when s ≤ r-2. The abstract should either match the theorem or explicitly say that it states a simplified stronger sufficient condition.","section":"Abstract and Theorem 1.3"},{"comment":"In both displayed equations the second conditional expectation is written as E(X(T)|A_T)Pr(A_T); it should be E(X(T)|\\overline{A_T})Pr(\\overline{A_T}). The intended meaning is clear from the context, but the notation should be corrected.","section":"Equations (3.2) and (4.2)"},{"comment":"The proof uses the bounds n ≥ 2s^2k in Claim 1 and n ≥ 3s^2k in Claim 2 without stating them as hypotheses of Lemma 2.3. These follow from the stated assumptions n ≥ s^3k + sr for s ≥ 3, but it would be clearer to derive them explicitly before use.","section":"Section 2, Lemma 2.3, Claims 1 and 2"},{"comment":"The lower-bound construction for the generalized Turán number is described and shown to be kK_r-free, but the text does not explicitly count the number of K_s copies it contains. Adding this short count would make the lower bound transparent rather than left to the reader.","section":"Sections 4, lower bounds for Theorems 1.5 and 1.6"}],"recommendation":"major_revision","confidential_remarks":"The missing t=0 case in Lemma 2.3 is a genuine gap in the written proof of the main theorem, but it has a short, clear fix and does not appear to threaten the result. The shifting concern raised in the stress-test does not land: Lemma 2.2 is correct and the termination argument via the decreasing potential is valid. I would be satisfied after the authors repair the t=0 case and address the minor presentation issues."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid exact Turán paper. Theorems 1.3–1.6 give exact values for three multipartite hypergraph Turán problems that were only known in the graph (s=2) and r-uniform cases. The headline is Theorem 1.3, a multipartite analogue of the Erdős matching conjecture under n1 ≥ s^3k + sr (or s^3k^2 + sr when s=r-1). The extremal construction is the obvious one — hold back a (k-1)-subset of the first part — and the work is in proving it is optimal.\n\nWhat is new: the s≥3 cases and the generalized Turán counts. I checked the boundary specializations: s=2 recovers De Silva et al., s=r recovers Aharoni–Howard, and the recurrences for f, g, h line up. The proof of Lemma 2.1 partitions the complete r-partite r-graph into n2...nr matchings of size n1, which is clean. The LP lemma (Lemma 3.1) is correct, and the lower-bound constructions saturate it. Theorem 1.6's rainbow-matching import from Glebov–Sudakov–Szabó is properly cited, and the threshold n4 ≥ r^r(k-1)k^{2r-2} matches their bound.\n\nSoft spots are mostly presentational. In Lemma 2.3, Case 2 divides by t without saying what happens when t=0; the strict inequality (2.1) gives an immediate contradiction, so the argument survives, but it should be stated. The abstract promises n1 ≥ s^3k^2 + sr uniformly, while the body only needs the weaker n1 ≥ s^3k + sr for s ≤ r-2. There are typos ('n1n1' for 'n1n2') and accented-character corruption in the PDF. The proof depends on Frankl's shifting lemma (Lemma 2.2); the single-swap proof is included and the termination argument via a decreasing potential is fine, so this is not a gap, just a reminder that the whole induction lives in the stable world.\n\nThe citation pattern looks honest. Theorem 1.1 is re-proved in the appendix because the De Silva–Heysse–Young preprint is hard to find, and all imported results are explicit. I found no circularity: lower bounds are deletion constructions, upper bounds are independent counting.\n\nWho this is for: anyone working on multipartite Turán problems or Erdős matching conjecture variants. It advances a small but active area, and it deserves a serious referee. I would send it to review, asking only for the t=0 case to be stated and the abstract/body condition mismatch fixed.","headline":"A solid exact Turán paper that genuinely extends the known graph and r-uniform results to s-uniform multipartite hypergraphs; refereeable after minor presentational fixes.","tokens_in":23881,"tokens_out":1849,"would_cite":true,"duration_ms":15915,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C65"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves exact formulas for the maximum number of edges avoiding k vertex-disjoint cliques in r-partite s-uniform hypergraphs, including a multipartite analogue of the Erdős matching conjecture and two related Turán problems.","keywords":["Turán number","multi-partite hypergraphs","Erdős matching conjecture","shifting technique","probabilistic argument","generalized Turán number","vertex-disjoint cliques","rainbow matching"],"falsifier":"For parameters satisfying the stated inequalities, exhibit any $kK^{(s)}_s$-free subgraph of $K^{(s)}_{n_1,\\ldots,n_r}$ with more than $(k-1)\\sum_{A \\subset [2,r], |A|=s-1} n_A$ edges; for example, at the smallest open parameter point $s=3, r=4, k=2, n_1=n_2=n_3=n_4=70$, this means deciding by search or integer programming whether a 3-partite 3-graph on four parts of size 70 can have more than $14{,}700$ edges and no two disjoint edges.","tokens_in":22607,"feed_emoji":"🧮","tokens_out":12009,"duration_ms":115441,"temperature":0.7,"pith_summary":"This paper is about Turán-type extremal problems in multipartite hypergraphs: given an r-partite host hypergraph whose edges choose at most one vertex from each of r parts, how many edges can a subgraph have if it contains no k vertex-disjoint copies of a fixed clique? The paper answers this exactly for three families of forbidden configurations. For k disjoint s-vertex cliques, which form a matching of size k, it determines the extremal number whenever the smallest part is at least a polynomial in s and k, giving a multipartite analogue of the Erdős matching conjecture. For k disjoint r-vertex cliques, it gives an exact formula for all k at most the size of the smallest part. It also gives exact counts of s-cliques in subgraphs of r-partite graphs that contain no k disjoint copies of the complete graph K_r, under two explicit size regimes.","feed_headline":"Exact edge counts for disjoint cliques in multipartite hypergraphs","feed_subtitle":"Exact answers for avoiding k disjoint cliques in r-partite hypergraphs, from matchings to clique counts.","key_machinery":"The proof rests on three mechanisms. First, a left-shifting operator $S_{uv}$ replaces a vertex $v$ by an earlier vertex $u$ in the same part when that does not create an existing edge; repeated application yields a stable graph with the same edge count and no larger matching number, so the extremal graph can be assumed closed under replacing vertices by earlier ones. Inside this stable world, the proof of Theorem 1.3 isolates the first vertex of each part, separates high- and low-degree vertices, shows every edge must touch $V_1$, and finishes with a double-counting argument over $r$-element transversals. A base lemma partitions the edge set of $K^{(r)}_{n_1,\\ldots,n_r}$ into $n_2\\cdots n_r$ matchings of size $n_1$, which drives the $s=r$ base case. Second, Theorems 1.4 and 1.5 use a probabilistic argument: choose one random vertex from each part, count the expected number of edges or $s$-cliques in the random $r$-set, upper-bound the expectation by the probability of hitting a $K_r$, and then solve a small linear program whose optimal value is the claimed formula. Third, Theorem 1.6 uses a rainbow-matching result: if every vertex of the last part creates $k$ disjoint $(r-1)$-cliques, those cliques form a colored $(r-1)$-graph whose rainbow matching would build a forbidden $kK_r$.","core_discovery":"The central discovery is that in each setting the natural ``put all edges through a small set'' construction is optimal. Theorem 1.3 states that for $2 \\leq s \\leq r$ and $n_1 \\leq \\cdots \\leq n_r$, if $n_1 \\geq s^3 k + sr$ for $s \\leq r-2$, or $n_1 \\geq s^3 k^2 + sr$ for $s = r-1$, or $n_1 \\geq k$ for $s = r$, then $\\operatorname{ex}_s(K^{(s)}_{n_1,\\ldots,n_r}, kK^{(s)}_s) = (k-1)\\sum_{A \\subset [2,r], |A|=s-1} n_A$. The extremal graph keeps exactly the edges that meet a fixed $(k-1)$-subset of the first part, and no larger graph can avoid $k$ disjoint $s$-cliques. Theorem 1.4 gives $\\operatorname{ex}_s(K^{(s)}_{n_1,\\ldots,n_r}, kK^{(s)}_r) = \\sum_{|A|=s} n_A - n_{[s]} + (k-1)n_{[2,s]}$ for $k \\leq n_1$, with the extremal graph obtained by deleting all edges between a large subset of $V_1$ and $V_2$. Theorems 1.5 and 1.6 give exact values for the generalized Turán problem of maximizing the number of $K_s$ copies in a $kK_r$-free subgraph of an $r$-partite graph, the second using the condition $n_4 \\geq r^r(k-1)k^{2r-2}$.","pith_inferences":["Beyond the paper's claims, the thresholds $n_1 \\geq s^3 k$ and $n_1 \\geq s^3 k^2$ appear to be artifacts of the induction and double-counting estimates; a natural next step is to determine the smallest $n_1$ for which the same extremal construction remains optimal.","The linear-programming lemma is generic: for any fixed forbidden family whose obstruction is controlled by the probability that a random $r$-set contains a forbidden clique, the same recipe should yield exact answers for shapes other than $K_r$.","Because the extremal graphs concentrate all edges on a small subset of the first part, the results suggest a strong stability property: every near-extremal $kK_s$-free subgraph must have most of its edges touching a small subset of $V_1$, which could be formulated as a stability theorem.","The rainbow-matching step only requires $n_4 \\geq r^r(k-1)k^{2r-2}$; replacing it with a stronger rainbow-matching bound would immediately widen the range of Theorem 1.6."],"forward_implications":["For $s = r$, Theorem 1.3 yields $\\operatorname{ex}_r(K^{(r)}_{n_1,\\ldots,n_r}, kK^{(r)}_r) = (k-1)n_2\\cdots n_r$, so the edge partition into $n_2\\cdots n_r$ matchings is optimal.","For $s = 2$, the results recover the known exact formulas for $\\operatorname{ex}(K_{n_1,\\ldots,n_r}, kK_2)$ and $\\operatorname{ex}(K_{n_1,\\ldots,n_r}, kK_r)$ as special cases.","The explicit formulas in Theorems 1.5 and 1.6 show that, for large enough last parts, the number of $K_s$ copies in a $kK_r$-free $r$-partite graph is maximized by a graph that is nearly complete except for all edges between a large subset of $V_1$ and $V_2$.","The hypotheses on $n_1$ are explicit polynomials in $s$ and $k$, giving effective ranges where the multipartite Erdős matching analogue holds exactly rather than asymptotically."],"supporting_citations":[{"why":"Supplies the decomposition of the complete $r$-partite $r$-graph edge set into $n_2\\cdots n_r$ matchings of size $n_1$, used in the base case of Theorem 1.3 and in bounding the number of $K_r$ copies.","marker":"[1]"},{"why":"Determines the graph case $s=2$ for two of the problems, providing the base case for the inductions and the exact formulas being generalized.","marker":"[6]"},{"why":"Proves that a left-shift operation does not increase the matching number, justifying the restriction to stable extremal graphs that carries the proof of Theorem 1.3.","marker":"[9]"},{"why":"Supplies the upper bound on rainbow matchings in colored uniform hypergraphs that drives the proof of Theorem 1.6.","marker":"[13]"}],"fun_headline_variants":["Exact Turán numbers for vertex-disjoint cliques in multipartite hypergraphs","Avoiding k disjoint cliques: exact edge counts in multipartite hypergraphs","Optimal subgraphs without k disjoint cliques in r-partite hypergraphs","Exact bounds for disjoint cliques in multi-partite hypergraphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument for Theorem 1.3 assumes the extremal graph can be taken stable under left-shifts, swapping a vertex for an earlier vertex in the same part without increasing the largest matching size, and every structural step in the proof depends on that stability.","fun_headline_variants_meta":{"raw":{"variants":["Exact Turán numbers for vertex-disjoint cliques in multipartite hypergraphs","Avoiding k disjoint cliques: exact edge counts in multipartite hypergraphs","Optimal subgraphs without k disjoint cliques in r-partite hypergraphs","Exact bounds for disjoint cliques in multi-partite hypergraphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000341,"raw_usage":{"total_tokens":2098,"prompt_tokens":1385,"completion_tokens":713,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":1001,"completion_tokens_details":{"reasoning_tokens":629}},"tokens_in":1001,"tokens_out":713,"duration_ms":6597,"temperature":1.0,"reasoning_tokens":629,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:04:03.158769+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For parameters satisfying the stated inequalities, exhibit any $kK^{(s)}_s$-free subgraph of $K^{(s)}_{n_1,\\ldots,n_r}$ with more than $(k-1)\\sum_{A \\subset [2,r], |A|=s-1} n_A$ edges; for example, at the smallest open parameter point $s=3, r=4, k=2, n_1=n_2=n_3=n_4=70$, this means deciding by search or integer programming whether a 3-partite 3-graph on four parts of size 70 can have more than $14{,}700$ edges and no two disjoint edges.","supporting_citations":[{"cited_title":"Aharoni and D","cited_arxiv_id":null,"evidence_quote":"Supplies the decomposition of the complete $r$-partite $r$-graph edge set into $n_2\\cdots n_r$ matchings of size $n_1$, used in the base case of Theorem 1.3 and in bounding the number of $K_r$ copies."},{"cited_title":"De Silva, K","cited_arxiv_id":null,"evidence_quote":"Determines the graph case $s=2$ for two of the problems, providing the base case for the inductions and the exact formulas being generalized."},{"cited_title":"Frankl, The shifting technique in extremal set theory , Surv","cited_arxiv_id":null,"evidence_quote":"Proves that a left-shift operation does not increase the matching number, justifying the restriction to stable extremal graphs that carries the proof of Theorem 1.3."},{"cited_title":"Glebov, B","cited_arxiv_id":null,"evidence_quote":"Supplies the upper bound on rainbow matchings in colored uniform hypergraphs that drives the proof of Theorem 1.6."}],"review_version":1}