Pith. sign in

REVIEW 19 references

A parity Erd\H{o}s-Hajnal theorem for $t$-intersecting curves

T0 review · reviewed 2026-06-27 · grok-4.3

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

Pith's one-line read Any large family of t-intersecting blue and green curves contains large subfamilies whose pairwise intersections all share the same parity.

desk verdict The paper gives a parity Erdős-Hajnal result for t-intersecting curves via a clean inductive reduction that recovers the t=1 case and yields a new bound on topological graphs. read the letter →

arxiv 2606.11649 v1 pith:MUXXTSQX submitted 2026-06-10 math.CO

Andrew Suk , Su Zhou This is my paper · ORCID
classification math.CO
keywords Erdős-Hajnalpropertyt-intersectingcurvesparityofintersectionstopologicalgraphsextremalgraphtheorypseudo-segments
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

The paper proves that for any fixed t at least 1, a mixed collection of blue and green curves where every pair intersects at most t times admits large subfamilies B prime and G prime such that all blue-green pairs inside them cross an even number of times or all cross an odd number of times. The size of each subfamily is at least an epsilon fraction of the original, with epsilon depending only on t. This parity statement recovers an earlier result for pseudo-segments when t equals 1 and immediately implies an upper bound of n times (log n) to the power O of t log k on the number of edges in an n-vertex topological graph whose edges form a t-intersecting family and contain no k edges that all cross one another oddly.

What carries the argument

Existence of large subfamilies with uniform intersection parity (even or odd) inside any t-intersecting blue-green curve collection.

What would settle it

A single explicit family of t-intersecting curves in the plane whose every sufficiently large blue subset and green subset contains both even-parity and odd-parity crossing pairs.

Watch

Extended reading notes

Core claim

Let B be a set of blue curves and G a set of green curves such that B union G forms a collection of t-intersecting curves in general position. Then there exist subfamilies B prime subset B and G prime subset G with absolute sizes at least epsilon times the sizes of B and G respectively, epsilon positive and depending only on t, such that either every pair from B prime times G prime intersects an even number of times or every such pair intersects an odd number of times.

Load-bearing premise

The blue and green curves form a t-intersecting family placed in general position.

Editorial extensions

If this is right

  • Any n-vertex topological graph whose edges form a t-intersecting family and contain no k edges that pairwise cross an odd number of times has at most n (log n) to the O_t(log k) edges.
  • The statement specializes to the known parity Erdős-Hajnal theorem for pseudo-segments when t equals 1.
  • The uniform-parity subfamilies supply a structural dichotomy that can be iterated to obtain quantitative bounds in geometric graph theory.

Reading between the lines

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

  • The same parity selection might apply directly to families of curves on surfaces or to higher-dimensional objects with bounded intersection multiplicity.
  • One could ask whether the dependence of epsilon on t is polynomial, exponential, or tower-like by constructing explicit lower-bound examples.
  • The graph-theoretic consequence suggests analogous bounds for other forbidden odd-crossing configurations in drawings with restricted edge intersections.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 0 minor

Summary. The manuscript proves that for every fixed t ≥ 1, any bichromatic family of t-intersecting curves in general position admits large subfamilies B' and G' such that all pairs from B' × G' have intersections of the same parity (all even or all odd), with the relative size ε > 0 depending only on t. The t = 1 case recovers the Fox–Pach–Suk theorem for pseudo-segments. An application yields an upper bound of n (log n)^{O_t(log k)} on the number of edges in an n-vertex topological graph whose edges form a t-intersecting family and contain no k pairwise odd-crossing edges.

Significance. If correct, the result provides a parity version of the Erdős–Hajnal property in the setting of t-intersecting curves, extending known results for pseudo-segments. The inductive argument via cutting or charging that preserves parity uniformity, together with the exact recovery of the base case and the concrete application to odd-crossing-free topological graphs, constitutes a meaningful advance in extremal combinatorial geometry.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, the accurate summary of our results, and the recommendation to accept. We are pleased that the significance of the parity Erdős–Hajnal property for t-intersecting curves and its application to topological graphs is recognized.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; derivation is inductive and externally grounded

full rationale

The paper proves the parity Erdős-Hajnal property for t-intersecting curves by induction on t. The t=1 base case recovers the external theorem of Fox-Pach-Suk on pseudo-segments (no self-citation). The inductive step reduces the t-case to the (t-1)-case via a cutting/charging argument that preserves parity uniformity on large subfamilies, using only the general-position hypothesis to ensure transverse intersections. No equations reduce a claimed prediction to a fitted input by construction, no uniqueness theorems are imported from the authors' prior work, and no ansatz is smuggled via self-citation. The result is self-contained against external benchmarks and does not rely on any of the enumerated circular patterns.

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

The result rests on standard domain assumptions about curves in the plane; no free parameters, no invented entities, and no ad-hoc constants are introduced in the abstract.

assumptions (1)
  • domain assumption Any two curves intersect at most t times and the whole collection is in general position.
    Explicitly required in the statement of the theorem (abstract).

how reviews work

0 comments
Cite this review

Pith. "Pith review of A parity Erd\H{o}s-Hajnal theorem for $t$-intersecting curves." pith.science (2026). https://pith.science/paper/MUXXTSQX

@misc{pith2026260611649,
  author       = {Pith},
  title        = {Pith review of: A parity Erd\Hos-Hajnal theorem for $t$-intersecting curves},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MUXXTSQX}},
  note         = {Machine review of arXiv:2606.11649}
}
abstract

For every fixed $t\ge 1$, we prove a parity analogue of the mighty Erd\H{o}s-Hajnal property for $t$-intersecting curves in the plane. Let $\mathcal B$ be a set of blue curves and $\mathcal G$ a set of green curves in the plane such that $\mathcal B\cup\mathcal G$ is a collection of $t$-intersecting curves in general position. We show that there exist subfamilies $\mathcal B'\subseteq\mathcal B$ and $\mathcal G'\subseteq\mathcal G$ such that $|\mathcal B'|\geq \varepsilon|\mathcal B|$ and $|\mathcal G'|\geq \varepsilon|\mathcal G|$, where $\varepsilon>0$ depends only on $t$, such that either every pair in $\mathcal B'\times\mathcal G'$ intersects an even number of times or every such pair intersects an odd number of times. For $t=1$, this recovers the theorem of Fox, Pach, and Suk for pseudo-segments. As an application, we show that every $n$-vertex topological graph with edges forming a $t$-intersecting family and with no $k$ edges that pairwise cross an odd number of times has at most $n(\log n)^{O_t(\log k)}$ edges.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 2 canonical work pages

  1. [1]

    Ackerman, On the maximum number of edges in topological graphs with no four pairwise crossing edges,Discrete Comput

    E. Ackerman, On the maximum number of edges in topological graphs with no four pairwise crossing edges,Discrete Comput. Geom.41 (2009), 365–375

    2009

  2. [2]

    Ackerman and G

    E. Ackerman and G. Tardos, On the maximum number of edges in quasi-planar graphs,J. Combin. Theory Ser. A114 (2007), 563–571

    2007

  3. [3]

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

    J. Fox, A bipartite analogue of Dilworth’s theorem,Order23 (2006), 197–209

    2006

  4. [4]

    J. Fox, J. Pach, and G. Tóth, Intersection patterns of curves,J. London Math. Soc.83 (2011), 389–406

    2011

  5. [5]

    J. Fox, J. Pach, and A. Suk, A structure theorem for pseudo-segments and its applications, arXiv:2312.01028

    work page arXiv

  6. [6]

    J. Fox, J. Pach, and A. Suk, Quasi-planar graphs, string graphs, and the Erdős–Gallai problem, Adv. Math.439 (2024), Paper No. 109501

    2024

  7. [7]

    G. N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM J. Comput.16 (1987), 1004–1022

    1987

  8. [8]

    $C_4$-free subgraphs of high degree with geometric applications

    Z. Hunter, A. Milojević, B. Sudakov, and I. Tomon,C4-free subgraphs of high degree with geometric applications, arXiv:2506.23942, 2025. 18

    work page Pith review arXiv 2025

Show all 19 references
  1. [9]

    P. N. Klein, S. Mozes, and C. Sommer, Structured recursive separator decompositions for planar graphs in linear time, inProceedings of the 45th ACM Symposium on Theory of Computing, 2013, 505–514

    2013

  2. [10]

    Korándi, J

    D. Korándi, J. Pach, and I. Tomon, Large homogeneous submatrices,SIAM J. Discrete Math. 34 (2020), no. 4, 2532–2552

    2020

  3. [11]

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

    1979

  4. [12]

    Matoušek,Lectures on Discrete Geometry, Graduate Texts in Mathematics 212, Springer- Verlag, New York, 2002

    J. Matoušek,Lectures on Discrete Geometry, Graduate Texts in Mathematics 212, Springer- Verlag, New York, 2002

    2002

  5. [13]

    G. L. Miller, Finding small simple cycle separators for 2-connected planar graphs,J. Comput. System Sci.32 (1986), 265–279

    1986

  6. [14]

    J. Pach, J. Radoičić, and G. Tóth, A generalization of quasi-planarity, inTowards a Theory of Geometric Graphs, Contemp. Math. 342, Amer. Math. Soc., Providence, RI, 2004, 177–183

    2004

  7. [15]

    Pach and J

    J. Pach and J. Solymosi, Crossing patterns of segments,J. Combin. Theory Ser. A96 (2001), 316–325

    2001

  8. [16]

    Pach and G

    J. Pach and G. Tóth, Disjoint edges in topological graphs, inCombinatorial Geometry and Graph Theory, Lecture Notes in Comput. Sci. 3330, Springer, Berlin, 2005, 133–140

    2005

  9. [17]

    Pach and G

    J. Pach and G. Tóth, Comments on Fox News,Geombinatorics15 (2006), 150–154

    2006

  10. [18]

    Thomassen, The Hanani–Tutte theorem,Combinatorica8 (1988), 67–72

    C. Thomassen, The Hanani–Tutte theorem,Combinatorica8 (1988), 67–72

    1988

  11. [19]

    Tomon, String graphs have the Erdős–Hajnal property,J

    I. Tomon, String graphs have the Erdős–Hajnal property,J. Eur. Math. Soc., to appear. 19

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.