← All problems

Sparsity of 1-universally rigid graphs

A graph G=(V,E)G=(V,E) is called 11-universally rigid if, for every generic realization p:V→Rp:V\to\mathbb{R}, every realization q:V→Rdq:V\to\mathbb{R}^d in any dimension d≥1d\geq 1 satisfying ∥q(u)−q(v)∥=∣p(u)−p(v)∣\lVert q(u)-q(v)\rVert=\lvert p(u)-p(v)\rvert for every uv∈Euv\in E is congruent to the realization of pp in Rd\mathbb{R}^d. The sparsity conjecture asks whether every 11-universally rigid graph with n=∣V∣n=\lvert V\rvert vertices satisfies ∣E∣≥2n−3\lvert E\rvert\geq 2n-3.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A new preprint claims stronger examples and a better edge bound, but the main sparsity question remains open.

The problem asks how sparse graphs can be while being 11-universally rigid, including whether the suspected bound ∣E∣≥2∣V∣−3|E|\geq 2|V|-3 always holds. The large-girth existence problem was suggested by Dantas e Moura, Jordán, and Silverman.

Known results

  • Previously known: every 11-universally rigid graph with at least six vertices satisfies ∣E∣≥(3/2)∣V∣|E|\geq (3/2)|V|.
  • The best-known constructions attain ∣E∣=2∣V∣−3|E|=2|V|-3.

October 2026 preprint

Ole Gabsdil, Ezra Hirschi, and Julien Portier claim that random graphs are 11-universally rigid with high probability above p≥Clog⁡n log⁡log⁡n/np\geq C\log n\,\log\log n/n, yielding examples of arbitrarily large girth. They also claim ∣E∣≥(3/2+ε)∣V∣|E|\geq (3/2+\varepsilon)|V| for sufficiently large graphs, with ε=1/26\varepsilon=1/26 possible. This is claimed progress, not a resolution: the bound ∣E∣≥2∣V∣−3|E|\geq 2|V|-3 remains open.

Current status (as of November 2026): An October 2026 preprint claims arbitrarily large-girth examples and improves the general lower bound, but the optimal sparsity bound ∣E∣≥2∣V∣−3|E|\geq 2|V|-3 remains open and the claims are unverified.

Sources

Solutions 0

No solutions have been posted yet.