# Sparse Incidence Geometries and Pebble Game Algorithms

Signe Lundqvist, Tovohery Randrianarisoa, Klara Stokes
and Joannes Vermant
Department of Mathematics and Mathematical Statistics
Umeå University, Umeå, 901 87, Sweden

(8 June 2023)

###### Abstract

In this paper we define sparsity and tightness of rank 2 incidence geometries,
and we develop an algorithm which recognises these properties. We give
examples from rigidity theory where such sparsity conditions are of interest.
Under certain conditions, this algorithm also allows us to find a maximum size
subgeometry which is tight. This work builds on so-called pebble game
algorithms for graphs and hypergraphs. The main difference compared to the
previously studied hypergraph case is that in this paper, the sparsity and
tightness are defined in terms of incidences, and not in terms of edges. This
difference makes our algorithm work not only for uniform hypergraphs, but for
all hypergraphs.

Keywords: incidence geometry, pebble game algorithm, sparse, tight
2000 MSC: 52C25, 52-08

##  1 Introduction

Generic rigidity of graphs in the plane is a well-studied topic in rigidity
theory. A graph $G=(V,E)$ is $(k,l)$-sparse if $|E^{\prime}|\leq
k|V(E^{\prime})|-l$ for all subsets $E^{\prime}\subseteq E$. The graph $G$ is
$(k,l)$-tight if it is $(k,l)$-sparse and $|E|=k|V|-l$. These notions are of
high interest as they are related to the rigidity of graphs. In fact, it is a
well-known result in rigidity theory that a graph is generically rigid in
$\mathbb{R}^{2}$ if and only if $G$ has a $(2,3)$-tight spanning subgraph [3,
5]. There are several algorithms for finding $(2,3)$-tight spanning subgraphs,
one of which is the pebble game algorithm, which was introduced by Jacobs and
Hendrickson [2].

In this paper, we introduce pebble game algorithms for sparse incidence
geometries of rank $2$. Suppose that $\Gamma=(P,L,I)$ is an incidence geometry
of rank $2$, and let $(\lambda,k_{1},k_{2},l)\in\mathbb{N}^{4}$. We define the
incidence geometry $\Gamma$ to be $(\lambda,k_{1},k_{2},l)$-sparse if for
every nonempty subset of $I^{\prime}\subseteq I$ it holds that

$\lambda|I^{\prime}|\leq k_{1}|P(I^{\prime})|+k_{2}|L(I^{\prime})|-l,$

where $P(I^{\prime})\times L(I^{\prime})$ is the support of $I^{\prime}$. We
say that $\Gamma$ is $(\lambda,k_{1},k_{2},l)$-tight if $\Gamma$ is sparse and

$\lambda|I|=k_{1}|P|+k_{2}|L|-l.$

The algorithm that we present recognises whether an incidence geometry is
sparse or tight. Furthermore, we prove that if $\lambda=1$, the tight
incidence geometries are the bases of a matroid, and in this case we can
extend the algorithm to find a maximal tight subgeometry. For almost all of
the proofs, the approach is analogous to that in [4, 7].

The paper is organised as follows. A common situation in rigidity theory is
that some sparsity condition on a combinatorial structure characterises some
geometric property. In Section 1.1, we give some examples where such a
sparsity count on the incidences of an incidence geometry gives interesting
characterisations. In Section 1.2 we give a short summary of further
generalisations of the pebble game. In Section 2, we give an algorithm that
can test whether an incidence geometry is sparse or tight. In Section 3, we
prove that if $\lambda$=1, then the $(1,k_{1},k_{2},l)$-sparse graphs are the
independent sets of a matroid, and give an algorithm for finding a maximum
size $(1,k_{1},k_{2},l)$-sparse subgeometry. Finally, in Section 4, we briefly
compare our notion of sparsity to the existing notion of sparsity for
hypergraphs. We also compare our pebble game algorithm to existing pebble game
algorithms.

###  1.1 Motivation

A rank $2$ incidence geometry is a triple, consisting of a set of points $P$,
a set of lines $L$, and a set of incidences $I\subseteq P\times L$. In various
contexts related to rigidity theory there are matroids on the incidences of a
rank $2$ incidence geometry.

The $k$-plane matroid, introduced by Whiteley [8], is a matroid with ground
set $A\times B$, for some sets $A$ and $B$. A set $I\subseteq A\times B$ is
independent if for any subset $I^{\prime}\subseteq I$ it holds that:

$|I^{\prime}|\leq|A(I^{\prime})|+k|B(I^{\prime})|-k$

where $A(I^{\prime})\times B(I^{\prime})\subseteq A\times B$ is the support of
$I$, i.e.

$A(I^{\prime})=\\{a\in A\>|\>\exists i\in I^{\prime},i=(a,b)\\}$

and

$B(I^{\prime})=\\{b\in L\>|\>\exists i\in I^{\prime},i=(a,b)\\}.$

The bases of this matroid have exactly

$|I|=|A|+k|B|-k$

incidences.

Let $\Gamma=(P,L,I)$ be an incidence geometry. The $k$-plane matroid defined
on the set $P\times L$, where $A=P$ and $B=L$, has applications in scene
analysis. More specifically, the lifting matrix, which has as its kernel the
$k$-dimensional scenes over a given $(k-1)$-picture of an incidence geometry
$\Gamma$, has independent rows if and only if $I$ is independent in the
$k$-plane matroid with $P=A$ and $L=B$ [8].

We can also consider the dual situation, where $P=B$ and $L=A$. The matrix
that has as its kernel the $d$-dimensional parallel redrawings of an incidence
geometry $\Gamma$ has independent rows if and only if $\Gamma$ is independent
in the dual $k$-plane matroid with $P=B$ and $L=A$.

Another case which has been studied is that of rod configurations. A rod
configuration is a realisation of an incidence geometry $\Gamma$ as points and
lines in the plane such that any motion of the points and lines preserves the
distance between any two collinear points. A rod configuration is rigid if the
only motions of the points and lines are rotations and translations. A rod
configuration is minimally rigid if no incidence can be removed without the
rod configuration becoming flexible - i.e. a rod configuration is minimally
rigid if all distance constraints between the points are necessary for the rod
configuration to be rigid. Whiteley proved that an incidence geometry
$\Gamma=(P,L,I)$ has a realisation as a minimally rigid rod configuration if
and only if

$2|I|=2|P|+3|L|-3$

and

$2|I^{\prime}|\leq 2|P(I^{\prime})|+3|L(I^{\prime})|-3$

for all subsets $I^{\prime}\subseteq I$, where $P(I^{\prime})\times
L(I^{\prime})$ is the support of $I^{\prime}$ [8].

In a recent work, two of the authors of the current article introduced an
approach to rigidity based on group theory and graphs of groups, which
generalises both of the above cases [6].

Suppose that we are given a geometric realisation of an incidence geometry,
and we want to study the ways in which this realisation can move while
respecting various constraints. If these constraints are invariant under the
action of a group $G$, then we can define motions of the structure solely in
terms of the group. When $G$ is a Lie group, the corresponding Lie algebra
allows to generalise the notion of Euclidean infinitesimal motions. Within
this context, in [6] we defined an analogue to the so-called Maxwell count.
Denoting the space of all infinitesimal motions by $M$, we proved the
following lower bound on the dimension of the infinitesimal motions:

$\dim(M)\geq\sum_{x\in
X}\dim(G/\rho(x))+\sum_{i\in\mathcal{I}}\dim(G/\rho(i))-\sum_{i\in\mathcal{I}}\sum_{x\in
i}\dim(G/\rho(x)),$

where $\rho(p),\rho(l)$ and $\rho(p*l)$ are stabilisers of realisations of
points, lines and incidences respectively under a smooth group action. If
$\rho(p)$ has the same dimension for all points, $\rho(l)$ has the same
dimension for all lines, and $\rho(p*l)$ has the same dimension for all
incidences, such counts simplify to a count of the form:

$\dim(M)\geq k_{1}|V|+k_{2}|L|-\lambda|I|.$

The intuition behind this formula is that adding incidences generally removes
$\lambda$ degrees of freedom from the structure. In some cases, there will be
dependencies, which will remove fewer degrees of freedom.

We may also define a notion of sparsity of an incidence geometry, related to
the Maxwell type bound on the dimension of the infinitesimal motions. Suppose
all motions of $\Gamma$ were to be trivial, in the sense that they come from
the group $G$, so that $\dim(M)=\dim(G)$. In this case, we see that

$\lambda|I|\geq k_{1}|V|+k_{2}|L|-\dim(G).$

Suppose that we are given an incidence geometry which only has trivial motions
with a minimum amount of incidences, in the sense that

$\lambda|I|=k_{1}|V|+k_{2}|L|-\dim(G),$

then, for every subset $I^{\prime}\subseteq I$ with

$\cap_{x\in I^{\prime}}\mathfrak{h}_{x}=\\{0\\},$

where $\mathfrak{h}_{x}$ is the Lie algebra of the group at $x$, one has:

$\lambda|I^{\prime}|\leq k_{1}|V(I^{\prime})|+k_{2}|L(I^{\prime})|-\dim(G).$

In this last equation $P(I^{\prime})\times L(I^{\prime})$ is the support of
$I^{\prime}$. If

$\cap_{x\in I^{\prime}}\mathfrak{h}_{x}=\\{0\\},$

for every nonempty subset $I^{\prime}\subseteq I$, this condition is precisely
the sparsity condition. In this way, we see that the ’minimally rigid’
incidence geometries are tight incidence geometries under a condition on the
intersection of the Lie algebras.

###  1.2 Sparse Graphs and Pebble Game Algorithms

The pebble game algorithm, introduced by Jacobs and Hendrickson, is an
algorithm for determining whether a graph has a $(2,3)$-tight spanning
subgraph [2]. The pebble game algorithm takes as its input a graph $G$, and
outputs a maximum size $(2,3)$-sparse subgraph. In particular, the algorithm
can decide whether the input graph has a $(2,3)$-tight spanning subgraph. The
$(2,3)$-tight graphs on $n$ vertices are the bases of a matroid on the edges
of the complete graph on $n$ vertices. Another algorithm that can extract a
$(2,3)$-tight subgraph was introduced by Gabow and Westerman [1].

For $l\geq 2k$, only the empty graph is $(k,l)$-sparse. For $l<0$,
$(k,l)$-sparsity does not behave well with respect to unions, in the sense
that the union of two vertex disjoint sparse graphs is not necessarily sparse.
Therefore, $(k,l)$-sparse graphs are primarily interesting to consider when
$l\in[0,2k)$.

Lee and Streinu introduced a family of $(k,l)$-pebble game algorithms that
recognise exactly the $(k,l)$-sparse multigraphs, for $l\in[0,2k)$ [4]. Lee
and Streinu show that the $(k,l)$-sparse multigraphs on $n$ vertices are the
independent sets of a matroid on the edges of the complete multigraph on $n$
vertices. The set of bases of this matroid is the set of $(k,l)$-tight
multigraphs on $n$ vertices.

Later, Streinu and Theran generalised the $(k,l)$-pebble game algorithms to
$r$-uniform hypergraphs, defining a hypergraph to be $(k,l)$-sparse if all
subsets $V^{\prime}$ of vertices span at most $k|V^{\prime}|-l$ edges [7].
They consider parameters $k$ and $l$ such that $0\leq l\leq kr-1$, where $r$
is the number of vertices in each edge. The $(k,l)$-sparse hypergraphs with
$n$ vertices also form the independent sets of a matroid, whenever
$(k,l)$-sparse $r$-uniform hypergraphs with $n$ vertices exist [4, 9]. The
$(k,l)$-tight hypergraphs on $n$ vertices are the bases of this matroid.

The fact that the $(k,l)$-sparse multigraphs and hypergraphs form the
independent sets of matroids is crucial to the pebble game algorithm, where an
independent set of edges is found by considering the edges in any order, and
an edge is added to the independent set if it is independent of the previously
considered edges. Building an independent set in this way (that is, greedily)
is only guaranteed to give a maximum size independent set if the independent
sets form a matroid.

Given the notions of sparsity and tightness of incidence geometries introduced
in Section 1.1, it is natural to consider an analogous pebble game algorithm
for incidence geometries. The pebble game algorithm introduced in this paper
generalises previously introduced pebble games for determining sparsity of
graphs and hypergraphs to rank two incidence geometries.

##  2 Algorithm for rank $2$ Geometries

The notions of sparsity and tightness are generalised to incidence geometries
as follows.

######  Definition 1.

Let $\Gamma=(P,L,I)$ be an incidence geometry of rank $2$, and let
$\lambda,k_{1},k_{2}$ and $l$ be integers in $\mathbb{N}$. The incidence
geometry $\Gamma$ is defined to be $(\lambda,k_{1},k_{2},l)$-sparse if for
every nonempty subset of $I^{\prime}\subseteq I$ it holds that

$\lambda|I^{\prime}|\leq k_{1}|P(I^{\prime})|+k_{2}|L(I^{\prime})|-l,$

where $P^{\prime}=P(I^{\prime})\times L^{\prime}=L(I^{\prime})$ is the support
$I^{\prime}$.

We say that $\Gamma$ is $(\lambda,k_{1},k_{2},l)$-tight if $\Gamma$ is sparse
and

$\lambda|I|=k_{1}|P|+k_{2}|L|-l.$

We simply say that $\Gamma$ is sparse (or tight) if the parameters are
understood.

As a remark, we notice $\Gamma$ is sparse if and only if for every subset
$I^{\prime}=I\cap(P^{\prime}\times L^{\prime})$, for some $P^{\prime}\subseteq
P$ and $L^{\prime}\subseteq L$, one has:

$\lambda|I^{\prime}|\leq k_{1}|P(I^{\prime})|+k_{2}|L(I^{\prime})|-l.$

Indeed, for every subset $I^{*}\subseteq I^{\prime}$, which is incident to the
same points and lines as $I^{\prime}$, one only decreases the left hand side
of the inequality, so if the inequality is valid for $I^{\prime}$, it will
also be valid for $I^{*}$.

As in [4] and [7], we develop a pebble game for such incidence geometries.

In our setting, we assume that

$k_{1}+k_{2}-\lambda\geq l.$ (1)

Under this condition, we can check whether a incidence geometry is
$(\lambda,k_{1},k_{2},l)$-sparse or tight. Since we can always reduce to the
case where $\textup{gcd}(\lambda,k_{1},k_{2},l)=1$, we can assume this without
loss of generality.

For an incidence geometry $\Gamma=(P,L,I)$, define $I_{\lambda}(\Gamma)$ to be
the multigraph constructed by taking the incidence graph of $\Gamma$, and
copying each edge $\lambda$ times. If $\Gamma$ is understood, we simply write
$I_{\lambda}$. In other words, $V(I_{\lambda}(\Gamma))=P\cup L$, and the edge
set is given by;

$E(I_{\lambda}(\Gamma))=\\{(p,l,i)\in P\times
L\times\\{1,\cdots\lambda\\}\>|\>(p,l)\in I\\},$

where the endpoints of an edge $(p,l,i)$ are $p$ and $l$. For $v\in
V(I_{\lambda}(\Gamma))$, set $\tau(v)=1$ if $v$ is a “point”, and set
$\tau(v)=2$ if $v$ is a “line”.

We now describe the pebble game. The input of the algorithm is a rank $2$
incidence geometry $\Gamma$.

During the pebble game, we maintain the following data:

  * •

The multigraph $I_{\lambda}(\Gamma)$.

  * •

A directed multigraph $D$, with $V(D)=V(I_{\lambda}(\Gamma))$, and with edge
set being a subset of $E(I_{\lambda}(\Gamma))$. We call the edges of $D$ as
_accepted_ edges.

  * •

For each vertex $v\in V(D)$, we store a natural number $\textup{peb}(v)$,
representing a number of ‘pebbles’.

The algorithm is initialised as follows:

  * •

Let $E(D)=\emptyset$.

  * •

For each vertex $v\in V(D)$, set $\textup{peb}(v)=k_{\tau(v)}$. In other
words, set $\textup{peb}(v)=k_{1}$ if $v$ is a “point”, and
$\textup{peb}(v)=k_{2}$ if $v$ is a “line”.

At any point in time we can make one of the following moves.:

  * •

Accept-Edge($e$): If $e=(v,w,i)$ is an edge in $I_{\lambda}(\Gamma)$ which is
not in $D$, and $\textup{peb}(v)+\textup{peb}(w)>l$, either remove a pebble
from $v$, add $(v,w,i)$ to $D$ and orient the edge from $v$ to $w$, or remove
a pebble from $w$, add $(v,w,i)$ to $D$ and orient the edge from $w$ to $v$.

  * •

Move-Pebble($v\leftarrow w$): A depth-first search algorithm is done to search
for a directed path whose source is $v$ and whose end point $w$ contain a
pebble. If there exists an oriented path $(v\dots w)=(v,v_{1},\dots,v_{n},w)$
of edges in $D$ from $v$ to $w$, and if $\textup{peb}(w)>0$, add a pebble to
$v$, remove a pebble from $w$ and change the orientation for every edge in
$(v\dots w)$.

We can then describe the pebble game algorithm in pseudocode in Algorithm 1.

Input: An incidence geometry $\Gamma$
Output: sparsity and/or tightness of $\Gamma$

for all incidences $(v,w)$ do

for $e=(v,w,i)\in E(I_{\lambda})$ associated to the incidence $(v,w)$ do

while $(v,w,i)$ not processed do

if $p(v)+p(w)>l$ then

Accept-Edge($e$).

$e$ has been processed.

else

search for a directed path $(v^{\prime}...u)$, $v^{\prime}\in\\{v,w\\}$,
$\\{v^{\prime},u\\}\neq\\{v,w\\}$, such that $\textup{peb}(u)>0$

if $(v^{\prime}...u)$ with $\textup{peb}(u)>0$ has been found then

Move-Pebble($v^{\prime}\leftarrow u$).

else

return : $\Gamma$ is not sparse.

end if

end if

end while

end for

end for

if $\sum_{v\in V}\textup{peb}(v)=l$ then

return $\Gamma$ is tight.

else

return $\Gamma$ is sparse, but not tight.

end if

Algorithm 1 Pebble game on Incidence graph

To following example explains how the algorithm works.

#### Example 1

We consider the incidence geometry $\Gamma=(P,L,I)$ described in Figure 1,
consisting of $|I|=3$ incidences from $|P|=2$ points and $L=2$ lines. Let
$\lambda=k_{1}=2$ and $k_{2}=l=3$. We have:

$6=\lambda|I|\leq k_{1}|P|+k_{2}|L|-l=7$

which means that the incidence geometry is sparse but not tight. The initial
state of $D$ is given by Figure 2(a), each vertex is labelled with the number
of pebbles at the vertex. At each step, for the edge being processed, we
always have at least $5$ pebbles in total. This allows us to accept two edges
while removing two pebbles from the source. At the end, in Figure 2(d), all
edges are accepted and we have 4 pebbles left. Therefore, as expected, the
algorithm concludes that the incidence geometry is sparse but not tight, as
there are more than $l$ remaining pebbles.

$p_{1}$$l_{1}$$p_{2}$$l_{2}$ Figure 1: Incidence graph of the incidence
geometry

$2$$3$$2$$3$

(a) Initial state

$0$$3$$2$$3$

(b) Intermediate

$0$$1$$2$$3$

(c) Intermediate

$0$$1$$0$$3$

(d) Final state

Figure 2: Multigraph $D$ at each step of the algorithm applied to the
incidence geometry of Figure 1 1

#### Complexity

Suppose that the algorithm terminates after accepting
$\lambda\epsilon+\lambda^{\prime}$ edges, where $\epsilon$ is the number of
fully “accepted” incidences and $\lambda^{\prime}$ is the number of edges from
the last partially accepted edge. For each edge, at most $l+1$ depth-first
searches are done through an oriented graph $D$ to collect enough pebbles. The
size of $D$ increases for each additional step but if we use the whole
incidence graph as an upper bound, in total the time complexity is given by

$\mathcal{O}((\lambda\epsilon+\lambda^{\prime})(l+1)(|P|+|L|+\lambda\epsilon+\lambda^{\prime})).$

In the worst case, this time complexity is approximately

$\mathcal{O}\left(\lambda l|I|(|P|+|L|+\lambda|I|)\right).$

On the storage side, only a directed graph is stored with $|P|+|L|+|I|$ data
from the incidence geometry and an additional
$\lambda\epsilon+\lambda^{\prime}$ for the orientations of accepted edges.
This gives a complexity

$\mathcal{O}(\lambda|I|+|P|+|L|).$

###  2.1 Invariants of the algorithm

For every subset $V\subseteq P\cup L$, define the following quantities.

$\displaystyle\textup{peb}(V)$ $\displaystyle:=\sum_{v\in V}\textup{peb}(v),$
$\displaystyle\textup{span}(V)$ $\displaystyle:=\\#\\{e\in D\>|\>o(e)\in
v\text{ and }t(e)\in V\\},$ $\displaystyle\textup{out}(V)$
$\displaystyle:=\\#\\{e\in D\>|\>o(e)\in v\text{ and }t(e)\notin V\\},$

where $o(e)$ is source of an oriented edge $e$, and $t(e)$ is the target. If
$V=\\{v\\}$, we write $\textup{out}(v)$ instead of $\textup{out}(\\{v\\})$.

######  Lemma 2.

The following are invariants of the algorithm:

  1. 1.

For all $v\in V$, one has $\textup{peb}(v)+\textup{out}(v)=k_{\tau(v)}$.

  2. 2.

Suppose that $V=A\cup B$, for some subsets $A\subseteq P$ and $B\subseteq L$.
Then $\textup{peb}(V)+\textup{span}(V)+\textup{out}(V)=k_{1}|A|+k_{2}|B|$.

  3. 3.

Suppose that $V=A\cup B$, for some nonempty subsets $A\subseteq P$ and
$B\subseteq L$. Then $\textup{peb}(V)+\textup{out}(V)\geq l$.

  4. 4.

Suppose that $V=A\cup B$, for some nonempty subsets $A\subseteq P$ and
$B\subseteq L$. Then $\textup{span}(V)\leq k_{1}|A|+k_{2}|B|-l$.

###### Proof.

To prove the first point, let $v\in V$. At the start of the algorithm,
$\textup{peb}(v)=k_{\tau(v)}$, and $\textup{out}(v)=0$, since
$E(D)=\emptyset$. Suppose that after $m$ steps, we have
$\textup{peb}(v)+\textup{out}(v)=k_{\tau(v)}$. At the $m$-th step, we can
either accept an edge, move pebbles, or end the algorithm. Let us verify all
cases where we accept an edge or move a pebble. If $P$ is a path which starts
at $v$ and ends at some $w$ with $\textup{peb}(w)>0$, then after moving the
pebble, $\textup{peb}(v)$ has increased by $1$ and $\textup{out}(v)$ has
decreased by $1$, since the path has changed direction. If $P$ is a path which
starts at some $w\in P\cup L$ and ends at $v$ with $\textup{peb}(w)>0$, then
after moving a pebble, $\textup{peb}(v)$ has decreased by $1$ and
$\textup{out}(v)$ has increased by $1$. For any other path, if we move a
pebble, $\textup{peb}(v)$ and $\textup{out}(v)$ remain the same. If we have
added an edge, with source $v$, then $\textup{peb}(v)$ has decreased by $1$
and $\textup{out}(v)$ has increased by $1$. If an edge is added with sources
different from $v$, both $\textup{out}(v)$ and $\textup{peb}(v)$ remain
unchanged.

Let us now turn to the second point. Thus let $V=A\cup B$, for some subsets
$A\subseteq P$ and $B\subseteq L$. We remark that

$\sum_{v\in V}\textup{out}(v)=\textup{span}(V)+\textup{out}(V).$

Hence,

$\begin{array}[]{cl}\textup{peb}(v)+\textup{span}(V)+\textup{out}(V)&=\sum_{v\in
V}(\textup{out}(v)+\textup{peb}(v))\\\ &=\sum_{v\in
A}(\textup{out}(v)+\textup{peb}(v))+\sum_{v\in
B}(\textup{out}(v)+\textup{peb}(v))\\\ &=k_{1}|A|+k_{2}|B|.\end{array}$

Now for the third point. Let $A,B$ be nonempty subsets of $P$ and $L$
respectively. If we are at the first step of the algorithm, then we have at
least $k_{1}$ pebbles in $A$ and $k_{2}$ pebbles in $B$. Then, since

$k_{1}+k_{2}>l,$

there are more than $l$ pebbles in $V=A\cup B$,

$\textup{peb}(V)+\textup{out}(V)=\textup{peb}(V)\geq l.$

Now, suppose the algorithm has run for $m$ steps. We analyse the various
cases. If in the last step, an edge was accepted with endpoints in $V$, there
must have been at least $l+1$ pebbles in $V$ before the edge was accepted, and
thus $\textup{peb}(V)+\textup{out}(V)\geq l$. If in the last step, an edge was
accepted, with endpoint not in $V$, then $\textup{peb}(V)+\textup{out}(V)$
remains invariant. By checking all cases, we also see that if a pebble is
moved, $\textup{peb}(V)+\textup{out}(V)$ remains invariant. Hence, whatever
happens in the algorithm, we see that $\textup{peb}(V)+\textup{out}(V)\geq l$.
The fourth point follows immediately from the third and second invariant:

$\begin{array}[]{cl}\textup{span}(V)&=k_{1}|A|+k_{2}|B|-\textup{out}(V)-\textup{peb}(V)\\\
&\leq k_{1}|A|+k_{2}|B|-l.\end{array}$

∎

######  Corollary 3.

Let $\Gamma=(P,L,I)$ be a rank $2$ incidence geometry. If all edges associated
to an incidence in $\Gamma$ are accepted in the pebble game, then $\Gamma$ is
sparse.
If there are exactly $l$ pebbles left in the graph, then $\Gamma$ is tight.

###### Proof.

Let $I^{\prime}$ be a set of incidences. Let

$A=\\{x\in P\>|\>x\in i\text{ for some incidence }i\in I^{\prime}\\},$

and

$B=\\{x\in L\>|\>x\in i\text{ for some incidence }i\in I^{\prime}\\}.$

By assumption, all edges in $I_{\lambda}(\Gamma)$ are accepted, and there are
$\lambda$ edges for each incidence. Thus, by invariant $4$ in the lemma above
we see that:

$\lambda|I^{\prime}|=\textup{span}(A\cup B)\leq k_{1}|A|+k_{2}|B|-l.$

This precisely means that $\Gamma$ is sparse. If there are exactly $l$ pebbles
left at the end of the algorithm we see by the second invariant applied to
$V=P\cup L$, that

$\textup{span}(V)+l=k_{1}|P|+k_{2}|L|,$

since $\textup{out}(V)=0$ and $\textup{peb}(V)=l$. This implies that $\Gamma$
is sparse. ∎

We have now shown that if every incidence in $\Gamma$ is accepted in the
pebble game, then $\Gamma$ is sparse. Now we show the converse, namely that if
$\Gamma$ is sparse, then every edge of $I_{\lambda}(\Gamma)$ will be accepted.
In the following proof, we need to define the notion of the $Reach$ of a
vertex in an oriented graph $D$. Let

$Reach(v):=\\{w\in V(D)\>|\>\mbox{ there exists an oriented path from }v\mbox{
to }w\\}.$

Note that in particular $v\in Reach(v)$, by taking the empty path.

######  Lemma 4.

Let $D$ be the set of edges we accepted so far and let $I_{D}$ be set of all
incidences having at least one edge in $D$. Suppose that $i_{0}\in I_{D}$ such
that

  * •

for all $i\neq i_{0}$, all edges associated to $i$ are in $D$,

  * •

some edge associated to $i_{0}$ is not in $D$.

If $I_{D}$ is sparse, then we can accept all edges associated to $i_{0}$.

###### Proof.

We show that if we are in this situation, we can always accept an edge, and
thus all edges can be accepted by induction.
Let $i_{0}=(uv)$, where $u$ is a point and $v$ is a line. If there are more
than $l$ pebbles at $u$ and $v$ together, we can add a new edge and remove a
pebble. So, we may assume that $\textup{peb}(u)+\textup{peb}(v)<l+1$. Let
$V=Reach(u)\cup Reach(v)$. Since $I_{D}$ is sparse, $span(V)<k_{1}|V\cap
P|+k_{2}|V\cap L|-l$. Note that $V\cap P$ and $V\cap L$ are nonempty since
$u\in V\cap P$ and $v\in V\cap L$. By the definition of $Reach$, $out(V)=0$
and by invariant 2 in Lemma 2,

$\textup{span}(V)+\textup{peb}(V)=k_{1}|V\cap P|+k_{2}|V\cap L|$

and thus

$\textup{peb}(V)>l.$

Hence, there is a point/line $w$ in $V$ such that $w\notin\\{v,u\\}$ with at
least one pebble left. Since it is reachable by either $v$ or $u$, we can move
that pebble while changing the direction of the path. Repeat this process
until we get enough pebbles together at $u$ and $v$ so that we can accept a
new edge and add it to $D$. ∎

######  Corollary 5.

Let $\Gamma=(P,L,I)$ be an incidence geometry. Given parameters
$\lambda,k_{1},k_{2},l$ such that $k_{1}+k_{2}-\lambda\geq l$. If $\Gamma$ is
sparse, then the pebble game accepts all edges of $I_{\lambda}(\Gamma)$.

###### Proof.

By Lemma 4, every incidence will be accepted by the pebble game. ∎

##  3 Matroidal properties of $(\lambda,k_{1},k_{2},l)$-sparsity.

Although we now have an algorithm which recognises whether an incidence
geometry is sparse or not, we are not necessarily able to use this algorithm
to greedily build a maximum size sparse subgeometry of a given incidence
geometry, which is possible for the classical pebble games. The property which
makes this possible is the fact that sparse graphs form the independent sets
of a matroid. Therefore, in this section, we consider whether or not we get a
matroid, depending on the values of $(\lambda,k_{1},k_{2},l)$. We will need
the following lemma, for which we need the following terminology. A
subgeometry of an incidence geometry $\Gamma=(P,L,I)$, is an incidence
geometry $\Lambda=(P^{\prime},L^{\prime},I^{\prime})$ such that
$P^{\prime}\subseteq P,L^{\prime}\subseteq L$ and $I\subseteq I^{\prime}$. A
block of an incidence geometry $\Gamma=(P,L,I)$, is a tight subgeometry
$B=(P^{\prime},L^{\prime},I)$.

######  Lemma 6.

Given two blocks $B_{1}=(P_{1},L_{1},I_{1}),B_{2}=(P_{2},L_{2},I_{2})$ of a
sparse incidence geometry $\Gamma=(P,L,I)$. If $P_{1}\cap P_{2}$ and
$L_{1}\cap L_{2}$ are nonempty, then $B_{1}\cap B_{2}$ and $B_{1}\cup B_{2}$
are also blocks, where these subgeometries are defined as

$\begin{array}[]{cl}I_{\cup}&:=\\{i\in I|i\in(P_{1}\cup P_{2})\times(L_{1}\cup
L_{2})\\}\\\ I_{\cap}&:=\\{i\in I|i\in(P_{1}\cap P_{2})\times(L_{1}\cap
L_{2})\\}\\\ B_{1}\cup B_{2}&:=(P_{1}\cup P_{2},L_{1}\cup L_{2},I_{\cup})\\\
B_{1}\cap B_{2}&:=(P_{1}\cap P_{2},L_{1}\cap L_{2},I_{\cap}).\end{array}$

###### Proof.

For any subset of $I^{\prime}\subseteq I_{\cup}$ or any subset of $I_{\cap}$,
sparsity holds by sparsity of $\Gamma$, thus we only need to show that
$I_{\cap}$ and $I_{\cup}$ have the desired cardinality. We compute

$\begin{array}[]{cl}\lambda|I_{\cup}|&\geq\lambda(|I_{1}|+|I_{2}|-|I_{\cap}|)\\\
&=k_{1}(|P_{1}|+|P_{2}|)+k_{2}(|L_{1}|+|L_{2}|)-2l-\lambda|I_{\cap}|\\\ &\geq
k_{1}(|P_{1}|+|P_{2}|-|P_{1}\cap P_{2}|)+k_{2}(|L_{1}|+|L_{2}|-|L_{1}\cap
L_{2}|)-l\\\ &=k_{1}(|P_{1}\cup P_{2}|)+k_{2}(|L_{1}\cup
L_{2}|)-l,\end{array}$

where we apply sparsity of $\Gamma$ to $I_{\cap}$ to get the third line from
the second. By sparsity of $\Gamma$, it also holds that

$\lambda|I_{\cup}|\leq k_{1}(|P_{1}\cup P_{2}|)+k_{2}(|L_{1}\cup L_{2}|)-l,$

and thus we have

$\lambda|I_{\cup}|=k_{1}(|P_{1}\cup P_{2}|)+k_{2}(|L_{1}\cup L_{2}|)-l.$

Thus $B_{1}\cup B_{2}$ is tight, and every inequality in the computation above
is necessarily an equality. Thus, for $B_{1}\cap B_{2}$, we see that

$\begin{array}[]{cl}\lambda|I_{\cap}|&=\lambda(|I_{1}|+|I_{2}|-|I_{\cup}|)\\\
&=k_{1}(|P_{1}|+|P_{2}|-|P_{1}\cup P_{2}|)+k_{2}(|L_{1}|+|L_{2}|-|L_{1}\cup
L_{2}|)-l\\\ &=k_{1}(|P_{1}\cap P_{2}|)+k_{2}(|L_{1}\cap
L_{2}|)-l.\end{array}$

This completes the proof of the claim. ∎

######  Lemma 7.

Suppose that

$l\leq k_{2}+k_{1}-1.$

Suppose that $n\geq k_{2},m\geq k_{1}$ are integers such that

$nm\geq k_{1}n+k_{2}m-l.$ (2)

Then, there exists a $(1,k_{1},k_{2},l)$-tight incidence geometry with $a_{0}$
points and $b_{0}$ lines, where $k_{2}\leq a_{0}\leq n$ and $k_{1}\leq
b_{0}\leq m$.

###### Proof.

Note that in any incidence geometry, there are at most $|P||L|$ incidences.
Hence, to get a tight incidence geometry, we need the following bound on the
points and lines:

$|P||L|\geq k_{1}|P|+k_{2}|L|-l.$

Note that the function

$f(x,y)=xy-k_{1}x-k_{2}y+l$

is increasing as a function of $x$ for all $y>k_{1}$ and similarly, for all
$x>k_{2}$ it is increasing as a function of $y$. Moreover, if $1\leq c$, and
$y\leq k_{1}$, then

$\displaystyle f(c,y)$ $\displaystyle=cy-k_{1}c-k_{2}y+l$
$\displaystyle=(y-k_{1}-k_{2}y+l)+(c-1)y-(c-1)k_{1}$
$\displaystyle=f(1,y)+(c-1)(y-k_{1}).$

which as non-increasing as a function of $x$. Similarly, if $1\leq x\leq
k_{2}$, then

$f(x,c)=f(x,1)+(c-1)(x-k_{2}),\\\ $

is non-increasing as a function of $y$. Furthermore, note that

$f(1,1)\leq 1-k_{2}-k_{1}+l\leq 0,$

since $k_{1}+k_{2}-1\geq l$. Hence, we see that for all $x,y$ with $x\leq
k_{2}$, or $y\leq k_{1}$, we have

$f(x,y)\leq 0.$

By these properties, there must exist some integers $a_{0}$ and $b_{0}$, with
$k_{2}\leq a_{0}\leq n$ and $k_{1}\leq b_{0}\leq m$ such that:

$a_{0}b_{0}-k_{1}a_{0}-k_{2}b_{0}+l\geq 0$

and such that for any integers $a,b$ with $0<a\leq a_{0}$ and $0<b\leq b_{0}$
with $a+b<a_{0}+b_{0}$ one has:

$ab-k_{1}a-k_{2}b+l\leq 0.$ (3)

Now, consider the incidence geometry with $a_{0}$ points $P$ and $b_{0}$ lines
$L$, and all incidences $P\times L$. Then remove any set of

$a_{0}b_{0}-k_{1}a_{0}-k_{2}b_{0}+l$

incidences. We claim the resulting incidence geometry is tight. Clearly, we
have:

$|I|=k_{1}|P|+k_{2}|L|-l.$

On the other hand, for any subset $I^{\prime}\subseteq I$, we have by the
property 3:

$|I^{\prime}|\leq|P(I^{\prime})||L(I^{\prime})|<k_{1}|P(I^{\prime})|+k_{2}|L(I^{\prime})|-l,$

Hence the incidence geometry is sparse. ∎

######  Theorem 8.

Suppose we are given a set of points $P$ and a set of lines $L$. Let
$(\lambda,k_{1},k_{2},l)$ be such that $\lambda=1$ and $k_{1}+k_{2}-1\geq l$.
Then letting $E=P\times L$, the collection

$\mathcal{I}=\\{I\subseteq E\>|\>(P,L,I)\textup{ is sparse}\\}$

are the independent sets of a matroid provided that $|P|,|L|$ are sufficiently
large.

###### Proof.

We prove that the tight incidence geometries on $|P|$ points and $|L|$ lines
are the bases of a matroid. Let $\mathcal{B}$ be the collection of all sets
$B_{i}\subseteq E$ such that $(P,L,B_{i})$ is a tight geometry. We need to
check the following $2$ properties

  1. 1.

$\mathcal{B}\neq\emptyset$
Let $P$ and $L$ be such that $|P|\geq k_{2}$, $|L|\geq k_{1}$ and $|P||L|\geq
k_{1}|P|+k_{2}|L|-l$. By Lemma 7, there are numbers $a_{0}$ and $b_{0}$ such
that $k_{2}\leq a_{0}\leq|P|$ and $k_{1}\leq b_{0}\leq|L|$ and there is a
tight incidence geometry with $a_{0}$ points and $b_{0}$ lines. Let $\Gamma$
be this incidence geometry. If $|P|>a_{0}$, we can add a point to $\Gamma$
which is incident to $k_{1}$ lines. The incidence geometry obtained in this
way will still be tight. We can do this inductively until the incidence
geometry has $|P|$ points. Similarly, if $|L|>b_{0}$, we can add a line to
$\Gamma$ which is incident to $k_{2}$ points. Again, the resulting incidence
geometry will be tight. We can do this inductively until $\Gamma$ has $|L|$
lines.

  2. 2.

$\forall B_{1},B_{2}\in\mathcal{B}\>\forall b\in B_{2}\setminus B_{1},\exists
c\in B_{1}\setminus
B_{2}:\left(\left(B_{1}\setminus\\{c\\}\right)\cup\\{b\\}\right)\in\mathcal{B}$
proof: Suppose that the incidence $b=(p,\ell)$. Consider:

$M=\bigcap_{\begin{subarray}{c}B\subseteq B_{1}\\\ B\textup{ is a block}\\\
p\in B,\ell\in B\end{subarray}}B$

We note that $M$ is nonempty since $B_{1}$ is in the collection we are
intersecting over, and $M$ is a block of $B_{1}$ by Lemma 6. Suppose that the
incidences in $M$ are incident to the points $P_{M}$ and $L_{M}$. Now, there
must exist some $c\in M\setminus B_{2}$, since otherwise $B_{2}$ would violate
sparsity on the set of incidences $I^{\prime}$ between $P_{M}$, and $L_{M}$,
since we would have:

$|I^{\prime}|\geq(|M|+1)=k_{1}|P_{M}|+k_{2}|L_{M}|-l+1.$

Now, consider $\left(B_{1}\setminus\\{c\\}\right)\cup\\{b\\}$. Let us show
that it is tight. Suppose for a contradiction that there is some set
$I_{*}\subseteq\left(B_{1}\setminus\\{c\\}\right)\cup\\{b\\}$ incident to
point set $P_{*}$ and line set $L_{*}$, which violates sparsity. So we assume,

$|I_{*}|>k_{1}|P_{*}|+k_{2}|L_{*}|-l.$

For this to be possible, $I_{*}$ must contain $b$. Now, note that

$|I_{*}\setminus\\{b\\}|>k_{1}|P_{*}|+k_{2}|L_{*}|-l-1$

and on the other hand

$|I_{*}\setminus\\{b\\}|\leq
k_{1}|P(I_{*}\setminus\\{b\\})|+k_{2}|L(I_{*}\setminus\\{b\\})|-l\leq
k_{1}|P_{*}|+k_{2}|L_{*}|-l.$

We see that:

$|I_{*}\setminus\\{b\\}|=k_{1}|P_{*}|+k_{2}|L_{*}|-l.$

This implies that $I_{*}\setminus\\{b\\}$ is a block of $B_{1}$. We also see
that $P(I_{*}\setminus\\{b\\})=P(I_{*})$, and
$L(I_{*}\setminus\\{b\\})=L(I_{*})$. Since $p\in P(I_{*})$, and $\ell\in
L(I_{*})$, this means that $M\subseteq I_{*}$, but then we must have $c\in
I_{*}$, as $c\in M$, which is a contradiction with the fact that
$I_{*}\subset(B_{1}\cup\\{B\\})\setminus\\{c\\}$.

∎

Figure 3: Two $(2,2,3,3)$-tight incidence geometries with 4 points and 5 lines

#### Example 2

Consider the two graphs in Figure 3. As incidence geometries, both graphs are
$(2,2,3,3)$-tight, and they have the same number of points and lines. Note
that, to go from one of the graphs in Figure 3 to the other, two incidences
need to be changed.

Hence, the $(2,2,3,3)$-tight incidence geometries do not form the bases of a
matroid on the set $V\times E$, where $V$ is the set of four vertices, and $E$
is the set of edges of $K_{4}$.

###  3.1 Algorithm for finding a tight subgeometry

By what we have shown, it is easy to see that Algorithm 2 returns a maximum
size $(1,k_{1},k_{2},l)$-sparse subgeometry, whenever $\lambda=1$,
$k_{1}+k_{2}-1\geq l$ and $P$ and $L$ are sufficiently large. Moreover, the
pebble game recognises whenever this subgeometry is sparse but not tight. The
difference to the pebble game described in section 2 is that instead of
stopping when we have found an edge which cannot be accepted, we continue to
see if we can add subsequent incidences, and we stop when we cannot add any
more incidences, or if all incidences are added to $D$. The description is
somewhat simplified because $\lambda=1$, so we can play the pebble game
directly on the incidence graph.

Input: An incidence geometry $\Gamma$

for all incidences $i$, with corresponding edge $e$ in the incidence graph do

while The edge $e$ has not been processed do

if $\textup{peb}(v)+\textup{peb}(w)>l$ then

Accept-Edge($e$).

$e$ has been processed.

else

search for a directed path $(v^{\prime}...u)$, $v^{\prime}\in\\{v,w\\}$,
$\\{v^{\prime},u\\}\neq\\{v,w\\}$, such that $\textup{peb}(u)>0$

if $(v^{\prime}...u)$ with $\textup{peb}(u)>0$ has been found then

Move-Pebble($v^{\prime}\leftarrow u$).

else

$e$ has been processed.

end if

end if

end while

end for

if $\sum_{v\in V}\textup{peb}(v)=l$ then

return the set of accepted edges $D$, which is tight.

else

return the set of accepted edges $D$, which is sparse but not tight.

end if

Algorithm 2 Pebble game for recognising a subgeometry

The complexity of this algorithm in the worst case is the same as Algorithm 1.
With $\lambda=1$, we have a time complexity of

$\mathcal{O}(l|I|(|P|+|L|+|I|)),$

and a storage complexity of

$\mathcal{O}(|I|+|P|+|L|).$

Probably, further extensions are possible to improve the complexity by
considering a pebble game with components, as is done in [4, 7].

##  4 Comparison to previously known pebble game algorithms

Any hypergraph $H=(V,E)$ can be considered as a rank $2$ incidence geometry
$\Gamma(H)$ with point set $V$ and line set $E$, where a point $v$ and a line
$e$ are incident if and only if $v$ is contained in the edge $e$. We remark
that if $H$ is $r$-uniform, then for each edge we get $r$ incidences. In the
counts above, it is thus easy to translate the condition for a hypergraph to
be sparse, into a condition for the associated incidence geometry to sparse:

######  Theorem 9.

For all natural numbers $\lambda\geq 1$, one has that $(k_{1},l)$-sparsity of
a $r$-uniform hypergraph $H$, corresponds to $(\lambda,k_{1},\lambda
r-1,l)$-sparsity of the incidence geometry $\Gamma(H)$. Moreover, $H$ is tight
if and only if $\Gamma(H)$ is tight.

###### Proof.

Suppose $H$ is $(k_{1},l)$-sparse. Then, for any subset $V^{\prime}$ of
vertices one has:

$|E(V^{\prime})|\leq k_{1}|V^{\prime}|-l,$

where $E(V^{\prime})=\\{e\in E|\>e\subseteq V^{\prime}\\}$. Hence for the set
$V^{\prime}\times E(V^{\prime})$, and $I^{\prime}:=I\cap V^{\prime}\times
E(V^{\prime})$ one has:

$\displaystyle(r-(r-1))|E(V^{\prime})|$ $\displaystyle\leq
k_{1}|V^{\prime}|-l$ $\displaystyle|I^{\prime}|$ $\displaystyle\leq
k_{1}|V^{\prime}|+(r-1)|E^{\prime}(V^{\prime})|-l.$

and for all $\lambda\in\mathbb{N}$, we get:

$\displaystyle\lambda|I|$ $\displaystyle\leq k_{1}|V^{\prime}|+(\lambda
r-1)|E(V^{\prime})|-l.$

Now, suppose we are given any subset of incidences $I^{\prime}$ given by
$I^{\prime}=I\cap V^{\prime}\times E^{\prime}$. Without loss of generality,
$V(I^{\prime})=V^{\prime}$, $E(I^{\prime})=E^{\prime}$. Let
$E^{\prime}(V^{\prime})$ be the set of $e\in E^{\prime}$ such that for any
incidences $v*e$ one has $v\in V^{\prime}$. We then have

$\displaystyle\lambda|I|$ $\displaystyle\leq\lambda
r|E^{\prime}(V^{\prime})|+\lambda(r-1)|E^{\prime}\setminus
E^{\prime}(V^{\prime})|$ $\displaystyle\leq k_{1}|V^{\prime}|+(\lambda
r-1)|E^{\prime}(V^{\prime})|+\lambda(r-1)|E^{\prime}\setminus
E(V^{\prime})|-l$ $\displaystyle\leq k_{1}|V^{\prime}|+(\lambda
r-1)|E^{\prime}|-l,$

Hence, we see that $\Gamma(H)$ is sparse.

Conversely, if $\Gamma(H)$ is sparse, then for any $V^{\prime}$, and
$E^{\prime}=E(V^{\prime})$, we have:

$\lambda|I^{\prime}|\leq k_{1}|V^{\prime}|+(\lambda r-1)|E^{\prime}|-l,$

and thus

$|E(V^{\prime})|\leq k_{1}|V^{\prime}|-l,$

which proves sparsity of $H$.

Finally, to finish the proof, we note that

$|E|=k|V|-l$

if and only if

$\lambda|I|=k|V|+(\lambda r-1)|E|-l,$

which shows the claim about tightness. ∎

If we wish to apply the pebble game, do notice that the condition
$k_{1}+(\lambda r-1)-\lambda\geq l$, forces us to increase $\lambda$ in order
to check sparsity and tightness. Furthermore, we find that if $\lambda=1$, we
are constrained to the case where $k_{1}+r-2\geq l$, so we can only find tight
substructures in this range.

We remark that our algorithm still works outside of the range $l>2k_{1}$ for
graphs, which is outside of the range stated in [4]. However, in this range
the graphs corresponding to sparse incidence geometries are not very
interesting in the sense that they will have at most one vertex in an edge.

######  Remark 10.

The algorithm for multigraphs in [4] is a particular case of the hypergraph
algorithm in [7]. We now show that there is a strong analogy between our
algorithm and that of [7], and therefore also that of [4].
Suppose that we are given a $r$-uniform hypergraph $H$, and we look at the
incidence geometry $\Gamma(H)$ as in Theorem 9. If we want to check
$(k_{1},l)$ sparsity of $H$, we check $(\lambda,k_{1},\lambda r-1,l)$-sparsity
of $\Gamma(H)$. Let $e=\\{v_{1},\cdots v_{r}\\}$ be an edge in $H$, and let
$x_{e}$ be its associated node in the incidence graph. If every incidence to
this edge is accepted, because of the invariant 1 in Lemma 2 we see that:

$\textup{out}(x_{e})+\textup{peb}(x_{e})=\lambda r-1.$

After reorienting edges, we may assume that $\textup{peb}(x_{e})=0$, and there
are $\lambda r-1$ edges pointing out of $x_{e}$. Since there are $\lambda r$
edges of $I_{\lambda}$ adjacent to $x_{e}$, we see that there is one edge
pointing into $x_{e}$. Such an orientation on the set of incidences to $x_{e}$
is the same thing as having an orientation on the edge as in the hypergraph
pebble game of [7]. For the hypergraph pebble game, whenever an edge is
accepted into the pebble, a tail of the edge is chosen, and one can move a
pebble from the tail to other vertices in the edge. In the incidence graph, we
can move pebbles in the same way.

#### Acknowledgements

This work has been supported by the Knut and Alice Wallenberg Foundation Grant
2020.0001 and 2020.0007.

## References

  * [1] Harold N. Gabow and Herbert H. Westermann.  Forests, frames, and games: algorithms for matroid sums and applications.  Algorithmica, 7(5-6):465–497, 1992.
  * [2] Donald J. Jacobs and Bruce Hendrickson.  An algorithm for two-dimensional rigidity percolation: the pebble game.  J. Comput. Phys., 137(2):346–365, 1997.
  * [3] G. Laman.  On graphs and rigidity of plane skeletal structures.  J. Engrg. Math., 4:331–340, 1970.
  * [4] Audrey Lee and Ileana Streinu.  Pebble game algorithms and sparse graphs.  Discrete Mathematics, 308(8):1425–1437, 2008.  Third European Conference on Combinatorics.
  * [5] H. Pollaczek-Geiringer.  Über die gliederung ebener fachwerke.  ZAMM - Journal of Applied Mathematics and Mechanics / Zeitschrift für Angewandte Mathematik und Mechanik, 7(1):58–72, 1927.
  * [6] Klara Stokes and Joannes Vermant.  Structural rigidity and flexibility using graphs of groups.  https://arxiv.org/abs/2305.07588, 2023.
  * [7] Ileana Streinu and Louis Theran.  Sparse hypergraphs and pebble game algorithms.  European Journal of Combinatorics, 30(8):1944–1964, 2009.  Combinatorial Geometries and Applications: Oriented Matroids and Matroids.
  * [8] Walter Whiteley.  A matroid on hypergraphs, with applications in scene analysis and geometry.  Discrete Comput. Geom., 4(1):75–95, 1989.
  * [9] Walter Whiteley.  Some matroids from discrete applied geometry.  In Matroid theory (Seattle, WA, 1995), volume 197 of Contemp. Math., pages 171–311. Amer. Math. Soc., Providence, RI, 1996.