Pith. sign in

REVIEW 2 cited by

Every $d(d+1)$-connected graph is globally rigid in $\mathbb{R}^d$

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2312.02028 v1 pith:QPXNGA7T submitted 2023-12-04 math.CO

Soma Villányi This is my paper · ORCID
classification math.CO
keywords connectedgloballyrigidconjecturegraphsmathbbproveargument
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

Using a probabilistic method, we prove that $d(d+1)$-connected graphs are rigid in $\mathbb{R}^d$, a conjecture of Lov\'asz and Yemini. Then, using recent results on weakly globally linked pairs, we modify our argument to prove that $d(d+1)$-connected graphs are globally rigid, too, a conjecture of Connelly, Jord\'an and Whiteley. The constant $d(d+1)$ is best possible.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Minimum degree conditions for graph rigidity

    math.CO 2024-12 accept novelty 7.0 of 10

    The paper proves that minimum degree (n+d)/2 - 1 forces d-rigidity for d=O(sqrt n), and (n+2d)/2 - 1 forces d-rigidity for d=O(n/log^2 n), plus a matching pseudoachromatic-number bound.

  2. On the Rigidity of Random Graphs in high-dimensional spaces

    math.CO 2024-12 conditional novelty 7.0 of 10

    For G(n,p), the largest rigidity dimension equals the minimum degree below p = C* log n/n, and equals (1/2 + o(1))np above it, up to p = o(n^{-1/2}).

Pith tools