论文标题
稀疏Erdős-rényi图的shot弹枪阈值
Shotgun threshold for sparse Erdős-Rényi graphs
论文作者
论文摘要
在图形的shot弹枪装配问题中，我们为某些$ r \ geq 1 $的深度$ r $（最高型同构）提供了经验概况，我们希望恢复基础图至同构。当基础图是一个erdős-rényi$ \ Mathcal g（n，\fracλ{n}）$时，我们表明shot弹枪装配阈值$ r_* \ of r_* \ of of frac {\ log n} {\ log n} {\ log log（λ^2γ_λ）具有参数$λ$的树是彼此植根的同构的。我们的结果使Mossel and Ross（2019）的先前工作中不断提高了一个因素，从而解决了其中的问题。
In the shotgun assembly problem for a graph, we are given the empirical profile for rooted neighborhoods of depth $r$ (up to isomorphism) for some $r\geq 1$ and we wish to recover the underlying graph up to isomorphism. When the underlying graph is an Erdős-Rényi $\mathcal G(n, \fracλ{n})$, we show that the shotgun assembly threshold $r_* \approx \frac{ \log n}{\log (λ^2 γ_λ)^{-1}}$ where $γ_λ$ is the probability for two independent Poisson-Galton-Watson trees with parameter $λ$ to be rooted isomorphic with each other. Our result sharpens a constant factor in a previous work by Mossel and Ross (2019) and thus solves a question therein.
