Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs (Q2240864)

\noindent Let \(G_n\) be a simple random graph on \(n\) vertices obtained by connecting each pair of vertices independently with probability \(p_n = \lambda/n\). Edges are given weights, which are nonnegative independent random variables with common distribution \(F_w^{(n)}\). \(F_w^{(n)}\) may depend on \(n\), but it is assumed to converge in total variation to some distribution \(F_w\). \noindent This paper considers functions \(f\) defined on \(G_n\), and introduces a method for establishing central limit theorems, \[\frac{f(G_n) - E [f(G_n)]}{\sqrt{Var [f(G_n)]}} \stackrel{d} {\longrightarrow} N(0,1).\] Examples covered by this framework consist of maximum weight matching, \(\lambda\)-diluted minimum matching, and optimal edge cover.