{"id":"774804f5-f211-4c3c-98b2-2cfeae1abdff","arxiv_id":"2506.23942","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new dichotomy about C4-free induced subgraphs and dense patches yields optimal O(sn) bounds for geometric Zarankiewicz problems and a near-tight semilinear bound.","lead":"This paper proves a new graph-theoretic dichotomy: any graph with large average degree either contains a large induced piece with no 4-cycles or a very dense subgraph. The authors use this tool to obtain optimal or near-optimal Zarankiewicz bounds for several geometric graph families.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.9 depends on unproved Lemma 3.3 from a preprint; if that lemma fails, the dichotomy and all geometric applications collapse.","rationale":"The paper's applications all rest on Theorem 1.9 and Corollary 1.10. The proof of Theorem 1.9 is deferred to Theorem 1.12, which is proved by a four-step induction. The second step (Lemma 3.4) is the only place where (c,t)-sparsity is converted into local upper bounds on codegrees, and it does so solely through Lemma 3.3. I checked the local arguments: with the correct interpretation of (1−ε, βt)-sparsity (density ≤ ε), the derivations of |S_a| < t0 and the deletion of high-degree vertices in Claim 3.5 are valid given the lemma. Thus the proof is coherent conditional on Lemma 3.3. I also considered the proof of Lemma 3.7; the independence-number step is terse but can be justified using triangle-freeness and Shearer's bound, so it does not appear to be a fatal gap. The reader's verdict CONDITIONAL matches the evidence: the main result is plausible and well-supported except for this unverified import, plus minor proof sketches and a recursion typo in Lemma 5.5. My stress-test does not change that verdict.","tokens_in":42443,"tokens_out":22337,"duration_ms":216892,"concrete_test":"Independently verify Lemma 3.1 of arXiv:2411.12659 for the specific bipartite graph H_v^(h): reproduce its proof and check whether β depends only on c, H, and ε and whether the conclusion holds for all t and for all (c,t)-sparse graphs with no induced H. As a sharper test, attempt to derive Claim 3.5's two sparsity uses directly from the original (c,t)-sparsity without Lemma 3.3; if they cannot be derived, the proof is genuinely dependent on the external lemma.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central dichotomy (Theorem 1.9) is derived from Theorem 1.12, whose proof hinges on Lemma 3.3, imported verbatim from Ding-Gao-Liu-Luan-Sun (arXiv:2411.12659) and not restated or proved. In Lemma 3.4, Lemma 3.3 is the only mechanism that upgrades (c,t)-sparsity to (1−ε, βt)-sparsity. This upgraded sparsity is then used twice: to show |S_a| < t0 for the set of vertices sharing many neighbours with a, and to delete from each Te all vertices with more than ε|Te′| neighbours in a candidate set Te′ (Claim 3.5). Without these two steps, the random sampling cannot eliminate K_{2,v+1} copies and the proof of Lemma 3.4 fails, breaking Theorem 1.12 and hence Theorem 1.9. The paper neither proves Lemma 3.3 nor indicates which properties of H_v^(h) are needed, so the load-bearing step is currently an external preprint claim. The reader's conditional verdict is appropriate, and the issue should be resolved before the paper is considered final.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces and proves a structural dichotomy for general graphs (Theorem 1.9): for every k there is c(k)>0 such that every graph of average degree at least d either contains an induced C4-free subgraph of average degree at least k, or a subgraph on d vertices with at least c d^2 edges. The dichotomy is derived from a stronger statement about (c,t)-sparse graphs (Theorem 1.12), proved through a four-step sampling argument in Section 3. The authors then use this tool to give uniform and, in several cases, optimal bounds for Zarankiewicz-type problems in geometric settings: string graphs, intersection graphs of k-intersecting curve families, intersection graphs of convex sets, incidence graphs of y-monotone pseudodisks, semilinear graphs, and polygon visibility graphs. The paper also derives a conjecture of Fox, Nenadov, and Pham on induced subdivisions in (c,t)-sparse graphs.","tokens_in":42686,"tokens_out":12211,"duration_ms":126174,"significance":"If the main dichotomy is accepted, the paper is a significant contribution: it unifies a broad range of geometric Zarankiewicz results and obtains tight dependence on s (often O(s n)) that previously required ad-hoc geometric arguments or separator theorems. The overall architecture is coherent and the applications are substantial. The proof of Theorem 1.9 is carefully structured, and the use of the published theorem of Du, Hunter, Girão, McCarty, and Scott (Theorem 3.8) as a black box is appropriate. The main barrier to acceptance is not the internal derivation but the reliance, at a single load-bearing point, on an unproved lemma imported from a preprint, together with a few proof gaps and typos that need to be repaired.","major_comments":[{"comment":"Lemma 3.3 is imported from Ding–Gao–Liu–Luan–Sun (arXiv:2411.12659) without a proof or even a full statement of the result in the present paper. This lemma is the only mechanism in Lemma 3.4 that upgrades (c,t)-sparsity to (1−ε,βt)-sparsity; that upgraded sparsity is then used twice: to bound |S_a| < t0 and to delete vertices from the sets T_e in Claim 3.5. If Lemma 3.3 fails, the proof of Lemma 3.4 collapses, and with it Theorem 1.12 and Theorem 1.9, on which all geometric applications depend. The paper should either prove the needed special case, give a precise statement with the dependence of β on H and ε, or cite a version that has passed peer review. As written, this is a load-bearing external-preprint dependency and must be resolved before the paper is considered final.","section":"Section 3, Lemma 3.3"},{"comment":"In the proof of Lemma 5.5, Step 4 says that a (d−1)-dimensional vertical face F is covered by at most f(d, 2(d−1)) parallelotopes, but the induction is on the dimension d, so the bound should refer to f(d−1, 2(d−1)). As written, the recurrence uses the same dimension d and is circular; this affects the proof of Lemma 5.2 and hence Proposition 5.1 and Theorem 1.7. The error appears to be a typo, but it must be corrected and the induction checked explicitly.","section":"Section 5, Lemma 5.5, Step 4"},{"comment":"Claim 2.7 is stated as a proof sketch, yet it is used to assert that the family of point-halfspace incidence graphs in R^4 is not degree-bounded, which the introduction presents as resolving the open case of dimension 4. Several steps are only sketched: the conversion from rectangles to inscribed ellipses, the deletion argument for close pairs, and the final lifting map. Since this is a claimed theorem rather than an aside, the proof should be completed or the claim should be explicitly downgraded to a conjecture or conditional construction.","section":"Section 2, Claim 2.7"}],"minor_comments":[{"comment":"There is a typo in 'we havεd' in the paragraph after the definition of t0; also the constant K is required to satisfy d/4 ≥ βt/ε, but the displayed inequality says K ≥ 4 C(v,h) β/ε, which should be checked for consistency with the subsequent lower bound on |N(a)|.","section":"Section 3, Lemma 3.4"},{"comment":"In the case e(G1) ≥ εn^2/3, the text says a point p in P' is contained in at least εn/2 pseudodisks, but the earlier deletion step only guarantees εn/6. The subsequent conclusion should be adjusted accordingly (the desired bound still follows).","section":"Section 4.2, Lemma 4.5"},{"comment":"Theorem 6.9 and Theorem 6.11 refer to 'Theorem 1.10' in their final sentences, but the correct reference is Corollary 1.10.","section":"Section 6"},{"comment":"The manuscript contains many typographical errors (e.g., 'strucutral', 'recieved', 'sugbgraph', 'biparite', 'indicedence', 'parrallelotope', 'the set A'' has size at least 2/3 |A''|' in the proof of Theorem 1.2). A careful proofreading pass is needed.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The decisive issue is the unproved external Lemma 3.3. It would be reasonable to ask the authors to include a proof or to obtain publication/acceptance of the preprint, and to confirm that the stated version of Lemma 3.3 indeed applies to the graphs H_v^{(h)} used in Lemma 3.4. The remaining issues appear local and fixable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: Theorem 1.9 is a genuinely new structural dichotomy, and it delivers what the abstract promises—a unified route to optimal O(sn) bounds for several geometric Zarankiewicz problems. The paper deserves a serious referee. But there is one load-bearing external dependency that needs to be resolved before I'd call it final.\n\nWhat's new: the C4-free-or-dense-patch statement (Theorem 1.9) and its (c,t)-sparse strengthening (Theorem 1.12) are not in the papers this builds on. The previous degree-boundedness program gave polynomial-in-s bounds; this dichotomy is a different kind of tool. The geometric applications are the real payoff: O(sn) for y-monotone pseudo-disks (Theorem 1.6), the near-optimal semilinear bound (Theorem 1.7), and O(sn) for polygon visibility graphs (Theorem 1.8). Section 3 is mostly coherent; the four-step sampling in Lemma 3.4 is detailed, and the derivation of Theorem 1.9 from Theorem 1.12 via (1/2,t)-sparsity is sound.\n\nThe soft spot is real and it is exactly where the stress-test put it. Lemma 3.3 is imported from Ding–Gao–Liu–Luan–Sun, stated as 'Lemma 3.1 in [13]' with no proof and no restatement of the relevant hypotheses. In Lemma 3.4, that lemma is the only mechanism that converts (c,t)-sparsity into (1−ε, βt)-sparsity, and both cleaning steps (the bound |S_a|<t0 and Claim 3.5) use that upgraded sparsity. If Lemma 3.3 fails, the proof of Theorem 1.12 collapses, and so does the dichotomy. I don't think it fails—the lemma is plausible and the source group is solid—but a referee cannot verify the main theorem without checking a preprint that isn't in the manuscript. That should be fixed by including a proof or at least a full statement with the required properties of H_v^(h).\n\nThe smaller issues: Claim 2.7 is labeled a proof sketch; it only affects a lower-bound side remark about R4, so it's minor. Lemma 5.5 has a recursion typo—'f(d,2(d−1))' should presumably be 'f(d−1, something)'—but the induction is clear and this doesn't touch the main results. The citation pattern is honest; the self-references are to published or posted theorems used as black boxes, and there's no circularity.\n\nBottom line: this is a serious paper for extremal graph theory and combinatorial geometry, and I'd bring it to the reading group. Send it to referees; one of them should be asked specifically to verify the imported lemma against [13], or demand a self-contained proof. With that resolved, accept.","headline":"Theorem 1.9 is a real result; referees need to verify the imported Lemma 3.3 before this is final.","tokens_in":43249,"tokens_out":3067,"would_cite":true,"duration_ms":28267,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C62","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every graph of average degree d hides either an induced C4-free subgraph of degree at least k or a d-vertex patch with c d^2 edges, and this dichotomy yields optimal Zarankiewicz bounds across geometry.","keywords":["Zarankiewicz problem","induced C4-free subgraph","degree-bounded families","density-Erdős-Hajnal property","geometric graph theory","string graphs","semilinear graphs","induced subdivisions"],"falsifier":"Search for a sequence of graphs that are (c,t)-sparse and induced-H-free for some fixed bipartite H yet contain two sets of size at least βt with at least (1−ε)|A||B| edges; such a construction would refute Lemma 3.3 and break the proof of Theorem 1.12.","tokens_in":42253,"feed_emoji":"📐","tokens_out":8952,"duration_ms":90187,"temperature":0.7,"pith_summary":"This paper tries to establish a graph-theoretic dichotomy and to show it is the right engine for a broad family of geometric Zarankiewicz problems. The dichotomy says that every graph of average degree d either contains an induced C4-free subgraph of average degree at least k, or contains a subgraph on d vertices with at least c(k)$d^{2}$ edges. If true, a hereditary family of graphs whose C4-free members have bounded average degree and whose dense members contain large bicliques automatically has K_{s,s}-free members of average degree O(s). The paper then uses this to derive tight or near-tight bounds for string graphs, k-intersecting families of curves, convex set intersection graphs, y-monotone pseudodisks, semilinear incidence graphs, and polygon visibility graphs, and to prove a conjecture that sparse graphs of large average degree contain induced subdivisions of any fixed graph.","feed_headline":"Dichotomy yields tight geometric Zarankiewicz bounds","feed_subtitle":"One graph theorem unifies string, pseudodisk, semilinear, and visibility bounds.","key_machinery":"The load-bearing object is the (c,t)-sparsity condition and the local control it gives over common neighbourhoods. The paper proves Theorem 1.12 by a four-step extraction: choose a maximal-average-degree induced subgraph with a balanced cut; use the imported Lemma 3.3 to upgrade sparsity so that vertices sharing many neighbours form a set of size O(t); randomly sample to keep edges while destroying all copies of K_{2,v+1} with two vertices on one side; then apply a known theorem converting K_{v+1,v+1}-freeness with large average degree into an induced C4-free subgraph. The 1-subdivision of $K_v^{{(h)}}$, a bipartite graph whose one side encodes all h-subsets of the other, is the obstruction gadget that makes the random sampling work.","core_discovery":"Theorem 1.9 states that for every k there is c=c(k)>0 such that every graph G with average degree d contains either an induced C4-free subgraph of average degree at least k or a subgraph on d vertices with at least c $d^{2}$ edges. The proof runs through a stronger statement, Theorem 1.12: every (c,t)-sparse graph of sufficiently large average degree contains a bipartite induced C4-free subgraph of average degree at least k. From the dichotomy, Corollary 1.10 draws the main structural conclusion: a hereditary family that is weakly degree-bounded (bounded average degree on C4-free members) and has the density-Erdős-Hajnal property (every dense induced subgraph contains a linear-size biclique) has K_{s,s}-free members of average degree O(s). The paper claims this unified mechanism recovers and improves a long list of geometric bounds, including O(s log s) for string graphs without separator theorems, O_k(sn) for k-intersecting curve families, O(sn) for convex sets and for two families of disjoint curves, O(sn) for y-monotone pseudodisks, and O_{dx,h}(t s n (log n/log log n)^{dy-1}) for semilinear graphs.","pith_inferences":["The dichotomy offers a reusable recipe: to prove degree-boundedness of a hereditary geometric family, check only C4-free members and dense-induced bicliques; this may shorten future proofs that currently rely on separators or epsilon-nets.","The semilinear bound suggests the log factor is governed by the ambient dimension of the point side, so any family representable by polytopes with O(1) facet directions should satisfy the same bound; testing point-box incidences in higher dimensions would confirm the range of the method.","If Lemma 3.3 turns out to hold only for particular bipartite H, Theorem 1.12 may still be salvageable for those H; a targeted search for counterexamples to the lemma would clarify which sparse graph classes the method covers.","The same dichotomy may extend to longer even cycles: replace C4-free by C_{2ℓ}-free in the hypothesis and ask whether the conclusion holds with a corresponding dense patch, which would give an analogue for higher even-cycle obstructions."],"forward_implications":["Any hereditary family with bounded average degree on C4-free members and large bicliques in dense induced subgraphs automatically has K_{s,s}-free members of average degree O(s).","The string graph bound O(s log s) follows without separator theorems, purely from the dichotomy plus a dense-string-graph biclique lemma.","For k-intersecting curve families, convex sets, and two families of disjoint curves, the dichotomy plus a new biclique-in-dense-bipartite-curve-intersection-graph theorem gives linear-in-s bounds.","Semilinear incidence graphs of dimension (dx,dy) and complexity (h,t) have K_{s,s}-free edge bound O_{dx,h}(t s n (log n/log log n)^{dy-1}), matching the point-box bound up to dimension-dependent constants.","A (c,t)-sparse graph of average degree Ω_{H,c}(t) contains an induced subdivision of every fixed graph H, confirming the sparse-graph conjecture."],"supporting_citations":[{"why":"Supplies Lemma 3.3, the imported sparsity-upgrade result that is the only place (c,t)-sparsity is converted into control of common neighbourhoods.","marker":"[13]"},{"why":"Supplies the theorem used in the final step to pass from K_{v+1,v+1}-free high-average-degree graphs to induced C4-free subgraphs.","marker":"[14]"},{"why":"Establishes that graphs of large average degree contain induced subdivisions, which makes string graphs weakly degree-bounded and turns Theorem 1.12 into the induced-subdivision conjecture.","marker":"[35]"},{"why":"Provides the random-sampling method for finding dense induced bipartite subgraphs in triangle-free graphs, adapted in Lemma 3.7.","marker":"[36]"},{"why":"Quantitatively sharpens the semialgebraic Zarankiewicz bound and supplies the dense biclique lemma used throughout the geometric applications.","marker":"[23]"},{"why":"Provides the point-box and point-halfspace incidence bounds that Proposition 5.1 extends and that set the target shape for the semilinear bound.","marker":"[8]"},{"why":"Gives the dense string graph biclique result used to obtain O(s log s) for K_{s,s}-free string graphs.","marker":"[21]"},{"why":"Establishes the O(s^6 n) degree-boundedness of pseudodisk intersection graphs, used as the degree-boundedness input for Theorem 1.6.","marker":"[31]"},{"why":"Supplies the cutting lemma for y-monotone pseudodisks used to prove the density-EH property for pseudodisk intersection graphs.","marker":"[11]"},{"why":"Provides the double-cherry forbidden substructure used to control polygon visibility graphs in Theorem 1.8.","marker":"[1]"}],"fun_headline_variants":["Dichotomy unifies geometric Zarankiewicz bounds","New graph dichotomy yields optimal geometric bounds","One theorem, many geometric Zarankiewicz results","C4-free subgraphs open up geometric graph bounds","Unified proof for geometric Zarankiewicz via dichotomy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof imports the unproved lemma that a graph which avoids induced copies of a fixed bipartite graph and has no dense pair of large sets (c,t-sparse) also has no nearly complete pair of sets of size βt; if that lemma fails, the local sparsity argument collapses.","fun_headline_variants_meta":{"raw":{"variants":["Dichotomy unifies geometric Zarankiewicz bounds","New graph dichotomy yields optimal geometric bounds","One theorem, many geometric Zarankiewicz results","C4-free subgraphs open up geometric graph bounds","Unified proof for geometric Zarankiewicz via dichotomy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000272,"raw_usage":{"total_tokens":1652,"prompt_tokens":982,"completion_tokens":670,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":598,"completion_tokens_details":{"reasoning_tokens":598}},"tokens_in":598,"tokens_out":670,"duration_ms":6640,"temperature":1.0,"reasoning_tokens":598,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:40:11.469133+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search for a sequence of graphs that are (c,t)-sparse and induced-H-free for some fixed bipartite H yet contain two sets of size at least βt with at least (1−ε)|A||B| edges; such a construction would refute Lemma 3.3 and break the proof of Theorem 1.12.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the theorem used in the final step to pass from K_{v+1,v+1}-free high-average-degree graphs to induced C4-free subgraphs."},{"cited_title":"Kühn, and D","cited_arxiv_id":null,"evidence_quote":"Establishes that graphs of large average degree contain induced subdivisions, which makes string graphs weakly degree-bounded and turns Theorem 1.12 into the induced-subdivision conjecture."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the random-sampling method for finding dense induced bipartite subgraphs in triangle-free graphs, adapted in Lemma 3.7."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Quantitatively sharpens the semialgebraic Zarankiewicz bound and supplies the dense biclique lemma used throughout the geometric applications."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the point-box and point-halfspace incidence bounds that Proposition 5.1 extends and that set the target shape for the semilinear bound."},{"cited_title":"Fox, and J","cited_arxiv_id":null,"evidence_quote":"Gives the dense string graph biclique result used to obtain O(s log s) for K_{s,s}-free string graphs."},{"cited_title":"Zarankiewicz's problem via $\\epsilon$-t-nets","cited_arxiv_id":"2311.13662","evidence_quote":"Establishes the O(s^6 n) degree-boundedness of pseudodisk intersection graphs, used as the degree-boundedness input for Theorem 1.6."},{"cited_title":"Chekuri, K","cited_arxiv_id":null,"evidence_quote":"Supplies the cutting lemma for y-monotone pseudodisks used to prove the density-EH property for pseudodisk intersection graphs."}],"review_version":1}