Pith. sign in

REVIEW 1 major objections 4 minor 20 references

A sharp threshold phenomenon in string graphs

T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every string graph with fewer than one quarter of all possible intersections contains two large mutually disjoint curve families, and the quarter is sharp.

desk verdict 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. read the letter →

arxiv 1908.05550 v1 pith:73YMAQ43 submitted 2019-08-15 math.CO

Istvan Tomon This is my paper · ORCID
classification math.CO MSC 05C6205C3505C10
keywords stringgraphsintersectionofcurvesanticompletepairsbi-cliquesthresholdphenomenonweaksubdivisionsextremalgraphtheoryregularitymethod
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

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.

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 (1)
  1. [§2.2 and Lemma 7] 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.
minor comments (4)
  1. [§2.2, definition of ε1-thin] 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.
  2. [Proposition 12, Case 2] 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.
  3. [Appendix, Case 2 of s=7 analysis] 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.
  4. [Abstract and Section 1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof reduces geometry to a new graph-theoretic statement via independent external tools and self-contained lemmas.

full rationale

I traced the derivation chain of Theorem 2. The high-level route is: Lee's separator theorem (Theorem 1, external) gives Lemma 4; a self-contained uncrossing argument gives Lemma 5 (string graphs contain no induced weak-subdivision of K5); combining these reduces Theorem 2 to a new graph-theoretic statement, Theorem 6. The proof of Theorem 6 then proceeds through the Regularity Lemma, the embedding Lemma 7, and the weighted-graph Lemmas 9, 10 and Proposition 13. Each of these is argued directly from definitions; no lemma assumes the conclusion of Theorem 2. The threshold value 1/4 is not imported as a fitted or assumed quantity but is derived in Proposition 13 from the structure of graphs with no H-admissible subgraph. The sharpness example uses the independent Pach–Tóth realization theorem for graphs partitionable into four cliques and a standard probabilistic construction; it does not rely on the main theorem. Self-citations occur (Pach–Tomon [14] is the conjectured x-monotone threshold and Pach–Tóth [15] is used in the sharpness construction), but they are not load-bearing in the sense of making the derivation circular: the central graph-theoretic contribution is proved rather than assumed, and the external citations are used as genuine independent inputs. I also checked the skeptical concern about the admissibility definition versus the inequality used in Lemma 7, Case 2: that is a possible typographical or correctness issue in the printed definition, not a case of the paper defining one quantity in terms of another or fitting a parameter to a predicted output. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim depends on external theorems (separator theorem, regularity lemma) and on prior constructions for the sharpness example, but introduces no free parameters or invented entities. The proof is a reduction: string graphs avoid weak-subdivisions of K5, and a dense graph with no large anticomplete pair must contain one.

assumptions (5)
  • standard math Szemerédi Regularity Lemma: every graph has a λ-regular partition into a bounded number of parts.
    Invoked in Section 2.1 and used to form the reduced graph in Lemma 7 and Theorem 6.
  • standard math Lee's separator theorem for string graphs: every string graph with m edges has a separator of size O(√m).
    Theorem 1, used to prove Lemma 4 which yields the (α,β)-density property for δ-full string graphs.
  • domain assumption Every string graph can be represented by curves with finitely many crossings, and intersections can be assumed to be crossings (Schaefer-Stefankovič).
    Section 1.1; this validates the crossing assumptions used in Lemma 5 and throughout.
  • standard math Graphs whose vertex set partitions into four cliques are intersection graphs of convex sets (Pach-Tóth).
    Used in Section 1 to justify the sharpness construction inherited from Pach-Tomon; a prior theorem, not proved here.
  • standard math The probabilistic construction yielding graphs with a four-part clique partition, edge density (1/4 + ε)n²/2, and largest anticomplete pair O((1/ε) log n).
    Cited in Section 1 as a standard probabilistic construction; supports the lower-bound half of the threshold.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A sharp threshold phenomenon in string graphs." pith.science (2026). https://pith.science/paper/73YMAQ43

@misc{pith2026190805550,
  author       = {Pith},
  title        = {Pith review of: A sharp threshold phenomenon in string graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/73YMAQ43}},
  note         = {Machine review of arXiv:1908.05550}
}
abstract

We prove that for every $\epsilon>0$ there exists $\delta>0$ such that the following holds. Let $\mathcal{C}$ be a collection of $n$ curves in the plane such that there are at most $(\frac{1}{4}-\epsilon)\frac{n^{2}}{2}$ pairs of curves $\{\alpha,\beta\}$ in $\mathcal{C}$ having a nonempty intersection. Then $\mathcal{C}$ contains two disjoint subsets $\mathcal{A}$ and $\mathcal{B}$ such that $|\mathcal{A}|=|\mathcal{B}|\geq \delta n$, and every $\alpha\in \mathcal{A}$ is disjoint from every $\beta\in\mathcal{B}$. On the other hand, for every positive integer $n$ there exists a collection $\mathcal{C}$ of $n$ curves in the plane such that there at most $(\frac{1}{4}+\epsilon)\frac{n^{2}}{2}$ pairs of curves $\{\alpha,\beta\}$ having a nonempty intersection, but if $\mathcal{A},\mathcal{B}\subset \mathcal{C}$ are such that $|\mathcal{A}|=|\mathcal{B}|$ and $\alpha\cap \beta=\emptyset$ for every $(\alpha,\beta)\in \mathcal{A}\times\mathcal{B}$, then $|\mathcal{A}|=|\mathcal{B}|=O(\frac{1}{\epsilon}\log n)$.

Figures

Figures reproduced from arXiv: 1908.05550 by the authors.

Figure 1
Figure 1. Consider four pairwise touching circles C1, C2, C3, C4 that touch at the six points pij for 1 ≤ i < j ≤ 4. For each vertex in Vi , we can define a convex set that only slightly deviates from the circle Ci . It is possible to define these convex sets such that if x ∈ Vi and y ∈ Vj for some 1 ≤ i < j ≤ 4, then the corresponding convex sets intersect in the small neighborhood of pij if xy ∈ E(G), and these convex sets … view at source ↗
Figure 2
Figure 2. A weak-subdivision of K5, where A, B, C, D, E are the branch-vertices. The edges that are part of the weak-subdivision but not the subdivision are red. Proof. It is enough to show that if H′ is a weak-subdivision of K5, then H′ is not a string graph. Suppose that H′ is a string graph and let C be a collection of curves realizing H′ . Let v1, . . . , v5 be the branch-vertices of H′ and let Ci ∈ C be the curve corresp… view at source ↗
Figure 3
Figure 3. Uncrossing two neighboring edges. induced weak-subdivision of H can be found in G if we can find |V (H)| parts in the partition of G satisfying certain properties. This argument is presented in Section 2.2. Then, we finish our proof in Section 2.3 by showing that a regular partition of G must contain |V (H)| parts with the desired properties. 2.1 Regularity Lemma In this section, we define the notion of regularity a… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: An embedding of a weak-2-subdivision of K4. The edges that are part of the weak-subdivision but not the subdivision are red. Proof. Let W ⊂ Vi be the set of vertices which are not average with respect to (Uj )j∈[h]\{i} . If |W| ≥ 2hλN, then there exists j ∈ [h] \ {i} a…
Figure 5
Figure 5. Figure 5: An illustration for the proof of Claim 14. s ≤ 4. In this case, we simply have φ(Q) ≥ Xs i=1 φ(i) 2 ≥ 1 s ≥ 1 4 . s = 5. If Q is not K5-admissible, then Q has at least two edges by Observation 1. But then φ(Q) ≥ X 5 i=1 φ(i) 2 + 2φ(1)φ(2) = (φ(1) + φ(2))2 + φ(3)2 + φ(4…
Figure 6
Figure 6. Figure 6: An illustration for Case 2. Left is the subcase wher [PITH_FULL_IMAGE:figures/full_fig_p021_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Benzer, On the topology of the genetic fine structure, Proc

    S. Benzer, On the topology of the genetic fine structure, Proc. Nat. Acad. Sci. 45 (1959): 1607–1620

    work page 1959

  2. [2]

    Pure pairs. II. Excluding all subdivisions of a graph

    M. Chudnovsky, A. Scott, P. Seymour, S. Spirkl, Sparse graphs without linear anticomplete pairs, arXiv:1804.01060 (2018)

    work page Pith review arXiv 2018

  3. [3]

    Fox, A bipartite analogue of Dilworth’s theorem, Order 23 (2006): 197–209

    J. Fox, A bipartite analogue of Dilworth’s theorem, Order 23 (2006): 197–209. 18

    work page 2006

  4. [4]

    J. Fox, J. Pach, A separator theorem for string graphs and its applications, Combin. Probab. Comput. 19 (3) (2010): 371–390

    work page 2010

  5. [5]

    J. Fox, J. Pach, String graphs and incomparability graphs, Advances in Mathematics 230 (2012): 1381–1401

    work page 2012

  6. [6]

    J. Fox, J. Pach, Applications of a new separator theorem for string graphs, Combin. Probab. Comput. 23 (1) (2014): 66–74

    work page 2014

  7. [7]

    J. Fox, J. Pach, C. D. T´ oth,Tur´ an-type results for partial orders and intersection graphs of convex sets, Israel Journal of Mathematics 178 (2010): 29–50

    work page 2010

  8. [8]

    J. Fox, J. Pach, Cs. T´ oth,Intersection patterns of curves, J. Lond. Math. Soc. 83 (2011): 389–406

    work page 2011

Show all 20 references
  1. [9]

    G. H. Hardy, J. E. Littlewood, G. P´ olya, Inequalities, Cambridge University Press (1952): Section 10.2, Theorem 368

    1952

  2. [10]

    J. R. Lee, Separators in region intersection graphs, in: 8th Innovations in Theoretical Comp. Sci. Conf. (ITCS 2017), LIPIcs 67 (2017): 1–8

    2017

  3. [11]

    Lipton, R

    J. Lipton, R. E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (2) (1979): 177–189

    1979

  4. [12]

    Matouˇ sek,Near-optimal separators in string graphs, Combinatorics, Probability & Computing 23 (1) (2014): 135–139

    J. Matouˇ sek,Near-optimal separators in string graphs, Combinatorics, Probability & Computing 23 (1) (2014): 135–139

    2014

  5. [13]

    J. Pach, B. A. Reed, Y. Yuditsky, Almost all string graphs are intersection graphs of plane convex sets , in: 34th Symposium on Computational Geometry (SoCG 2018): 68:1–14. Discrete & Computational Geometry, to appear

    2018

  6. [14]

    J. Pach, I. Tomon, Ordered graphs and large bi-cliques in intersection graphs of curves, to appear in European Journal of Combinatorics (2019)

    2019

  7. [15]

    J. Pach, G. T´ oth. How many ways can one draw a graph?, Combinatorica 26 (2006): 559–576

    2006

  8. [16]

    Schaefer, D

    M. Schaefer, D. ˇStefankoviˇ c,Decidability of string graphs, J. Comput. System Sci. 68 (2004): 319–334

    2004

  9. [17]

    F. W. Sinden, Topology of thin film RC-circuits, Bell System Technological Journal (1966): 1639–1662

    1966

  10. [18]

    Szemer´ edi,Regular partitions of graphs, in Proc

    E. Szemer´ edi,Regular partitions of graphs, in Proc. Colloque Inter. CNRS (J.-C. Bermond, J.-C. Fournier, M. Las Vergnas, D. Sotteau, eds.) (1978): 399–401

    1978

  11. [19]

    Tur´ an,On an extremal problem in graph theory, Matematikai ´ es Fizikai Lapok (in Hungarian) 48 (1941): 436–452

    P. Tur´ an,On an extremal problem in graph theory, Matematikai ´ es Fizikai Lapok (in Hungarian) 48 (1941): 436–452. 19 Appendix - Proof of Proposition 13, s = 7 Suppose that s = 7. First, we show that if Q contains either a cycle of length 6 or 7, we have φ(Q) ≥ 1 4 . Indeed,...

    1941

  12. [20]

    If c1c2 is not an edge, then there are at least three edges between c1 and C, so there are two consecutive vertices of C joined to c1

    In both cases Q[B ∪ {a}] contains a cycle C of length 5. If c1c2 is not an edge, then there are at least three edges between c1 and C, so there are two consecutive vertices of C joined to c1. But then C ∪ {c1} contains a cycle of length 6, so we are done. Therefore, we can sup...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.