Generic Rigidity

Definition 16 (Generic realization and framework)

Let \(G\) be a graph. A \(d\)-dimensional realization \(p\) of \(G\) whose coordinates are algebraically independent is called generic. A framework \((G, p)\), where \(p\) is generic, is called a generic framework.

Definition 17 (Generically rigid graph)

Let \(G\) be a graph and \(d \in \NN\). The graph \(G\) is called (generically) \(d\)-rigid if any generic d-dimensional framework \((G, p)\) is rigid; this is equivalent to \((G, p)\) being infinitesimally rigid.

PyRigi: is_rigid()

Definition 18 (Minimally generically rigid graphs)

Let \(G\) be a graph, let \(d, k \in \NN\). The graph \(G\) is called minimally (generically) \(d\)-rigid if a (equivalently, any) generic framework \((G, p)\) is minimally (infinitesimally) d-rigid.

PyRigi: is_min_rigid()

Theorem 1

A graph \(G = (V, E)\) with \(|V|\geq 2\) is minimally (generically) \(2\)-rigid if and only if \(G\) is (2,3)-tight.

References: [PollaczekGeiringer27] [Lam70]

Theorem 2

Let \(G = (V, E)\) be a minimally (generically) \(d\)-rigid graph with \(|V|\geq d+1\). Then \(G\) is \((d,\binom{d+1}{2})\)-tight.

References: compare [Whi96]

Theorem 3

Let \(G = (V, E)\) be a graph with \(|V|\leq d+1\). Then \(G\) is minimally (generically) \(d\)-rigid if and only if \(G\) is a complete graph.

References: compare [GSS93, Lem 2.6.1]

Theorem 4

Let \(G = (V, E)\) be a graph and let \(F=(G,p)\) be a framework with a random parametrization \(p\) with coordinates between 1 and some \(N\). If \(F\) is (minimally) infinitesimally \(d\)-rigid, then \(G\) is (minimally) \(d\)-rigid. If \(F\) is not (minimally) infinitesimally \(d\)-rigid, then \(G\) is not (minimally) \(d\)-rigid with probability \(1-(dn-\binom{d+1}{2})/N\). In other words the probability of a false negative is \((dn-\binom{d+1}{2})/N\). References: [GHT10]

Definition 19 (Rigid components in \(\RR^d\))

Let \(G\) be a graph, let \(d \in \NN\). The d-rigid components of \(G\) are the maximal vertex-induced subgraphs of \(G\) that are d-rigid.

PyRigi: rigid_components()