pith. sign in

arxiv: 2605.21480 · v1 · pith:UIAGEXPUnew · submitted 2026-05-20 · 🧮 math.CO · math.MG· math.PR

Thresholds for geometric graphs

Bhargav Narayanan This is my paper

Pith reviewed 2026-05-21 03:00 UTC · model grok-4.3

classification 🧮 math.CO math.MGmath.PR
keywords random geometric graphsthresholdsmonotone graph propertiesmetric probability spacesuniform expansiontorispherescubes
0
0 comments X

The pith

Uniform expansion of a metric space ensures its random geometric graph has thresholds for every monotone property.

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

The paper shows that a metric probability space admits thresholds for its random geometric graphs precisely when the space expands uniformly. This means that for any monotone graph property the probability of the property holding in the graph jumps from near zero to near one at a critical radius. A reader would care because the result identifies a geometric condition that produces sharp phase transitions in models of spatial networks. The authors prove the connection and verify that all standard tori, spheres, and cubes satisfy it.

Core claim

A metric probability space M admits thresholds if the random geometric graph on M has a threshold for every monotone graph property. The paper connects the existence of thresholds to the uniform expansion of M and proves that all standard tori, spheres, and cubes admit thresholds.

What carries the argument

Uniform expansion of the metric probability space M, which the authors use to derive the threshold property for every monotone graph property in the induced random geometric graph.

If this is right

  • Every standard torus, sphere, and cube admits thresholds for all monotone graph properties in its random geometric graph.
  • The existence of thresholds follows directly from uniform expansion rather than from other geometric features of the space.
  • Monotone properties in these geometric graphs exhibit a sharp jump in probability at a critical radius determined by the expansion rate.

Where Pith is reading between the lines

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

  • The same link between expansion and thresholds may hold for other compact manifolds that expand uniformly.
  • The result suggests checking uniform expansion as a quick test for whether a geometric model will display abrupt network transitions.
  • Extensions to non-compact or discrete spaces with analogous expansion could be tested by direct simulation of the radius parameter.

Load-bearing premise

Uniform expansion of the metric probability space is sufficient to guarantee thresholds for every monotone graph property.

What would settle it

A concrete metric probability space that expands uniformly yet fails to produce a sharp threshold for some monotone property such as connectivity would disprove the claimed connection.

Figures

Figures reproduced from arXiv: 2605.21480 by Bhargav Narayanan.

Figure 1
Figure 1. Figure 1: The folding map in one coordinate. Lemma 4.2. For every monotone graph property F on [n] and every r ≥ 0, µ n Cd (FCd (r)) ≤ µ n Td (FTd (r)) ≤ µ n Cd (FCd (2r)). (3) Proof. For the first inequality, sample points in the fundamental cube [0, 1)d and view them once in the cube and once in the torus. Torus distance is never larger than cube distance, so every edge present in the cube at radius r is also pres… view at source ↗
Figure 2
Figure 2. Figure 2: A schematic picture of the pillowcase quotient. for the flat pillowcase. As shown in [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The suspension step, drawn on S 2 . Let the expansion of S m−1 be witnessed by maps drawn from a finitely supported probability measure P, and let q < 1 be the corresponding contraction factor. Suspend each map ϕ ∈ supp P to S m by bϕ(sin θ, cos θ u) = (sin θ, cos θ ϕ(u)). This map preserves spherical measure: conditional on the height h1 = sin θ, the point u is uniform on the latitude copy of S m−1 . It i… view at source ↗
read the original abstract

A metric probability space $M$ admits thresholds if the random geometric graph on $M$ has a threshold for every monotone graph property. We connect the existence of thresholds to the uniform expansion of $M$ and prove that all standard tori, spheres, and cubes admit thresholds.

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

2 major / 2 minor

Summary. The paper defines that a metric probability space M admits thresholds if the random geometric graph on M has a threshold for every monotone graph property. It connects the existence of thresholds to the uniform expansion of M and proves that all standard tori, spheres, and cubes admit thresholds.

Significance. If the central implication holds, the result supplies a sufficient condition (uniform expansion) for sharp thresholds across all monotone properties in geometric random graphs, with direct verification for the standard model spaces. This would clarify the role of expansion in controlling phase transitions and could extend to other geometric settings.

major comments (2)
  1. [§3] §3 (the step deriving thresholds from uniform expansion): the argument invokes that the expansion inequality forces the measure of small balls to behave uniformly at all scales and locations, but does not explicitly control the modulus of continuity of the measure or handle boundary effects; this is load-bearing for the claim that every monotone property has a threshold, and the implication can fail for density-sensitive properties on the cube.
  2. [Theorem 4.1] Theorem 4.1 (cubes): the verification of uniform expansion for the cube is given, yet the subsequent appeal to the general implication does not address how the flat boundary affects the local regularity needed for the threshold property; this undermines the conclusion that cubes admit thresholds for all monotone properties.
minor comments (2)
  1. [Introduction] The abstract states the main result cleanly, but the introduction could add a short paragraph contrasting the new expansion condition with earlier doubling or Ahlfors-regularity assumptions in the geometric-graph literature.
  2. [§2] Notation for the random geometric graph G(M,p) is introduced without an explicit reference to the underlying probability measure; a one-line reminder in §2 would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the major comments point by point below, providing clarifications and indicating planned revisions where appropriate.

read point-by-point responses

  1. Referee: [§3] §3 (the step deriving thresholds from uniform expansion): the argument invokes that the expansion inequality forces the measure of small balls to behave uniformly at all scales and locations, but does not explicitly control the modulus of continuity of the measure or handle boundary effects; this is load-bearing for the claim that every monotone property has a threshold, and the implication can fail for density-sensitive properties on the cube.

    Authors: We appreciate the referee highlighting the need for greater explicitness in this derivation. The uniform expansion property, as defined and used in §3, does force uniform behavior of ball measures at all scales and locations via a direct comparison argument: any non-uniformity in the measure of a small ball would produce a set violating the expansion inequality at the corresponding radius. We will revise §3 to include an auxiliary lemma that extracts an explicit modulus of continuity from the expansion constant, making this control fully transparent. On boundary effects and density-sensitive properties, we maintain that the implication does not fail for the cube (or other spaces with boundary): the definition of uniform expansion is intrinsic to the metric measure space and already incorporates cut-off balls near the boundary, while the monotonicity of the graph property ensures the threshold is insensitive to local density variations. We will add a short discussion subsection confirming this robustness for density-sensitive monotone properties. revision: partial

  2. Referee: [Theorem 4.1] Theorem 4.1 (cubes): the verification of uniform expansion for the cube is given, yet the subsequent appeal to the general implication does not address how the flat boundary affects the local regularity needed for the threshold property; this undermines the conclusion that cubes admit thresholds for all monotone properties.

    Authors: We thank the referee for this observation on the cube case. The verification of uniform expansion in Theorem 4.1 already uses the Euclidean metric restricted to the cube, so that boundary effects are built into the expansion constant; the flat boundary has measure zero and does not create local irregularities that violate the expansion inequality. Nevertheless, to directly address the concern about local regularity, we will expand the proof of Theorem 4.1 with an additional paragraph that isolates the boundary layer, shows its contribution is controlled by the global expansion constant, and confirms that the general implication from §3 applies without modification. This will strengthen the conclusion that cubes admit thresholds for all monotone properties. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation connects thresholds to expansion via independent proof

full rationale

The paper defines a metric probability space M as admitting thresholds when its random geometric graph has a threshold for every monotone property. It then claims to connect this existence to uniform expansion of M and verifies the property explicitly for standard tori, spheres, and cubes. No equation or step reduces the threshold existence to a fitted parameter, a self-referential definition, or a load-bearing self-citation; the connection is presented as a derived implication rather than an ansatz or renaming. The argument for the standard spaces rests on their geometric properties, which are external to the definition of thresholds and do not loop back to the input assumptions by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard definitions of metric probability spaces, random geometric graphs, and monotone properties; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard axioms of metric spaces and probability measures on them.
    Invoked in the definition of M and the random geometric graph construction.

pith-pipeline@v0.9.0 · 5550 in / 1087 out tokens · 27205 ms · 2026-05-21T03:00:17.989431+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

32 extracted references · 32 canonical work pages

  1. [1]

    B. J. Alder and T. E. Wainwright,Phase transition for a hard sphere system, The Journal of Chemical Physics27(1957), 1208–1209. 3

    work page 1957

  2. [2]

    Banyaga, A.,The structure of classical diffeomorphism groups, Mathematics and Its Applications, Kluwer Academic Publishers, 1997. 12

    work page 1997

  3. [3]

    F.,The geometry of discrete groups, Graduate Texts in Mathematics, Springer-Verlag, New York, 1983

    Beardon, A. F.,The geometry of discrete groups, Graduate Texts in Mathematics, Springer-Verlag, New York, 1983. 8

    work page 1983

  4. [4]

    and Erdős, P.,On a Ramsey–Turán type problem, J

    Bollobás, B. and Erdős, P.,On a Ramsey–Turán type problem, J. Combin. Theory Ser. B21(1976), 166–168. 3

    work page 1976

  5. [5]

    and Thomason, A.,Threshold functions, Combinatorica7(1987), 35–38

    Bollobás, B. and Thomason, A.,Threshold functions, Combinatorica7(1987), 35–38. 2

    work page 1987

  6. [6]

    Duminil-Copin, H., Raoufi, A., and Tassion, V.,Sharp phase transition for the random-cluster and Potts models via decision trees, Ann. of Math. (2)189(2019), 75–99. 3

    work page 2019

  7. [7]

    and Rényi, A.,On the evolution of random graphs, Magyar Tud

    Erdős, P. and Rényi, A.,On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl.5(1960), 17–61. 2

    work page 1960

  8. [8]

    C. M. Fortuin, P. W. Kasteleyn, and J. Ginibre,Correlation inequalities on some partially ordered sets, Communications in Mathematical Physics22(1971), 89–103. 3

    work page 1971

  9. [9]

    of Math.194(2021), 475–495

    Frankston, K., Kahn, J., Narayanan, B., and Park, J.,Thresholds versus fractional expectation-thresholds, Ann. of Math.194(2021), 475–495. 3

    work page 2021

  10. [10]

    Friedgut, E.,Sharp thresholds of graph properties, and thek-SAT problem, J. Amer. Math. Soc.12(1999), 1017–1054, With an appendix by Jean Bourgain. 3, 16

    work page 1999

  11. [11]

    and Kalai, G.,Every monotone graph property has a sharp threshold, Proc

    Friedgut, E. and Kalai, G.,Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc.124(1996), 2993–3002. 3, 16

    work page 1996

  12. [12]

    and Velenik, Y.,Statistical mechanics of lattice systems: A concrete mathematical introduction, Cambridge University Press, Cambridge, 2017

    Friedli, S. and Velenik, Y.,Statistical mechanics of lattice systems: A concrete mathematical introduction, Cambridge University Press, Cambridge, 2017. 3

    work page 2017

  13. [13]

    Gebelein, H.,Das statistische Problem der Korrelation als Variations- und Eigen- wertproblem und sein Zusammenhang mit der Ausgleichsrechnung, Z. Angew. Math. Mech.21(1941), 364–379. 13

    work page 1941

  14. [14]

    N.,Random plane networks, J

    Gilbert, E. N.,Random plane networks, J. Soc. Indust. Appl. Math.9(1961), 533–543. 3 17

    work page 1961

  15. [15]

    Goel, A., Rai, S., and Krishnamachari, B.,Monotone properties of random geometric graphs have sharp thresholds, Ann. Appl. Probab.15(2005), 2535–2552. 16

    work page 2005

  16. [16]

    O.,A connection between correlation and contingency, Proc

    Hirschfeld, H. O.,A connection between correlation and contingency, Proc. Cam- bridge Philos. Soc.31(1935), 520–524. 13

    work page 1935

  17. [17]

    Janson, S., Łuczak, T., and Ruciński, A.,Random graphs, Wiley-Interscience, 2000. 3

    work page 2000

  18. [18]

    Katona, G. O. H.,A theorem of finite sets, Theory of Graphs, Academic Press, New York, 1968, pp. 187–207. 2

    work page 1968

  19. [19]

    Kesten, H.,Symmetric random walks on groups, Trans. Amer. Math. Soc.92(1959), 336–354. 8

    work page 1959

  20. [20]

    Kotecký and D

    R. Kotecký and D. Preiss,Cluster expansion for abstract polymer models, Commu- nications in Mathematical Physics103(1986), 491–498. 3

    work page 1986

  21. [21]

    Kowalski, E.,An introduction to expander graphs, Cours Spécialisés, Société Mathé- matique de France, Paris, 2019. 8

    work page 2019

  22. [22]

    B.,The number of simplices in a complex, Mathematical Optimization Techniques, University of California Press, 1963, pp

    Kruskal, J. B.,The number of simplices in a complex, Mathematical Optimization Techniques, University of California Press, 1963, pp. 251–278. 2

    work page 1963

  23. [23]

    Lubotzky, A., Phillips, R., and Sarnak, P.,Ramanujan graphs, Combinatorica8 (1988), 261–277. 2

    work page 1988

  24. [24]

    Ma, J., Shen, W., and Xie, S.,An exponential improvement for Ramsey lower bounds, Invent. Math. (2026), to appear. 4

    work page 2026

  25. [25]

    A.,Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators, Problems Inform

    Margulis, G. A.,Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators, Problems Inform. Transmission24(1988), 39–46. 2

    work page 1988

  26. [26]

    L.,Threshold functions for random graphs on a line segment, Combin

    McColm, G. L.,Threshold functions for random graphs on a line segment, Combin. Probab. Comput.13(2004), 373–387. 2, 4

    work page 2004

  27. [27]

    and Pham, H

    Park, J. and Pham, H. T.,A proof of the Kahn–Kalai conjecture, J. Amer. Math. Soc.37(2024), 235–243. 3

    work page 2024

  28. [28]

    Penrose, M.,Random geometric graphs, Oxford University Press, 2003. 3

    work page 2003

  29. [29]

    Perkins, W.,Searching for (sharp) thresholds in random structures: Where are we now?, Bull. Amer. Math. Soc. (N.S.)62(2025), 113–143. 4

    work page 2025

  30. [30]

    Rényi, A.,On measures of dependence, Acta Math. Acad. Sci. Hungar.10(1959), 441–451. 13

    work page 1959

  31. [31]

    Stein, E. M. and Weiss, G.,Introduction to Fourier analysis on Euclidean spaces, Princeton University Press, 1971. 14

    work page 1971

  32. [32]

    S.,On sequences of pairs of dependent random variables, SIAM J

    Witsenhausen, H. S.,On sequences of pairs of dependent random variables, SIAM J. Appl. Math.28(1975), 100–113. 14 Department of Mathematics, Rutgers University, Piscataway, NJ 08854, USA Email address:narayanan@math.rutgers.edu 18

    work page 1975