pith. sign in

arxiv: 2606.07806 · v1 · pith:2JQGBMQQnew · submitted 2026-06-05 · 🧮 math.CO · cs.CG

Blow-ups of order types of positive density

Ruy Fabila-Monroy , Benedikt Hahn , Jes\'us Lea\~nos This is my paper

Pith reviewed 2026-06-27 21:23 UTC · model grok-4.3

classification 🧮 math.CO cs.CG
keywords order typespositive densityblow-upscolored point setsgeneral positioncombinatorial geometryRamsey-type theoremspoint configurations
0
0 comments X

The pith

A κ-colored order type on k points with positive density δ in an n-point set in R^d admits k disjoint subsets each of size at least c n on which every transversal realizes the same order type and color pattern.

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

The paper proves a blow-up theorem for order types in colored geometric point sets. Given a sequence P of n points in general position in R^d that is colored with κ colors, and a fixed κ-colored order type ρ on k ≤ d+1 points that appears in at least δ fraction of all k-subsets, the result guarantees k disjoint subsets X1 through Xk each containing at least c n points (with c depending only on d, δ, k, and κ) such that every choice of one point from each Xi reproduces exactly the order type and color pattern of ρ. This shows that locally dense combinatorial patterns can be lifted to globally uniform large-scale structures inside the same point set. A reader cares because the statement supplies an explicit linear-size guarantee rather than a merely existential or sublinear one, and it works uniformly across dimensions and color counts.

Core claim

Let P be a κ-colored sequence of n ≥ d+1 points in general position in R^d. Let ρ be a κ-colored order type on k ≤ d+1 points that has positive density on P; that is, for some constant δ >0, there are δ ⋅ binom(n,k) k-point subsequences of P that have the same order type as ρ and the same color pattern. Then there exists a constant c >0 (depending only on d, δ, k and κ) and disjoint subsets X1,…,Xk of P, each with at least c⋅n points, such that for every choice of k points xi∈Xi, (x1,…,xk) has the same order type and color pattern as ρ.

What carries the argument

The collection of k disjoint linear-sized subsets X1 to Xk such that the Cartesian product X1 × ⋯ × Xk is monochromatic in the order type ρ and its color pattern.

If this is right

  • The linear-size guarantee applies uniformly for every fixed dimension d, every number of colors κ, and every k up to d+1.
  • The same density δ forces the existence of the blow-up regardless of the particular geometry of the ambient space beyond general position.
  • Every sufficiently dense local order-type pattern can be realized by a product of k large subsets inside the original point set.
  • The result is stable under recoloring or small perturbations that preserve the positive-density condition.

Where Pith is reading between the lines

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

  • The same technique may yield density versions of other order-type Ramsey statements that currently have only tower-type bounds.
  • One could test the dependence of c on δ by constructing explicit point sets in low dimension where the blow-up constant is close to the density threshold.
  • The result suggests that order-type regularity lemmas might exist with linear-sized parts rather than merely positive-density parts.
  • Extending the statement to k > d+1 would require new arguments because the order type is no longer determined by convex hulls alone.

Load-bearing premise

The n points lie in general position in R^d.

What would settle it

A finite colored point set in some R^d together with a positive-density order type ρ for which the largest possible c is o(1), i.e., every collection of k subsets realizing ρ uniformly has at least one subset of size smaller than any fixed positive fraction of n.

Figures

Figures reproduced from arXiv: 2606.07806 by Benedikt Hahn, Jes\'us Lea\~nos, Ruy Fabila-Monroy.

Figure 1
Figure 1. Figure 1: The signed central projection from o with respect to the hyperplanes Π and Π′ . Because p, q and o are collinear, p and q are sent to the same point πo(p) = πo(q) but with different signs. In the remainder of the paper, no such collisions of points in P occur, as P ∪ {o} will be in general position. Proof. Order types are invariant under rotations, translations and scaling. Thus, we may assume that o is th… view at source ↗
read the original abstract

Order types are an equivalence relation between point configurations that capture their combinatorial and convexity properties. Let $P$ be a $\kappa$-colored sequence of $n \ge d+1$ points in general position in $\mathbb{R}^d$. Let $\rho$ be a $\kappa$-colored order type on $k \le d+1$ points that has positive density on $P$; that is, for some constant $\delta >0$, there are $\delta \cdot \binom{n}{k}$ $k$-point subsequences of $P$ that have the same order type as $\rho$ and the same color pattern. In this paper we show that there exists a constant $c >0$ (depending only on $d, \delta$, $k$ and $\kappa$) and disjoint subsets $X_1,\dots,X_k$ of $P$, each with at least $c \cdot n$ points, such that for every choice of $k$ points $x_i \in X_i$, $(x_1,\dots,x_k)$ has the same order type and color pattern as $\rho$.

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

0 major / 2 minor

Summary. The manuscript proves a density theorem for colored order types: given a κ-colored point set P of n ≥ d+1 points in general position in R^d, and a colored order type ρ on k ≤ d+1 points that occurs with positive density δ (i.e., at least δ ⋅ binom(n,k) k-tuples realize ρ), there exist a constant c > 0 depending only on d, δ, k, κ and disjoint subsets X1, …, Xk ⊆ P each of size ≥ c n such that every k-tuple (x1 ∈ X1, …, xk ∈ Xk) realizes exactly the order type and color pattern of ρ.

Significance. If the proof is correct, the result supplies a geometric analogue of density Ramsey theorems, guaranteeing large 'blow-ups' of any positive-density colored order type. This is potentially useful for extremal problems in discrete geometry and for regularity lemmas in higher-dimensional point configurations. The parameter dependence (c depending only on d, δ, k, κ) and the restriction k ≤ d+1 (ensuring finitely many order types) are the expected form for such statements.

minor comments (2)
  1. The abstract states the main theorem cleanly, but the manuscript should include an explicit statement of the theorem (with all parameters) in the introduction or §1 to make the central claim immediately locatable.
  2. Notation for order types and color patterns should be defined once at the beginning rather than assumed from context; a short preliminary section on order types would improve readability for readers outside combinatorial geometry.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our result on blow-ups of positive-density colored order types and for recommending minor revision. No specific major comments were listed in the report, so we have no point-by-point responses. We are happy to incorporate any minor editorial suggestions in the revised version.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper states a density Ramsey-type existence theorem for order types in general position. The claim asserts large disjoint subsets realizing a fixed positive-density colored order type on k-tuples; the constant c depends only on the stated parameters d, δ, k, κ. No equations, fitted parameters, self-referential definitions, or load-bearing self-citations appear in the abstract or the described derivation chain. The result is presented as a theorem whose hypotheses (general position, positive density) are independent of the conclusion, with no reduction of the output to the input by construction. This is the normal, non-circular case for a pure combinatorial existence result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard definition of order types and the general-position assumption common to combinatorial geometry; no free parameters or new entities are introduced.

axioms (2)
  • domain assumption Points of P are in general position in R^d
    Explicitly stated in the first sentence of the abstract as the setting for the point sequence.
  • standard math Order types capture combinatorial and convexity properties of point configurations
    Used as the foundational equivalence relation in the opening definition.

pith-pipeline@v0.9.1-grok · 5732 in / 1235 out tokens · 20734 ms · 2026-06-27T21:23:49.304164+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

11 extracted references

  1. [1]

    M. H. Albert, M. D. Atkinson, C. C. Handley, D. A. Holton, and W. Stromquist. On packing densities of permutations. Electron. J. Combin. , 9(1):Research Paper 5, 20, 2002

    2002

  2. [2]

    Kleitman

    Noga Alon, Imre B\'ar\'any, Zolt\'an F\"uredi, and Daniel J. Kleitman. Point selections and weak -nets for convex hulls. Combin. Probab. Comput. , 1(3):189--200, 1992

    1992

  3. [3]

    An ongoing project to improve the rectilinear and the pseudolinear crossing constants

    Oswin Aichholzer, Frank Duque, Ruy Fabila-Monroy, Oscar García-Quintero, and Carlos Hidalgo-Toscano. An ongoing project to improve the rectilinear and the pseudolinear crossing constants. Journal of Graph Algorithms and Applications , 24(3):421–432, Mar. 2020

    2020

  4. [4]

    A positive fraction E rd o s- S zekeres theorem

    Imre B \'a r \'a ny and Pavel Valtr. A positive fraction E rd o s- S zekeres theorem. Discrete & Computational Geometry , 19(3):335--342, 1998

    1998

  5. [5]

    New Bounds for the Same-Type Lemma

    Boris Bukh and Alexey Vasileuski. New Bounds for the Same-Type Lemma . The Electronic Journal of Combinatorics , pages P2.60--P2.60, 2024

    2024

  6. [6]

    Erd o s and G

    P. Erd o s and G. Szekeres. A combinatorial problem in geometry. Compositio Math. , 2:463--470, 1935

    1935

  7. [7]

    Overlap properties of geometric expanders

    Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, and J\'anos Pach. Overlap properties of geometric expanders. J. Reine Angew. Math. , 671:49--83, 2012

    2012

  8. [8]

    Carath\'eodory's theorem in depth

    Ruy Fabila-Monroy and Clemens Huemer. Carath\'eodory's theorem in depth. Discrete Comput. Geom. , 58(1):51--66, 2017

    2017

  9. [9]

    A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing

    Jacob Fox, J\'anos Pach, and Andrew Suk. A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing. SIAM J. Comput. , 45(6):2199--2223, 2016

    2016

  10. [10]

    A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing

    Jacob Fox, J \'a nos Pach, and Andrew Suk. A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing . SIAM Journal on Computing , 45(6):2199--2223, 2016

    2016

  11. [11]

    Goodman and Richard Pollack

    Jacob E. Goodman and Richard Pollack. Multidimensional sorting. SIAM J. Comput. , 12(3):484--507, 1983

    1983