Global rigidity of random graphs in \( \mathbb{R} \)
Consider a finite set of vertices \(V\) and suppose that we only know distances between some of them. In other words, consider a random graph \( G \) over \(V\) and a function \(d: E(G) \to \mathbb{R}^+ \cup {0}\). What properties of \(G\) make it possible to uniquely reconstruct the configuration of \(V\) (up to isometry)? We will show that the minimum degree \(\ge 2\) is alone sufficient with high probability.
A talk about the paper Global rigidity of random graphs in \(\mathbb{R}\) by Richard Montgomery, Rajko Nenadov, Tibor Szabó that I gave at the Spring School of Combinatorics 2024.