{"id":"f6f52019-dca6-45fa-88b8-5bd412f8c6bd","arxiv_id":"1908.05550","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every string graph with n vertices and at most (1/4 − ε)n²/2 edges contains two disjoint linear-size subsets with no edges between them; the constant 1/4 is sharp.","lead":"This paper proves a sharp threshold for string graphs: below one quarter edge density, any family of curves contains two large subfamilies with no intersections between them. Above that density, large disjoint subfamilies can fail, so the threshold is exactly 1/4.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The printed admissibility definition in §2.2 does not imply the inequality used in Lemma 7's thin-edge case; Lemma 7's proof relies on an unstated stronger condition.","rationale":"The reader's weakest assumption was Lemma 5, the uncrossing argument showing string graphs avoid induced weak-subdivisions of K5. That proof is terse, but it can plausibly be repaired by choosing a crossing that is first along both curves from the common branch vertex, so I do not regard it as the most decisive issue. The more concrete problem is an internal mismatch in the graph-theoretic core: the printed admissibility condition in Section 2.2 is strictly weaker than the condition used in the proof of Lemma 7. Because Lemma 7 is the embedding lemma that produces the weak-subdivision inside a regular partition, any gap here directly threatens Theorem 6 and therefore Theorem 2. The manuscript itself signals the intended stronger condition in Proposition 13, so a correction may be straightforward, but the proof as written is not self-contained and a reader cannot verify the central claim without resolving the inconsistency. Hence the appropriate verdict is CONDITIONAL rather than a full rejection or an unconditional acceptance.","tokens_in":18520,"tokens_out":27650,"duration_ms":289606,"concrete_test":"Re-derive the thin-edge step of Lemma 7 with the weights w(ab) = 0, w(ai) = 0.1, w(bi) = 0.9 and ε1 = 0.05. Check whether the printed (H,ε1)-admissibility condition is satisfied: it is, since w(ab) + w(ai) = 0.1 < 0.95. Then check whether the lower-bound |U'_i| ≥ |U_i|(ε1 − 2λ) used in Case 2 can hold: it requires w(ai) + w(bi) ≤ 1 − ε1 = 0.95, but the sum is 1.0. This demonstrates the proof needs a different, stronger admissibility condition. Confirm whether the intended definition is the one in Proposition 13 (either b(x)b(z) or b(y)b(z) is a non-edge), and if so, verify that Lemma 9 transfers that stronger property from (R0,w0) to (R,w).","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Section 2.2, (H,ε1)-admissibility is defined with the condition: if xy ∈ E(H), x ≺ y, and b(x)b(y) is ε1-thin, then w(b(x)b(y)) + w(b(x)b(z)) < 1 − ε1 for every z with x ≺ z. This inequality involves only one of the two chosen vertices. In the proof of Lemma 7, Case 2, however, the argument needs w(ai) + w(bi) ≤ 1 − ε1 for every active i, i.e. the sum of weights from both embedded vertices to the third vertex. The stated definition does not imply this: for example, with w(ab) = 0, w(ai) = 0.1, w(bi) = 0.9, the stated condition holds for small ε1, but w(ai) + w(bi) = 1.0 violates the inequality used to lower-bound |U'_i|. The later combinatorial formulation in Proposition 13 uses the stronger condition requiring that for every z after x, either b(x)b(z) or b(y)b(z) is a non-edge, which is exactly what the embedding proof needs. This suggests the Section 2.2 definition is mistyped rather than the argument being hopeless, but as written the central embedding lemma is not justified. Since Lemma 7 is the bridge between the regular partition and the weak-subdivision K5, Theorem 6 and hence the proof of Theorem 2 depend on resolving this inconsistency.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that 1/4 is the sharp threshold for the density of string graphs to force a linear-sized anticomplete pair. Specifically, for every ε>0 there exists δ>0 such that any string graph on n vertices with at most (1/4−ε)n^2/2 edges contains two disjoint sets A,B each of size at least δn with no edges between them; conversely, for every n there are string graphs with at most (1/4+ε)n^2/2 edges whose largest anticomplete pair has size O((1/ε) log n). The proof reduces the geometric statement to a purely graph-theoretic theorem (Theorem 6) using Lee's separator theorem (Lemma 4) and the fact that string graphs avoid induced weak-subdivisions of K5 (Lemma 5). Theorem 6 is then proved via the Szemerédi regularity lemma, an embedding lemma (Lemma 7) that turns an admissible weighted subgraph of the reduced graph into an induced weak-2-subdivision of a small graph H, and an extremal lemma (Lemmas 9–10) showing that any weighted graph of total weight below (1/4−ε)k^2/2 contains an admissible subgraph for some partial subdivision of K5 on at most 8 vertices. The extremal analysis culminates in Proposition 13, a weighted Turán-type statement whose proof includes a detailed case analysis for the 7-vertex case in the appendix.","tokens_in":18842,"tokens_out":24751,"duration_ms":216725,"significance":"If correct, the result resolves a conjecture of Pach and Tomon and extends their x-monotone threshold result to all string graphs, a notable step for intersection graphs of arbitrary curves. The proof is technically substantial: it combines a topological uncrossing argument, Lee's separator theorem, the regularity method, and a new weighted extremal graph lemma. The paper is carefully structured, and the s=7 case of Proposition 13 is treated in an appendix rather than omitted. I checked the interaction between the admissibility definition (§2.2) and the thin-edge case of Lemma 7; the printed definition contains exactly the sum w(b(x)b(z)) + w(b(y)b(z)) that the embedding proof needs, so the potentially circular or under-specified step flagged in the stress-test does not materialize. The sharpness construction is cited from earlier work of Pach–Tomon and Pach–Tóth rather than reproved, which is appropriate. The main new graph-theoretic contribution, Proposition 13, is presented with enough detail to be verified, and the paper appears to be a genuine advance.","major_comments":[{"comment":"The stress-test concern that the admissibility definition does not imply the inequality used in Lemma 7's thin-edge case does not land. The definition on page 7 states: if xy ∈ E(H), x ≺ y, and b(x)b(y) is ε1-thin, then w(b(x)b(z)) + w(b(y)b(z)) < 1 − ε1 for every z with x ≺ z. This is precisely the condition invoked in Case 2 of Lemma 7, where a < b and i ∈ {a+1,…,h}\\{b} gives w(ai) + w(bi) ≤ 1 − ε1. Thus the embedding lemma is justified as written, subject to the ε1-thin typo noted below.","section":"§2.2 and Lemma 7"}],"minor_comments":[{"comment":"The definition says an edge is ε1-thin if w(xy) ≤ λ, but the intended threshold is ε1, as used throughout the proof (e.g., Lemma 9 treats w(f) ≤ ε1 as thin). As printed, a literal reader would not be able to apply the admissibility condition in Lemma 7's Case 2, since w(ab) < ε1 does not imply w(ab) ≤ λ. Please correct λ to ε1.","section":"§2.2, definition of ε1-thin"},{"comment":"The weight-replacement operation w′(f) = w(yu) for f = xu or f = zu is undefined when u ∈ {x,y,z} (e.g., for f = xy it would require w(yy)). The intended meaning is to copy the neighborhood of y onto x and z while keeping the edges among {x,y,z} fixed except that xz is set to weight 1. Please make this explicit to avoid ambiguity.","section":"Proposition 12, Case 2"},{"comment":"In the sentence 'let the edge s of this cycle be c1c2, c2c3, c3c4', the word 'cycle' should presumably be 'path', since C was identified as a path of length 3. This is a typographical slip that should be corrected.","section":"Appendix, Case 2 of s=7 analysis"},{"comment":"The abstract contains the phrase 'there at most (1/4+ε)n^2/2 pairs' with a missing 'are'; also the proof of Lemma 5 refers to 'the edges of this cycle' where 'path' is meant in one place. These are minor wording issues.","section":"Abstract and Section 1"}],"recommendation":"minor_revision","confidential_remarks":"The paper is sound in its main line. The stress-test concern about the admissibility definition appears to be the result of a misreading of the printed formula, which already contains the sum w(b(x)b(z)) + w(b(y)b(z)). The only substantive issues are local typos (ε1-thin threshold, the undefined w(yy) in Proposition 12, and a few wording slips), so I recommend minor revision rather than accept as-is. The sharpness construction is cited from prior work; this is acceptable, but the editor may wish to confirm the authors have permission to rely on the published versions of [14] and [15]."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Tomon proves the Pach–Tomon conjecture: at edge density below 1/4, every string graph has a linear-size anticomplete pair. The proof is genuinely new and mostly solid, but there is one definitional slip in the central embedding lemma that needs fixing.\n\nThe main theorem is a real advance. The 1/4 threshold was known for x-monotone curves; extending it to all string graphs required a new graph-theoretic reduction. The key step is to pass from geometry to a purely combinatorial statement: if a graph with fewer than (1/4−ε)n²/2 edges is sufficiently dense in every large induced subgraph and is δ-full, then it contains an induced weak-subdivision of K5. The proof of this via regularity, admissible weighted subgraphs, and the Turán-type extremal analysis (Propositions 11–13) is original and works. The sharpness example is properly attributed to Pach–Tomon and Pach–Tóth.\n\nThe soft spot is in Section 2.2. The printed definition of (H, ε1)-admissibility says that for a thin edge xy, w(b(x)b(y)) + w(b(x)b(z)) < 1 − ε1 for every z after x. But Lemma 7, Case 2, needs w(b(ai)) + w(b(bi)) ≤ 1 − ε1, i.e., the sum of the weights from both endpoints to the third vertex. The stated condition does not imply this. This is almost certainly a typo: the later Q-admissibility formulation in Proposition 13 uses exactly the stronger condition (for every z after x, at least one of b(x)b(z), b(y)b(z) is a non-edge), which is what the embedding argument requires. As written, Lemma 7 isn't justified, but with the corrected definition the proof goes through. A referee should ask the author to fix this. The uncrossing proof of Lemma 5 is terse but standard; the appendix's s=7 case is tedious and I didn't find a gap.\n\nThe paper is for extremal graph theorists and anyone working on intersection graphs or regularity lemmas. It deserves a serious referee—the theorem is significant and the overall structure is sound, with a fixable typo rather than a fatal flaw.","headline":"Proves the 1/4 threshold for anticomplete pairs in string graphs; strong and original, though the admissibility definition in Lemma 7 has a fixable typo.","tokens_in":19314,"tokens_out":8177,"would_cite":true,"duration_ms":67569,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C62","05C35","05C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every string graph with fewer than one quarter of all possible intersections contains two large mutually disjoint curve families, and the quarter is sharp.","keywords":["string graphs","intersection graphs of curves","anticomplete pairs","bi-cliques","threshold phenomenon","weak subdivisions","extremal graph theory","regularity method"],"falsifier":"Exhibit a string graph whose vertex set cannot be split into two equal linear-size anticomplete sets while its edge count is at most $(\\frac14-\\varepsilon)\\frac{n^2}{2}$; or, more locally, produce a string graph containing an induced weak-subdivision of $K_5$. The second would directly disprove Lemma 5, the load-bearing geometric step.","tokens_in":18345,"feed_emoji":"📉","tokens_out":9447,"duration_ms":90249,"temperature":0.7,"pith_summary":"This paper establishes the exact density at which a family of $n$ plane curves must contain two large subfamilies with no intersection between them. For every $\\varepsilon>0$, any string graph with at most $(\\frac14-\\varepsilon)\\frac{n^2}{2}$ edges contains two disjoint vertex sets $A,B$ with $|A|=|B|\\ge \\delta n$ and no edges between $A$ and $B$. A matching construction shows the bound is sharp: just above $\\frac14\\frac{n^2}{2}$ edges, the largest such anticomplete pair can be as small as $O(\\frac1\\varepsilon\\log n)$. This settles the conjecture that $\\frac14$ is the critical threshold for linear-size anticomplete pairs in intersection graphs of arbitrary curves.","feed_headline":"Below 1/4 density, string graphs split into two large disjoint parts","feed_subtitle":"Above the threshold, constructions force the largest mutually disjoint subfamilies to shrink to O(log n).","key_machinery":"The machinery rotates around weak-subdivisions of $K_5$: replace the ten edges of $K_5$ by internally disjoint paths, then allow extra edges only between vertices lying on paths that correspond to adjacent edges of $K_5$. Lemma 5 shows no string graph contains such a graph as an induced subgraph: choosing one point on each branch curve, the paths between them form a drawing of $K_5$ whose only crossings are between adjacent edges, and an uncrossing operation repeatedly eliminates those crossings, producing a planar drawing of $K_5$, a contradiction. The other half is a graph-theoretic embedding and extremal argument. Starting from the given sparse string graph, a graph regularity lemma produces a reduced weighted graph; the proof defines $(H,\\epsilon_1)$-admissible subgraphs of that weighted graph and shows, via an embedding lemma, that any such admissible subgraph yields an induced weak-2-subdivision of a partial subdivision of $K_5$ in the original graph. The extremal core is a weighted graph $Q$ whose total weight $\\varphi(Q)$ is at least $\\frac14$ unless an admissible subgraph exists; the case analysis for up to seven parts, including a rearrangement inequality in the seven-part case, supplies the $\\frac14$ bound.","core_discovery":"The central discovery is a sharp threshold at edge density $\\frac14$. Theorem 2 states that for every $\\varepsilon>0$ there is $\\delta>0$ so that every string graph on $n$ vertices with at most $(\\frac14-\\varepsilon)\\frac{n^2}{2}$ edges contains an anticomplete pair of linear size, meaning disjoint equal sets $A,B$ with $|A|=|B|\\ge\\delta n$ and $E(A,B)=\\varnothing$. The paper also proves that $\\frac14$ cannot be improved: for every $n$ there are string graphs with at most $(\\frac14+\\varepsilon)\\frac{n^2}{2}$ edges in which every anticomplete pair has size $O(\\frac1\\varepsilon\\log n)$. The route is to reduce the geometric statement to a graph-theoretic dichotomy: a sparse graph that is $\\delta$-full and has uniform lower density on all large induced subgraphs must contain an induced weak-subdivision of $K_5$, while string graphs cannot contain such an induced subgraph.","pith_inferences":["The same machinery gives a template for other topological intersection graphs: whenever a class forbids induced weak-subdivisions of $K_t$ at the conjectured threshold $1/(t-1)$, the corresponding curve-intersection threshold follows.","The extremal weighted graph $Q$ resembles a density version of Ramsey-type phenomena, suggesting the testable extension that replacing $K_5$ by any fixed graph $H$ yields threshold $1/(\\chi(H)-1)$ for linear anticomplete pairs.","A computational probe at moderate $n$ could sample string graphs just below density $1/4$ and measure the largest anticomplete pair; the predicted worst-case growth is $O(\\log n)$ in $\\varepsilon^{-1}$, which would be distinguishable from any linear lower bound."],"forward_implications":["The threshold $\\frac14$ is optimal: above it, string graphs can be built with only $O(\\varepsilon^{-1}\\log n)$-size anticomplete pairs, so no linear bound survives.","The geometric input enters only through the forbidden weak-subdivision lemma, so any hereditary class of graphs that excludes induced weak-subdivisions of $K_5$ obeys the same $\\frac14$ threshold for linear anticomplete pairs.","The paper proves a weaker $K_t$ version: graphs with fewer than $\\frac{1}{2(t-1)}\\frac{n^2}{2}$ edges and no induced weak-subdivision of $K_t$ contain linear anticomplete pairs.","The four-part clique construction behind the sharpness example shows how to pack nearly one quarter of all intersections while suppressing large disjoint subfamilies."],"supporting_citations":[{"why":"Supplies the string-graph separator theorem used to show that a delta-full sparse string graph is dense on all large induced subgraphs, reducing the problem to the dense case.","marker":"[10]"},{"why":"Establishes the x-monotone-curve threshold and formulates the conjecture for arbitrary curves that this paper proves.","marker":"[14]"},{"why":"Provides the earlier geometric lemma that Lemma 5 generalizes to show string graphs do not contain weak-subdivisions of K5.","marker":"[15]"},{"why":"Supplies the companion lemma, also generalized in Lemma 5, used to forbid weak-subdivisions of K5 in string graphs.","marker":"[13]"},{"why":"Guarantees that every string graph can be realized by curves with finitely many crossings, supporting the perturbation assumptions at the start of the proof.","marker":"[16]"},{"why":"Provides the rearrangement inequality used in the appendix to lower-bound the weighted graph's value in the seven-part extremal case.","marker":"[9]"}],"fun_headline_variants":["String graphs hit sharp threshold at 1/4 edge density","Below 1/4 density, string graphs split into linear disjoint sets","Sharp 1/4 threshold: linear vs logarithmic disjoint subgraphs","String graph phase transition at 1/4 edge density"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Lemma 5: no string graph contains an induced weak-subdivision of $K_5$, proved by an uncrossing operation that removes crossings between adjacent edges of a drawn $K_5$; if that operation is invalid in some drawing, the reduction from curve families to the graph-theoretic dichotomy would fail.","fun_headline_variants_meta":{"raw":{"variants":["String graphs hit sharp threshold at 1/4 edge density","Below 1/4 density, string graphs split into linear disjoint sets","Sharp 1/4 threshold: linear vs logarithmic disjoint subgraphs","String graph phase transition at 1/4 edge density"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000231,"raw_usage":{"total_tokens":1516,"prompt_tokens":1005,"completion_tokens":511,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":621,"completion_tokens_details":{"reasoning_tokens":438}},"tokens_in":621,"tokens_out":511,"duration_ms":5298,"temperature":1.0,"reasoning_tokens":438,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:11:59.482931+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a string graph whose vertex set cannot be split into two equal linear-size anticomplete sets while its edge count is at most $(\\frac14-\\varepsilon)\\frac{n^2}{2}$; or, more locally, produce a string graph containing an induced weak-subdivision of $K_5$. The second would directly disprove Lemma 5, the load-bearing geometric step.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the string-graph separator theorem used to show that a delta-full sparse string graph is dense on all large induced subgraphs, reducing the problem to the dense case."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the x-monotone-curve threshold and formulates the conjecture for arbitrary curves that this paper proves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the earlier geometric lemma that Lemma 5 generalizes to show string graphs do not contain weak-subdivisions of K5."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the companion lemma, also generalized in Lemma 5, used to forbid weak-subdivisions of K5 in string graphs."},{"cited_title":"Schaefer, D","cited_arxiv_id":null,"evidence_quote":"Guarantees that every string graph can be realized by curves with finitely many crossings, supporting the perturbation assumptions at the start of the proof."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the rearrangement inequality used in the appendix to lower-bound the weighted graph's value in the seven-part extremal case."}],"review_version":1}