22
$\begingroup$

It is an old result that every $6$-connected graph is rigid in $\mathbb{R}^2$:

Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete Methods 3, no. 1 (1982): 91-98. DOI.

It is natural to hope that sufficiently high connectivity implies rigidity in $\mathbb{R}^3$.

Q. Is it known that there is some $k$ such that any $k$-connected graph is generically rigid in $\mathbb{R}^3$?

Informally, $G$ is rigid if the distances between vertices connected in $G$ determine all the distances between vertices not connected in $G$. More formally, $G$ is generically rigid in $\mathbb{R}^d$ if every generic representation in $\mathbb{R}^d$ is infinitesimally rigid—no infinitesimal length-preserving velocities (if they exist) can be extended. An embedded graph representation (a framework) is generic if the coordinates of its configuration do not satisfy any non-trivial algebraic equation with rational coefficients.

There have been recent advances in 3D rigidity and I am unclear on the current status of this question Q.

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ For the reader: $k$-connected means that there are $>k$ vertices, and removing any $< k$ vertices yields a connected graph. $\endgroup$
    – YCor
    Commented May 9, 2021 at 11:25
  • $\begingroup$ @FedorPetrov: I believe the implication direction is: If infinitesimally rigid in $\mathbb{R}^3$, then $m \ge 3 n - 6$, where $m$ is the number of edges and $n$ the number of vertices. It is iff in the plane (with $m \ge 2 n - 3$). The flexible, generic double-banana satisfies $m = 3n-6$. $\endgroup$
    – Joseph O'Rourke
    Commented May 9, 2021 at 12:46
  • $\begingroup$ I do not think that even on the plane it is iff: glue two large complete graphs by a vertex. Actually, if for certain $k$ vertices there are more than $3k-6$ edges between them, and total number of edges is $3n-6$, it can not be rigid (analogously in dimension 2). $\endgroup$
    – Fedor Petrov
    Commented May 9, 2021 at 14:24
  • $\begingroup$ @FedorPetrov: Sorry, my misinterpretation of JieGao lecture notes: It is, instead of $m$, the rank of the rigidity matrix $R$---"disregarding global translation and rotation, the framework $G(P)$ is infinitesimally rigid if and only if rank$(R) = 2n − 3$." PDF. $\endgroup$
    – Joseph O'Rourke
    Commented May 9, 2021 at 14:39
  • 1
    $\begingroup$ Adding nothing but a physical example to what has already been described. A door is a physical realization of an infinitely connected graph that is not rigid. $\endgroup$
    – Anthony Quas
    Commented May 10, 2021 at 1:56

2 Answers 2

Reset to default
17
$\begingroup$

Update. The recent paper Every $d(d+1)$-connected graph is globally rigid in $\mathbb{R}^d$ by Soma Villányi gives a positive answer to the question.

Old Answer. I think this is still an open problem, but recent work of Clinch, Jackson, and Tanigawa (almost) shows every $12$-connected graph is generically rigid in $\mathbb{R}^3$.

In that paper, they prove that $12$-connectivity is sufficient to force rigidity in the $C_2^1$-cofactor matroid (see the paper for precise definitions). In an earlier paper, the same authors showed that the $C_2^1$-cofactor matroid is the unique maximal abstract $3$-rigidity matroid. A long-standing conjecture in rigidity theory is that the unique maximal abstract $3$-rigidity matroid is in fact the generic $3$-dimensional rigidity matroid. If you believe this conjecture, then the answer to your quesiton is yes, with one million replaced with $12$.

Acknowledgement. The old answer is entirely due to Katie Clinch.

Improve this answer
$\endgroup$
5
$\begingroup$

update: this is an answer without generic configuration assumption

I am afraid that no. Take two half-planes with a common boundary line $a$, and many points both on $a$ and in these half-planes. Join by edges all pairs of points in the same half-plane. Now rotate one of the half-planes around $a$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I can't claim to fully understand the terms used in the question, but I don't think this is a counterexample to generic rigidity. $\endgroup$
    – Wojowu
    Commented May 9, 2021 at 11:55
  • $\begingroup$ My apologies for not defining "generic." Now added. $\endgroup$
    – Joseph O'Rourke
    Commented May 9, 2021 at 12:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .