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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Global Rigidity of Random Graphs in \({\mathbb{R}}\)

  • Richard Montgomery,
  • Rajko Nenadov,
  • Tibor Szabó

摘要

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.