<p>In the graph shotgun assembly problem, we are given the balls of radius <i>r</i> 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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="440_2025_1380_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="52" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mathcal {G}}(n,p)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">G</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for a wide range of values of <i>r</i>. We determine the threshold for reconstructibility for each <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="440_2025_1380_Article_IEq2.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(r\ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, extending and improving substantially on results of Mossel and Ross for <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="440_2025_1380_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(r=3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>=</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>. For <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="440_2025_1380_Article_IEq4.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(r=2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="440_2025_1380_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(r=1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Shotgun assembly of random graphs

  • Tom Johnston,
  • Gal Kronenberg,
  • Alexander Roberts,
  • Alex Scott

摘要

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 \({\mathcal {G}}(n,p)\) G ( n , p ) for a wide range of values of r. We determine the threshold for reconstructibility for each \(r\ge 3\) r 3 , extending and improving substantially on results of Mossel and Ross for \(r=3\) r = 3 . For \(r=2\) r = 2 , 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 \(r=1\) r = 1 .