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 34 (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 35 (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 36 (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 37 (Realization Space)

Let \(G=(V,E)\) be a \(d\)-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 38 (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. For \(2\)-rigid graphs that are not minimally \(2\)-rigid the algorithm from [DGS+25] is used to compute \(c_2(G)\), (see also Theorem 36 and Theorem 37).

Complex Sphere

Definition 39 (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 40 (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 41 (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 42 (Spherical Realization Space)

Let \(G=(V,E)\) be a \(d\)-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 43 (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. For \(2\)-rigid graphs that are not minimally \(2\)-rigid the algorithm from [DGS+25] is used to compute \(c_2^{\circ}(G)\), (see also Theorem 36 and Theorem 37).

Theorems

Theorem 35

In any positive dimension we have \(c_d(G)\leq c_d^{\circ}(G)\).

References: [DG24, Thm 1.1]

Lemma 5

Let \(G\) be a \(d\)-rigid graph and let \(G'\) be obtained from \(G\) by a \(0\)-extension. Then \(c_d(G')=2c_d(G)\) and \(c_d^{\circ}(G')=2c_d^{\circ}(G)\).

References: [DG24, Lem 7.1]

Theorem 36

Let \(G=(V,E)\) be a 2-rigid graph that is not 3-connected with vertices \(u,v\) separating \(G\) into \(G_1,G_2\). Then \(G_1+uv\) and \(G_2+uv\) are 2-rigid and \(G_1\) or \(G_2\) is 2-rigid and

\[\begin{equation*} c_2(G):= \begin{cases} 2 c_2(G_1)c_2(G_2+uv), & \text{if $uv\not\in E$ and $G_1$ is 2-rigid, $G_2$ is not 2-rigid,}\\ 2 c_2(G_1+uv)c_2(G_2+uv), & \text{if $uv\in E$ or both $G_1$ and $G_2$ are 2-rigid.} \end{cases} \end{equation*}\]

This also holds for \(c_2^{\circ}\).

References: [JO19, Thm 6.6]

Theorem 37

Let \(G=(V,E)\) be a 2-rigid graph that is 3-connected but not redundantly 2-rigid. Let \(e\in E\) such that \(G-e\) is not 2-rigid and let \(G_1,\ldots,G_m\) be the maximal 2-rigid subgraphs of \(G-e\). Let further be \(H_i\) be a minimally 2-rigid subgraph of \(G_i\) for each \(i\in\{1,\ldots,m\}\) and let \(H=H_1\cup\cdots\cup H_m\cup\{e\}\). Then

\[\begin{equation*} c_2(G)= c_2(H) \prod_{i=1}^m \frac{c_2(G_i)}{c_2(H_i)}. \end{equation*}\]

This also holds for \(c_2^{\circ}\).

References: [DGS+25, Thm 1]