1
Introduction
▶
Organization of the blueprint
Reading this blueprint
2
Edges in a vertex set
▶
2.1
Definition and basic properties
2.2
Vertex deletion
2.3
Modularity: intersection, union, and supermodular counts
3
\((k,\ell )\)-sparsity and \((k,\ell )\)-tightness
▶
3.1
Definitions
3.2
Basic properties and the global edge bound
3.3
Low-degree vertex and non-adjacency consequences
3.4
Invariance under isomorphism
3.5
Unions and intersections of tight sets
3.6
Splittings and tight sets
3.7
Sparse-graph reverse decomposition
4
Laman graphs
▶
4.1
Definition and isomorphism invariance
4.2
The base case: \(K_2\)
4.3
Degree bounds
5
Henneberg moves
▶
5.1
Definitions
5.2
Edge sets and edge counts
5.3
Preservation of the Laman property
5.4
Reverse decomposition
5.5
An example: \(K_4\) minus an edge
6
Frameworks and infinitesimal rigidity
▶
6.1
Definitions
6.2
Rank and kernel bounds
6.3
Graph monotonicity
6.4
Transport along graph isomorphism
6.5
Openness of infinitesimal rigidity
6.6
The edge-count bound
6.7
Worked example: \(K_2\) is generically rigid in every dimension
7
Rigidity preservation under Henneberg moves (dimension 2)
▶
7.1
The Type I move
7.2
The Type II move
8
Trivial infinitesimal motions
▶
8.1
Translations
8.2
Infinitesimal rotations
8.3
The space of trivial motions
8.4
A lower bound on the dimension
9
Laman’s theorem
▶
9.1
The edge count in the plane
9.2
The \(\Leftarrow \) direction
9.3
The \(\Rightarrow \) direction
9.4
Laman’s theorem
10
The planar rigidity matroid
▶
10.1
Lifting row-independence through Henneberg moves
10.2
Row-independent edge sets in the plane
10.3
The rigidity matroid as a count matroid
10.4
The rigidity matroid of a framework
11
The \((k, \ell )\)-count matroid
▶
11.1
Components and augmentation
11.2
The matroid
12
Verified depth-first search
▶
12.1
Reachability regions
13
The \((k, \ell )\)-pebble game
▶
13.1
State and moves
13.2
Invariants
13.3
The basic algorithm
13.4
Soundness
13.5
Completeness
13.6
Correctness
13.7
The verdict
13.8
Independence in the count matroid
14
Executable pebble game
▶
14.1
Sorted lists
14.2
The computable pebble game
14.3
Deciding sparsity, tightness and the Laman property
14.4
Runtime and backends
14.5
Worked examples
14.6
CLI binary
15
Matroid union and Edmonds’ partition theorem
▶
15.1
Matroids from submodular functions
15.2
Matroid union
16
Body-bar Tay theorem
▶
16.1
Sparsity and the union of cycle matroids
16.2
The \(k\)-frame matroid as a union of cycle matroids
16.3
Decompositions into forests and spanning trees
16.4
Body-bar frameworks and the rigidity matrix
16.5
Tay’s theorem
17
Body-hinge Tay–Whiteley theorem
▶
17.1
Body-hinge frameworks and the hinge-to-bar reduction
17.2
The Tay–Whiteley theorem
18
Grassmann–Cayley extensor algebra
▶
18.1
Homogeneous coordinates and affine independence
18.2
Extensors, the join, and Plücker coordinates
18.3
Independence of the \((d-1)\)-extensors (KT Lemma 2.1)
19
The panel-hinge rigidity matrix \(R(G,p)\)
▶
19.1
Body-hinge frameworks and the rigidity matrix
19.2
Rank lemmas
19.3
Rank-addition lemmas
20
The matroid \(M(\tilde G)\), deficiency, and \(k\)-dof graphs
▶
20.1
The matroid \(M(\tilde G)\), the deficiency and \(k\)-dof-graphs
20.2
The deficiency and the rank of \(M(\tilde G)\)
20.3
The deficiency and the rank of \(R(G,p)\)
20.4
Rigid subgraphs and structural lemmas
21
The combinatorial induction: graph operations and KT Theorem 4.9
▶
21.1
Circuits and the contraction of a rigid subgraph
21.2
Removal, splitting off and edge-splitting
21.3
Forest surgery: KT Lemmas 4.1 and 4.2
21.4
Splitting off and removal: KT Lemmas 4.3–4.8
21.5
KT Theorem 4.9 and the induction for KT Theorem 5.5
21.6
Simplicity, and two adjacent vertices of degree two
21.7
A chain or a short cycle: KT Lemma 4.6
22
Grassmann–Cayley meet and projective duality
▶
22.1
The complement isomorphism and the meet
22.2
Lines in projective three-space
23
The algebraic induction: KT Theorem 5.5 and its three cases
▶
23.1
Panel-hinge frameworks
23.2
Two operations on frameworks
23.3
The rank formula from a bound on the motions
23.4
KT Theorems 5.5 and 5.6 and the molecular conjecture
23.5
KT Theorem 5.6 and the molecular conjecture for multigraphs
23.6
Case I: a proper rigid subgraph
23.7
The rank at generic normals
23.8
Counting rows and motions
23.9
Case II: no proper rigid subgraph and \(k {\gt} 0\)
23.10
Case III: no proper rigid subgraph and \(k = 0\)
24
The generic bar-joint rigidity matroid
▶
24.1
Generic placements
24.2
The matroid and its rank function
25
Projective duality and the molecule modelling equivalence
▶
25.1
The square graph and molecular frameworks
25.2
Projective invariance and duality
25.3
Screw velocity fields
25.4
Molecular realizations in general position
25.5
The square-graph dictionary
26
The molecule rank formula (KT Corollary 5.7)
▶
26.1
The generic rank bounds the rank at every placement
26.2
Simple graphs as multigraphs
26.3
The two inequalities and the formula
27
Independence and rank of molecular graphs
▶
27.1
The three-dimensional Laman condition
27.2
Tight partitions
27.3
The counting bound
27.4
Independence implies the Laman condition
27.5
Zero-extensions in dimension three
27.6
Jacobs’ conjecture
27.7
The degree-one rank formula
28
The generic form of the realization theorems
▶
28.1
Abundance of generic placements
28.2
Every generic realization of a square
28.3
Every generic panel-and-hinge realization
28.4
Every generic body-and-bar realization
28.5
Every generic body-and-hinge realization
29
Pencil realizations: hinges concurrent within a common panel
▶
29.1
Extensors through a point
29.2
Pencil realizations
29.3
The polarity and self-duality
29.4
The coincident-panel pencil pair
29.5
Pencil cycles: degree-two concurrency is automatic
29.6
The two-pencil extension step
29.7
Reduction on all spanning multigraphs
29.8
Nondegenerate realizations and the conditioned pair
29.9
Reduction to the main component
30
The main component of the pencil configuration space
▶
30.1
Planar pictures, the lifting space, and the main component
30.2
The flat rank
30.3
Jackson and Jordán’s equality
30.4
Cut vertices and bridges
30.5
Contraction at an additive core
30.6
Ears and cycles
30.7
Open ears with two, three or four interior bodies
30.8
Open ears with one or two interior bodies at non-adjacent ends
30.9
Splitting off a body of degree two
30.10
The deficiency of a sparse graph
30.11
The structural coverage
30.12
The two main-component statements
A
Notes on the formalization
▶
A.1
The \(d = 3\)-first scaffolding arc
A.2
Statement-faithfulness episodes
A.3
Abstraction-layer mis-factorings
A.4
Walls from mis-modelling
A.5
Process/tracking failures
B
Bibliography
Dependency graph
Combinatorial Rigidity
Bryan Gin-ge Chen
1
Introduction
Organization of the blueprint
Reading this blueprint
2
Edges in a vertex set
2.1
Definition and basic properties
2.2
Vertex deletion
2.3
Modularity: intersection, union, and supermodular counts
3
\((k,\ell )\)-sparsity and \((k,\ell )\)-tightness
3.1
Definitions
3.2
Basic properties and the global edge bound
3.3
Low-degree vertex and non-adjacency consequences
3.4
Invariance under isomorphism
3.5
Unions and intersections of tight sets
3.6
Splittings and tight sets
3.7
Sparse-graph reverse decomposition
4
Laman graphs
4.1
Definition and isomorphism invariance
4.2
The base case: \(K_2\)
4.3
Degree bounds
5
Henneberg moves
5.1
Definitions
5.2
Edge sets and edge counts
5.3
Preservation of the Laman property
5.4
Reverse decomposition
5.5
An example: \(K_4\) minus an edge
6
Frameworks and infinitesimal rigidity
6.1
Definitions
6.2
Rank and kernel bounds
6.3
Graph monotonicity
6.4
Transport along graph isomorphism
6.5
Openness of infinitesimal rigidity
6.6
The edge-count bound
6.7
Worked example: \(K_2\) is generically rigid in every dimension
7
Rigidity preservation under Henneberg moves (dimension 2)
7.1
The Type I move
7.2
The Type II move
8
Trivial infinitesimal motions
8.1
Translations
8.2
Infinitesimal rotations
8.3
The space of trivial motions
8.4
A lower bound on the dimension
9
Laman’s theorem
9.1
The edge count in the plane
9.2
The \(\Leftarrow \) direction
9.3
The \(\Rightarrow \) direction
9.4
Laman’s theorem
10
The planar rigidity matroid
10.1
Lifting row-independence through Henneberg moves
10.2
Row-independent edge sets in the plane
10.3
The rigidity matroid as a count matroid
10.4
The rigidity matroid of a framework
11
The \((k, \ell )\)-count matroid
11.1
Components and augmentation
11.2
The matroid
12
Verified depth-first search
12.1
Reachability regions
13
The \((k, \ell )\)-pebble game
13.1
State and moves
13.2
Invariants
13.3
The basic algorithm
13.4
Soundness
13.5
Completeness
13.6
Correctness
13.7
The verdict
13.8
Independence in the count matroid
14
Executable pebble game
14.1
Sorted lists
14.2
The computable pebble game
14.3
Deciding sparsity, tightness and the Laman property
14.4
Runtime and backends
14.5
Worked examples
14.6
CLI binary
15
Matroid union and Edmonds’ partition theorem
15.1
Matroids from submodular functions
15.2
Matroid union
16
Body-bar Tay theorem
16.1
Sparsity and the union of cycle matroids
16.2
The \(k\)-frame matroid as a union of cycle matroids
16.3
Decompositions into forests and spanning trees
16.4
Body-bar frameworks and the rigidity matrix
16.5
Tay’s theorem
17
Body-hinge Tay–Whiteley theorem
17.1
Body-hinge frameworks and the hinge-to-bar reduction
17.2
The Tay–Whiteley theorem
18
Grassmann–Cayley extensor algebra
18.1
Homogeneous coordinates and affine independence
18.2
Extensors, the join, and Plücker coordinates
18.3
Independence of the \((d-1)\)-extensors (KT Lemma 2.1)
19
The panel-hinge rigidity matrix \(R(G,p)\)
19.1
Body-hinge frameworks and the rigidity matrix
19.2
Rank lemmas
19.3
Rank-addition lemmas
20
The matroid \(M(\tilde G)\), deficiency, and \(k\)-dof graphs
20.1
The matroid \(M(\tilde G)\), the deficiency and \(k\)-dof-graphs
20.2
The deficiency and the rank of \(M(\tilde G)\)
20.3
The deficiency and the rank of \(R(G,p)\)
20.4
Rigid subgraphs and structural lemmas
21
The combinatorial induction: graph operations and KT Theorem 4.9
21.1
Circuits and the contraction of a rigid subgraph
21.2
Removal, splitting off and edge-splitting
21.3
Forest surgery: KT Lemmas 4.1 and 4.2
21.4
Splitting off and removal: KT Lemmas 4.3–4.8
21.5
KT Theorem 4.9 and the induction for KT Theorem 5.5
21.6
Simplicity, and two adjacent vertices of degree two
21.7
A chain or a short cycle: KT Lemma 4.6
22
Grassmann–Cayley meet and projective duality
22.1
The complement isomorphism and the meet
22.2
Lines in projective three-space
23
The algebraic induction: KT Theorem 5.5 and its three cases
23.1
Panel-hinge frameworks
23.2
Two operations on frameworks
23.3
The rank formula from a bound on the motions
23.4
KT Theorems 5.5 and 5.6 and the molecular conjecture
23.5
KT Theorem 5.6 and the molecular conjecture for multigraphs
23.6
Case I: a proper rigid subgraph
23.7
The rank at generic normals
23.8
Counting rows and motions
23.9
Case II: no proper rigid subgraph and \(k {\gt} 0\)
23.10
Case III: no proper rigid subgraph and \(k = 0\)
24
The generic bar-joint rigidity matroid
24.1
Generic placements
24.2
The matroid and its rank function
25
Projective duality and the molecule modelling equivalence
25.1
The square graph and molecular frameworks
25.2
Projective invariance and duality
25.3
Screw velocity fields
25.4
Molecular realizations in general position
25.5
The square-graph dictionary
26
The molecule rank formula (KT Corollary 5.7)
26.1
The generic rank bounds the rank at every placement
26.2
Simple graphs as multigraphs
26.3
The two inequalities and the formula
27
Independence and rank of molecular graphs
27.1
The three-dimensional Laman condition
27.2
Tight partitions
27.3
The counting bound
27.4
Independence implies the Laman condition
27.5
Zero-extensions in dimension three
27.6
Jacobs’ conjecture
27.7
The degree-one rank formula
28
The generic form of the realization theorems
28.1
Abundance of generic placements
28.2
Every generic realization of a square
28.3
Every generic panel-and-hinge realization
28.4
Every generic body-and-bar realization
28.5
Every generic body-and-hinge realization
29
Pencil realizations: hinges concurrent within a common panel
29.1
Extensors through a point
29.2
Pencil realizations
29.3
The polarity and self-duality
29.4
The coincident-panel pencil pair
29.5
Pencil cycles: degree-two concurrency is automatic
29.6
The two-pencil extension step
29.7
Reduction on all spanning multigraphs
29.8
Nondegenerate realizations and the conditioned pair
29.9
Reduction to the main component
30
The main component of the pencil configuration space
30.1
Planar pictures, the lifting space, and the main component
30.2
The flat rank
30.3
Jackson and Jordán’s equality
30.4
Cut vertices and bridges
30.5
Contraction at an additive core
30.6
Ears and cycles
30.7
Open ears with two, three or four interior bodies
30.8
Open ears with one or two interior bodies at non-adjacent ends
30.9
Splitting off a body of degree two
30.10
The deficiency of a sparse graph
30.11
The structural coverage
30.12
The two main-component statements
A
Notes on the formalization
A.1
The \(d = 3\)-first scaffolding arc
A.2
Statement-faithfulness episodes
A.3
Abstraction-layer mis-factorings
A.4
Walls from mis-modelling
A.5
Process/tracking failures
B
Bibliography