pith. sign in

arxiv: 2605.20705 · v1 · pith:VDZ2SRVJnew · submitted 2026-05-20 · 🧮 math.CO

Extremal structure in dense arrangements of k-intersecting curves

Andrew Suk , Su Zhou This is my paper

Pith reviewed 2026-05-21 04:30 UTC · model grok-4.3

classification 🧮 math.CO
keywords incidencesk-intersecting curvesextremal combinatoricsPach-Sharir boundforbidden configurationspseudo-segmentspoint-curve arrangements
0
0 comments X

The pith

If a point set avoids s points where every k+1-tuple lies on a distinct curve, then incidences with k-intersecting curves become little-o of the Pach-Sharir maximum.

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

The paper establishes an improved upper bound on the number of incidences between n points and n simple k-intersecting curves when a particular local configuration is forbidden. Under the assumption that no s points exist such that each of their (k+1)-subsets lies on a different curve from the collection, the incidence count drops from the classical O(n to the power (3k+1)/(2k+1)) to little-o of that quantity. This structural condition identifies when dense arrangements cannot reach the extremal order. The result recovers and extends Solymosi's theorem in the special case of pseudo-segments.

Core claim

For any fixed integers s > k+1 ≥ 2, if a set P of n points and a collection C of n simple k-intersecting curves contain no s points of P such that every (k+1)-tuple among them is contained in a distinct curve of C, then the incidence number I(P,C) satisfies I(P,C) = o(n^{(3k+1)/(2k+1)}). This strengthens the 1998 Pach-Sharir theorem precisely when the forbidden configuration is absent.

What carries the argument

The forbidden s-point configuration in which every (k+1)-subset determines a unique curve from the collection.

If this is right

  • Extremal arrangements reaching the Pach-Sharir order are forced to contain the forbidden local pattern.
  • The incidence bound improves automatically for pseudo-segment arrangements that avoid the configuration.
  • Near-extremal examples must embed the complete incidence pattern on s points.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same forbidden-configuration technique may sharpen bounds in other geometric incidence settings.
  • Determining the precise growth rate when the pattern is forbidden remains open and could lie strictly between o and O of the exponent.
  • Constructions that deliberately avoid the pattern might achieve intermediate incidence orders useful for lower-bound examples.

Load-bearing premise

Any arrangement that achieves the full Pach-Sharir incidence order must contain the forbidden s-point configuration.

What would settle it

An explicit construction of n points and n k-intersecting curves that avoids the s-point forbidden configuration yet realizes Theta of n to the power (3k+1)/(2k+1) incidences.

Figures

Figures reproduced from arXiv: 2605.20705 by Andrew Suk, Su Zhou.

Figure 1
Figure 1. Figure 1: The local modification near p. We are now ready to prove Theorem 1.2. Throughout the proof, we use the O(·) and Ω(·) notation to suppress only those constants that have already been fixed, either earlier in the proof or in previous sections. In particular, any constant that is to be chosen later will always remain explicit until it is determined. Proof of Theorem 1.2. Set T = n 1 2k+1 . Let P be a set of n… view at source ↗
read the original abstract

Let $P$ be a set of $n$ points in the plane, and let $\mathcal C$ be a collection of $n$ simple $k$-intersecting curves, meaning that every two distinct curves of $\mathcal C$ meet in at most $k$ points. A classical theorem of Pach and Sharir from 1998 gives the upper bound $I(P,\mathcal C)=O_k(n^{(3k+1)/(2k+1)})$. We prove that this bound can be improved when one excludes a complete local incidence pattern. More precisely, for any fixed integers $s>k+1\ge 2$, if there do not exist $s$ points of $P$ such that every $(k+1)$-tuple among them is contained in a distinct curve of $\mathcal C$, then $I(P,\mathcal C)=o(n^{(3k+1)/(2k+1)})$. In the special case of pseudo-segments, this extends Solymosi's theorem on dense point-line arrangements to dense arrangements of pseudo-segments.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript proves a conditional improvement to the classical Pach-Sharir incidence bound for n points and n simple k-intersecting curves. For any fixed integers s > k+1 ≥ 2, if the arrangement avoids an s-point configuration in which every (k+1)-tuple lies on a distinct curve, then I(P, C) = o(n^{(3k+1)/(2k+1)}). The result is also presented as an extension of Solymosi’s theorem from lines to pseudo-segments.

Significance. If the central extraction argument holds, the work clarifies the extremal structure needed to saturate the Pach-Sharir bound and supplies a concrete forbidden-subconfiguration criterion that forces a strictly sub-extremal incidence count. The pseudo-segment extension is a direct strengthening of an existing result and may be useful in subsequent work on higher-order incidence problems.

major comments (1)
  1. Abstract, second paragraph: the o() improvement is derived by showing that any arrangement meeting the Pach-Sharir extremal order must contain the forbidden s-point configuration. The manuscript must therefore contain an explicit supersaturation or removal lemma that extracts this configuration from any near-extremal incidence graph. It is not yet clear whether this step remains valid when multiple curves share more than k intersections at a single point or when the point set admits higher-order linear dependencies; such cases would constitute counter-examples to the claimed improvement.
minor comments (1)
  1. The statement of the main theorem should explicitly record the dependence of the o() notation on both k and s.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. The central contribution is a forbidden-configuration criterion that forces a strict improvement over the Pach-Sharir bound. We address the single major comment below and will revise the manuscript to make the extraction argument fully explicit.

read point-by-point responses

  1. Referee: [—] Abstract, second paragraph: the o() improvement is derived by showing that any arrangement meeting the Pach-Sharir extremal order must contain the forbidden s-point configuration. The manuscript must therefore contain an explicit supersaturation or removal lemma that extracts this configuration from any near-extremal incidence graph. It is not yet clear whether this step remains valid when multiple curves share more than k intersections at a single point or when the point set admits higher-order linear dependencies; such cases would constitute counter-examples to the claimed improvement.

    Authors: We agree that isolating the extraction step as a standalone lemma will improve readability. The current proof (Section 3) already derives the o() bound by contradiction: assuming I(P,C) = Ω(n^{(3k+1)/(2k+1)}) and the absence of the forbidden s-point configuration, a double-counting argument on the (k+1)-uniform hypergraph of incidences produces a density increment that forces the configuration to appear. We will extract this argument into an explicit supersaturation lemma (new Lemma 3.1) in the revision. On the potential counter-examples: the k-intersecting hypothesis bounds pairwise intersections by k, but permits multiple curves to concur at a single point. The extraction operates combinatorially on the incidence graph and selects (k+1)-tuples lying on distinct curves; concurrence of more than two curves at a vertex does not create additional (k+1)-tuples on the same curve and is therefore already accounted for. Higher-order linear dependencies among points are likewise irrelevant because the argument never invokes algebraic or geometric dependence beyond the combinatorial incidence relation. We will add a short paragraph after the lemma clarifying these points and confirming that no counter-example arises under the stated hypotheses. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external classical bound

full rationale

The central result improves the 1998 Pach-Sharir incidence bound to o(n^{(3k+1)/(2k+1)}) upon excluding a fixed s-point configuration. The argument proceeds by showing near-extremal arrangements must contain the forbidden pattern, which is a standard supersaturation extraction step in extremal set theory. The Pach-Sharir theorem is cited from independent prior work with no author overlap, and the special-case extension to Solymosi's theorem likewise invokes external results. No equation reduces a claimed prediction to a fitted parameter by construction, no self-citation is load-bearing for the main claim, and the derivation remains self-contained against the external benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the classical Pach-Sharir incidence theorem and standard crossing lemmas or double-counting arguments typical in incidence geometry; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Every pair of curves intersects in at most k points (definition of k-intersecting curves).
    Stated in the first sentence of the abstract as the setup for the collection C.

pith-pipeline@v0.9.0 · 5711 in / 1373 out tokens · 28375 ms · 2026-05-21T04:30:42.496630+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    N. Alon, P. D. Seymour, and R. Thomas, A separator theorem for nonplanar graphs, Journal of the American Mathematical Society 3 (1990), 801–808

    work page 1990

  2. [2]

    Balko and N

    M. Balko and N. Frankl, On forbidden configurations in poi nt-line incidence graphs, SIAM J. Discrete Math. 39 (2025), no. 4, 2296–2310

    work page 2025

  3. [3]

    Elekes, On the number of sums and products, Acta Arithmetica 81 (1997), 365–367

    G. Elekes, On the number of sums and products, Acta Arithmetica 81 (1997), 365–367

    work page 1997

  4. [4]

    G. N. Frederickson, Fast algorithms for shortest paths i n planar graphs, with applications, SIAM Journal on Computing 16 (1987), 1004–1022

    work page 1987

  5. [5]

    W. T. Gowers, Hypergraph regularity and the multidimens ional Szemer´ edi theorem,Ann. of Math. (2) 166 (2007), no. 3, 897–946

    work page 2007

  6. [6]

    Guth and N

    L. Guth and N. H. Katz, On the Erd˝ os distinct distances pr oblem in the plane, Annals of Mathematics 181 (2015), 155–190

    work page 2015

  7. [7]

    P. N. Klein, S. Mozes, and C. Sommer, Structured recursiv e separator decompositions for planar graphs in linear time, In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC) , 2013, 505–514

    work page 2013

  8. [8]

    R. J. Lipton and R. E. Tarjan, A separator theorem for plan ar graphs, SIAM Journal on Applied Mathematics 36 (1979), 177–189

    work page 1979

  9. [9]

    Matouˇ sek,Lectures on Discrete Geometry , Springer, 2002

    J. Matouˇ sek,Lectures on Discrete Geometry , Springer, 2002

    work page 2002

  10. [10]

    G. L. Miller, Finding small simple cycle separators for 2-connected planar graphs, Journal of Computer and System Sciences 32 (1986), 265–279. 19

    work page 1986

  11. [11]

    Nagle, V

    B. Nagle, V. R¨ odl, M. Schacht, and J. Skokan, The counti ng lemma for regular k-uniform hypergraphs, Random Structures Algorithms 28 (2006), no. 2, 113–179

    work page 2006

  12. [12]

    Pach and M

    J. Pach and M. Sharir, On the number of incidences betwee n points and curves, Combinatorics, Probability and Computing 7 (1998), 121–127

    work page 1998

  13. [13]

    Plotkin, S

    S. Plotkin, S. Rao, and W. D. Smith, Shallow excluded min ors and improved graph decom- positions, In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discret e Algorithms (SODA), 1994, 462–470

    work page 1994

  14. [14]

    R¨ odl and M

    V. R¨ odl and M. Schacht, Regular partitions of hypergra phs: Regularity lemmas, Combin. Probab. Comput. 16 (2007), no. 6, 833–885

    work page 2007

  15. [15]

    R¨ odl and J

    V. R¨ odl and J. Skokan, Regularity lemma for k-uniform hypergraphs, Random Structures Algorithms 25 (2004), no. 1, 1–42

    work page 2004

  16. [16]

    Sharir and P

    M. Sharir and P. K. Agarwal, Davenport–Schinzel Sequences and Their Geometric Applica- tions, Cambridge University Press, 1995

    work page 1995

  17. [17]

    Solymosi, Dense arrangements are locally very dense

    J. Solymosi, Dense arrangements are locally very dense . I, SIAM Journal on Discrete Mathe- matics 20 (2006), no. 3, 623–627

    work page 2006

  18. [18]

    Mirzaei and A

    M. Mirzaei and A. Suk, On grids in point-line arrangemen ts in the plane, Discrete Comput. Geom. 65 (2021), 1232–1243

    work page 2021

  19. [19]

    Sharir and J

    M. Sharir and J. Zahl, Cutting algebraic curves into pse udo-segments and applications, J. Combin. Theory Ser. A 150 (2017), 1–35

    work page 2017

  20. [20]

    Suk and I

    A. Suk and I. Tomon, Hasse diagrams with large chromatic number, Bull. Lond. Math. Soc. 53 (2021), no. 3, 747–758

    work page 2021

  21. [21]

    L. A. Sz´ ekely, Crossing numbers and hard Erd˝ os problems in discrete geometry, Combinatorics, Probability and Computing 6 (1997), no. 3, 353–358

    work page 1997

  22. [22]

    Szemer´ edi and W

    E. Szemer´ edi and W. T. Trotter, Extremal problems in di screte geometry, Combinatorica 3 (1983), 381–392

    work page 1983

  23. [23]

    Tao, A variant of the hypergraph removal lemma, J

    T. Tao, A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A 113 (2006), no. 7, 1257–1280. 20

    work page 2006