Sparsity of 1-universally rigid graphs
A graph is called -universally rigid if, for every generic realization , every realization in any dimension satisfying for every is congruent to the realization of in . The sparsity conjecture asks whether every -universally rigid graph with vertices satisfies .
References
- On sparse universally rigid graphs in R — arXiv — Ole Gabsdil, Ezra Hirschi, Julien Portier
Source: arXiv
Progress summary
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 -universally rigid, including whether the suspected bound always holds. The large-girth existence problem was suggested by Dantas e Moura, Jordán, and Silverman.
Known results
- Previously known: every -universally rigid graph with at least six vertices satisfies .
- The best-known constructions attain .
October 2026 preprint
Ole Gabsdil, Ezra Hirschi, and Julien Portier claim that random graphs are -universally rigid with high probability above , yielding examples of arbitrarily large girth. They also claim for sufficiently large graphs, with possible. This is claimed progress, not a resolution: the bound 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 remains open and the claims are unverified.
Sources
Solutions 0
No solutions have been posted yet.