论文标题
随机图的shot弹枪装配
Shotgun assembly of random graphs
论文作者
论文摘要
在图形shot弹枪装配问题中，我们将在图形的每个顶点周围为半径$ r $的球提供，并要求重建图形。我们研究了Erdős-rényi随机图$ \ Mathcal G（n，p）$的shot弹枪议会，其值为$ r $。我们确定每个$ r \ geq 3 $重构的阈值，以$ r = 3 $的成绩扩展并改善了Mossel和Ross的结果。对于$ r = 2 $，我们提供的上限和下界通过多项式因素改善了高迪奥和摩塞的结果。我们还以$ r = 1 $的价格对黄和Tikhomirov的结果进行了锐化。
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)$ for a wide range of values of $r$. We determine the threshold for reconstructibility for each $r\geq 3$, extending and improving substantially on results of Mossel and Ross for $r=3$. For $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$.
