The conjecture that random 4-regular graphs are globally rigid in the real line

Let GG be a random 44-regular graph on nn vertices. Global rigidity is considered for frameworks in R\mathbb{R}.

Random 4-regular graph rigidity conjecture. A random 44-regular graph with nn vertices is globally rigid in R\mathbb{R} with high probability.

The preceding result rules out the analogous statement for random 33-regular graphs. For sufficiently large degrees, the paper's methods imply global rigidity with high probability, so the conjecture concerns whether degree four is already sufficient; the smallest suitable degree is otherwise left open.

Sources & referencesView supporting material

Primary source

Richard Montgomery, Rajko Nenadov, Julien Portier and Tibor Szabó, “Global rigidity of random graphs in R”, arXiv:2401.10803 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.