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.

$\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
    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$ 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$ 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$ 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$ May 10, 2021 at 1:56

2 Answers 2

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.

$\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$.

$\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
    May 9, 2021 at 11:55
  • $\begingroup$ My apologies for not defining "generic." Now added. $\endgroup$ May 9, 2021 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.