Shotgun Threshold for Sparse Erdos-Renyi Graphs

被引：0
|
作者：
Ding, Jian [1 ]
Jiang, Yiyang [1 ]
Ma, Heng [1 ]
机构：
[1] Peking Univ, Sch Math Sci, Beijing 100871, Peoples R China
来源：
IEEE TRANSACTIONS ON INFORMATION THEORY | 2023年 / 69卷 / 11期
关键词：
Vegetation; DNA; Upper bound; Stress; Sequential analysis; Random variables; Neural networks; Shotgun assembly; Erdoos-Renyi graphs; phase transition; Poisson-Galton-Watson trees; ISOMORPHISM; THEOREM;
D O I：
10.1109/TIT.2023.3298515
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In the shotgun assembly problem for a graph,we are given the empirical profile for rooted neighborhoods of depth r(up to isomorphism) for somer >= 1 and we wish to recover the underlying graph up to isomorphism. When the underlying graph is an Erdos-Renyi G(n,lambda / n), we show that the shotgun assembly threshold r(& lowast; )satisfies that r(& lowast;) approximate to logn / log(lambda(2)gamma lambda(-1 )where gamma(lambda )is the probability for two independent Poisson-Galton-Watson trees with parameter lambda 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
引用
收藏
页码：7373 / 7391
页数：19
相关论文
共 34 条
1234