Global Rigidity of Random Graphs in \({\mathbb{R}}\)
摘要
Consider the Erdős-Rényi random graph process \(\{ G_{m} \}_{m \ge 0}\) in which we start with an empty graph G0 on the vertex set [n], and in each step form Gi from \(G_{i - 1}\) by adding one new edge chosen uniformly at random. Resolving a conjecture by Benjamini and Tzalik, we give a simple proof that w.h.p. as soon as Gm has minimum degree 2 it is globally rigid in the following sense: For any function \(d:E(G_{m} ) \to {\mathbb{R}}\) , there exists at most one injective function \(f:[n] \to {\mathbb{R}}\) (up to isometry) such that \(d(ij) = \left| {f(i) - f(j)} \right|\) for every \(ij \in E(G_{m} )\) . We also resolve a related question of Girão, Illingworth, Michel, Powierski, and Scott in the sparse regime for the random graph and give some open problems.