Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 4 (2011) 141–151
Natural realizations of sparsity matroids
Ileana Streinu ∗
Computer Science Department, Ford Hall, Smith College
Northampton, MA 01063, USA
Louis Theran †
Mathematics Department, Temple University
1805 North Broad Street, Philadelphia, PA 19122, USA
Received 5 July 2010, accepted 16 December 2010, published online 19 March 2011
Abstract
A hypergraph G with n vertices and m hyperedges with d endpoints each is (k, `)-
sparse if for all sub-hypergraphs G′ on n′ vertices and m′ edges, m′ ≤ kn′ − `. For
integers k and ` satisfying 0 ≤ ` ≤ dk − 1, this is known to be a linearly representable
matroidal family.
Motivated by problems in rigidity theory, we give a new linear representation theorem
for the (k, `)-sparse hypergraphs that is natural; i.e., the representing matrix captures the
vertex-edge incidence structure of the underlying hypergraph G.
Keywords: Matroids, combinatorial rigidity, sparse graphs and hypergraphs.
Math. Subj. Class.: 52C25, 05B35, 05C65, 68R10
1 Introduction
Let G be a d-uniform hypergraph; i.e., G = (V,E), where V is a finite set of n vertices
and E is a multi-set of m hyperedges, which each have d distinct endpoints. We define G
to be (k, `)-sparse if, for fixed integer parameters k and `, any non-empty sub-hypergraph
G′ of G on n′ vertices and m′ hyperedges satisfies the relation m′ ≤ kn′−`; if, in addition
m = kn− `, then G is (k, `)-tight.
For a fixed n, and integer parameters k, `, and d satisfying 0 ≤ ` ≤ dk − 1, the family
of (k, `)-tight d-uniform hypergraphs on n vertices form the bases of a matroid [21], which
we define to be the (k, `)-sparsity-matroid. The topic of this paper is linear representations
of the (k, `)-sparsity-matroids with a specific form.
∗Supported by grants NSF CCF-1016988, CCF-0728783 and a DARPA 23 Mathematical Challenges grant.
†This author’s PhD research was funded by grant NSF CCF-0728783 to Ileana Streinu, with preparation
supported by CDI-I grant DMR 0835586 to Igor Rivin and M. M. J. Treacy.
E-mail addresses: istreinu@smith.edu (Ileana Streinu), theran@temple.edu (Louis Theran)
Copyright c© 2011 DMFA Slovenije
142 Ars Math. Contemp. 4 (2011) 141–151
Main Theorem. Our main result is the following. Detailed definitions of (k, `)-sparse
hypergraphs are given in Section 2; detailed definitions of linear representations are given
in Section 3.
Theorem 1.1 (Natural Realizations). Let k, `, and d be integer parameters satisfying the
inequality 0 ≤ ` ≤ kd − 1. Then, for sufficiently large n, the (k, `)-sparsity-matroid of
d-uniform hypergraphs on n vertices is representable by a matrix M with:
• Real entries
• k columns corresponding to each vertex (for a total of kn)
• One row for each hyperedge e
• In the row corresponding to each edge e, the only non-zero entries appear in columns
corresponding to endpoints of e
Novelty. As a comparison, standard matroidal constructions imply that there is a linear
representation that is m × kn for all the allowed values of k, ` and d. For d = 2, ` ≤ k,
the (k, `)-sparsity-matroid is characterized as the matroid union of ` copies of the standard
graphic matroid and (k−`) copies of the bicycle matroid, so the desired representation fol-
lows from the Matroid Union Theorem [2, Section 7.6] for linearly representable matroids.
Theorem 1.1, in contrast, applies to the entire matroidal range of parameters k, `, and
d. In particular, it applies in the so-called upper range in which ` > k. In the upper range,
no reduction to matroid unions are known, so proofs based on the Matroid Union Theorem
do not apply.
Motivation. Our motivation for this work comes from rigidity theory, which is the study
of structures defined by geometric constraints. Examples include: bar-joint frameworks,
which are structures made of fixed-length bars connected by universal joints, with full
rotational freedom; and body-bar frameworks, which are made of rigid bodies connected
by fixed length bars attached to universal joints. A framework is rigid if the only allowed
continuous motions that preserve the lengths and connectivity of the bars are rigid motions
of Euclidean space.
In both cases, the formal description of the framework is given in two parts: a graph G,
defining the combinatorics of the framework; geometric data, specifying the lengths of the
bars, and their attachment points on the bodies. Rigidity is a difficult property to establish
in all cases, the with best known algorithms relying on exponential-time Gröbner basis
computations. However, for generic geometric data (and almost all lengths are generic, see
[16] for a detailed discussion), rigidity properties can be determined from the combinatorics
of the framework alone, as shown by the following two landmark theorems:
Theorem 1.2 (Maxwell-Laman Theorem: Generic planar bar-joint rigidity [7, 13]). A
generic bar-joint framework in R2 is minimally rigid if and only if its underlying graph G
is (2, 3)-tight.
Theorem 1.3 (Tay’s Theorem: Generic body-bar rigidity [17]). A generic body-bar
framework in Rd is minimally rigid if and only if its underlying graph G is (D,D)-tight,
where D =
(
d+1
2
)
.
I. Streinu and L. Theran: Natural realizations of sparsity matroids 143
All known proofs of theorems such as 1.2 and 1.3 proceed via a linearization of the
problem called infinitesimal rigidity. The key step in all of these proofs is to prove that a
specific matrix, called the rigidity matrix, which arises as the differential of the equations
for the length constraints, is, generically, a linear representation of some (k, `)-sparsity
matroid.
The rigidity matrices arising in Theorems 1.2 and 1.3 are specializations of our natural
realizations: they have the same pattern of zero and non-zero entries. The present work
arises out of the first author’s longer-term research project aimed at understanding rigidity
“from the combinatorics up” by studying (k, `)-sparse graphs and their generalizations.
Our main Theorem 1.1 and the implied natural realizations occupy an intermediate position
in between the rigidity theorems and the combinatorial matroids of (k, `)-sparse graphs.
The natural realizations presented here may be useful as building blocks for a new, more
general class of rigidity theorems in the line of Theorems 1.2 and 1.3.
Related work: (k, `)-sparse graphs. Graphs and hypergraphs defined by hereditary
sparsity counts first appeared as an example of matroidal families in the work of Lorea [11].
Whiteley, as part of a project with Neil White, reported in [21, Appendix], studied them
from the rigidity perspective. Michael Albertson and Ruth Haas [1] studied (k, `)-sparse
graphs from an extremal perspective as an instance of graphs characterized by “bounding
functions.”
The results in this paper build upon a sequence of papers by the first author, her stu-
dents and collaborators: [9] develops the structural and algorithmic theory of (k, `)-sparse
graphs; [15] extends the results of [9] to hypergraphs; [5, 14] give characterizations in
terms of decompositions into trees and “map-graphs”; [10] extends the sparsity concept to
allow different counts for different types of edges.
Related work: matroid representations. For the specific parameter values d = 2,
` ≤ k, natural realizations of the type presented in Theorem 1.1 may be deduced from
the Matroid Union Theorem [2, Section 7.6]; this was done by Whiteley [19], where the re-
alizations for d = 2, ` = l go by the name “k-frame.” In addition, White and Whiteley [21,
Appendix] have shown, using a geometric construction involving picking projective flats
in general position and then the Higgs Lift [2, Section 7.5] that all (k, `)-sparsity matroids
for graphs and hypergraphs are linearly representable.
Whiteley [20] proved a very similar result for the special case of k = 1; he also gave
representations for a related class of matroids on bipartite incidence graphs. These matroids
have also appeared in the Ph.D. thesis of Audrey Lee-St. John [8] under the name mixed
sparsity.
All known rigidity representation theorems [7, 6, 16, 17, 19] provide natural realizations
for the specific sparsity parameters involved. However, all these give more specialized
representations, arising from geometric considerations, with more specialized proofs. All
the arguments having a matroidal flavor seem to rely, in one way or another, on the Matroid
Union Theorem, or the explicit determinantal formulas used to prove it.
Related work: rigidity theory. Lovász and Yemini [12] introduced the matroidal per-
spective to rigidity theory with their proof of the Maxwell-Laman Theorem 1.2 based on an
explicit computation of the rank function of the (2, 3)-sparsity matroid that uses its special
relationship with the union of graphic matroids. Whiteley [19] gives a very elegant proof of
144 Ars Math. Contemp. 4 (2011) 141–151
Tay’s Theorem 1.3 [17] using the Matroid Union Theorem and geometric observations spe-
cific to the body-bar setting. White and Whiteley [18] analyzed the minors of k-frames of
[19] in detail, describing “pure conditions” that determine the rigidity behavior of body-bar
frameworks.
In both [12, 19], as well as in more recently proven Maxwell-Laman-type theorems of
Katoh and Tanigawa [6] and the authors’ [16], the connection between (k, `)-sparsity and
sparsity-certifying decompositions [14] of the minimally rigid family of graphs appears in
an essential way. In contrast, here we only need to employ sparsity itself, yielding a much
more general family of realizations. The price for this added generality is that we cannot
immediately deduce rigidity results directly from Theorem 1.1.
Organization. Section 2 introduces (k, `)-sparse hypergraphs and gives the necessary
structural properties. Section 3 gives the required background in linear representability of
matroids and then the proof of Theorem 1.1. In Section 4, we describe two extensions of
Theorem 1.1: to non-uniform (k, `)-sparse hypergraphs and to (k, `)-graded-sparse hyper-
graphs. We conclude in Section 5 with some remarks on the relationship between natural
realizations and rigidity.
Notations. A hypergraph G = (V,E) is defined by a finite set V of vertices and a multi-
set E of hyperedges, which are subsets of V ; if e ∈ E(G) is an edge and v ∈ e is a vertex,
then we call v an endpoint of the edge e. A hypergraph G is defined to be d-uniform
if all the edges have d endpoints. Sub-hypergraphs are typically denoted as G′ with n′
vertices and m′ edges; whether they are vertex- or hyperedge-induced will be explicitly
states. For d-uniform hypergraphs, we use the notation e1, e2, . . . , ed for the d endpoints
of a hyperedge e ∈ E(G).
Matrices M are denoted by bold capital letters, vectors v by bold lowercase letters.
The rows of a matrix M are denoted by mi.
The letters k, `, and d denote sparsity parameters.
Dedication. This paper is dedicated to the memory of Michael Albertson.
2 The (k, `)-sparsity matroid
Let (k, `, d) be a triple of non-negative integers such that 0 ≤ ` ≤ dk − 1; we define
such a triple as giving matroidal sparsity parameters (this definition is justified below in
Proposition 2.1). A d-uniform hypergraph G = (V,E) with n vertices and m hyperedges
is (k, `)-sparse if, for all subsets V ′ ⊂ V of n′ vertices inducing at least one hyperedge,
the subgraph induced by V ′ has m′ edges with m′ ≤ kn′ − `. If, in addition, m = kn− `,
G is (k, `)-tight. For brevity, we call (k, `)-tight d-uniform hypergraphs (k, `, d)-graphs.
The starting points for the results of this paper is the matroidal property of (k, `, d)-
graphs. We define Kdk−`n,d to be the complete d-uniform hypergraph on n vertices with
dk − ` copies of each hyperedge.
Proposition 2.1 ([11, 21, 15]). Let d, k and ` be non-negative integers satisfying ` ∈
[0, dk − 1]. Then the family of (k, `, d)-graphs on n vertices forms the bases of a matroid
on the edges of Kdk−`n,d , for a sufficiently large n, depending on k, `, and d.
I. Streinu and L. Theran: Natural realizations of sparsity matroids 145
We define the matroid appearing in Proposition 2.1 to be the (k, `, d)-sparsity-matroid.
From now on, the parameters k, ` and d are always matroidal sparsity parameters and
n is assumed to be large enough so that Proposition 2.1 holds.
The other fact we need is the following lemma from [15] characterizing the special case
of (k, 0, d)-graphs. We define an orientation of a hypergraph to be an assignment of a tail
to each hyperedge by selecting one of its endpoints (unlike in the graph setting, there is no
uniquely defined head).
Lemma 2.2 ([15]). Let G be a d-uniform hypergraph with n vertices and m = kn hy-
peredges. Then G is a (k, 0, d)-graph if and only if there is an orientation such that each
vertex is the tail of exactly k hyperedges.
3 Natural Realizations
In this section we prove our main theorem:
Theorem 1.1 (Natural Realizations). Let k, `, and d be integer parameters satisfying the
inequality 0 ≤ ` ≤ kd − 1. Then, for sufficiently large n, the (k, `)-sparsity-matroid of
d-uniform hypergraphs on n vertices is representable by a matrix M with:
• Real entries
• k columns corresponding to each vertex (for a total of kn)
• One row for each hyperedge e
• In the row corresponding to each edge e, the only non-zero entries appear in columns
corresponding to endpoints of e
Roadmap. This section is structured as follows. We begin by defining generic matrices
and then introduce the required background in linear representation of matroids. The proof
of Theorem 1.1 then proceeds by starting with the special case of (k, 0)-sparse hypergraphs
and then reducing to it via a general construction.
The generic rank of a matrix. A generic matrix has as its non-zero entries generic
variables, or formal polynomials over R or C in generic variables. Its generic rank is given
by the largest number r for which M has an r × r matrix minor with a determinant that is
formally non-zero.
Let M be a generic matrix in m generic variables x1, . . . , xm, and let v = (vi) ∈ Rm
(or Cm). We define a realization of M to be the matrix obtained by replacing the variable
xi with the corresponding number vi. A vector v is defined to be a generic point if the rank
of the associated realization is equal to the generic rank of M; otherwise v is defined to be
a non-generic point.
We will make extensive use of the following well-known facts from algebraic geomety
(see, e.g., [3]):
• The rank of a generic matrix M in m variables is equal to the maximum over v ∈ Rm
(Cm) of the rank of all realizations.
• The set of non-generic points of a generic matrix M is an algebraic subset of Rm
(Cm).
146 Ars Math. Contemp. 4 (2011) 141–151
• The rank of a generic matrix M in m variables is at least as large as the rank of any
specific realization; i.e., generic rank can be established by a single example.
Generic representations of matroids. LetM be a matroid on ground set E. We define
a generic matrix M to be a generic representation ofM if:
• There is a bijection between the rows of M and the ground set E.
• A subset of rows of M attains the rank of the matrix M if and only if the correspond-
ing subset of E is a basis ofM.
Natural realizations for (k,0, d)-graphs. Fix matroidal parameters k, ` = 0 and d,
and let G be a d-uniform hypergraph on n vertices and m hyperedges. For a hyperedge
e ∈ E(G) with endpoints ei, i ∈ [1, d], define the vector aei = (ajei)j∈[1,k] to have as its
entries k generic variables for each of the d endpoints of e.
Next, we define the generic matrix Mk,0,d(G) to have m rows, indexed by the hyper-
edges of G, and kn columns, indexed by the vertices of G, with k columns for each vertex.
The filling pattern of Mk,0,d is given as follows:
• If a vertex i ∈ V (G) is an endpoint of an edge e, then the k entries associated with i
in the row indexed by e are given by the vector aei .
• All other entries are zero.
For example, if G is a 3-uniform hypergraph, the matrix Mk,0,3(G) has the following
pattern:

e1 e2 e3
· · · · · · · · · · · · · · · · · · · · ·
e 0 · · · 0 a1e1 · · · a
k
e1 0 · · · 0 a
1
e2 · · · a
k
e2 0 · · · 0 a
1
e3 · · · a
k
e3 0 · · · 0
· · · · · · · · · · · · · · · · · · · · ·
.
The following lemma is a consequence of the Matroid Union Theorem and a represen-
tation result for the (1, 0, d)-sparsity-matroid due to Edmonds [4]. We give a more direct
proof for completeness. We note that Whiteley, in [20, Prop. 2.4], reproduces Edmonds’s
proof; here, even in the (1, 0, d)-case we go along different lines.
Lemma 3.1. Let G be a d-uniform hypergraph on n vertices and m = kn edges. Then
Mk,0,d(G) has generic rank kn if and only if G is a (k, 0, d)-graph.
Proof. First, we suppose that G is a (k, 0, d)-graph. By Lemma 2.2, there is an assignment
of a distinct tail to each edge such that each vertex is the tail of exactly k edges. Fix such
an orientation, giving a natural association of k edges to each vertex. Now specialize the
matrix Mk,0,d(G) as follows:
• Let i ∈ V (G) be a vertex that is the tail of edges ei1 , ei2 , . . . , eik .
• In row eij , set the variable ajeij to 1 and all other entries to zero.
Because each edge has exactly one tail, this process defines a setting for the entries of
Mk,0,d(G) with no ambiguity. Moreover, after rearranging the rows and columns, this
I. Streinu and L. Theran: Natural realizations of sparsity matroids 147
setting of the entries turns Mk,0,d(G) into the identity matrix, so this example shows its
rank generic is kn.
In the other direction, we suppose that G is not a (k, 0, d)-graph. Since G has kn edges,
it is not (k, 0)-sparse, so some subgraph G′ spanning n′ vertices induces at least kn′ + 1
edges. Arranging the edges and vertices of G′ into the top-left corner of Mk,0,d(G), we
see that G′ induces a submatrix with at least kn′ + 1 rows and only kn′ columns that are
not entirely zero. It follows that Mk,0,d(G) must be, generically, rank deficient.
Corollary 3.2. The matrix Mk,0,d(Kdkn,d) is a generic representation for the (k, 0, d)-
sparsity matroid.
Proof. Lemma 3.1 shows that a kn× kn matrix minor is generically non-zero if and only
if the set of rows it induces corresponds to a (k, 0, d)-graph, so the bases of Mk,0,d(Kdkn,d)
are in bijective correspondence with (k, 0, d)-graphs.
Corollary 3.3. Let G be a (k, `)-sparse d-uniform hypergraph with m hyperedges. The set
of v ∈ Rdkm such that the associated realization of Mk,0,d(G) has full rank is the open,
dense complement of an algebraic subset of Rdkm.
Proof. Corollary 3.2 implies that the rank drops only when v is a common zero of all the
m×m minors of Mk,0,d(G), which is a polynomial condition.
The natural representation matrix Mk,`,d(G). Fix matroidal sparsity parameters k, `,
and d, and let G be a d-uniform hypergraph. Let U be an kn × ` matrix with generic
entries. We define the matrix Mk,`,d(G) to be a generic matrix that is a formal solution to
the equation (3.1) below, with the entries of U fixed and the entries of Mk,0,d(G) as the
variables:
Mk,0,d(G)U = 0 (3.1)
We note that the process of solving (3.1) does not change the location of zero and non-zero
entries in Mk,0,d(G), preserving the naturalness property required by Theorem 1.1.
With this definition, we can restate Theorem 1.1 as follows: the matrix Mk,`,d(Kdk−`n,d )
is a generic representation of the (k, `, d)-sparsity matroid.
Main lemmas. The next two lemmas give the heart of the proof of Theorem 1.1. The
first says that if G is not (k, `)-sparse, then Mk,`,d(G) has a row dependency.
Lemma 3.4. Let k, `, and d be matroidal parameters and be G a d-uniform hypergraph
with m = kn− `. If G is not (k, `)-sparse, then Mk,`,d(G) is not generically full rank.
Proof. Since G is not (k, `)-sparse, it must have some vertex-induced subgraph G′ on n′
vertices and m′ > kn′ − ` edges. The sub-matrix of Mk,`,d(G) induced by the edges of
G′ has at least kn′ − `+1 rows and only kn′ columns that are not all zero, so it must have
a row dependency, since, by definition, the kernel of such a sub-matrix has dimension at
least `.
The following is the key lemma. It says that, generically, the dependencies of the type
described by Lemma 3.4 are the only ones.
148 Ars Math. Contemp. 4 (2011) 141–151
Lemma 3.5. Let k, `, and d be matroidal parameters and be G a d-uniform hypergraph
with m = kn − `. If G is (k, `)-sparse, i.e., it is a (k, `, d)-graph, then Mk,`,d(G) is
generically full rank.
Proof. We prove this by constructing an example, from which the generic statement fol-
lows. From Corollary 3.2 and Corollary 3.3, we may select values for the variables ajei in
the generic matrix Mk,0,d(G) so that the resulting realization M of Mk,0,d(G) is full rank.
Denote by me, for e ∈ E(G), the rows of M. Define the subspace WG of Rkn to be the
linear span of the me. For each vertex-induced subgraph G′ on n′ vertices of G define WG′
to be the linear span of {me : e ∈ E(G′)}; WG′ is a subspace of Rkn, and, because the
me span exactly kn′ non-zero columns in M, it has a natural identification as a subspace
of Rkn′ .
We will show that there is a subspace U of Rkn such that WG ∩ U⊥ has dimension
kn − `; taking the matrix U to be a basis of U and then solving meU = 0 for each row
of M gives a solution to (3.1) with full rank. This proves the lemma, since the resulting
matrix will have as its rows a basis for WG ∩ U⊥, which has dimension kn− `.
Now let U be an `-dimensional subspace of Rkn with basis given by the columns of the
kn × ` matrix U. For each vertex-induced subgraph G′ of G on n′ vertices, associate the
corresponding kn′ rows of U to determine a subspace UG′ .
Let G′ be a vertex-induced subgraph of G on n′ vertices and consider the subspace
WG′ . Since dimWG′ = dim(WG′ ∩ UG′) + dim(WG′ ∩ U⊥G′), if dim(WG′ ∩ U⊥G′) <
dimWG′ , thenWG′ ∩ UG′ is at least one-dimensional.
Here is the key to the proof (and where the combinatorial assumption of (k, `)-sparsity
enters in a fundamental way): by the (k, `)-sparsity of G, the dimension of WG′ is at
most kn′ − `. Since UG′ is only (at most) an `-dimensional subspace of Rkn
′
, this only
happens if the bases of WG′ and UG′ satisfy a polynomial relation. Since there are only
finitely many subgraphs, this gives a finite polynomial condition specifying which U are
disallowed, completing the proof.
Proof of the Main Theorem 1.1 With the two key Lemmas 3.4 and 3.5, the proof
of Theorem 1.1 is very similar to that of Corollary 3.2. We form the generic matrix
Mk,`,d(K
dk−`
n,d ). Lemma 3.4 and Lemma 3.5 imply that a set of rows forms a basis if
and only if the corresponding hypergraph G is a (k, `, d)-graph.
4 Extensions: non-uniform hypergraphs and graded sparsity
In this section, we extend Theorem 1.1 in two directions: to (k, `)-sparse hypergraphs that
are not d-uniform; to (k, `)-graded sparse hypergraphs.
Non-uniform hypergraphs. The theory of (k, `)-sparsity we developed in [15], does not
require that a hypergraph G be d-uniform. All the definitions are similar, except we require
only that if ` ≥ (d− 1)k, then each hyperedge have at least d endpoints. The ground set of
the corresponding sparsity matroid now is the more complicated hypergraph on n vertices
with ik − ` copies of each hyperedge with i endpoints for i ≥ d.
The combinatorial properties enumerated in Section 2 all hold in the non-uniform set-
ting, and the proofs in Section 3 all go through verbatim, with slightly more complicated
notation, yielding:
I. Streinu and L. Theran: Natural realizations of sparsity matroids 149
Theorem 4.1 (Natural Realizations: non-uniform version). Let k, `, be integer param-
eters satisfying the inequality 0 ≤ ` ≤ kd − 1. Then, for sufficiently large n, the (k, `)-
sparsity-matroid of non-uniform hypergraphs on n vertices is representable by a matrix M
with:
• Real entries
• k columns corresponding to each vertex (for a total of kn)
• One row for each hyperedge e
• In the row corresponding to each edge e, the only non-zero entries appear in columns
corresponding to endpoints of e
Graded-sparsity. In [10], we developed an extension of (k, `)-sparsity called (k, `)-
graded-sparsity. Graded-sparsity is the generalization of the sparsity counts appearing in
our work on slider-pinning rigidity [16].
Define the hypergraph K+n,k, to be the complete hypergraph on n vertices, where hy-
peredges with d endpoints have multiplicity dk. A grading (E1, E2, . . . , Es) of K+n is a
strictly decreasing sequence of sets of edges E(K+n ) = E1 ) E2 ) · · · ) Es. Now fix
a grading on K+n and let G = (V,E) be a hypergraph. Define G≥i as the subgraph of G
induced by E ∩ Ei. Let ` be a vector of s non-negative integers. We say that G is (k, `)-
graded sparse if G≥i is (k, `i)-sparse for every i; G is (k, `)-graded tight if, in addition,
it is (k, `1)-tight.
The main combinatorial result of [10] is that (k, `)-graded-sparse hypergraphs form the
bases of a matroid, which we define to be the (k, `)-graded-sparsity matroid.
Theorem 4.2 (Natural Realizations: graded-sparsity). Fix a grading of K+n,k and let
k and ` be graded-sparsity parameters. Then, for sufficiently large n, the (k, `)-sparsity-
matroid s on n vertices is representable by a matrix M with:
• Real entries
• k columns corresponding to each vertex (for a total of kn)
• One row for each hyperedge e
• In the row corresponding to each edge e, the only non-zero entries appear in columns
corresponding to endpoints of e
Because of the presence of the grading, we need to modify the proof of Theorem 1.1 to
account for it. The formal matrix Mk,0,+(K+n,k) is defined analogously to Mk,0,d(K
dk−`
n,d ),
except we sort the rows by the grading. The counterpart to (3.1) then becomes the system:
Mk,0,d(E≥i)Ui = 0, i = 1, 2, . . . , s (4.1)
where V1 is kn× `1, and each successive Ui is Ui with `i additional columns.
With this setup, the proof of Theorem 1.1 goes through with appropriate notational
changes.
150 Ars Math. Contemp. 4 (2011) 141–151
5 Conclusions and remarks on rigidity
We provided linear representations for the matroidal families of (k, `)-sparse hypergraphs
and (k, `)-graded-sparse hypergraphs that are natural, in the sense that the representing
matrices capture the vertex-edge incidence pattern. This family of representations, which
extends to the entire matroidal range of sparsity parameters, may be useful as a building
block for “Maxwell-Laman-type” rigidity theorems. We conclude with a brief discussion of
why one cannot conclude rigidity theorems such as Theorem 1.2 and Theorem 1.3 directly
from Theorem 1.1.
The proof of the critical Lemma 3.5 is very general, since it has to work for the entire
range of sparsity parameters. What it guarantees is that the entries of Mk,`,d(G) are some
polynomials, but not what these polynomials are. For rigidity applications, specific poly-
nomials are forced by the geometry, which would require more control over the matrix U
appearing in Equation (3.1) than the proof technique here allows.
For example, in the planar bar-joint rigidity case the “trivial infinitesimal motions” can
be given the basis:
• (1, 0, 1, 0 . . . , 1, 0) and (0, 1, 0, 1, . . . , 0, 1), representing infinitesimal translation
• (−y1,−y2, . . . ,−yn, x1, x2, . . . , xn), representing infinitesimal rotation around the
origin
It is important to note that Theorem 1.1 cannot simply be applied with this collection as
the columns of U to conclude the Maxwell-Laman Theorem 1.2. However, using specific
properties of the parameters d = 2, k = 2, ` = 3 Lovász and Yemini [12] do prove the
Maxwell-Laman Theorem starting from an algebraic result in the same vein as our Lemma
3.5, providing evidence that our results may have some relevance to rigidity.
References
[1] M. O. Albertson and R. Haas, Bounding functions and rigid graphs. SIAM J. Discrete Math. 9
(1996), 269–273.
[2] T. Brylawski, Constructions, in N. White (ed.), Theory of Matroids, Encyclopedia of Mathe-
matics and Its Applications, chapter 7, Cambridge University Press, 1986, 127–223.
[3] D. A. Cox, J. Little and D. O’Shea, Ideals, Varieties and Algorithms, Undergraduate texts in
Mathematics, Springer Verlag, New York, second edition, 1997.
[4] J. Edmonds, Systems of distinct representatives and linear algebra, J. Res. Nat. Bur. Standards
Sect. B, 71 (1967), 241–245.
[5] R. Haas, A. Lee, I. Streinu and L. Theran, Characterizing sparse graphs by map decomposi-
tions, J. Combin. Math. Combin. Comput. 62 (2007), 3–11.
[6] N. Katoh and S. Tanigawa, A proof of the molecular conjecture, in Proc. 25th Symp. on
Computational Geometry (SoCG’09), 2009, 296–305.
[7] G. Laman, On graphs and rigidity of plane skeletal structures, J. Eng. Math. 4 (1970), 331–340.
[8] A. Lee, Geometric Constraint Systems with Applications in CAD and Biology, PhD thesis,
University of Massachusetts Amherst, May 2008.
[9] A. Lee and I. Streinu, Pebble game algorithms and sparse graphs, Discrete Math. 308 (2008),
1425–1437.
[10] A. Lee, I. Streinu and L. Theran, Graded sparse graphs and matroids, J. Univers. Comput. Sci.
13 (2007), 1671–1679.
I. Streinu and L. Theran: Natural realizations of sparsity matroids 151
[11] M. Loréa, On matroidal families, Discrete Math. 28 (1979), 103–106.
[12] L. Lovász and Y. Yemini, On generic rigidity in the plane, SIAM J. Algebra. Discr. 3 (1982),
91–98.
[13] J. Maxwell, On the calculation of the equilibrium and stiffness of frames, Philosophical
Magazine Series 4, Jan 1864.
[14] I. Streinu and L. Theran, Sparsity-certifying graph decompositions, Graph. Combinator. 25
(2009), 219–238.
[15] I. Streinu and L. Theran, Sparse hypergraphs and pebble game algorithms, Eur. J. Combin. 30
(2009), 1944–1964.
[16] I. Streinu and L. Theran, Slider-pinning rigidity: a Maxwell-Laman-type theorem, Discrete
Comput. Geom. 44 (2010), 812–837.
[17] T.-S. Tay, Rigidity of multigraphs I: linking rigid bodies in n-space, J. Comb. Theory B 26
(1984), 95–112.
[18] N. White and W. Whiteley, The algebraic geometry of motions of bar-and-body frameworks,
SIAM J. Algebra. Discr. 8 (1987), 1–32.
[19] W. Whiteley, The union of matroids and the rigidity of frameworks, SIAM J. Discrete Math. 1
(1988), 237–255.
[20] W. Whiteley, A matroid on hypergraphs, with applications in scene analysis and geometry,
Discrete Comput. Geom. 4 (1989), 75–95.
[21] W. Whiteley, Some matroids from discrete applied geometry, in: J. Bonin, J. G. Oxley, and
B. Servatius (eds), Matroid Theory, volume 197 of Contemp. Math. (1996), 171–311.