Realization Counting

Here by \(||x||^2\) we denote the extension of the squared Euclidean norm to \(\CC^d\) by defining \(||x||^2:= \sum_{i=1}^d x_i^2\), where \(x_i\) is the \(i\)-th coordinate of \(x\).

Complex Space

Definition 26 (Complex Realization)

Let \(G=(V,E)\) be a simple graph and \(d\in\NN\). A \(d\)-dimensional complex realization of \(G\) is a map \(p\colon V\rightarrow \CC^d\). We denote \(p(v)\) also by \(p_v\).

Definition 27 (Congruent Complex Realizations)

Two complex realizations \(p,q\in(\CC^d)^V\) are congruent if \(p_v = A q_v + b\) for all \(v\in V\), where \(A\) is a \(d\times d\) matrix over \(\CC\) with \(AA^T=A^TA=I\) and \(b\in\CC^d\).

Definition 28 (Complex Rigidity Map)

Let \(G=(V,E)\) be a rigid graph. We define \(f_{G,d}\colon (\CC^d)^V \rightarrow \CC^E\) by \(p\mapsto \left(\frac{1}{2}||p_v-p_w||^2\right)_{vw\in E}\) to be the complex rigidity map.

Definition 29 (Realization Space)

Let \(G=(V,E)\) be a rigid graph and \(p\) a complex realization, \(p\in(\CC^d)^V\). We define \(C_d(G,p):=f^{-1}_{G,d}(f_{G,d}(p))/_\sim\) to be the complex realization space, where \(\sim\) denotes the congruence of complex realizations.

Definition 30 (Number of Realizations)

Let \(G=(V,E)\) be a \(d\)-rigid graph. We define the number of complex realizations by \(c_d(G)\), where

\[\begin{equation*} c_d(G):= \begin{cases} |C_{G,d}(p)| \text{ for some generic } p\in(\CC^d)^V, & \text{if } |V|\geq d+1,\\ 1, & \text{otherwise, i.e. if $G$ is a complete graph with $|V|\leq d$.} \end{cases} \end{equation*}\]

PyRigi: number_of_realizations()

The implemented combinatorial algorithm for computing \(2\cdot c_2(G)\) for minimally \(2\)-rigid graphs can be found in [CGG+18]. Note that this algorithm does count reflections to be different realizations, while here we do not.

Complex Sphere

Definition 31 (Complex Spherical Realization)

Let \(G=(V,E)\) be a simple graph and \(d\in\NN\). A \(d\)-dimensional complex spherical realization of \(G\) is a map \(p\colon V\rightarrow \mathbb{S}_{\CC}^d := \{x\in\CC^{d+1}\colon ||x||^2 = 1\}\).

Definition 32 (Congruent Complex Spherical Realizations)

Two complex spherical realizations \(p,q\in(\mathbb{S}_{\CC}^d)^V\) are congruent if \(p_v = A q_v\) for all \(v\in V\), where \(A\) is a \(d\times d\) matrix over \(\CC\) with \(AA^T=A^TA=I\).

Definition 33 (Complex Spherical Rigidity Map)

Let \(G=(V,E)\) be a rigid graph. We define \(s_{G,d}\colon (\mathbb{S}_{\CC}^d)^V \rightarrow \CC^E\) by \(p\mapsto \left(\frac{1}{2}||p_v-p_w||^2\right)_{vw\in E}\) to be the complex spherical rigidity map.

Definition 34 (Spherical Realization Space)

Let \(G=(V,E)\) be a rigid graph and \(p\) a complex spherical realization, \(p\in(\mathbb{S}_{\CC}^d)^V\). We define \(C_d^{\circ}(G,p):=s^{-1}_{G,d}(s_{G,d}(p))/_\sim\) to be the complex spherical realization space, where \(\sim\) denotes the congruence of complex spherical realizations.

Definition 35 (Number of Spherical Realizations)

Let \(G=(V,E)\) be a \(d\)-rigid graph. We define the number of complex spherical realizations by \(c_d^{\circ}(G)\), where

\[\begin{equation*} c_d^{\circ}(G):= \begin{cases} |C^{\circ}_{G,d}(p)| \text{ for some generic } p\in(\mathbb{S}_{\CC}^d)^V, & \text{if } |V|\geq d+1,\\ 1, & \text{otherwise, i.e. if $G$ is a complete graph with $|V|\leq d$.} \end{cases} \end{equation*}\]

PyRigi: number_of_realizations()

The implemented combinatorial algorithm for computing \(2\cdot c_2^{\circ}(G)\) for minimally \(2\)-rigid graphs can be found in [GGS20]. Note that this algorithm does count reflections to be different realizations, while here we do not.