# Sparsity matroid

A **sparsity matroid** (also called a **count matroid**) is a matroid defined on the edge set of a graph in which a set of edges is independent exactly when the subgraph it induces is (k, ℓ)-sparse, meaning every non-empty edge subset F satisfies |F| ≤ k|V(F)| − ℓ, where V(F) is the set of vertices incident to F.<sup>[1](https://arxiv.org/abs/1103.2581)</sup> The two integer parameters k and ℓ select a whole family of matroids; for each pair the edge sets of the (k, ℓ)-sparse subgraphs of a graph G form the independent sets of a matroid on E, denoted \\( \mathcal{M}_{k,\ell}(G) \\).<sup>[1](https://arxiv.org/abs/1103.2581)</sup><sup> • </sup><sup>[2](https://pmc.ncbi.nlm.nih.gov/articles/PMC7254890/)</sup>

| Key fact | Detail |
|---|---|
| Independence condition | A set of edges is independent if every non-empty F ⊆ E satisfies \\( |F| \le k|V(F)| - \ell \\); sparsity is meaningful only when \\( 2k - \ell \ge 1 \\).<sup>[1](https://arxiv.org/abs/1103.2581)</sup> |
| Tight and full | A graph is (k, ℓ)-tight if it is sparse with exactly kn − ℓ edges, and (k, ℓ)-full if it contains a tight subgraph on all n vertices; G is full exactly when the matroid rank \\( \rho_{k,\ell}(E) = kn - \ell \\).<sup>[1](https://arxiv.org/abs/1103.2581)</sup> |
| Rigidity case | The (2, 3)-sparsity matroid on the edges of the complete graph K\_n is the generic 2D rigidity matroid, and its bases are the Laman graphs.<sup>[3](https://epubs.siam.org/doi/10.1137/21M1437986)</sup> |
| Tree packing | By Nash-Williams' theorem (1964), a graph contains k edge-disjoint spanning trees if and only if it is (k, k)-full.<sup>[1](https://arxiv.org/abs/1103.2581)</sup> |
| Exact computation | The pebble game algorithm of Lee and Streinu computes the rank of \\( \mathcal{M}_{k,\ell}(G) \\) in O(n²) time.<sup>[1](https://arxiv.org/abs/1103.2581)</sup> |
| Constant-time testing | Ito, Tanigawa, and Yoshida (2011) gave a constant-time approximation algorithm for the rank in the bounded-degree model, yielding constant-time testers for (k, ℓ)-fullness.<sup>[1](https://arxiv.org/abs/1103.2581)</sup> |
| Hypergraph extension | For hypergraphs with d endpoints per edge, (k, ℓ)-sparse hypergraphs form a linearly representable matroidal family whenever 0 ≤ ℓ ≤ dk − 1.<sup>[4](https://arxiv.org/abs/0711.3013)</sup> |

## Definition and basic structure

Let G = (V, E) be a graph, k a positive integer, and ℓ an integer with ℓ ≤ 2k − 1. A subgraph is (k, ℓ)-sparse if every subset X of vertices induces at most k|X| − ℓ edges, and (k, ℓ)-tight if it is sparse with exactly kn − ℓ edges in total.<sup>[1](https://arxiv.org/abs/1103.2581)</sup><sup> • </sup><sup>[5](https://arxiv.org/abs/2209.06204)</sup> A graph is (k, ℓ)-full, also called (k, ℓ)-spanning, if it contains a tight subgraph spanning the whole vertex set.<sup>[1](https://arxiv.org/abs/1103.2581)</sup><sup> • </sup><sup>[6](https://web.cs.umass.edu/publication/docs/2007/UM-CS-2007-002.pdf)</sup>

The condition becomes vacuous outside a bounded range: if 2k − ℓ < 1, even a single edge violates the count, so no non-empty graph can be sparse.<sup>[1](https://arxiv.org/abs/1103.2581)</sup> Within the admissible range, the sparse edge sets satisfy the matroid exchange axioms, so independent edges can be added to a sparse graph in any order until it becomes tight, and all maximal independent sets (bases) have the same cardinality.<sup>[6](https://web.cs.umass.edu/publication/docs/2007/UM-CS-2007-002.pdf)</sup> A minimal dependent set is a circuit; in the (2, 3) case, adding one edge to a [Laman graph](https://www.edgepedia.org/laman-graph) creates a dependent set of 2n − 2 edges containing a unique circuit.<sup>[3](https://epubs.siam.org/doi/10.1137/21M1437986)</sup>

For the tight graphs themselves, Lee and Streinu characterize exactly when the (k, ℓ)-tight graphs on n vertices form the bases of a matroid on the edges of the complete multi-graph, with loop multiplicity k − ℓ and edge multiplicity 2k − ℓ, under three conditions on n, k, and ℓ covering ℓ ∈ [0, k], ℓ ∈ (k, 3k/2), and ℓ ∈ [3k/2, 2k).<sup>[7](https://doi.org/10.1016/j.disc.2007.07.104)</sup>

## Relation to rigidity theory

The most studied instance is the (2, 3)-sparsity matroid, which coincides with the generic two-dimensional [rigidity matroid](https://www.edgepedia.org/rigidity-matroid) of the complete graph K\_n.<sup>[3](https://epubs.siam.org/doi/10.1137/21M1437986)</sup> Laman's theorem of 1970 states that a two-dimensional generic bar-and-joint framework is rigid if and only if its graph has a 2-sparse subgraph with 2|V| − 3 edges; the deficiency between 2n − 3 and the rank of the (2, 3)-sparsity matroid equals the degrees of freedom of the graph in the plane.<sup>[1](https://arxiv.org/abs/1103.2581)</sup><sup> • </sup><sup>[8](https://arxiv.org/abs/1104.4415)</sup>

More generally, Maxwell showed in 1864 that a necessary condition for a generic framework with at least d + 1 vertices to be rigid in \\( \mathbb{R}^d \\) is that G have a d-sparse subgraph with d|X| − C(d+1, 2) edges; this condition is also sufficient when d = 1 or 2 but not when d ≥ 3.<sup>[8](https://arxiv.org/abs/1104.4415)</sup> Sparsity matroids also enter global rigidity: for generic frameworks in the plane, or on a cylinder with the [Euclidean norm](https://www.edgepedia.org/euclidean-norm), global rigidity is characterized using the connectivity of a (k, ℓ)-sparsity matroid of the graph together with vertex-connectivity properties.<sup>[9](https://egres.elte.hu/www/tr-22-05.html)</sup> Applications extend to molecular rigidity, where a molecular graph is modeled as the square G² of a graph, and to scene analysis and sensor network localization.<sup>[1](https://arxiv.org/abs/1103.2581)</sup><sup> • </sup><sup>[2](https://pmc.ncbi.nlm.nih.gov/articles/PMC7254890/)</sup>

## Connections to tree packing and orientation

Two classical theorems identify special sparsity parameters with connectivity properties. A 1964 theorem of Nash-Williams on partitioning graphs into forests states that an undirected graph G has k edge-disjoint spanning trees exactly when it is (k, k)-full.<sup>[1](https://arxiv.org/abs/1103.2581)</sup> Combined with Edmonds' arc-disjoint branching theorem, this implies G is (k, 0)-edge-connected-orientable if and only if G is (k, k)-full.<sup>[1](https://arxiv.org/abs/1103.2581)</sup>

The unifying notion is (k, ℓ)-edge-connected-orientability: an undirected graph G is (k, ℓ)-ec-orientable if its edges can be oriented so that the resulting digraph has a root r from which every vertex v is reachable by k arc-disjoint dipaths, and from which ℓ arc-disjoint dipaths return from v to r.<sup>[1](https://arxiv.org/abs/1103.2581)</sup> By Nash-Williams' orientation theorem, (k, k)-ec-orientability is equivalent to 2k-edge-connectivity, so the orientability notion interpolates between conventional edge-connectivity and sparsity.<sup>[1](https://arxiv.org/abs/1103.2581)</sup>

## Algorithms

**Pebble games.** The (k, ℓ)-pebble game of Lee and Streinu recognizes the (k, ℓ)-sparse graphs for the full range ℓ ∈ [0, 2k). Each vertex starts with k pebbles; an edge is accepted when ℓ + 1 pebbles can be gathered on its endpoints, using depth-first searches to move pebbles along previously accepted edges.<sup>[6](https://web.cs.umass.edu/publication/docs/2007/UM-CS-2007-002.pdf)</sup><sup> • </sup><sup>[7](https://doi.org/10.1016/j.disc.2007.07.104)</sup> The basic game runs in O(n³) worst-case time and O(kn) space for dense inputs with constant parameters, and a component-based variant is one order of magnitude faster, giving O(n²) time overall.<sup>[7](https://doi.org/10.1016/j.disc.2007.07.104)</sup> The game solves the decision, extraction, spanning, and, with edges sorted by weight, the optimization problems for sparse graphs.<sup>[6](https://web.cs.umass.edu/publication/docs/2007/UM-CS-2007-002.pdf)</sup> Jacobs and Hendrickson's earlier algorithm is the (2, 3) case, and pebble game heuristics have been used in studies of protein flexibility.<sup>[6](https://web.cs.umass.edu/publication/docs/2007/UM-CS-2007-002.pdf)</sup> Improving the O(n²) bound for computing the rank of the (k, ℓ)-sparsity matroid for general parameters has been recognized as an open problem.<sup>[1](https://arxiv.org/abs/1103.2581)</sup>

**Constant-time property testing.** Hiro Ito, Shin-ichi Tanigawa, and Yuichi Yoshida gave a constant-time (1, εn)-approximation algorithm for the rank \\( \rho_{k,\ell}(E) \\) of a degree-bounded undirected graph, which yields a constant-time tester for (k, ℓ)-fullness in the bounded-degree model, with query complexity \\( (k+d)^{O(1/\epsilon'^{2})}(1/\epsilon')^{O(1/\epsilon')} \\) where \\( \epsilon' = \epsilon/(k + d\ell) \\).<sup>[1](https://arxiv.org/abs/1103.2581)</sup> For ℓ = 0 the rank reduces to a maximum matching in an auxiliary bipartite graph, which can be approximated in constant time.<sup>[1](https://arxiv.org/abs/1103.2581)</sup> They also derived a constant-time tester for (k, ℓ)-ec-orientability, resolving an open problem of Orenstein (2010).<sup>[1](https://arxiv.org/abs/1103.2581)</sup> The result has limits: for k ≥ 2 and proper ℓ ≥ 0, any one-sided error tester for (k, ℓ)-fullness or (k, ℓ)-ec-orientability requires Ω(n) queries, so constant time is achievable only with two-sided error.<sup>[1](https://arxiv.org/abs/1103.2581)</sup>

**Components and applications.** Csaba Király and András Mihálykó showed in a 2022 Egerváry Research Group technical report that the components of the (k, ℓ)-sparsity matroid can be computed in O(|V|²) time, and used this to check global rigidity of generic frameworks in the plane or on a cylinder, and to solve the global rigidity augmentation problem, finding a minimum edge set that makes a generically rigid graph globally rigid, in O(|V|²) time.<sup>[9](https://egres.elte.hu/www/tr-22-05.html)</sup>

## Generalizations

The definition extends to hypergraphs: a hypergraph G with n vertices and m hyperedges, each with d endpoints, is (k, ℓ)-sparse if no subset V′ of vertices spans more than k|V′| − ℓ hyperedges.<sup>[4](https://arxiv.org/abs/0711.3013)</sup><sup> • </sup><sup>[10](https://arxiv.org/abs/math/0703921)</sup> For 0 ≤ ℓ ≤ dk − 1 these form a linearly representable matroidal family, and Streinu and Theran gave a natural linear representation in which the representing matrix captures the vertex-edge incidence structure of the hypergraph.<sup>[4](https://arxiv.org/abs/0711.3013)</sup> Their pebble game constructions extend from graphs to hypergraphs, and the theory links arboricity counts to theorems of Haas, Lovász, Nash-Williams, Tutte, and White and Whiteley.<sup>[10](https://arxiv.org/abs/math/0703921)</sup> Related variants include gain-sparsity for symmetric frameworks and graded sparse graphs.<sup>[6](https://web.cs.umass.edu/publication/docs/2007/UM-CS-2007-002.pdf)</sup>

## References

1. [Hiro Ito, Shin-ichi Tanigawa, Yuichi Yoshida (2011). Constant-Time Algorithms for Sparsity Matroids. arXiv.](https://arxiv.org/abs/1103.2581)
2. [The Steiner Problem for Count Matroids. PMC.](https://pmc.ncbi.nlm.nih.gov/articles/PMC7254890/)
3. [Computing Circuit Polynomials in the Algebraic Rigidity Matroid. SIAM Journal on Applied Algebra and Geometry.](https://epubs.siam.org/doi/10.1137/21M1437986)
4. [Ileana Streinu, Louis Theran. Natural realizations of sparsity matroids. arXiv.](https://arxiv.org/abs/0711.3013)
5. [Count and cofactor matroids of highly connected graphs. arXiv.](https://arxiv.org/abs/2209.06204)
6. [Audrey Lee, Ileana Streinu (2008). Pebble Game Algorithms and Sparse Graphs. Discrete Mathematics 308(8), 1425–1437; UMass technical report.](https://web.cs.umass.edu/publication/docs/2007/UM-CS-2007-002.pdf)
7. [Pebble game algorithms and sparse graphs. ScienceDirect.](https://doi.org/10.1016/j.disc.2007.07.104)
8. [Bill Jackson, Hakan Guler (2011). A necessary condition for generic rigidity of bar-and-joint frameworks in d-space. arXiv.](https://arxiv.org/abs/1104.4415)
9. [Csaba Király, András Mihálykó (2022). Fast algorithms for sparsity matroids and the global rigidity augmentation problem. EGRES Technical Report TR-2022-05.](https://egres.elte.hu/www/tr-22-05.html)
10. [Ileana Streinu, Louis Theran (2007). Sparse Hypergraphs and Pebble Game Algorithms. arXiv.](https://arxiv.org/abs/math/0703921)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Matroid theory › Rigidity and sparsity matroids*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license