学术报告

您所在的位置:首页  学术交流  学术报告

All-something-nothing phase transition in planted subgraph recovery

发布时间:2025-06-04阅读次数:10

We uncover an interesting “all-something-nothing” phase transition in the recovery of certain sparse planted structures within an Erdős–Rényi random graph. This finding complements the result by Mossel, Niles-Weed, Sun and Zadik who established that for certain sufficiently dense graphs, the problem undergoes an “all-or-nothing” phase transition, jumping from near-perfect to near-zero recovery. In particular, we prove the existence of a transitional “something” regime when the planted structure is a k-factor, when k is a fixed constant; and when the planted structure is a union of cycles.

海报.pdf