MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

A proof of the Molecular Conjecture

Naoki Katoh
Kyoto University
AG1 Mittagsseminar (own work)
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS  
AG Audience
English

Date, Time and Location

Tuesday, 1 September 2009
13:00
45 Minutes
E1 4
024
Saarbrücken

Abstract

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
$\left({d+1 \choose 2}-1\right)G$ contains ${d+1\choose 2}$
edge-disjoint spanning trees, where $\left({d+1 \choose 2}-1\right)G$
is the graph obtained from G
by replacing each edge by $\left({d+1\choose 2}-1\right)$ 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 bofy-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.
Recently we proved 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.
This is a joint work with Shin-ichi Tanigawa.

Contact

Michael Kerber
--email hidden
passcode not visible
logged in users only

Michael Kerber, 08/31/2009 13:37
Michael Kerber, 08/31/2009 13:36 -- Created document.