Pith. sign in

REVIEW 3 minor 20 references

Sharp threshold for reconstructing points on the line

T0 review · 0 major / 3 minor · reviewed 2026-05-10 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A supercritical random graph on points in the line reconstructs almost all pairwise distances inside its giant 2-core component.

desk verdict This paper proves the Girão et al. conjecture by showing a reconstructible subset of size (1-o(1)) times the 2-core component in supercritical random geometric graphs on the line, and extends it to ε=ω(1/ln n). read the letter →

arxiv 2604.09176 v1 submitted 2026-04-10 math.CO

Georgii Zakharov This is my paper · ORCID
classification math.CO
keywords reconstructiblesubsetsrandomgraphsontheline2-coredistancepreservationsupercriticalregimeErdős–RényilinearindependenceoverQ
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 establishes that when vertices are arbitrary points on the real line and edges appear independently with probability (1+ε)/n, a large subset of the 2-core becomes reconstructible with high probability. Reconstructible means that any map to the reals preserving distances on the random edges must automatically preserve all distances inside the subset. The authors prove the reconstructible piece can be taken to have size (1-o(1)) times the number of vertices in the largest 2-core component, which is stronger than the linear-size conjecture made earlier. The same conclusion holds even when ε grows slowly as ω(1/ln n).

What carries the argument

Reconstructible subset: a subset U whose pairwise distances are forced by any distance-preserving injection on the edges of G(V,p). The argument uses the known structure of the supercritical 2-core together with linear-independence arguments to control the possible embeddings.

What would settle it

An explicit point configuration on the line together with a random graph realization in which every reconstructible subset inside the 2-core component omits a fixed positive fraction of its vertices would falsify the claim.

Watch

Extended reading notes

Core claim

For every ε>0, in the random graph G(V,p) with p=(1+ε)/n on any set V of n points in R, with high probability the largest component C of the 2-core contains a reconstructible subset U satisfying |U|=|V(C)|(1-o(1)). When the points of V are linearly independent over Q the size R of any largest reconstructible subset satisfies R≤max(2,|V(C)|), showing the new lower bound is asymptotically tight.

Load-bearing premise

The analysis relies on the 2-core of G(n,p) behaving exactly as it does in the standard supercritical Erdős–Rényi model, together with the definition of reconstructibility through real-valued distance-preserving injections.

Editorial extensions

If this is right

  • The earlier conjecture of Girão, Illingworth, Michel, Powierski and Scott holds in a strengthened form that captures almost the entire 2-core.
  • Reconstruction of distances is possible for all but an o(1) fraction of the points that lie in the giant 2-core component.
  • The same almost-complete reconstruction persists when the edge probability is taken as (1+ω(1/ln n))/n.
  • When the points are linearly independent over the rationals, no larger reconstructible set exists than the one constructed here, up to an additive constant of 2.

Reading between the lines

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

  • The result indicates that the dense connectivity inside the 2-core forces global rigidity on the line once a single distance is anchored.
  • Similar thresholds may exist for random graphs whose vertices lie in higher-dimensional Euclidean space or in other metric spaces with rigid motions.
  • Algebraic dependencies among the coordinates could allow strictly larger reconstructible sets, which the paper leaves open for future investigation.
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 / 3 minor

Summary. The paper proves that for a set of n points V on the real line, in the random graph G(V,p) with p=(1+ε)/n for any fixed ε>0, with high probability the largest component C of the 2-core admits a reconstructible subset U satisfying |U| = |V(C)|(1-o(1)). A subset U is reconstructible if every edge-distance-preserving injection φ:V→R also preserves all pairwise distances within U. This establishes a stronger form of the conjecture of Girão et al. The argument relies on the standard structure of the supercritical 2-core together with unique realization up to global isometry for all but o(|V(C)|) vertices. Asymptotic sharpness follows from the observation that when the points are linearly independent over Q, the maximum reconstructible size R satisfies R ≤ max(2,|V(C)|). The result is extended to the regime ε=ω(1/ln n).

Significance. If the central claims hold, the work resolves the conjecture in a quantitatively strong form by exhibiting an asymptotically complete reconstructible subset inside the 2-core. It combines standard random-graph analysis of the 2-core with a distance-preservation argument and supplies a clean, parameter-free upper bound via linear independence over Q. The extension to slowly vanishing ε is a useful strengthening. Credit is due for the matching upper bound that demonstrates asymptotic optimality and for keeping the argument self-contained within the tools of random graph theory.

minor comments (3)
  1. [Abstract] Abstract: the quantity R is introduced as the size of a largest reconstructible subset but is not explicitly linked to the main theorem; a single sentence tying the (1-o(1)) result to the definition of R would improve readability.
  2. [Upper bound section] Upper-bound argument: the claim that linear independence over Q immediately yields R ≤ max(2,|V(C)|) is described as straightforward, yet a one-paragraph sketch of why only two points can be reconstructed would help readers outside algebraic combinatorics.
  3. [Extension paragraph] Extension to ε(n)=ω(1/ln n): the o(1) terms in the size guarantee depend on n; a brief remark on the uniformity of the high-probability statement across this range would clarify the scope of the result.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of our work, which correctly identifies the main result: that whp the largest reconstructible subset inside the 2-core is asymptotically the full size of the giant 2-core component, establishing a quantitatively strong form of the Girão et al. conjecture, together with the matching upper bound via linear independence over Q and the extension to ε=ω(1/ln n). We appreciate the recognition of the self-contained nature of the argument and its significance.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The paper's central result—that a (1-o(1)) fraction of the 2-core vertices form a reconstructible set under distance-preserving injections into R—is derived from the standard supercritical structure of the Erdős–Rényi 2-core (an externally established fact) together with a direct argument that linear independence over Q forces uniqueness of realization for all but o(|V(C)|) points. The upper-bound comparison is an immediate verification from the definition of linear independence and does not rely on any fitted parameters, self-referential definitions, or load-bearing self-citations. No step reduces a claimed prediction to its own inputs by construction, and the argument remains self-contained against independent literature on random graphs and rigidity.

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

The claim rests on standard results from random graph theory about the 2-core in the supercritical regime and the definition of reconstructibility; no free parameters are fitted and no new entities are postulated.

assumptions (1)
  • standard math Known structural properties of the 2-core in Erdős–Rényi graphs G(n,p) for p=(1+ε)/n
    The paper invokes the existence and size of the giant 2-core component as background.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sharp threshold for reconstructing points on the line." pith.science (2026). https://pith.science/paper/2604.09176

@misc{pith2026260409176,
  author       = {Pith},
  title        = {Pith review of: Sharp threshold for reconstructing points on the line},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2604.09176}},
  note         = {Machine review of arXiv:2604.09176}
}
abstract

For a set of $n$ points $V \subseteq \mathbb{R}$ let $G(V, p)$ be the random graph on $V$ where each possible edge is present independently with probability $p$. We call a subset $U \subseteq V$ {\emph {reconstructible}} if every injection $\varphi:V\to \mathbb{R}$ that preserves the distances along the edges of $G(V, p)$ also preserves all pairwise distances in $U$. How large is the size $\mathsf{R}$ of a largest reconstructible subset? Gir\~ao, Illingworth, Michel, Powierski and Scott conjectured that the answer is linear whp when $p = (1+\varepsilon)/n$ for every $\varepsilon > 0$. In this paper, we show that for every $\varepsilon>0$ whp there exists a reconstructible subset $U$ of the largest component $\mathcal{C}$ of the 2-core satisfying $|U| = |V(\mathcal{C})|(1-o(1))$, proving a stronger form of the conjecture. The bound is asymptotically best possible, since for $V \subseteq \mathbb{R}$ linearly independent over $\mathbb{Q}$ it is straightforward to verify that $\mathsf{R} \leq \max(2, |V(\mathcal{C})|)$. Furthermore, we extend these results to every $\varepsilon:= \varepsilon(n)$ satisfying $\varepsilon = \omega(1/\ln n)$.

Figures

Figures reproduced from arXiv: 2604.09176 by the authors.

Figure 1
Figure 1. The figure illustrates the structure of K∗ , U, and N. The red subset consists of vertices v ∈ V (K) with fixed random value π(v). the number of ways to define φ on U. In order to do that consider a subtree T with vertex set {u ∗} ⊔ U, which exists due to B1. Then, for every edge uv ∈ E(T ) we have φ(π(v)) − φ(π(u)) = ±(π(v) − π(u)). (5) Since by B3 φ(π(u ∗ )) = π(u ∗ ) deciding the signs in (5) over the edges of T … view at source ↗
Figure 2
Figure 2. The figure illustrates the structure of TK in K given by P6. We assign to each edge E(K) a sign from {+, −, ?} as follows. For an edge uv ∈ E(K), we assign either “+” or “−” if φ(π(u))−φ(π(v)) π(u)−π(v) equals to 1 or −1 respectively, otherwise we assign “?”. In the figure, the boxes represent the equivalence classes of P and the red edges make up the tree TK. Notice that, in the picture, the tree TK should contain … view at source ↗
Figure 3
Figure 3. The figure illustrates the structure of F in K. For an edge uv ∈ E(K), we assign either “+” or “−” if φ(π(u))−φ(π(v)) π(u)−π(v) equals to 1 or −1 respectively, otherwise we assign “?”. The boxes represent the equivalence classes of P and the red edges make up the forest F. Then, F suits the role described above. Indeed, let TK be an arbitrary spanning tree containing F. Then, P5 holds trivially from Q1. In order to … view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: The figure illustrates the structure of TK, E1, and E2 in K in the proof of Claim 4.16. In the figure, the boxes represent the equivalence classes of P and the red edges make up the tree TK. The edges lying in E1 and E2 are labelled 1 and 2 respectively. Proof. Let us …
Figure 5
Figure 5. Figure 5: The figure illustrates the four types of edges, [PITH_FULL_IMAGE:figures/full_fig_p024_5.png]
Figure 6
Figure 6. Figure 6: The figure illustrates the structure of S, NK(S), and V¯ in K. Let us set V¯ = {v ∈ V (K) | φ(π(v)) = π(v)}, so B2 holds due to (29). Since φ disproves that π({v ∈ V (K) | D(v) holds}) is reconstructible, there exists a vertex v ∈ V (K) such that D(v) holds but φ(π(v))…
Figure 7
Figure 7. Figure 7: The figure illustrates the structure of S, N, δU, U ˜ , and F in K and C. The kernel K in the left figure is similar to K from the toy example, [PITH_FULL_IMAGE:figures/full_fig_p030_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Alon and J.H

    N. Alon and J.H. Spencer,The Probabilistic Method, (2016)

    work page 2016

  2. [2]

    Benjamini, K

    I. Benjamini, K. Gady, and W. Nicholas,The mixing time of the giant component of a random graph, Random Structures & Algorithms45:3 (2014), 383-407

    work page 2014

  3. [3]

    Determining a Points Configuration from a Subset of the Pairwise Distances

    I. Benjamini and E. Tzalik,Determining a Points Configuration on the Line from a Subset of the Pairwise Distances, arXiv preprint, arXiv:2208.13855, (2024)

    work page Pith review arXiv 2024

  4. [4]

    Bollob´ as,The art of mathematics: Coffee time in Memphis, Cambridge University Press (2006)

    B. Bollob´ as,The art of mathematics: Coffee time in Memphis, Cambridge University Press (2006)

    work page 2006

  5. [5]

    Bollob´ as,The isoperimetric number of random regular graphs.European Journal of Com- binatorics9:3 (1988), 241–244

    B. Bollob´ as,The isoperimetric number of random regular graphs.European Journal of Com- binatorics9:3 (1988), 241–244

    work page 1988

  6. [6]

    D. G. Brown,How I wasted too long finding a concentration inequality for sums of geometric variablesfound at https://cs.uwaterloo.ca/⁄tildelowbrowndg/negbin.pdf, (2011)

    work page 2011

  7. [7]

    Ding, J.H

    J. Ding, J.H. Kim, E. Lubetzky, and Y. Peres,Anatomy of a young giant component in the random graph, Random Structures & Algorithms,39:2, (2011) 139-178

    work page 2011

  8. [8]

    J. Ding, E. Lubetzky, and Y. Peres,Anatomy of the giant component: The strictly supercritical regime, European Journal of Combinatorics,35, (2014) 155-168

    work page 2014

Show all 20 references
  1. [9]

    Friedman,A proof of Alon’s second eigenvalue conjecture and related problems, American Mathematical Society, (2008)

    J. Friedman,A proof of Alon’s second eigenvalue conjecture and related problems, American Mathematical Society, (2008)

    2008

  2. [10]

    Frieze, M

    A. Frieze, M. Karo´ nski,Introduction to Random Graphs, Cambridge University Press (2015)

    2015

  3. [11]

    P. Gao, Y. Ohapkin.Subgraph probability of random graphs with specified degrees and appli- cations to chromatic number and connectivity, Random Structures & Algorithms,62:4 (2023) 911-934

    2023

  4. [12]

    Garamv¨ olgyi,Global rigidity of (quasi-)injective frameworks on the line, Discrete Mathe- matics,345:2, (2022)

    D. Garamv¨ olgyi,Global rigidity of (quasi-)injective frameworks on the line, Discrete Mathe- matics,345:2, (2022)

    2022

  5. [13]

    Gir˜ ao, F

    A. Gir˜ ao, F. Illingworth, L. Michel, E. Powierski, and A. Scott,Reconstructing a Point Set from a Random Subset of Its Pairwise Distances, SIAM Journal on Discrete Mathematics, 38:4, (2024), 2709-2720

    2024

  6. [14]

    Graver, B

    J. Graver, B. Servatius, and H. Servatius,Combinatorial Rigidity, American Mathematical Society, (1993). 46

    1993

  7. [15]

    Greenhill and B

    C. Greenhill and B. D. McKay,Asymptotic Enumeration of Sparse Multigraphs with Given Degrees, SIAM Journal on Discrete Mathematics,27:4, (2013), 2064-2089

    2013

  8. [16]

    Montgomery, R

    R. Montgomery, R. Nenadov, J. Portier, and T. Szab´ o,Global rigidity of random graphs in R, arXiv preprint arXiv:2401.10803 (2024)

    2024

  9. [17]

    Pittel, J

    B. Pittel, J. Spencer, and N. WormaldSudden Emergence of a Giant k-Core in a Random Graph, Journal of Combinatorial Theory Series B,67:1 (1996), 111-151

    1996

  10. [18]

    Portier,Reconstructing a Giant Component of a Point Set inR, arXiv preprint, arXiv:2602.23122, (2026)

    J. Portier,Reconstructing a Giant Component of a Point Set inR, arXiv preprint, arXiv:2602.23122, (2026)

    2026

  11. [19]

    Portier,Topics in Probabilistic Combinatorics, Doctoral Dissertation (2025)

    J.P. Portier,Topics in Probabilistic Combinatorics, Doctoral Dissertation (2025)

    2025

  12. [20]

    Janson and M.J

    S. Janson and M.J. LuczakA simple solution to the k-core problem, Random Structures & Algorithms,30:(1-2), (2007), 50-62. 47

    2007

Pith tools

Reviewed May 10, 2026 · model on record in the stance chip above.