A Proof of the Molecular Conjecture

Abstract

A d-dimensional body-and-hinge framework is, roughly speaking, a structure consisting of rigid bodies connected by hinges in d-dimensional space. The generic infinitesimal rigidity of a body-and-hinge framework has been characterized in terms of the underlying multigraph independently by Tay and Whiteley as follows: A multigraph G can be realized as an infinitesimally rigid body-and-hinge framework by mapping each vertex to a body and each edge to a hinge if and only if ((d+1 2)-1) G contains (d+2 1) edge-disjoint spanning trees, where ((d+1 2)-1) G is the graph obtained from G by replacing each edge by ((d+1 2)-1) parallel edges. In 1984 they jointly posed a question about whether their combinatorial characterization can be further applied to a nongeneric case. Specifically, they conjectured that G can be realized as an infinitesimally rigid body-and-hinge framework if and only if G can be realized as that with the additional "hinge-coplanar" property, i.e., all the hinges incident to each body are contained in a common hyperplane. This conjecture is called the Molecular Conjecture due to the equivalence between the infinitesimal rigidity of "hinge-coplanar" body-and-hinge frameworks and that of bar-and-joint frameworks derived from molecules in 3-dimension. In 2-dimensional case this conjecture has been proved by Jackson and Jordan in 2006. In this paper we prove this long standing conjecture affirmatively for general dimension. Also, as a corollary, we obtain a combinatorial characterization of the 3-dimensional bar-and-joint rigidity matroid of the square of a graph.

d次元空間上の剛体ヒンジ構造とはd次元の部分空間(剛体)が(d-2)次元アフィン空間(ヒンジ)によって接続された構造物であり, 各剛体は接続されたヒンジ周りを回転し動く事が出来る.特に各剛体が(d-1)次元アフィン空間(剛板)として実現される際, 構造物は剛板ヒンジ構造と呼ばれる.剛体ヒンジ構造物の1次剛性は, その接続関係の組合せ構造によって特徴付けされる事が知られており, 1984年にTay and Whiteleyはその組合せ的特徴付けが剛板ヒンジ構造物に対しても適用可能であると予想した.より正確には「グラフGに対して, 各頂点を剛板, 各辺をヒンジに対応させ実現される剛板ヒンジ構造が全体として剛となる必要十分条件は((d+1 2)-1)Gが(d+1 2)個の辺素な全域木を含む事である」という予想を彼らは行った.ここで((d+1 2)-1)GはGの各辺を((d+1 2)-1)個の多重辺で置き換えたグラフである.3次元空間において分子構造の1次剛性は剛板ヒンジ構造物を用いて表現できる事が知られており, そのためこの予想は"the Molecular Conjecture"と呼ばれている.本稿では, 長年未解決であったこの予想に対する証明を与える.またこの結果から, G^2の辺集合を台集合とする3次元剛性マトロイドの組合せ的特徴付けが得られる.