{"id":"2a6a85c6-1c5b-4ad2-942b-17e8db8ffba4","arxiv_id":"2607.23928","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"For bipartite graphs avoiding matchings/co-matchings of size t, the paper gives a valid ~√t/4^t lower bound for pure pairs but an unproven ~√t/2^{t/2} upper bound.","lead":"Matchings and co-matchings are forbidden as induced subgraphs; this note proves new explicit lower bounds on the guaranteed pure subgraph and claims matching upper-bound constructions. The lower-bound proof is solid, but the random-graph upper bound contains an invalid Lovász Local Lemma calculation.","discovery_kind":"extension","skeptic_critique":null,"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies quantitative strong Erdős–Hajnal bounds for bipartite graphs avoiding induced matchings and co-matchings. It defines p(k,ℓ) and proves a lower bound via a recurrence (Theorem 1.1), giving a diagonal lower bound of order √t/4^t (Corollary 1.2). It claims a matching upper bound of order √t/2^{t/2} using a random construction and the Lovász Local Lemma (Theorem 1.3). Off-diagonal results include a lower bound for k=3 (Corollary 1.4) and an algebraic upper bound from generalized quadrangles (Theorem 1.5). The final sections extend some results to hypergraphs and slice rank (Theorems 1.6–1.8).","tokens_in":12411,"tokens_out":32557,"duration_ms":414554,"significance":"If the lower bound stands, the paper provides a new and nontrivial quantitative Erdős–Hajnal statement for matchings and co-matchings; the recurrence proof is elementary and appears correct. The generalized-quadrangle construction for k=3 is elegant and gives a polynomial upper bound with exponent 1/5. The hypergraph results, including the O(n^2)-edge threshold, are interesting. The paper does not ship machine-checked proofs or code, but the derivations are transparent enough to verify by hand. However, the advertised upper bound in Theorem 1.3 is not supported by the proof as written.","major_comments":[{"comment":"The LLL estimate is incorrect. With L=(1-2log t/t)√(2/e)√t 2^{t/2}, the correct asymptotic for the LLL expression is eP(A)(Δ+1)=Θ(t^{5/2}), not o(1). The displayed inequality eP(A)(Δ+1)≤3t^4(e L^{2-2/t}/t^{2t})^t appears to lose the 2^{t^2} factor in the denominator; substituting L gives e L^2/(t 2^t)=2(1-o(1)), so the t-th power is exponentially large. In fact the expected number of events is C(L,t)^2 P(A)=Θ(2^t/√t). Therefore the Lovász Local Lemma cannot be applied, and Theorem 1.3 — together with the upper bound in Corollary 2.1 — is not established.","section":"§2.1, proof of Theorem 1.3"}],"minor_comments":[{"comment":"The independence explanation contains a typo: 'no pair (x,y) lies in both X×Y and Y×Y′' should read 'X×Y and X′×Y′'. Also, independence holds when either |X∩X′|=0 or |Y∩Y′|=0, not only the former.","section":"§2.1, proof of Theorem 1.3"},{"comment":"The claim that 'the adjacency tensors of the matching and co-matching of size two have slice rank two' is inaccurate for k≥3: the co-matching tensor is the all-ones tensor minus the matching tensor, and its slice rank is 3, not 2. The proof only needs slice rank >1, so Theorem 1.7 is unaffected, but the statement should be corrected.","section":"§4, proof of Theorem 1.7"},{"comment":"The conclusion that neighborhoods are nested ('either N(x)⊆N(x′) or N(x′)⊆N(x)') follows from the absence of an induced 2-matching; the proof would be clearer with a one-sentence justification.","section":"§2, base case of Theorem 1.1"},{"comment":"The sentence 'for all X⊆A,Y⊆B with |X| ≥ ⌈m/L⌉ t and |Y| ≥ ⌈n/L⌉ t, we have that (X,Y) cannot be a pure pair' is terse. It would help to state explicitly that such sets must intersect at least t distinct blow-up classes on each side, so a pure pair would descend to a t-by-t pure pair in G′.","section":"§2.1, blow-up step"}],"recommendation":"major_revision","confidential_remarks":"The LLL error is the main obstruction. I would encourage the editor to invite a revision in which Theorem 1.3 is either correctly proved (possibly with a weaker constant) or explicitly downgraded, and the resulting changes are propagated through Corollary 2.1. The lower-bound proof and the generalized-quadrangle construction appear sound and are worth preserving."},"author_rebuttal":null,"desk_editor":null,"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C65","05C70","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper quantifies how large a guaranteed complete-or-empty induced subgraph must be in a bipartite graph that forbids induced matchings and co-matchings, giving explicit lower and upper bounds in terms of the forbidden sizes.","keywords":["bipartite graphs","induced matchings","co-matchings","pure pairs","strong induced-subgraph property","log-rank conjecture","hypergraph Ramsey theory","slice rank"],"falsifier":"For the random graph G(L,L,1/2) with L=(1−2log t/t)√(2/e)√t·2^{t/2}, compute the expected number of induced matchings of size t; a direct estimate gives Θ(e^t/√t), meaning the local lemma cannot certify a survivor. If a second-moment calculation confirms that this expected count is typically realized, the claimed upper-bound construction at density 1/2 fails, and any recovery would require a different L or non-uniform edge probabilities.","tokens_in":12325,"feed_emoji":"🧩","tokens_out":12818,"duration_ms":110844,"temperature":0.7,"pith_summary":"The author studies bipartite graphs that contain neither an induced matching of size k nor an induced co-matching of size ℓ, and asks how large a pure pair—a complete or empty induced subgraph—must be on both sides. The main theorem provides a lower bound on this pure-pair proportion that decays like an inverse binomial coefficient in k and ℓ; in the diagonal case this reads as at least (64√π/13 + o(1))√t/4^t. Complementing this, the paper constructs graphs that avoid matchings and co-matchings of size t while having no pure pairs beyond about √t/2^{t/2}, so the guaranteed proportion is pinned between two exponential bases. Off-diagonal results determine p(2,ℓ)=1/2 exactly and place p(3,ℓ) between roughly 1/(3ℓ) and ℓ^{-1/5}. The same questions for k-partite k-uniform hypergraphs behave very differently, with O(n^2)-edge slice-rank-one examples avoiding linear pure boxes for k≥3.","feed_headline":"Forbidden matchings still force a 4^{-t}-sized pure pair","feed_subtitle":"The guaranteed pure-pair size sits between 1/4^t and 1/2^{t/2}; hypergraph analogues collapse.","key_machinery":"The central object is the pure pair (X,Y): an induced subgraph that is either complete or empty and whose two parts have specified sizes relative to |A| and |B|. The lower bound is carried by a recurrence s_{2,ℓ}=s_{k,2}=2 and s_{k,ℓ} = (s_{k−1,ℓ}+s_{k,ℓ−1}+2 + sqrt((s_{k−1,ℓ}+s_{k,ℓ−1})^2+4))/2, whose solution is approximately (13/4)binom(k+ℓ−4,k−2). The induction partitions vertices into high- and low-degree sets and shows that any pure pair smaller than the claimed size forces either an induced matching, an induced co-matching, or contradiction by edge double-counting. For the upper bounds, the paper uses a uniform random graph at density 1/2 with equitable blow-ups, and for the k=3 bound","core_discovery":"The paper's central claim is that forbidding induced matchings and co-matchings in bipartite graphs does not destroy the strong induced-subgraph property; rather, the guaranteed pure-pair proportion is controlled by a two-parameter recurrence whose closed form is a binomial coefficient. Concretely, a graph with no matching of size k and no co-matching of size ℓ must contain a pure pair (X,Y) with |X| ≥ 4/[13·binom(k+ℓ−4,k−2)−5] · |A| and |Y| likewise. The author also claims an upper-bound construction showing that, in the diagonal case, one cannot force pure pairs much larger than about √t/2^{t/2}, so p(t) sits between roughly √t/4^t and √t/2^{t/2}. In the off-diagonal regime, k=2 gives the","pith_inferences":["Editorial inference: if the binomial-coefficient lower bound is close to tight, then the log-rank-type obstruction supplied by permutation submatrices has a quantitative limit around 4^{-t}; the gap to the 2^{-t/2} upper bound suggests a natural target—improving the upper construction would directly sharpen the best monochromatic-submatrix guarantee for functions whose only rank obstructions are m","Editorial inference: the hypergraph construction with slice-rank-one adjacency tensor indicates that slice rank cannot detect matching-like forbidden patterns for k≥3, so a tensor-based log-rank conjecture would require a different notion of rank; testing whether the O(n^2) edge threshold is sharp for other ranks is a natural next step.","Editorial inference: the k=3 lower and upper bounds differ by a factor of ℓ^{4/5}; a promising route would be replacing the finite-geometry incidence graph with a random algebraic pseudorandom graph that has no K_{2,2} but weaker spectral expansion, to see whether the exponent 1/5 can be pushed toward 1."],"forward_implications":["If a bipartite graph avoids induced matchings and co-matchings of size t, it must contain a complete or empty induced subgraph with parts of size at least (64√π/13 + o(1))√t/4^t of the original parts, giving explicit quantitative strong induced-subgraph behavior for every fixed t.","The upper construction shows that no guaranteed proportion above roughly √t/2^{t/2} is possible, so the true value of p(t) is determined up to a subexponential factor with exponential base between 4 and 2^{1/2}.","For k=2 the exact answer is p(2,ℓ)=1/2 for all ℓ, meaning the smallest forbidden matching already yields an optimal constant.","For k=3 the guaranteed pure-pair proportion is polynomial in ℓ, lying between about 1/(3ℓ) and ℓ^{-1/5}; closing this exponent gap is a concrete open problem suggested by the paper.","In k-partite k-uniform hypergraphs with k≥3, no analogue of the strong property survives: there exist O(n^2)-edge hypergraphs with slice-rank-one adjacency tensors that avoid linear-size pure boxes while forbidding matchings and co-matchings of size 2."],"fun_headline_variants":["Forbidden matchings force pure pairs between 4^{-t} and 2^{-t/2}","No matchings, still large pure pairs: ~4^{-t} to ~2^{-t/2}","Pure pair size between 4^{-t} and 2^{-t/2} in bipartite graphs","Matchings and co-matchings: pure pairs shrink slowly","Quantitative bounds for forbidden matchings: pure pairs of size ~4^{-t}"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The upper-bound construction depends on a probabilistic local lemma estimate that the paper asserts vanishes; a direct recalculation of the relevant product gives Θ(t^3), not zero, so the claimed existence of a graph with no large matchings and no large pure pairs at the stated parameters is not actually established.","fun_headline_variants_meta":{"raw":{"variants":["Forbidden matchings force pure pairs between 4^{-t} and 2^{-t/2}","No matchings, still large pure pairs: ~4^{-t} to ~2^{-t/2}","Pure pair size between 4^{-t} and 2^{-t/2} in bipartite graphs","Matchings and co-matchings: pure pairs shrink slowly","Quantitative bounds for forbidden matchings: pure pairs of size ~4^{-t}"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001315,"raw_usage":{"total_tokens":5167,"prompt_tokens":690,"completion_tokens":4477,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":434,"completion_tokens_details":{"reasoning_tokens":4360}},"tokens_in":434,"tokens_out":4477,"duration_ms":31249,"temperature":1.0,"reasoning_tokens":4360,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T03:35:06.557444+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the random graph G(L,L,1/2) with L=(1−2log t/t)√(2/e)√t·2^{t/2}, compute the expected number of induced matchings of size t; a direct estimate gives Θ(e^t/√t), meaning the local lemma cannot certify a survivor. If a second-moment calculation confirms that this expected count is typically realized, the claimed upper-bound construction at density 1/2 fails, and any recovery would require a different L or non-uniform edge probabilities.","supporting_citations":[],"review_version":2}