Abstract
Motivated by the application of tracking moving particles from snapshots, we study the problem of recovering a planted perfect matching hidden in an Erdős–Rényi bipartite graph. We establish the information-theoretic threshold for almost exact recovery of the hidden matching. Our result extends to general weighted graphs across both dense and sparse regimes. Further more, in the special case of exponential weights, we prove that the optimal reconstruction error is infinitely smooth at the threshold, confirming the conjectured infinite-order phase transition in [Semerjian et al. 2020]. This is joint work with Jian Ding (Penn), Yihong Wu (Yale) and Jiaming Xu (Duke).