🔢 mathematics

The $d$ -dimensional realisation number of a rigid graph

This paper introduces two new tools for determining the realisation numbers of rigid graphs in arbitrary dimensions—subgraph inclusion divisibility and lower bounds under specific operations—which are used to prove that triangulated spheres have at least $2^{n-4}$ realisations in 3D and to resolve a family of conjectures regarding the effects of 1-extensions, X-replacements, and V-replacements.

Original authors: Sean Dewar, Anthony Nixon, Ben Smith

Published 2026-02-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sean Dewar, Anthony Nixon, Ben Smith

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a structure made of sticks and joints, like a child's construction set or a geodesic dome. In math, we call this a framework. The sticks are the edges, and the joints are the vertices.

The big question this paper asks is: "If I give you the exact lengths of every stick, how many different shapes can this structure take?"

Sometimes, the answer is just one. If you build a triangle with three specific stick lengths, there's only one way to put it together (ignoring flipping it over or moving it around the room). This is called being "globally rigid."

But often, the answer is more than one. A square made of four sticks is floppy; you can squish it into a diamond shape. But if you add a diagonal stick to make it rigid, you might find that it can still be assembled in two different ways (like a mirror image).

The authors of this paper are mathematicians who study these structures in 3D space (and higher dimensions). They want to know: How many different "versions" of a rigid shape exist?

Here is a breakdown of their discoveries using simple analogies:

1. The "Divisibility" Rule (The Lego Block Analogy)

Imagine you have a giant, complex Lego castle (Graph $G$ ). Inside that castle, there is a smaller, self-contained tower (Subgraph $H$ ).

The authors discovered a surprising rule: The number of ways to build the whole castle is always a multiple of the number of ways to build the inner tower.

The Metaphor: If the inner tower can be built in 4 different ways, the whole castle must be buildable in 4, 8, 12, 16... ways. It can never be 5 or 7.
Why it matters: This is a powerful shortcut. Instead of trying to count the billions of ways to build a massive, complex structure, you can look at a smaller piece inside it. If you know the smaller piece has a specific number of variations, you instantly know that the big structure's number of variations must be divisible by that number.

2. The "Magic Operations" (The Shape-Shifting Analogy)

The paper looks at specific ways to modify these structures, like adding a new stick or splitting a joint. They found that certain moves act like a "volume knob" for the number of possible shapes.

The 0-Extension (Adding a new joint): Imagine you take a rigid structure and add a new joint connected to $d$ $d$ existing joints.
- The Result: This operation doubles the number of possible shapes. If you had 1 shape, now you have 2. If you had 100, now you have 200. It's like flipping a switch that creates a perfect mirror image of every existing solution.
Vertex Splitting (Splitting a joint): Imagine taking one joint and splitting it into two separate joints that are glued together at the same spot.
- The Result: This usually at least doubles the number of shapes. It's like taking a single door and splitting it into a double door; you now have more ways to open it.

3. The Triangulated Sphere (The Soccer Ball)

One of the most famous shapes in geometry is a triangulated sphere—think of a soccer ball made entirely of triangles.

The Discovery: The authors proved that for a soccer ball with $n$ vertices (dots), there are at least $2^{n-4}$ different ways to assemble it with the same stick lengths.
The Analogy: If you have a soccer ball with 20 dots, there are at least $2^{16}$ (65,536) different ways to build it! As the ball gets bigger, the number of possible "versions" explodes exponentially. This extends a known rule for 2D flat shapes to 3D balls.

4. Solving the "Grasegger Conjectures"

There was a list of guesses (conjectures) made by a researcher named Grasegger about what happens when you perform specific, tricky operations on these graphs (like swapping edges or replacing a vertex).

The Result: The authors used their "Divisibility Rule" and "Magic Operations" to prove these guesses were correct. They showed that under very specific conditions, these complex swaps exactly double the number of possible shapes.

Why Should You Care?

You might think, "Who cares how many ways a math graph can be built?"

Actually, this is crucial for:

Robotics: When a robot arm moves, it needs to know if it can reach a spot in only one way or if it has multiple "elbow" configurations.
Chemistry: Molecules are like these frameworks. Knowing how many ways a molecule can fold helps chemists understand how drugs interact with the body.
Computer Vision: When a computer tries to reconstruct a 3D object from a 2D photo, it needs to know if the solution is unique or if there are multiple possibilities.

Summary

This paper is like a new rulebook for a game of 3D construction. The authors found that:

Small parts dictate the whole: The number of shapes a small piece can take divides the number of shapes the whole thing can take.
Specific moves double the fun: Adding a joint or splitting one in a specific way reliably doubles the number of possible shapes.
Bigger balls = exponentially more shapes: The more vertices a 3D sphere has, the more wildly the number of possible shapes grows.

They didn't just find the answers; they built the tools to solve these puzzles for any size or dimension, turning a chaotic guessing game into a predictable mathematical system.

1. Problem Statement

The paper addresses a fundamental problem in discrete geometry and rigidity theory: determining the number of distinct realizations of a rigid graph given a specific set of edge lengths.

Context: A framework $(G, p)$ in $\mathbb{R}^d$ consists of a graph $G$ and a mapping $p$ of vertices to points in space. The framework is rigid if it cannot be continuously deformed without changing edge lengths, except via isometries (rigid motions).
The Challenge: While rigidity is a generic property (holding for almost all edge lengths), the number of realizations (up to isometry) is not. It varies depending on the specific edge lengths chosen.
Definitions:
- $r(G, p)$ : The number of real realizations for a specific framework.
- $c(G, p)$ : The number of complex realizations.
- Real $d$ -realisation number ( $r_d(G)$ ): The maximum value of $r(G, p)$ over all generic realizations.
- Complex $d$ -realisation number ( $c_d(G)$ ): The value of $c(G, p)$ for any generic realization (a generic property).
Goal: To develop combinatorial tools to compute or bound $c_d(G)$ and $r_d(G)$ for $d \geq 2$ , as algebraic methods (like Gröbner bases) become computationally intractable for higher dimensions.

2. Methodology

The authors employ a blend of rigidity theory, algebraic geometry, and combinatorial graph operations.

Algebraic Geometry Framework:
- They utilize the rigidity map $f_{G,d}$ , which maps vertex coordinates to squared edge lengths.
- The realisation number corresponds to the degree of this map (specifically, the size of the fiber over a generic point).
- They use dominant maps and Zariski topology to establish relationships between the degrees of maps associated with subgraphs and supergraphs.
- Pinned Frameworks: To handle the quotient by isometries, they restrict the domain to "pinned" frameworks (fixing $d$ vertices to remove translational and rotational degrees of freedom), allowing them to work directly with algebraic varieties.
Graph Operations:
- The paper analyzes how specific graph operations affect the realisation number. Key operations include:
  - 0-extension: Adding a vertex connected to $d$ existing vertices.
  - Vertex-splitting: Splitting a vertex into two, distributing its neighbors.
  - Spider-splitting: A variation of vertex-splitting where the new vertices are connected to all neighbors of the original vertex.
  - Subgraph Substitution: Replacing a rigid subgraph with another rigid subgraph.

3. Key Contributions and Results

A. Divisibility of Realisation Numbers

The authors prove that the realisation number of a rigid graph is divisible by the realisation number of its rigid subgraphs under specific conditions.

Theorem 1.1 (Spanning Subgraphs): If $H$ $H$ is a spanning $d$ $d$ -rigid subgraph of a $d$ $d$ -rigid graph $G$ $G$ , then $c_d(G)$ $c_{d} (G)$ divides $c_d(H)$ $c_{d} (H)$ .
- Significance: This allows the computation of $c_d(G)$ by analyzing its subgraphs. If $c_d(H) = 1$ , then $c_d(G) = 1$ (global rigidity).
Theorem 1.2 (Non-spanning Subgraphs): Under specific conditions involving minimally rigid subgraphs, $c_d(H)$ $c_{d} (H)$ divides $c_d(G)$ $c_{d} (G)$ even if $H$ $H$ is not spanning.
- Application: This generalizes a lemma by Grasegger and provides a tool to analyze graph modifications.

B. Behavior Under Graph Operations

The paper establishes lower bounds for realisation numbers when applying graph operations in arbitrary dimensions $d$ .

0-extensions: Proves that a $d$ -dimensional 0-extension exactly doubles the realisation number ( $c_d(G') = 2c_d(G)$ and $r_d(G') = 2r_d(G)$ ).
Vertex-splitting: Proves that vertex-splitting at least doubles the complex realisation number ( $c_d(G') \geq 2c_d(G)$ ) and the real realisation number ( $r_d(G') \geq 2r_d(G)$ ).
Spider-splitting: Proves that spider-splitting preserves or increases the realisation number ( $c_d(G') \geq c_d(G)$ and $r_d(G') \geq r_d(G)$ ).

C. Lower Bounds for Triangulated Spheres

Combining the divisibility results with the behavior of vertex-splitting, the authors derive a significant lower bound for triangulated spheres in 3D.

Theorem 1.3: For any triangulated sphere $G$ $G$ with $n$ $n$ vertices:
$c_3(G) \geq r_3(G) \geq 2^{n-4}$
- Derivation: Steinitz's theorem states that any triangulated sphere can be constructed from $K_4$ (which has $c_3=1$ ) via $n-4$ vertex splits. Since each split at least doubles the count, the result follows.
- Extension: This result is extended to minimally 3-rigid projective planar graphs (Theorem 5.1).

D. Resolution of Conjectures

The tools developed are used to resolve a family of conjectures by Grasegger regarding specific graph operations:

1-extensions: Proven to double the realisation number when applied to a clique of size $d+1$ .
X-replacements and V-replacements: Proven to double the realisation number in 3D when the induced subgraph on the involved vertices is minimally 3-rigid.

4. Significance

Theoretical Advancement: The paper moves beyond the 2-dimensional case (where combinatorial algorithms exist) to arbitrary dimensions $d \geq 3$ , where such algorithms were previously unknown.
Computational Efficiency: By establishing divisibility rules and lower bounds, the authors provide a way to estimate or bound realisation numbers without solving complex polynomial systems.
Global Rigidity: The divisibility theorems offer a new method for proving global rigidity (where $c_d(G)=1$ ). If a graph contains a subgraph with a known realisation number, the divisibility constraint can force the supergraph to be globally rigid.
Geometric Insight: The results deepen the understanding of how local graph modifications (like splitting vertices) propagate to global geometric properties (the number of distinct shapes a structure can take).

In summary, this work provides a robust algebraic-combinatorial framework for analyzing the complexity of rigid structures in higher dimensions, solving open conjectures, and establishing tight lower bounds for important geometric classes like triangulated spheres.