Pith. sign in

REVIEW 3 minor 20 references

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

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-05-10 17:18 UTC

load-bearing objection 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).

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

Sharp threshold for reconstructing points on the line

Georgii Zakharov This is my paper
classification math.CO
keywords reconstructible subsetsrandom graphs on the line2-coredistance preservationsupercritical regimeErdős–Rényi graphslinear independence over Q
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

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).

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.

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.

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.

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 this falsifier. Get emailed when new claim-graph text bears on it.

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.

Where Pith is reading between the lines

These are 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.

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 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.

axioms (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.

pith-pipeline@v0.9.0 · 5555 in / 1223 out tokens · 69248 ms · 2026-05-10T17:18:41.017845+00:00 · methodology

0 comments
read the original 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 Georgii Zakharov.

Figure 1
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 e… view at source ↗
Figure 2
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 shoul… view at source ↗
Figure 3
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… view at source ↗
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 give a brief plan of the proof. We suppose that, for some choice of π, the number of edges from E(K) satisfying D is less than 30εk. We firs… view at source ↗
Figure 5
Figure 5. Figure 5: The figure illustrates the four types of edges, [PITH_FULL_IMAGE:figures/full_fig_p024_5.png] view at source ↗
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)) ̸= π(v). Let S ⊆ V (K) be the vertex set of the component of K−V¯ containing v (see [PITH_FULL_IMAGE:figures/full_fig_p029_6.png] view at source ↗
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] view at source ↗

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

20 extracted references · 20 canonical work pages · 1 internal anchor

  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 internal anchor 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

  9. [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)

    work page 2008

  10. [10]

    Frieze, M

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

    work page 2015

  11. [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

    work page 2023

  12. [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)

    work page 2022

  13. [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

    work page 2024

  14. [14]

    Graver, B

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

    work page 1993

  15. [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

    work page 2013

  16. [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)

    work page arXiv 2024

  17. [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

    work page 1996

  18. [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)

    work page arXiv 2026

  19. [19]

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

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

    work page 2025

  20. [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

    work page 2007