Shotgun assembly of random graphs

Tom Johnston; Gal Kronenberg; Alexander Roberts; Alex Scott

doi:10.1007/s00440-025-01380-x

Shotgun assembly of random graphs

Tom Johnston, Gal Kronenberg, Alexander Roberts, Alex Scott

School of Mathematics

Research output: Contribution to journal › Article (Academic Journal) › peer-review

Abstract

In the graph shotgun assembly problem, we are given the balls of radius r around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the Erdős-Rényi random graph for a wide range of values of r. We determine the threshold for reconstructibility for each , extending and improving substantially on results of Mossel and Ross for . For , we give upper and lower bounds that improve on results of Gaudio and Mossel by polynomial factors. We also give a sharpening of a result of Huang and Tikhomirov for .

Original language	English
Journal	Probability Theory and Related Fields
Early online date	5 Jun 2025
DOIs	https://doi.org/10.1007/s00440-025-01380-x
Publication status	E-pub ahead of print - 5 Jun 2025

Bibliographical note

Publisher Copyright:
© The Author(s) 2025.

Access to Document

10.1007/s00440-025-01380-xLicence: CC BY

Handle.net

Persistent link

Cite this

@article{fb113808fc0a4938b5cf0ede33fb52db,

title = "Shotgun assembly of random graphs",

abstract = "In the graph shotgun assembly problem, we are given the balls of radius r around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the Erd{\H o}s-R{\'e}nyi random graph for a wide range of values of r. We determine the threshold for reconstructibility for each , extending and improving substantially on results of Mossel and Ross for . For , we give upper and lower bounds that improve on results of Gaudio and Mossel by polynomial factors. We also give a sharpening of a result of Huang and Tikhomirov for .",

author = "Tom Johnston and Gal Kronenberg and Alexander Roberts and Alex Scott",

note = "Publisher Copyright: {\textcopyright} The Author(s) 2025.",

year = "2025",

month = jun,

day = "5",

doi = "10.1007/s00440-025-01380-x",

language = "English",

journal = "Probability Theory and Related Fields",

issn = "0178-8051",

publisher = "Springer, New York, NY",

}

TY - JOUR

T1 - Shotgun assembly of random graphs

AU - Johnston, Tom

AU - Kronenberg, Gal

AU - Roberts, Alexander

AU - Scott, Alex

PY - 2025/6/5

Y1 - 2025/6/5

N2 - In the graph shotgun assembly problem, we are given the balls of radius r around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the Erdős-Rényi random graph for a wide range of values of r. We determine the threshold for reconstructibility for each , extending and improving substantially on results of Mossel and Ross for . For , we give upper and lower bounds that improve on results of Gaudio and Mossel by polynomial factors. We also give a sharpening of a result of Huang and Tikhomirov for .

AB - In the graph shotgun assembly problem, we are given the balls of radius r around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the Erdős-Rényi random graph for a wide range of values of r. We determine the threshold for reconstructibility for each , extending and improving substantially on results of Mossel and Ross for . For , we give upper and lower bounds that improve on results of Gaudio and Mossel by polynomial factors. We also give a sharpening of a result of Huang and Tikhomirov for .

U2 - 10.1007/s00440-025-01380-x

DO - 10.1007/s00440-025-01380-x

M3 - Article (Academic Journal)

SN - 0178-8051

JO - Probability Theory and Related Fields

JF - Probability Theory and Related Fields

ER -

Shotgun assembly of random graphs

Abstract

Bibliographical note

Access to Document

Handle.net

Fingerprint

Cite this