{"id":"ba90964d-8e4a-4e4f-b616-2872518bd622","arxiv_id":"1908.03189","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For t by t split patterns, the new upper bound is n^{2 - 1/t + o(1)}, and for one-sided t-split patterns it is n^{2 - 1/t + 1/(2t^2) + o(1)}.","lead":"This paper proves new upper bounds on how many ones a large grid of zeros and ones can contain without hiding a given forbidden pattern. The results cover patterns with a natural split into parts and give stronger limits for a broad family of grid pictures.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 4's recursion uses a stronger K_{u,t} amplification than Lemma 6 supplies, so the stated k may not yield the claimed N_{u,i} lower bounds; the Theorem 1 proof needs a constant check.","rationale":"The reader identified Claim 11 as the most fragile dependency, and I agree that the recursive verification of Claim 11 is where the proof of Theorem 1 is least secure. My stress-test found a concrete constant mismatch in that verification: Lemma 6 provides a block with u!/(4 r^{u-1} u^u) N/k copies, but Section 4 applies it with u^{u-1} in the denominator and chooses k to match that weaker denominator. With the lemma as stated, the desired inequality N_{u,i+1} >= N_{u,i}/k^{1+delta} is false by a factor U for u=U, and the loss propagates through the recursion used to prove Claim 11. This does not disprove the theorem: the natural repair is to enlarge k by replacing U^{U-1} with U^U, which preserves the claimed exponent because k only affects o(1) terms and 'n sufficiently large' thresholds. But as written, the proof of Theorem 1 has a gap in its central induction. I therefore recommend CONDITIONAL acceptance rather than outright rejection: the authors should correct the constant and re-verify the subsequent estimates.","tokens_in":20354,"tokens_out":28175,"duration_ms":273130,"concrete_test":"Recompute the induction step with u=U using the constant from Lemma 6: check whether N_{U,i+1} >= (U!/(4 r^{U-1} U^U)) N_{U,i}/k >= N_{U,i}/k^{1+delta} holds for the k defined in Section 4. If k^delta = 4 r^{U-1} U^{U-1}/U!, the second inequality fails by a factor U; then rerun the proof with k^delta = 4 r^{U-1} U^U/U! and verify that all Claim 11 estimates remain valid.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 6 concludes that one horizontal block contains at least u!/(4 r^{u-1} u^u) * N/k copies of K_{u,t}. In Section 4, after verifying Claim 11, the proof invokes Lemma 6 and asserts N_{u,i+1} >= (u!/(4 r^{u-1} u^{u-1})) N_{u,i}/k >= N_{u,i}/k^{1+delta}, with k chosen so that k^delta = 4 r^{U-1} U^{U-1}/U!. The middle expression uses u^{u-1}, not u^u. If Lemma 6 is as stated, the correct factor at u=U is k^{-delta}/U, so the recursion loses an extra factor U at every step; the lower bound N_{u,i} >= ... used in Claim 11 is not established with the stated k. Since Claim 11 is the premise for every recursive application of Lemma 6 in Theorem 1, the proof of the exponent 2 - 1/t + 1/(2t^2) + o(1) is not complete as written. This appears fixable by choosing k^delta = 4 r^{U-1} U^U/U! instead, but the current text does not do so.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies extremal numbers of zero-one matrices (equivalently, bipartite ordered graphs) under the containment relation of deleting rows/columns and turning 1s to 0s. The main results are Theorem 1, which asserts that every column-t-partite matrix A satisfies ex(n,A) < n^{2-1/t+1/(2t^2)+o(1)}, and Theorem 2, which improves this to ex(n,A) < n^{2-1/t+o(1)} when A is both row- and column-t-partite. The proofs use a density-increment recursion over horizontal (and, in Theorem 2, vertical) blocks, combined with dependent-random-choice-type counting of K_{u,t} copies. Section 3 proves Theorem 2 via an extension of the block lemma, Section 4 proves Theorem 1 by counting K_{u,t} with a varying u and handling jumps with a copy-amplification lemma, and Section 5 proves ex(n,A)=O(n^{3/2}) for x-monotone cycles. The paper ends with open problems, including a conjecture for matrices with at most t ones per row.","tokens_in":20621,"tokens_out":25001,"duration_ms":231797,"significance":"If correct, Theorem 2 gives the conjectured exponent 2-1/t for the t-by-t-partite case, and Theorem 1 gives the first general upper bound for column-t-partite matrices that is within an additive 1/(2t^2) of the conjectured value; these are natural ordered analogues of the Furedi/Alon-Krivelevich-Sudakov bounds for bipartite graphs of bounded degree in one class. The proof method, a block-based density increment with a K_{u,t} counting lemma and a jump step, is original and the constants are explicit and not fitted to the conclusion. The paper is largely self-contained and includes a clean proof of the ordered-hypergraph lemma (Lemma 5). However, as written, several constant-level errors in Sections 3 and 4 are load-bearing for the main theorems, so the paper needs a substantive revision before the results can be considered established.","major_comments":[{"comment":"The printed definition k = ceil((U!/(4 r^{U-1} U^{U-1}))^{1/delta}) gives k^delta = U!/(4 r^{U-1} U^{U-1}), which is smaller than 1 for every allowed U and r, so after the ceiling one obtains k=1 and the recursive shrinking of Mi fails. What the proof needs is the reciprocal value: after Lemma 6, the factor gained per step is at least u!/(4 r^{u-1} u^u k), so to conclude N_{u,i+1} >= N_{u,i}/k^{1+delta} one requires k^delta >= 4 r^{u-1} u^u / u! for every u <= U, with the worst case u=U. Additionally, the text uses the factor u!/(4 r^{u-1} u^{u-1}) instead of the u^u factor that Lemma 6 actually proves; with the corrected Lemma 6 constant the correct requirement is k^delta >= 4 r^{U-1} U^U / U!. Since Claim 11 is the premise for every application of Lemma 6 in the recursion, this is a load-bearing error: choosing the correct k repairs the proof, but the current text does not.","section":"Section 4, definition of k and application of Lemma 6"},{"comment":"In the jump handling for t+1 <= u <= U, the paper claims the identity u*lambda_u + eps - (1+delta)(lambda_u - lambda_{u+1}) = u*lambda_{u+1} - t/(u+1) + eps - delta. Substituting lambda_u - lambda_{u+1} = t/((u-1)(u+1)) gives (u-1)lambda_u + lambda_{u+1} = u*lambda_{u+1} + t/(u+1), not minus t/(u+1). With the printed minus sign, after applying Lemma 10 the exponent is smaller than the claimed (u+1)lambda_{u+1} + (2u+1)/(2u)*eps by 2t/u, a constant deficit in the exponent that cannot be absorbed by the factor 1/2. Thus the lower bound N_{u+1,i+1} >= n^{(u+1)lambda_{u+1}+eps} does not follow as written. The sign should be plus, after which the jump argument goes through; but this correction must be made explicitly.","section":"Section 4, jump-case exponent after Lemma 10"},{"comment":"The proof of Lemma 9 sets C = 4 s^{t-1} t^t k / t! * C' with C' = max{C(t,t,r,s,k), C(t,t,s,r,k)}. After the first application of Lemma 6 to the horizontal blocks, the block M' contains N' >= t!/(4 r^{t-1} t^t k) * N copies, so with N >= C n^t one gets N' >= (s/r)^{t-1} C' n^t. If r > s, this is smaller than the C' n^t threshold needed to apply the symmetric Lemma 6 a second time. This can be repaired by taking C = 4 max(r,s)^{t-1} t^t k / t! * C' (or by applying the two block directions in the opposite order), but as written the proof of Theorem 2 has a gap whenever A has more rows than columns.","section":"Section 3, Lemma 9 constants"}],"minor_comments":[{"comment":"The definition of vertical block uses the column indices (p-1)m/k+1, ..., pm/k; since the matrix is m x n and columns are indexed up to n, this should use n rather than m.","section":"Definition 2"},{"comment":"In the statement of Claim 7, the set N(i1,i2,...,it) should be N(i1,i2,...,iu); the subscript t appears to be a typo.","section":"Lemma 6, Claim 7"},{"comment":"In Case 1 of Lemma 15, the pigeonhole step says 'there exists i in [r]' but the summation is over the k horizontal blocks; this should be i in [k].","section":"Lemma 15, Case 1"},{"comment":"In the second application of Lemma 6, the matrix M'' is a vertical block of M' (hence a block of the original partition), not a horizontal block of M'; the wording 'horizontal block M''' is a slip.","section":"Lemma 9 proof"}],"recommendation":"major_revision","confidential_remarks":"The constant errors in Sections 3 and 4 look like fixable typos rather than conceptual flaws: the intended definitions and signs are clear from the surrounding calculations. However, they are not merely cosmetic, since the printed k in Section 4 gives k=1 and the jump-case exponent is wrong, so the main proofs are not valid as written. I would ask the authors to correct these constants and re-verify the recursion with explicit computations before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Methuku–Tomon is a real contribution, but I want you to know about a gap in the proof of Theorem 1 before citing it as-is. The paper proves new upper bounds for extremal numbers of ordered bipartite graphs, and the proof technique—layering a density-increment argument on dependent random choice—is the most interesting part. Theorem 2, giving ex(n,A) < n^{2 - 1/t + o(1)} for t x t-partite A, looks correct and essentially settles the exponent for that family. Theorem 13, the O(n^{3/2}) bound for x-monotone cycles, is also new and appears sound. The counting arguments in Sections 2 and 3 are detailed, and I verified the main steps without finding issues.\n\nThe soft spot is Section 4. Lemma 6 is stated and proved with a factor u!/(4 r^{u-1} u^u) per block. But when the proof of Theorem 1 applies the lemma, it writes the factor as u!/(4 r^{u-1} u^{u-1}). The chosen k satisfies k^delta = 4 r^{U-1} U^{U-1}/U!, which would be fine for the stronger factor u^{u-1} but is not enough for what Lemma 6 actually gives. With the lemma as written, each step of the recursion loses an extra factor U, and that propagates through z steps, so the lower bound in Claim 11 is not established. This is exactly the kind of constant slip a referee should catch, and it is fixable—set k^delta = 4 r^{U-1} U^U/U! and the argument goes through. But as written, the proof of Theorem 1 is incomplete. Theorems 2 and 13 are not affected by this.\n\nMinor issues: the vertical block definition uses m instead of n, and the acknowledgment mentions a master thesis but gives no citation. Both are small.\n\nThis paper deserves a serious referee. The reader's ACCEPT is close to my own view, except that I would make acceptance conditional on repairing the Section 4 constants. It should be a major revision, not a rejection, because the core ideas are sound and the gap is technical. I would cite this paper, but only after the fix.","headline":"A solid, genuinely useful paper whose main new exponent for column-t-partite matrices rests on a repairable constant mismatch in the recursion; Theorem 2 and the method itself hold up.","tokens_in":671,"tokens_out":2857,"would_cite":true,"duration_ms":90786,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Column-t-partite zero-one matrices have extremal number at most $n^{2-1/t+1/(2t^2)+o(1)}$, and t×t-partite matrices reach the conjectured exponent $n^{2-1/t+o(1)}$.","keywords":["zero-one matrices","extremal numbers","ordered graphs","Turán numbers","column-t-partite","dependent random choice","density increment","bipartite graphs"],"falsifier":"Take a small column-2-partite matrix $A$ that is not row-2-partite, such as the $4\\times4$ example in Figure 1, and compute $\\mathrm{ex}(n,A)$ for $n = 5,\\dots,15$ by integer programming. If for some fixed $\\varepsilon>0$ any value reaches $n^{13/8+\\varepsilon}$, Theorem 1 as stated is false; if the values stay near $n^{3/2}$ or below, they are consistent with the theorem and with the conjecture that the $+1/(2t^2)$ slack is unnecessary.","tokens_in":20167,"feed_emoji":"📊","tokens_out":15110,"duration_ms":133219,"temperature":0.7,"pith_summary":"The paper proves upper bounds on the maximum number of 1-entries in an $n\\times n$ zero-one matrix that avoids a fixed pattern $A$. For any column-$t$-partite pattern—one that splits into $t$ column bands with at most one 1 per row in each band—the extremal number is below $n^{2-1/t+1/(2t^2)+o(1)}$. For patterns that are $t$-partite in both directions, the stronger bound $n^{2-1/t+o(1)}$ holds, matching the exponent conjectured for the one-sided case. These are ordered analogues of classical Turán-type results for bipartite graphs with bounded degree in one class, and the proofs combine a density-increment recursion with dependent random choice.","feed_headline":"Near-optimal bound for forbidden t-partite zero-one matrices","feed_subtitle":"Column-t-partite patterns cap 1-entries near n^(2-1/t); fully t-partite ones hit the conjectured exponent.","key_machinery":"The central mechanism is a density-increment lemma (Lemma 6) that counts copies of $K_{u,t}$ in an $m\\times n$ matrix avoiding $A$. If many such copies exist, then one of $k$ horizontal blocks contains a density of $K_{u,t}$ copies amplified by a constant factor; the proof uses a dependent random choice-style double counting of 'light' $K_{u,t}$ copies split by the horizontal blocks that witness them, together with a hypergraph lemma (Lemma 5) that bounds the number of edges in an interval $t$-partite hypergraph with no complete $t$-partite subhypergraph. Lemma 10 amplifies $K_{u,t}$ counts to $K_{u+1,t}$ counts, and Claim 11 verifies that throughout the recursion the count stays large enough for Lemma 6 to apply. In the $t\\times t$-partite case, Lemma 9 applies the same block restriction in both dimensions, producing a $k^2$-block density increment.","core_discovery":"The central discovery is that the extremal number of a forbidden zero-one matrix is controlled by its partiteness in the column direction, and that restricting to submatrices that are $t$-partite in both directions yields the conjectured exponent. Concretely, Theorem 1 states $\\mathrm{ex}(n,A) < n^{2-1/t+1/(2t^2)+o(1)}$ for every column-$t$-partite $A$, and Theorem 2 states $\\mathrm{ex}(n,A) < n^{2-1/t+o(1)}$ for every $t\\times t$-partite $A$. The proof constructs a nested sequence of submatrices, each a horizontal (or vertical) block of the previous one, and forces the density of complete bipartite patterns $K_{u,t}$ to grow geometrically while the matrix shrinks; the contradiction is that a $1\\times n$ or $1\\times 1$ matrix cannot hold the mandated number of such patterns. Theorem 13 adds that every $x$-monotone cycle matrix has extremal number $O(n^{3/2})$.","pith_inferences":["The slack $1/(2t^2)$ in Theorem 1 is likely an artifact of the copy-count amplification (Lemma 10); replacing it with a lossless count of $K_{u,t}$ copies would remove the slack and prove the conjectured exponent for column-$t$-partite matrices.","The $u$-varying recursion of Section 4—where the tracked parameter $u$ rises as the matrix shrinks—should extend to matrices with at most $t$ ones per row, which is exactly the open Conjecture 16; the authors note their method works for a large class but not all such matrices.","For ordered cycles, Theorem 13 suggests the extremal number is governed by geometric $x$-monotonicity rather than cycle length; if true, non-monotone cycles would be the natural candidates for larger extremal numbers, and settling the $\\Theta(n^{4/3})$ conjecture for all 6-cycles would require breaking this geometric constraint.","The telescoping identity used to define the decreasing exponent sequence $\\lambda_u$ is a purely algebraic device; the same recursion style could set exponents for other extremal problems on ordered structures with a layered partiteness condition."],"forward_implications":["For every column-$t$-partite matrix $A$, $\\mathrm{ex}(n,A) < n^{2-1/t+1/(2t^2)+o(1)}$; in particular, for $t=2$ this is $n^{13/8+o(1)}$.","For every $t\\times t$-partite matrix $A$, $\\mathrm{ex}(n,A) < n^{2-1/t+o(1)}$, which is sharp up to the $o(1)$ term provided the lower bound $\\mathrm{ex}(n,K_{t,t})=\\Theta(n^{2-1/t})$ holds.","The $t\\times t$ case covers all $2\\times2$-partite matrices, so patterns corresponding to disjoint unions of cycles have extremal number at most $n^{3/2+o(1)}$.","Every $x$-monotone cycle matrix $A$ satisfies the stronger bound $\\mathrm{ex}(n,A)=O(n^{3/2})$ (Theorem 13), complementing the $t=2$ case of Theorem 2.","Because ordered bipartite graphs correspond to zero-one matrices, these bounds carry over to ordered Turán numbers: an ordered bipartite graph whose bi-adjacency matrix is column-$t$-partite has ordered extremal number at most $n^{2-1/t+1/(2t^2)+o(1)}\\log n$."],"supporting_citations":[{"why":"Supplies the dependent random choice method and the unordered result for bipartite graphs with maximum degree $t$ in one class that motivates Theorems 1 and 2.","marker":"[1]"},{"why":"Establishes the unordered extremal bound $O(n^{2-1/t})$ for bipartite graphs with maximum degree $t$ in one class, the model case the paper extends to ordered graphs.","marker":"[9]"},{"why":"Gives the standard extremal bound for complete bipartite graphs, cited to show the exponent in Theorem 1 cannot be smaller than $2-1/t$.","marker":"[17]"},{"why":"Provides the dictionary between ordered graph Turán numbers and zero-one matrix extremal numbers, and the positive-cycle theorem used in Section 5.","marker":"[16]"},{"why":"The hypergraph density theorem used inside Lemma 5 to force a complete $t$-partite subhypergraph in a dense interval $t$-partite hypergraph.","marker":"[7]"},{"why":"Provides the background on column-1-partite matrices and the conjectures for acyclic matrices that motivate the $t$-partite definitions.","marker":"[10]"},{"why":"Gives the linear bound for permutation ($1\\times1$-partite) matrices, the base case for the extremal exponents studied here.","marker":"[18]"}],"fun_headline_variants":["T-partite zero-one matrices: near-optimal extremal bounds","Column-t-partite patterns cap 1-entries near n^(2-1/t)","Forbidden t-partite ordered graphs: new extremal bounds","Dependent random choice sharpens t-partite matrix bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The recursion collapses unless at every step the chosen submatrix contains at least $C\\max\\{(n/k^i)^u, n^t\\}$ copies of the complete bipartite pattern $K_{u,t}$; this retention bound, verified as Claim 11, is the load-bearing premise.","fun_headline_variants_meta":{"raw":{"variants":["T-partite zero-one matrices: near-optimal extremal bounds","Column-t-partite patterns cap 1-entries near n^(2-1/t)","Forbidden t-partite ordered graphs: new extremal bounds","Dependent random choice sharpens t-partite matrix bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000951,"raw_usage":{"total_tokens":4169,"prompt_tokens":1170,"completion_tokens":2999,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":786,"completion_tokens_details":{"reasoning_tokens":2923}},"tokens_in":786,"tokens_out":2999,"duration_ms":23457,"temperature":1.0,"reasoning_tokens":2923,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:21:40.855495+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small column-2-partite matrix $A$ that is not row-2-partite, such as the $4\\times4$ example in Figure 1, and compute $\\mathrm{ex}(n,A)$ for $n = 5,\\dots,15$ by integer programming. If for some fixed $\\varepsilon>0$ any value reaches $n^{13/8+\\varepsilon}$, Theorem 1 as stated is false; if the values stay near $n^{3/2}$ or below, they are consistent with the theorem and with the conjecture that the $+1/(2t^2)$ slack is unnecessary.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the dependent random choice method and the unordered result for bipartite graphs with maximum degree $t$ in one class that motivates Theorems 1 and 2."},{"cited_title":"F¨ uredi,On a Tur´ an type problem of Erd˝ os.Combinatorica, 11 (1) (1991): 75–79","cited_arxiv_id":null,"evidence_quote":"Establishes the unordered extremal bound $O(n^{2-1/t})$ for bipartite graphs with maximum degree $t$ in one class, the model case the paper extends to ordered graphs."},{"cited_title":"K˝ ov´ ari, V","cited_arxiv_id":null,"evidence_quote":"Gives the standard extremal bound for complete bipartite graphs, cited to show the exponent in Theorem 1 cannot be smaller than $2-1/t$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the dictionary between ordered graph Turán numbers and zero-one matrix extremal numbers, and the positive-cycle theorem used in Section 5."},{"cited_title":"Erd˝ os, On extremal problems of graphs and generalized graphs, Israel J","cited_arxiv_id":null,"evidence_quote":"The hypergraph density theorem used inside Lemma 5 to force a complete $t$-partite subhypergraph in a dense interval $t$-partite hypergraph."},{"cited_title":"F¨ uredi, P","cited_arxiv_id":null,"evidence_quote":"Provides the background on column-1-partite matrices and the conjectures for acyclic matrices that motivate the $t$-partite definitions."},{"cited_title":"Marcus, G","cited_arxiv_id":null,"evidence_quote":"Gives the linear bound for permutation ($1\\times1$-partite) matrices, the base case for the extremal exponents studied here."}],"review_version":1}