Search

Here we propose a class of frameworks in the plane, braced polygons, that may be globally rigid and are analogous to convex polyopes in 3 space that are rigid by Cauchy's rigidity Theorem in 1813., Comment: 35 pages, 25 figures

We show that a generic tensor $T\in \mathbb{F}^{n\times n\times \dots\times n}$ of order $k$ and CP rank $d$ can be uniquely recovered from $n\log n+dn\log \log n +o(n\log \log n) $ uniformly random entries with high probability if $d$ and $k$ are constant and $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$. The bound is tight up to the coefficient of the second leading term and improves on the existing $O(n^{\frac{k}{2}}{\rm polylog}(n))$ upper bound for order $k$ tensors. The bound is obtained by showing that the projection of the Segre variety to a random axis-parallel linear subspace preserves $d$-identifiability with high probability if the dimension of the subspace is $n\log n+dn\log \log n +o(n\log \log n) $ and $n$ is sufficiently large.

This work considers the distance constrained formation control problem with an additional constraint requiring that the formation exhibits a specified spatial symmetry. We employ recent results from the theory of symmetry-forced rigidity to construct an appropriate potential function that leads to a gradient dynamical system driving the agents to the desired formation. We show that only $(1+1/|\Gamma|)n$ edges are sufficient to implement the control strategy when there are $n$ agents and the underlying symmetry group is $\Gamma$. This number is considerably smaller than what is typically required from classic rigidity-theory based strategies ($2n-3$ edges). We also provide an augmented control strategy that ensures the agents can converge to a formation with respect to an arbitrary centroid. Numerous numerical examples are provided to illustrate the main results., Comment: Submitted to the IEEE Transactions on Control of Network Systems

The celebrated result of Gortler-Healy-Thurston (independently, Jackson-Jord\'an for $d=2$) shows that the global rigidity of graphs realised in the $d$-dimensional Euclidean space is a generic property. Extending this result to the global rigidity problem in $\ell_p$-spaces remains an open problem. In this paper we affirmatively solve this problem when $d=2$ and $p$ is an even positive integer. A key tool in our proof is a sufficient condition for the $d$-tangentially weakly non-defectiveness of projective varieties due to Bocci, Chiantini, Ottaviani, and Vannieuwenhoven. By specialising the condition to the $p$-Cayley-Menger variety, which is the $\ell_p$-analogue of the Cayley-Menger variety for Euclidean distance, we provide an $\ell_p$-extension of the generic global rigidity theory of Connelly. As a by-product of our proof, we also offer a purely graph-theoretical characterisation of the $2$-identifiability of an orthogonal projection of the $p$-Cayley-Menger variety along a coordinate axis of the ambient affine space.

Belk and Connelly introduced the realizable dimension $\textrm{rd}(G)$ of a finite graph $G$, which is the minimum nonnegative integer $d$ such that every framework $(G,p)$ in any dimension admits a framework in $\mathbb{R}^d$ with the same edge lengths. They characterized finite graphs with realizable dimension at most $1$, $2$, or $3$ in terms of forbidden minors. In this paper, we consider periodic frameworks and extend the notion to $\mathbb{Z}$-symmetric graphs. We give a forbidden minor characterization of $\mathbb{Z}$-symmetric graphs with realizable dimension at most $1$ or $2$, and show that the characterization can be checked in polynomial time for given quotient $\mathbb{Z}$-labelled graphs., Comment: 18 pages, 3 figures

The identifiability problem arises naturally in a number of contexts in mathematics and computer science. Specific instances include local or global rigidity of graphs and unique completability of partially-filled tensors subject to rank conditions. The identifiability of points on secant varieties has also been a topic of much research in algebraic geometry. It is often formulated as the problem of identifying a set of points satisfying a given set of algebraic relations. A key question then is to prove sufficient conditions for relations to guarantee the identifiability of the points. This paper proposes a new general framework for capturing the identifiability problem when a set of algebraic relations has a combinatorial structure and develops tools to analyse the impact of the underlying combinatorics on the local or global identifiability of points. Our framework is built on the language of graph rigidity, where the measurements are Euclidean distances between two points, but applicable in the generality of hypergraphs with arbitrary algebraic measurements. We establish necessary and sufficient (hyper)graph theoretical conditions for identifiability by exploiting techniques from graph rigidity theory and algebraic geometry of secant varieties. In particular our work analyses combinatorially the effect of non-generic projections of secant varieties.

A super stable tensegrity introduced by Connelly in 1982 is a globally rigid discrete structure made from stiff bars or struts connected by cables with tension. In this paper we show an exact relation between the maximum dimension that a multigraph can be realized as a super stable tensegrity and Colin de Verdi\`{e}re number~$\nu$ from spectral graph theory. As a corollary we obtain a combinatorial characterization of multigraphs that can be realized as 3-dimensional super stable tensegrities.

We consider the global rigidity problem for bar-joint frameworks where each vertex is constrained to lie on a particular line in $\mathbb R^d$. In our setting we allow multiple vertices to be constrained to the same line. Under a mild assumption on the given set of lines we give a complete combinatorial characterisation of graphs that are generically globally rigid in this setting. This gives a $d$-dimensional extension of the well-known combinatorial characterisation of 1-dimensional global rigidity., Comment: 24 pages, 5 figures

Spectral hypergraph sparsification, an attempt to extend well-known spectral graph sparsification to hypergraphs, has been extensively studied over the past few years. For undirected hypergraphs, Kapralov, Krauthgamer, Tardos, and Yoshida~(2022) have proved an $\varepsilon$-spectral sparsifier of the optimal $O^*(n)$ size, where $n$ is the number of vertices and $O^*$ suppresses the $\varepsilon^{-1}$ and $\log n$ factors. For directed hypergraphs, however, the optimal sparsifier size has not been known. Our main contribution is the first algorithm that constructs an $O^*(n^2)$-size $\varepsilon$-spectral sparsifier for a weighted directed hypergraph. Our result is optimal up to the $\varepsilon^{-1}$ and $\log n$ factors since there is a lower bound of $\Omega(n^2)$ even for directed graphs. We also show the first non-trivial lower bound of $\Omega(n^2/\varepsilon)$ for general directed hypergraphs. The basic idea of our algorithm is borrowed from the spanner-based sparsification for ordinary graphs by Koutis and Xu~(2016). Their iterative sampling approach is indeed useful for designing sparsification algorithms in various circumstances. To demonstrate this, we also present a similar iterative sampling algorithm for undirected hypergraphs that attains one of the best size bounds, enjoys parallel implementation, and can be transformed to be fault-tolerant.

Let $\cX$ be a family of subsets of a finite set $E$. A matroid on $E$ is called an $\cX$-matroid if each set in $\cX$ is a circuit. We consider the problem of determining when there exists a unique maximal $\cX$-matroid in the weak order poset of all $\cX$-matroids on $E$, and characterizing its rank function when it exists., Comment: typographical corrections, exposition improvements

We consider the problem of characterising the generic rigidity of bar-joint frameworks in $\mathbb{R}^d$ in which each vertex is constrained to lie in a given affine subspace. The special case when $d=2$ was previously solved by I. Streinu and L. Theran in 2010 and the case when each vertex is constrained to lie in an affine subspace of dimension $t$, and $d\geq t(t-1)$ was solved by Cruickshank, Guler and the first two authors in 2019. We extend the latter result by showing that the given characterisation holds whenever $d\geq 2t$., Comment: 6 pages. This version corrects an error in the proof of Theorem 3.2

A tensegrity is a structure made from cables, struts and stiff bars. A $d$-dimensional tensegirty is universally rigid if it is rigid in any dimension $d'$ with $d'\geq d$. The celebrated super stability condition due to Connelly gives a sufficient condition for a tensegrity to be universally rigid. Gortler and Thurston showed that super stability characterizes universal rigidity when the point configuration is generic and every member is a stiff bar. We extend this result in two directions. We first show that a generic universally rigid tensegrity is super stable. We then extend it to tensegrities with point group symmetry, and show that this characterization still holds as long as a tensegrity is generic modulo symmetry. Our strategy is based on the block-diagonalization technique for symmetric semidefinite programming problems, and our proof relies on the theory of real irreducible representation of finite groups.

We give a short proof of a result of Jordan and Tanigawa that a 4-connected graph which has a spanning planar triangulation as a proper subgraph is generically globally rigid in R^3. Our proof is based on a new sufficient condition for the so called vertex splitting operation to preserve generic global rigidity in R^d., Comment: Revision to v2: new results added in collaboration with Shin-ichi Tanigawa

A conjecture of Graver from 1991 states that the generic $3$-dimensional rigidity matroid is the unique maximal abstract $3$-rigidity matroid with respect to the weak order on matroids. Based on a close similarity between the generic $d$-dimensional rigidity matroid and the generic $C_{d-2}^{d-1}$-cofactor matroid from approximation theory, Whiteley made an analogous conjecture in 1996 that the generic $C_{d-2}^{d-1}$-cofactor matroid is the unique maximal abstract $d$-rigidity matroid for all $d\geq 2$. We verify the case $d=3$ of Whiteley's conjecture in this paper. A key step in our proof is to verify a second conjecture of Whiteley that the `double V-replacement operation' preserves independence in the generic $C_2^1$-cofactor matroid.

We showed in the first paper of this series that the generic $C_2^1$-cofactor matroid is the unique maximal abstract $3$-rigidity matroid. In this paper we obtain a combinatorial characterization of independence in this matroid. This solves the cofactor counterpart of the combinatorial characterization problem for the rigidity of generic 3-dimensional bar-joint frameworks. We use our characterization to verify that the counterparts of conjectures of Dress (on the rank function) and Lov\'{a}sz and Yemini (which suggested a sufficient connectivity condition for rigidity) hold for this matroid.

As a generalization of the Edmonds arborescence packing theorem, Kamiyama--Katoh--Takizawa (2009) gave a good characterization of directed graphs that contain arc-disjoint arborescences spanning the set of vertices reachable from each root. Fortier--Kir\'aly--L\'eonard--Szigeti--Talon (2018) asked whether the result can be extended to mixed graphs by allowing both directed arcs and undirected edges. In this paper, we solve this question by developing a polynomial-time algorithm for finding a collection of edge and arc-disjoint arborescences spanning the set of vertices reachable from each root in a given mixed graph., Comment: 10 pages

We introduce a new class of structured symmetric matrices by extending the notion of perfect elimination ordering from graphs to weighted graphs or matrices. This offers a common framework capturing common vertex elimination orderings of monotone families of chordal graphs, Robinsonian matrices and ultrametrics. We give a structural characterization for matrices that admit perfect elimination orderings in terms of forbidden substructures generalizing chordless cycles in graphs., Comment: 16 pages, 3 figures

A one-to-one correspondence between the infinitesimal motions of bar-joint frameworks in $\mathbb{R}^d$ and those in $\mathbb{S}^d$ is a classical observation by Pogorelov, and further connections among different rigidity models in various different spaces have been extensively studied. In this paper, we shall extend this line of research to include the infinitesimal rigidity of frameworks consisting of points and hyperplanes. This enables us to understand correspondences between point-hyperplane rigidity, classical bar-joint rigidity, and scene analysis. Among other results, we derive a combinatorial characterization of graphs that can be realized as infinitesimally rigid frameworks in the plane with a given set of points collinear. This extends a result by Jackson and Jord\'{a}n, which deals with the case when three points are collinear., Comment: 33 pages, 9 figures

A symmetric matrix is Robinsonian if its rows and columns can be simultaneously reordered in such a way that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. The adjacency matrix of a graph is Robinsonian precisely when the graph is a unit interval graph, so that Robinsonian matrices form a matrix analogue of the class of unit interval graphs. Here we provide a structural characterization for Robinsonian matrices in terms of forbidden substructures, extending the notion of asteroidal triples to weighted graphs. This implies the known characterization of unit interval graphs and leads to an efficient algorithm for certifying that a matrix is not Robinsonian., Comment: 21 pages, 1 figure

In 1992, Hendrickson proved that (d+1)-connectivity and redundant rigidity are necessary conditions for a generic (non-complete) bar-joint framework to be globally rigid in $\mathbb{R}^d$. Jackson and Jordan confirmed in 2005 that these conditions are also sufficient in $\mathbb{R}^2$, giving a combinatorial characterization of graphs whose generic realizations in $\mathbb{R}^2$ are globally rigid. In this paper, we establish analogues of these results for infinite periodic frameworks under fixed lattice representations. Our combinatorial characterization of globally rigid generic periodic frameworks in $\mathbb{R}^2$ in particular implies toroidal and cylindrical counterparts of the theorem by Jackson and Jordan., Comment: 38 pages, 2 figures

The singularity degree of a semidefinite programming problem is the smallest number of facial reduction steps to make the problem strictly feasible. We introduce two new graph parameters, called the singularity degree and the nondegenerate singularity degree, based on the singularity degree of the positive semidefinite matrix completion problem. We give a characterization of the class of graphs whose parameter value is equal to one for each parameter. Specifically, we show that the singularity degree of a graph is equal to one if and only if the graph is chordal, and the nondegenerate singularity degree of a graph is equal to one if and only if the graph is the clique sum of chordal graphs and $K_4$-minor free graphs. We also show that the singularity degree is bounded by two if the treewidth is bounded by two, and exhibit a family of graphs with treewidth three, whose singularity degree grows linearly in the number of vertices.

We give a signed generalization of Laurent's theorem that characterizes feasible positive semidefinite matrix completion problems in terms of metric polytopes. Based on this result, we give a characterization of the maximum rank completions of the signed positive semidefinite matrix completion problem for odd-$K_4$ minor free signed graphs. The analysis can also be used to bound the minimum rank over the completions and to characterize uniquely solvable completion problems for odd-$K_4$ minor free signed graphs. As a corollary we derive a characterization of the universal rigidity of odd-$K_4$ minor free spherical tensegrities, and also a characterization of signed graphs whose signed Colin de Verdi\`ere parameter $\nu$ is bounded by two, recently shown by Arav et al.

A graph $G=(V,E)$ is called $(k,\ell)$-sparse if $|F|\leq k|V(F)|-\ell$ for any nonempty $F\subseteq E$, where $V(F)$ denotes the set of vertices incident to $F$. It is known that the family of the edge sets of $(k,\ell)$-sparse subgraphs forms the family of independent sets of a matroid, called the $(k,\ell)$-count matroid of $G$. In this paper we shall investigate lifts of the $(k,\ell)$-count matroid by using group labelings on the edge set. By introducing a new notion called near-balancedness, we shall identify a new class of matroids, where the independence condition is described as a count condition of the form $|F|\leq k|V(F)|-\ell +\alpha_{\psi}(F)$ for some function $\alpha_{\psi}$ determined by a given group labeling $\psi$ on $E$.

This paper presents a polynomial-time $1/2$-approximation algorithm for maximizing nonnegative $k$-submodular functions. This improves upon the previous $\max\{1/3, 1/(1+a)\}$-approximation by Ward and \v{Z}ivn\'y~(SODA'14), where $a=\max\{1, \sqrt{(k-1)/4}\}$. We also show that for monotone $k$-submodular functions there is a polynomial-time $k/(2k-1)$-approximation algorithm while for any $\varepsilon>0$ a $((k+1)/2k+\varepsilon)$-approximation algorithm for maximizing monotone $k$-submodular functions would require exponentially many queries. In particular, our hardness result implies that our algorithms are asymptotically tight. We also extend the approach to provide constant factor approximation algorithms for maximizing skew-bisubmodular functions, which were recently introduced as generalizations of bisubmodular functions.

A rigidity theory is developed for bar-joint frameworks in $\mathbb{R}^{d+1}$ whose vertices are constrained to lie on concentric $d$-spheres with independently variable radii. In particular, combinatorial characterisations are established for the rigidity of generic frameworks for $d=1$ with an arbitrary number of independently variable radii, and for $d=2$ with at most two variable radii. This includes a characterisation of the rigidity or flexibility of uniformly expanding spherical frameworks in $\mathbb{R}^{3}$. Due to the equivalence of the generic rigidity between Euclidean space and spherical space, these results interpolate between rigidity in 1D and 2D and to some extent between rigidity in 2D and 3D. Symmetry-adapted counts for the detection of symmetry-induced continuous flexibility in frameworks on spheres with variable radii are also provided., Comment: 22 pages, 2 figures, updated references

We investigate how to find generic and globally rigid realizations of graphs in $\mathbb{R}^d$ based on elementary geometric observations. Our arguments lead to new proofs of a combinatorial characterization of the global rigidity of graphs in $\mathbb{R}^2$ by Jackson and Jord\'an and that of body-bar graphs in $\mathbb{R}^d$ recently shown by Connelly, Jord\'an, and Whiteley. We also extend the 1-extension theorem and Connelly's composition theorem, which are main tools for generating globally rigid graphs in $\mathbb{R}^d$. In particular we show that any vertex-redundantly rigid graph in $\mathbb{R}^d$ is globally rigid in $\mathbb{R}^d$, where a graph $G=(V,E)$ is called vertex-redundantly rigid if $G-v$ is rigid for any $v\in V$.

The mathematical theory of rigidity of body-bar and body-hinge frameworks provides a useful tool for analyzing the rigidity and flexibility of many articulated structures appearing in engineering, robotics and biochemistry. In this paper we develop a symmetric extension of this theory which permits a rigidity analysis of body-bar and body-hinge structures with point group symmetries. The infinitesimal rigidity of body-bar frameworks can naturally be formulated in the language of the exterior (or Grassmann) algebra. Using this algebraic formulation, we derive symmetry-adapted rigidity matrices to analyze the infinitesimal rigidity of body-bar frameworks with Abelian point group symmetries in an arbitrary dimension. In particular, from the patterns of these new matrices, we derive combinatorial characterizations of infinitesimally rigid body-bar frameworks which are generic with respect to a point group of the form $\mathbb{Z}/2\mathbb{Z}\times \dots \times \mathbb{Z}/2\mathbb{Z}$. Our characterizations are given in terms of packings of bases of signed-graphic matroids on quotient graphs. Finally, we also extend our methods and results to body-hinge frameworks with Abelian point group symmetries in an arbitrary dimension. As special cases of these results, we obtain combinatorial characterizations of infinitesimally rigid body-hinge frameworks with $\mathcal{C}_2$ or $\mathcal{D}_2$ symmetry - the most common symmetry groups found in proteins., Comment: arXiv:1308.6380 version 1 was split into two papers. The version 2 of arXiv:1308.6380 consists of Sections 1 - 6 of the version 1. This paper is based on the second part of the version 1 (Sections 7 and 8)

We propose new symmetry-adapted rigidity matrices to analyze the infinitesimal rigidity of arbitrary-dimensional bar-joint frameworks with Abelian point group symmetries. These matrices define new symmetry-adapted rigidity matroids on group-labeled quotient graphs. Using these new tools, we establish combinatorial characterizations of infinitesimally rigid two-dimensional bar-joint frameworks whose joints are positioned as generic as possible subject to the symmetry constraints imposed by a reflection, a half-turn or a three-fold rotation in the plane. For bar-joint frameworks which are generic with respect to any other cyclic point group in the plane, we provide a number of necessary conditions for infinitesimal rigidity., Comment: The version 1 was split into two papers, and this version 2 consists of Sections 1 - 6 of the first version. The second part of the version 1 (Sections 7 and 8) is given in arXiv:1402.0039

A G-gain graph is a graph whose oriented edges are labeled invertibly from a group G. Zaslavsky proposed two matroids of G-gain graphs, called frame matroids and lift matroids, and investigated linear representations of them. Each matroid has a canonical representation over a field F if G is isomorphic to a subgroup of F^{\times} in the case of frame matroids or G is isomorphic to an additive subgroup of F in the case of lift matroids. The canonical representation of the frame matroid of a complete graph is also known as a Dowling geometry, as it was first introduced by Dowling for finite groups. In this paper, we extend these matroids in two ways. The first one is extending the rank function of each matroid, based on submodular functions over G. The resulting rank function generalizes that of the union of frame matroids or lift matroids. Another one is extending the canonical linear representation of the union of d copies of a frame matroid or a lift matroid, based on linear representations of G on a d-dimensional vector space. We show that linear matroids of the latter extension are indeed special cases of the first extensions, as in the relation between Dowling geometries and frame matroids. We also discuss an attempt to unify the extension of frame matroids and that of lift matroids. This work is motivated from recent research on the combinatorial rigidity of symmetric graphs. As special cases, we give several new results on this topic, including combinatorial characterizations of the symmetry-forced rigidity of generic body-bar frameworks with point group symmetries or crystallographic symmetries and the symmetric parallel redrawability of generic bar-joint frameworks with point group symmetries or crystallographic symmetries.

Abstractions of crystalline materials known as periodic body-and-bar frameworks are made of rigid bodies connected by fixed-length bars and subject to the action of a group of translations. In this paper, we give a Maxwell-Laman characterization for generic minimally rigid periodic body-and-bar frameworks. As a consequence we obtain efficient polynomial time algorithms for their recognition based on matroid partition and pebble games.

As an extension of a classical tree-partition problem, we consider decompositions of graphs into edge-disjoint (rooted-)trees with an additional matroid constraint. Specifically, suppose we are given a graph $G=(V,E)$, a multiset $R=\{r1,..., r_t\}$ of vertices in $V$, and a matroid ${\cal M}$ on $R$. We prove a necessary and sufficient condition for $G$ to be decomposed into $t$ edge-disjoint subgraphs $G_1=(V_1,T_1),..., G_t=(V_t,T_t)$ such that (i) for each $i$, $G_i$ is a tree with $r_i\in V_i$, and (ii) for each $v\in V$, the multiset $\{r_i\in R\mid v\in V_i\}$ is a base of ${\cal M}$. If ${\cal M}$ is a free matroid, this is a decomposition into $t$ edge-disjoint spanning trees; thus, our result is a proper extension of Nash-Williams' tree-partition theorem. Such a matroid constraint is motivated by combinatorial rigidity theory. As a direct application of our decomposition theorem, we present characterizations of the infinitesimal rigidity of frameworks with non-generic "boundary", which extend classical Laman's theorem for generic 2-rigidity of bar-joint frameworks and Tay's theorem for generic $d$-rigidity of body-bar frameworks.

A graph $G=(V,E)$ is called $(k,\ell)$-full if $G$ contains a subgraph $H=(V,F)$ of $k|V|-\ell$ edges such that, for any non-empty $F' \subseteq F$, $|F'| \leq k|V(F')| - \ell$ holds. Here, $V(F')$ denotes the set of vertices incident to $F'$. It is known that the family of edge sets of $(k,\ell)$-full graphs forms a family of matroid, known as the sparsity matroid of $G$. In this paper, we give a constant-time approximation algorithm for the rank of the sparsity matroid of a degree-bounded undirected graph. This leads to a constant-time tester for $(k,\ell)$-fullness in the bounded-degree model, (i.e., we can decide with high probability whether an input graph satisfies a property $P$ or far from $P$). Depending on the values of $k$ and $\ell$, it can test various properties of a graph such as connectivity, rigidity, and how many spanning trees can be packed. Based on this result, we also propose a constant-time tester for $(k,\ell)$-edge-connected-orientability in the bounded-degree model, where an undirected graph $G$ is called $(k,\ell)$-edge-connected-orientable if there exists an orientation $\vec{G}$ of $G$ with a vertex $r \in V$ such that $\vec{G}$ contains $k$ arc-disjoint dipaths from $r$ to each vertex $v \in V$ and $\ell$ arc-disjoint dipaths from each vertex $v \in V$ to $r$. A tester is called a one-sided error tester for $P$ if it always accepts a graph satisfying $P$. We show, for $k \geq 2$ and (proper) $\ell \geq 0$, any one-sided error tester for $(k,\ell)$-fullness and $(k,\ell)$-edge-connected-orientability requires $\Omega(n)$ queries.

We prove that the linear matroid that defines generic rigidity of $d$-dimensional body-rod-bar frameworks (i.e., structures consisting of disjoint bodies and rods mutually linked by bars) can be obtained from the union of ${d+1 \choose 2}$ graphic matroids by applying variants of Dilworth truncation $n_r$ times, where $n_r$ denotes the number of rods. This leads to an alternative proof of Tay's combinatorial characterizations of generic rigidity of rod-bar frameworks and that of identified body-hinge frameworks.

A $d$-dimensional body-and-hinge framework is 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 \choose 2}-1)G$ contains ${d+1\choose 2}$ edge-disjoint spanning trees, where $({d+1 \choose 2}-1)G$ is the graph obtained from $G$ by replacing each edge by $({d+1\choose 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 Jord{\'a}n in 2006. In this paper we prove this long standing conjecture affirmatively for general dimension.