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.
