Optimal detection of planted matchings via the cluster expansion
Presenter
January 13, 2026
Event: 66451
Abstract
We study the problem of detecting a planted matching — an independent edge set of order n — hidden in an Erdős–Rényi random graph G(n,p), formulated as a hypothesis testing problem. Unlike planted models with low-rank structures, the detection of a matching exhibits a smooth, not sharp, phase transition. More precisely, we show that the detection threshold occurs when p is on the order of n^(-1/2), at which the log-likelihood ratio is asymptotically normal. Moreover, the signed count of wedges (paths of length 2) is shown to be an asymptotically optimal statistic. Our main technique is the cluster expansion from statistical physics. In contrast to the widely used orthogonal expansion of the likelihood ratio, the cluster expansion is a series expansion of the log-likelihood ratio, which allows us to show its asymptotic normality directly.