A proof of the molecular conjecture

ABSTRACT

A 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 graph independently by Tay and Whiteley as follows: A graph 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+1/2} 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 Jordán 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.

REFERENCES

• 1: N. M. Amato, The Protein Folding Server, Parasol, http://parasol.tamu.edu/groups/amatogroup/.
• 2: M. Chubynsky, B. Hespenheide, D. J. Jacobs, L. A. Kuhn, M. Lei, S. Menor, A. J. Rader, M. F. Thorpe, W. Whiteley and M. I. Zavodszky, Constraint theory applied to proteins, Nanotechnology Research Journal, 2:61--72, 2008.
• 3: H. Crapo and W. Whiteley, Statics of frameworks and motions of panel structures; a projective geometric introduction, Structural Topology, 6:43--82, 1982.
• 4: William H. Cunningham, Optimal attack and reinforcement of a network, Journal of the ACM (JACM), v.32 n.3, p.549-561, July 1985 [doi>10.1145/3828.3829]
• 5: Flexweb Server, http://flexweb.asu.edu.
• 6: J. Graver, B. Servatius and H. Servatius. Combinatorial Rigidity, Graduate Studies in Mathematics vol. 2. American Mathematical Society, 1993.
• 7: D. Gusfield. Connectivity and edge-disjoint spanning trees, Inform Process. Lett. 16:87--89, 1983.
• 8: B. Jackson and T. Jordán, Rank and independence in the rigidity matroid of molecular graphs, Technical Report, Egerváry Research Group, Budapest, 2006, TR-2006-02.
• 9: Bill Jackson , Tibor Jordan, Rigid Components in Molecular Graphs, Algorithmica, v.48 n.4, p.399-412, August 2007 [doi>10.1007/s00453-007-0170-8]
• 10: B. Jackson and T. Jordán, Pin-collinear body-and-pin frameworks and the molecular conjecture, Technical Report, Egerváry Research Group, Budapest, 2006, TR-2006-06.
• 11: Bill Jackson , Tibor Jordán, Pin-Collinear Body-and-Pin Frameworks and the Molecular Conjecture, Discrete & Computational Geometry, v.40 n.2, p.258-278, September 2008 [doi>10.1007/s00454-008-9100-z]
• 12: B. Jackson and T. Jordán, Brick partitions of graphs, Technical Report, Egerváry Research Group, Budapest, 2007, TR-2007-05.
• 13: B. Jackson and T. Jordán, The generic rank of body-bar-and-hinge frameworks, Technical Report, Egerváry Research Group, Budapest, 2007, TR-2007-06.
• 14: D. J. Jacobs, Generic rigidity in three-dimensional bond--bending networks, J. Phys. Math. Gen. 31:6653--6668, 1998.
• 15: D. J. Jacobs, L. A. Kuhn and M. F. Thorpe, Flexible and rigid regions in proteins, In Rigidity Theory and Applications, Kluwer Academic/Plenum Press, pages 357--384, 1999.
• 16: N. Katoh and S. Tanigawa, A proof of the Molecular Conjecture, http://arxiv.org/abs/0902.0236.
• 17: A. Lee and I. Streinu, Pebble game algorithms and sparse graphs. Discrete Math., 308(8), 1425--1437 (2008).
• 18: M. Lei, M. I. Zavodszky, L. A. Kuhn, M. F. Thorpe, Sampling Protein Conformations and Pathways. J. Comp. Chem., 25:1133--1148, 2004.
• 19: L. Lovász, Combinatorial Problems and Exercises, North-Holland, 1979.
• 20: C. St. J. A. Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. London Mathematical Society, 36:445--450, 1961.
• 21: J. Oxley. Matroid Theory}, Oxford University Press, 1992.
• 22: T. S. Tay, Linking (n-2)-dimensional panels in n-space II: (n-2, 2)-frameworks and body and hinge structures, Graphs and Combinatorics}, 5:245--273, 1989.
• 23: T. S. Tay and W. Whiteley, Recent advances in the generic rigidity of structures, Structural Topology, 9:31--38, 1984.
• 24: M. F. Thorpe, M. Chubynsky, B. Hespenheide, S. Menor, D. J. Jacobs, L. A. Kuhn, M. I. Zavodszky, M. Lei, A. J. Rader and W. Whiteley, Flexibility in biomolecules, In Current topics in physics, Chapter 6, 97--112, Imperial College Press, London, 2005.
• 25: S. Wells, S. Menor, B. Hespenheide and M. F. Thorpe, Constrained geometric simulation of diffusive motion in proteins, Physical Biology, 2:S127--S136, 2005.
• 26: Neil White , Walter Whiteley, The algebraic geometry of motions of bar-and-body frameworks, SIAM Journal on Algebraic and Discrete Methods, v.8 n.1, p.1-32, January 2, 1987 [doi>10.1137/0608001]
• 27: Walter Whiteley, Rigidity and scene analysis, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 28: Walter Whiteley, The union of matroids and the rigidity of frameworks, SIAM Journal on Discrete Mathematics, v.1 n.2, p.237-255, May 1988 [doi>10.1137/0401025]
• 29: W. Whiteley, A matroid on hypergraphs with applications in scene analysis and geometry, Discrete Comput. Geom. 4:75--95, 1989.
• 30: W. Whiteley, Matroids from discrete geometry, In Matroid Theory, J. Bonin, J. Oxley and B. Servatius eds. AMS Contemporary Mathematics, 171--313, 1997
• 31: W. Whiteley, Counting out to the flexibility of molecules, Physical Biology, 2, S116--126, 2005.
• 32: W. T. Tutte. On the problem of decomposing a graph into n connected factors, J. London Mathematical Society, 36:221--230, 1961.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.m Miscellaneous

General Terms:
Theory

Keywords:
bar-and-joint frameworks, body-and-hinge frameworks, edge-disjoint spanning trees, rigidity, the molecular conjecture