Redundant Rigidity

Definition 17 (Redundantly rigid frameworks)

Let \((G,p)\) be a \(d\)-dimensional framework and let \(k \in \NN\). The framework \((G, p)\) is called

• redundantly (infinitesimally) \(d\)-rigid if removing any edge from \(G\) yields an (infinitesimally) rigid framework;

• vertex redundantly (infinitesimally) \(d\)-rigid if removing any vertex from \(G\) yields an (infinitesimally) rigid framework;

• \(k\)-redundantly (infinitesimally) \(d\)-rigid if removing any set of \(k\) edges from \(G\) yields an (infinitesimally) rigid framework;

• \(k\)-vertex redundantly (infinitesimally) \(d\)-rigid if removing any set of \(k\) vertices from \(G\) yields an (infinitesimally) rigid framework.

PyRigi: is_redundantly_rigid()

Definition 18 (Redundantly generically rigid graphs)

Let \(G\) be a graph, let \(d, k \in \NN\). The graph \(G\) is called

• redundantly (generically) \(d\)-rigid if a (equivalently, any) generic framework \((G, p)\) is redundantly (infinitesimally) d-rigid;

• vertex redundantly (generically) \(d\)-rigid if a (equivalently, any) generic framework \((G, p)\) is vertex redundantly (infinitesimally) d-rigid;

• \(k\)-redundantly (generically) \(d\)-rigid if a (equivalently, any) generic framework \((G, p)\) is k-redundantly (infinitesimally) d-rigid;

• \(k\)-vertex redundantly (generically) \(d\)-rigid if a (equivalently, any) generic framework \((G, p)\) is k-vertex redundantly (infinitesimally) d-rigid.

Note, that the word generically is often omitted when talking about graphs.

PyRigi: is_redundantly_rigid() is_vertex_redundantly_rigid() is_k_redundantly_rigid() is_k_vertex_redundantly_rigid()

Definition 19 (Minimally redundantly generically rigid graphs)

Let \(G\) be a graph, let \(d, k \in \NN\). The graph \(G\) is called

• minimally_redundantly (generically) \(d\)-rigid if it is redundantly (generically) d-rigid and there is an edge such that the graph obtained by deleting this edge is not redundantly (generically) \(d\)-rigid any more.

• minimally_vertex_redundantly (generically) \(d\)-rigid if it is vertex_redundantly (generically) d-rigid and there is an edge such that the graph obtained by deleting this edge is not vertex_redundantly (generically) \(d\)-rigid any more.

• minimally_k_redundantly (generically) \(d\)-rigid if it is k_redundantly (generically) d-rigid and there is an edge such that the graph obtained by deleting this edge is not k_redundantly (generically) \(d\)-rigid any more.

• minimally_k_vertex_redundantly (generically) \(d\)-rigid if it is k_vertex_redundantly (generically) d-rigid and there is an edge such that the graph obtained by deleting this edge is not k_vertex_redundantly (generically) \(d\)-rigid any more.

Note, that the word generically is often omitted when talking about graphs.

PyRigi: is_min_redundantly_rigid() is_min_vertex_redundantly_rigid() is_min_k_redundantly_rigid() is_min_k_vertex_redundantly_rigid()

Theorem 4

Let \(G = (V, E)\) be a k-vertex-redundantly d-rigid graph with \(|V|\geq d^2+d+k+1\). Then

\[\begin{equation*} |E| \geq d |V| - \binom{d + 1}{2} + k d + max \left\{ 0, \left\lceil k - \frac{d + 1}{2} \right\rceil \right\} \,. \end{equation*}\]

References: [KK15, Thm 5]

Theorem 5

Let \(G = (V, E)\) be a k-vertex-redundantly d-rigid graph with \(|V|\geq d + k + 1\) and let \(k \geq d + 1\). Then

\[\begin{equation*} |E| \geq \left\lceil \frac{d + k}{2} |V| \right\rceil \,. \end{equation*}\]

References: [KK15, Thm 6]

Theorem 6

Let \(G = (V, E)\) be a 1-vertex-redundantly 2-rigid graph with \(|V|\geq 5\). Then

\[\begin{equation*} |E| \geq 2 |V| - 1 \,. \end{equation*}\]

References: [Ser89] [SYA08, Lem 1]

Theorem 7

Let \(G = (V, E)\) be a 2-vertex-redundantly 2-rigid graph with \(|V|\geq 6\). Then

\[\begin{equation*} |E| \geq 2 |V| + 2 \,. \end{equation*}\]

References: [AMYA14, Lem 4.9]

Theorem 8

Let \(G = (V, E)\) be a k-vertex-redundantly 2-rigid graph with \(|V|\geq 6 (k + 1) + 23\) and let \(k \geq 3\). Then

\[\begin{equation*} |E| \geq \left\lceil \frac{k + 2}{2} |V| \right\rceil \,. \end{equation*}\]

References: [Jor21, Thm 5]

Theorem 9

Let \(G = (V, E)\) be a 3-vertex-redundantly 3-rigid graph with \(|V|\geq 15\). Then

\[\begin{equation*} |E| \geq 3 |V| + 5 \,. \end{equation*}\]

References: [JPR22, Thm 2.12]

Theorem 10

Let \(G = (V, E)\) be a k-vertex-redundantly 3-rigid graph with \(|V|\geq 12 (k + 1) + 10\) where \(|V|\) is even and \(k \geq 4\). Then

\[\begin{equation*} |E| \geq \left\lceil \frac{k + 3}{2} |V| \right\rceil \,. \end{equation*}\]

References: [JPR22, Thm 3.3]

Theorem 11

Let \(G = (V, E)\) be a k-redundantly 2-rigid graph with \(|V|\geq 6 (k + 1) + 23\) and let \(k \geq 3\). Then

\[\begin{equation*} |E| \geq \left\lceil \frac{k + 2}{2} |V| \right\rceil \,. \end{equation*}\]

References: [Jor21, Thm 6]

Theorem 12

Let \(G = (V, E)\) be a 1-redundantly 2-rigid graph with \(|V|\geq 5\). Then

\[\begin{equation*} |E| \geq 2 |V| \,. \end{equation*}\]

References: [Jor21, Thm 7]

Theorem 13

Let \(G = (V, E)\) be a 2-redundantly 3-rigid graph with \(|V|\geq 14\). Then

\[\begin{equation*} |E| \geq 3 |V| - 4 \,. \end{equation*}\]

References: [JPR22, Thm 4.5]

Theorem 14

Let \(G = (V, E)\) be a k-redundantly 3-rigid graph with \(|V|\geq 12 (k + 1) + 10\) where \(|V|\) is even and \(k \geq 4\). Then

\[\begin{equation*} |E| \geq \left\lceil \frac{k + 3}{2} |V| \right\rceil \,. \end{equation*}\]

References: [JPR22, Thm 4.9]

Theorem 15

Let \(G = (V, E)\) be a minimally k-vertex-redundantly d-rigid graph. Then

\[\begin{equation*} |E| \leq (d + k) |V| - \binom{d + k + 1}{2} \,. \end{equation*}\]

References: [KK15, Thm 7]

Theorem 16

Let \(G = (V, E)\) be a minimally k-vertex-redundantly 1-rigid graph with \(|V| \geq 3 (k + 1) - 1\). Then

\[\begin{equation*} |E| \leq (k + 1) |V| - (k + 1)^2 \,. \end{equation*}\]

References: [KK15, Thm 8]

Theorem 17

Let \(G = (V, E)\) be a minimally 1-redundantly 2-rigid graph with \(|V| \geq 7\). Then

\[\begin{equation*} |E| \leq 3 |V| - 9 \,. \end{equation*}\]

References: [Jor16]