Krivelevich–Lew–Michaeli edge-counting conjecture for graph rigidity

Let f(n,d)f(n,d) be the smallest integer such that every nn-vertex graph with minimum degree at least f(n,d)f(n,d) is dd-rigid. A graph is dd-rigid when every generic framework in Rd\mathbb{R}^d is rigid. Krivelevich–Lew–Michaeli's conjecture. For 1d<n1\leq d<n,

f(n,d)max{n+d22,2dd(d+1)n}.f(n,d)\leq \max\left\{\left\lceil\frac{n+d-2}{2}\right\rceil,\left\lceil 2d-\frac{d(d+1)}{n}\right\rceil\right\}.

The paper states that this conjecture is verified in the special cases d{2,3}d\in\{2,3\}; the general case is not asserted to be solved here.

Sources & referencesView supporting material

Primary source

Tibor Jordán, Xuemei Liu and Soma Villányi, “Degree Sum Conditions for Graph Rigidity”, arXiv:2510.25689 (2025).

Additional references

2 papers in this index state this conjecture (2024–2025). The statement above is taken from the most recent of them; the others are arXiv:2412.13127.

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.