# Abstract 3-Rigidity and Bivariate $C_{2}^{1}$-Splines II: Combinatorial
Characterization

Katie Clinch Department of Mathematical Informatics, Graduate School of
Information Science and Technology, University of Tokyo, Japan. Current
address: Department of Electrical and Electronic Engineering, University of
Melbourne, Parkville, Victoria, 3010, Australia. email:
<EMAIL_ADDRESS>Bill Jackson School of Mathematical Sciences,
Queen Mary University of London, Mile End Road, London E1 4NS, England. email:
<EMAIL_ADDRESS>and Shin-ichi Tanigawa Department of Mathematical
Informatics, Graduate School of Information Science and Technology, University
of Tokyo, 7-3-1 Hongo, Bunkyo-ku, 113-8656, Tokyo Japan. email:
<EMAIL_ADDRESS>
(16 April 2021)

###### Abstract

We showed in the first paper of this series that the generic
$C_{2}^{1}$-cofactor matroid is the unique maximal abstract $3$-rigidity
matroid. In this paper we obtain a combinatorial characterization of
independence in this matroid. This solves the cofactor counterpart of the
combinatorial characterization problem for the rigidity of generic
3-dimensional bar-joint frameworks. We use our characterization to verify that
the counterparts of conjectures of Dress (on the rank function) and Lovász and
Yemini (which suggested a sufficient connectivity condition for rigidity) hold
for the $C_{2}^{1}$-cofactor matroid.

Keywords: graph rigidity, rigidity matroid, bivariate spline, cofactor
matroid, matroid erection, free elevation

††MSC 2010 classification : primary 52C25; secondary 05B35

##  1 Introduction

We will consider a $d$-dimensional (bar-joint) framework, which is a pair
consisting of a finite simple graph $G=(V,E)$ and a map
$p:V\rightarrow\mathbb{R}^{d}$. It is rigid if every continuous motion of the
vertices of $G$ in $\mathbb{R}^{d}$ which preserves the lengths of the edges,
results in a framework which is congruent to $(G,p)$. The framework has the
stronger property of being infinitesimally rigid if every length preserving
infinitesimal motion of the vertices is induced by an infinitesimal isometry
of $\mathbb{R}^{d}$. Maxwell [34] gave the following necessary condition for
infinitesimal rigidity: if $(G,p)$ is an infinitesimally rigid $d$-dimensional
framework with at least $d$ vertices, then $G$ has a spanning subgraph $H$
such that

  * •

$|E(H)|=d|V(H)|-{d+1\choose 2}$, and

  * •

$|E(H^{\prime})|\leq d|V(H^{\prime})|-{d+1\choose 2}$ for any subgraph
$H^{\prime}$ of $H$ with $|V(H^{\prime})|\geq d$.

It is straightforward to check that this condition is also sufficient when
$d=1$. A celebrated result of Pollaczek-Geiringer [39], rediscovered by Laman
[29], shows that Maxwell’s condition is also sufficient when $d=2$ if $p$ is
generic, i.e., the set of coordinates in $p$ is algebraically independent over
the rational field. When $d\geq 3$, Maxwell’s condition is no longer
sufficient to imply infinitesimal rigidity, even for generic frameworks, and
finding a combinatorial characterization for generic 3-dimensional rigidity
has been the central open problem in graph rigidity for many years, see for
example [21, 50]. Maxwell’s condition is known to be sufficient for generic
3-dimensional rigidity of some restricted classes such as triangulations of
closed 2-surfaces (with/without holes) [11, 12, 18, 17], graphs with no
$K_{5}$-minor [35], and squares of graphs [27]. We refer the reader to [40]
for a recent survey on graph rigidity.

Gluck [19] observed that the properties of rigidity and infinitesimal rigidity
coincide when $p$ is generic, and are completely determined by the graph $G$
and the dimension $d$. This fact motivated Asimow and Roth [1] to define a
graph $G$ as being rigid in $\mathbb{R}^{d}$ if some, or equivalently every,
generic $d$-dimensional framework $(G,p)$ is infinitesimally rigid. The
rigidity of a graph $G$ is determined by the rank of the generic
$d$-dimensional rigidity matroid ${\cal R}_{d}(G)$ of $G$ and exploring the
combinatorial structure of ${\cal R}_{d}(G)$ using machinery from matroid
theory is a common approach to attack problems in rigidity, see for example
[45, 21, 50]. We will build on this matroidal approach to obtain a
combinatorial characterization of a matroid from the theory of bivariate
splines which is conjectured to be equal to the generic 3-dimensional rigidity
matroid.

Graver [20] defined the class of abstract $d$-rigidity matroids on the edge
set of the complete graph $K_{n}$ using two fundamental properties of rigidity
in $d$-space. The generic $d$-dimensional rigidity matroid ${\cal
R}_{d}(K_{n})$ is an example of an abstract $d$-rigidity matroid, and Graver
[20] conjectured that, for all $d\geq 1$, ${\cal R}_{d}(K_{n})$ is the unique
maximal matroid in the set of all abstract $d$-rigidity matroids on $E(K_{n})$
with respect to the weak order of matroids. Graver showed that his conjecture
is true for $d=1,2$ but it was subsequently shown to be false for $d\geq 4$.
It remains open for $d=3$. (See Section 4 of this paper or [6] for a more
detailed discussion.)

Whiteley [50] found a new candidate for a unique maximal abstract $d$-rigidity
matroid from approximation theory by taking the row matroid of the
$C^{s-1}_{s}$-cofactor matrix of a(ny) generic 2-dimensional framework
$(K_{n},p)$. This is the $|E(K_{n})|\times(s+1)n$ matrix in which sets of
consecutive $(s+1)$ columns are associated with vertices, rows are associated
with edges, and the row associated to the edge $e=v_{i}v_{j}$ with $i<j$ is

$\hbox{}\vbox{\kern 0.86108pt\hbox{$\kern 0.0pt\kern
2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{i}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle v_{j}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\\\e=v_{i}v_{j}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\cdots 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle D_{ij}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0\cdots 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle-D_{ij}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\cdots 0$\hfil\kern 5.0pt\crcr}}}}\right]$}},$

where
$D_{i,j}=((x_{i}-x_{j})^{s},(x_{i}-x_{j})^{s-1}(y_{i}-y_{j}),\dots,(x_{i}-x_{j})(y_{i}-y_{j})^{s-1},(y_{i}-y_{j})^{s})\in\mathbb{R}^{s+1}$
when $p(v_{i})=(x_{i},y_{i})\in\mathbb{R}^{2}$ for each $v_{i}\in V(K_{n})$.
We refer to the row matroid of this matrix as the $C_{s}^{s-1}$-cofactor
matroid and denote it by ${\cal C}_{s}^{s-1}(K_{n})$. Whiteley [50] showed
that ${\cal C}_{d-1}^{d-2}(K_{n})$ is an abstract $d$-rigidity matroid, that
${\cal C}_{d-1}^{d-2}(K_{n})={\cal R}_{d}(K_{n})$ when $d=1,2$ and that ${\cal
C}_{d-1}^{d-2}(K_{n})\not\preceq{\cal R}_{d}(K_{n})$ when $d\geq 4$. He
conjectured further that ${\cal C}_{d-1}^{d-2}(K_{n})$ is the unique maximal
abstract $d$-rigidity matroid on $E(K_{n})$ for all $d\geq 1$. Note that
Whiteley’s conjecture holds when $d=1,2$ by the above mentioned result of
Graver. In our first paper [6] in this series, we verified Whiteley’s
conjecture for $d=3$ by showing that ${\cal C}_{2}^{1}(K_{n})$ is the unique
maximal abstract $3$-rigidity matroid (see Theorem 4.5 below).

Because of the strong similarity between rigidity matroids and cofactor
matroids, Whiteley [48, page 55] also remarked that finding a combinatorial
characterization of independence in the generic $C_{2}^{1}$-cofactor matroid
may be as challenging as the corresponding problem for the generic
$3$-dimensional rigidity matroid, and went on to conjecture that these two
matroids are equal in [50, Conjecture 10.3.2]. This paper solves the
characterization problem for the generic $C_{2}^{1}$-cofactor matroid (and
equivalently for the maximal abstract 3-rigidity matroid) by giving a co-NP
type characterization for independence (we will see below that an NP type
characterization follows immediately from the Schwartz-Zippel Lemma). We then
use our characterization to verify the cofactor counterpart of two long-
standing conjectures on the generic 3-dimensional rigidity matroid.

Dress gave two conjectures on the rank of the 3-dimensional generic rigidity
matroid in the 1980’s. The first conjecture, which appeared in [14], suggested
a co-NP type characterization for independence, but was subsequently disproved
by Jackson and Jordán [23]. The second conjecture, which was given at a
rigidity conference in Montreal in 1987, see [9, 21, 44], describes the rank
function in terms of the ‘rigid clusters’ of the underlying graph and still
remains open. It would give a useful structural property of the rigidity
matroid but would not obviously give rise to a co-NP type characterization. We
prove in Theorem 6.3 below that the corresponding conjecture holds for the
generic $C_{2}^{1}$-cofactor matroid. We also show that the modified versions
of Dress’s first conjecture given in [24, 22] hold for this matroid.

Lovász and Yemini [32] proved that 6-connectivity is sufficient to imply that
graphs are generically rigid in 2-dimensional space, and conjectured that
12-connectivity is sufficient for rigidity in 3-space. We prove in Theorem 7.2
that the corresponding statement is true for the generic $C_{2}^{1}$-cofactor
matroid

The main technical innovation in our work is to find a new kind of rank
formula for a matroid. One of the major difficulties in attacking the
3-dimensional rigidity problem is the lack of understanding of how to
construct a matroid based on Maxwell’s condition when $d\geq 3$. It is well-
known that, for $d=1,2$, the edge sets satisfying Maxwell’s condition form an
independent set family of a matroid. Lovász and Yemini [32] showed that the
structure of this matroid can be completely understood using the theory of
intersecting submodular functions. Currently, this theory does not seem to
apply when $d\geq 3$. In particular, it is not clear how to use this theory to
obtain a polynomial algorithm to evaluate our formula for the rank function of
the $C_{2}^{1}$-cofactor matroid.

Our rank formula was inspired by a matroid construction due to Crapo [8]. He
defined an erection of a matroid as an inverse operation to truncation. He
showed that the set of all erections of a matroid $M$ forms a lattice under
the weak order for matroids, and defined the maximum matroid in this lattice
to be the free erection of $M$. A sequence of (free) erections starting from
$M$ always terminates after a finite number of steps and we refer to a matroid
obtained by such a sequence as a (free) elevation of $M$. Examples due to
Brylawski [4, Figure 7.9] and the second two authors [26, Theorem 5.4] show
that the free elevation may not be the unique maximal element in the poset of
all elevations of $M$, but we show in Lemma 3.1 that it is always a maximal
element. We then obtain an upper bound on the rank function of all elevations
of $M$ in terms of the non-spanning circuits of $M$ in Lemma 3.3. Conjecture
3.4 states that this upper bound is tight if and only if the free elevation of
$M$ is the unique maximal element in the poset of all elevations of $M$. Our
main result, Theorem 5.7, shows that the upper bound is tight for the generic
$C_{2}^{1}$-cofactor matroid and verifies a special case of this conjecture.

Our results are relevant to another long-standing open problem, the polynomial
identity testing problem for symbolic determinants (or the Edmonds problem).
In this problem, we are given a matrix $A$ with entries in
$\mathbb{Q}[x_{1},\dots,x_{n}]$ and we are asked to decide whether the rank of
$A$ over $\mathbb{Q}(x_{1},\dots,x_{n})$ is at least a given number. The
Schwartz-Zippel Lemma [41, 51] implies that this problem admits a randomized
polynomial time algorithm, but developing a deterministic polynomial time
algorithm is a major open problem in theoretical computer science. The same
lemma also tells us that the problem is in the class NP, but it is not known
whether it is in co-NP. One approach, pioneered by Tutte [47], Edmonds [15]
and Lovász [31], is to give a good characterization for the rank of $A$ by
showing it is the minimum value for a certain combinatorial optimization
problem. Our result offers a new example of this approach. Indeed Lovász [31,
Section 5] states that the generic 3-dimensional rigidity problem is an
important special case of the polynomial identity testing problem. Our
technique solves the closely related problem for generic $C_{2}^{1}$-cofactor
matrices.

The research direction of this paper was motivated by the fundamental papers
of Graver [20] and Whiteley [50], and more recently by a talk given by Meera
Sitharam at a BIRS workshop in 2015 on her joint work with Jialong Cheng and
Andrew Vince, see [42], in which she described a recursive procedure for
constructing the closure operator in a maximal matroid on the edge set of a
complete graph in which every $K_{5}$-subgraph is a circuit.

Our paper is structured as follows. In Section 2 we review the theory of
matroid erections, using a primal approach instead of the traditional dual
approach. We introduce the free elevation of a matroid $M$ in Section 3 and
prove two key results: Lemma 3.3 gives an upper bound on the rank of any
elevation of $M$; Lemma 3.8 shows that if every element of $M$ is contained in
a non-spanning circuit of $M$ then every cyclic flat of the free elevation of
$M$ is the union of non-spanning circuits of $M$. We describe the family of
abstract $d$-rigidity matroids and $C_{d-1}^{d-2}$-cofactor matroids in
Section 4. We obtain our main result, Theorem 5.7, which gives a polynomially
verifiable characterization of the rank function of the maximal abstract
3-rigidity matroid ${\cal C}_{2}^{1}$ in Section 5. We give two alternative
expressions for the rank function of ${\cal C}_{2}^{1}$ in Section 6 and use
these to obtain sufficient connectivity conditions for the ${\cal
C}_{2}^{1}$-matroid of a graph to have maximum possible rank in Section 7. We
close with some open problems and remarks in Section 8.

##  2 Matroid erections

Matroid erection, introduced by Crapo [8], is a key tool in this paper. We
give a detailed exposition of matroid erection in this preliminary section for
the benefit of readers who are unfamiliar with the topic. For an introduction
to the concepts below, see [38].

Given a matroid $M$, we use $E_{M}$ to denote its ground set, ${\rm cl}_{M}$
to denote its closure operator, and $r_{M}$ to denote its rank function. We
will often suppress the subscript $M$ when it is obvious which matroid we are
referring to. For $X\subseteq E$, $M|_{X}$ denotes the restriction of $M$ to
$X$ and $M-X$ denotes $M|_{E{\setminus}X}$. The contracted matroid $M/X$ is
the matroid on $E{\setminus}X$ in which a set $F\subseteq E{\setminus}X$ is
independent if and only if $F\cup X$ is independent in $M$. When $X=\\{e\\}$,
we simplify the notation for matroid deletion and contraction to $M-e$ and
$M/e$, respectively.

A set $X\subseteq E$ is said to be spanning if ${\rm cl}_{M}(X)=E$ and to be a
flat if ${\rm cl}_{M}(X)=X$. A hyperplane of $M$ is a flat $F$ with
$r(F)=r(E)-1$. The poset of all flats ordered by set inclusion forms a
geometric lattice by setting the meet and join of two flats $F_{1}$ and
$F_{2}$ to be $F_{1}\cap F_{2}$, and $\operatorname{cl}_{M}(F_{1}\cup F_{2})$,
respectively. A pair $X,Y$ of subsets of $E$ is said to be modular if
$r_{M}(X)+r_{M}(Y)=r_{M}(X\cap Y)+r_{M}(X\cup Y)$. The dual of $M$ is denoted
by $M^{*}$. The weak order on a set of all matroids with the same ground set
$E$ is the partial order in which $M_{1}\preceq M_{2}$ if every independent
set of $M_{1}$ is independent in $M_{2}$.

#### One-point extensions and elementary quotients.

Given two matroids $M$ and $P$, we say that $P$ is a one-point extension of
$M$ if $M=P-p$ for some $p\in E_{P}$. The structure of one-point extensions
can be understood by introducing the concept of modular cuts. A family ${\cal
F}$ of flats of $M$ is said to be a modular cut of $M$ if it is up-closed in
the lattice of flats and $X\cap Y\in{\cal F}$ for all modular pairs $X,Y$ in
${\cal F}$. Given a modular cut ${\cal F}$ of $M$, we can define a matroid $P$
on $E_{M}+p$ as follows. For all $X\subseteq E_{M}$ we put
$r_{P}(X)=r_{M}(X)$, and

$r_{P}(X+p)=\begin{cases}r_{M}(X)&\mbox{if ${\rm cl}_{M}(X)\in{\cal F}$},\\\
r_{M}(X)+1&\mbox{if ${\rm cl}_{M}(X)\not\in{\cal F}$.}\end{cases}$

One can easily check that $r_{P}$ is indeed a matroid rank function. We will
denote the one-point extension of $M$ with respect to the modular cut $\cal F$
by $M+_{\cal F}p$. Every one-point extension of $M$ can be uniquely
constructed in this manner. More precisely, the map ${\cal F}\mapsto M+_{\cal
F}p$ is a bijection between the set of modular cuts of $M$ and the set of one-
point extensions of $M$. (See [38] for more details.)

Given a modular cut $\cal F$ of $M$, the matroid $N=(M+_{\cal F}p)/p$, is
called the elementary quotient of $M$ with respect to ${\cal F}$. Observe that
$E_{M}=E_{N}=:E$ and, for all $X\subseteq E$,

$r_{N}(X)=\begin{cases}r_{M}(X)-1&\mbox{if ${\rm cl}_{M}(X)\in{\cal F}$},\\\
r_{M}(X)&\mbox{if ${\rm cl}_{M}(X)\not\in{\cal F}$.}\end{cases}$ (1)

#### Elementary lifts.

Given two matroids $M$ and $N$, we say that $N$ is an elementary lift of $M$
if $M$ is an elementary quotient of $N$ i.e. $N=P-p$ and $M=P/p$ for some
$1$-point extension $P$ of $N$. In this case we can use matroid duality to
deduce that $M^{*}=P^{*}-p$ and $N^{*}=P^{*}/p$. Hence $N$ is an elementary
lift of $M$ if and only if $N^{*}$ is an elementary quotient of $M^{*}$. The
correspondence between elementary quotients and modular cuts now gives us a
bijection between the set of elementary lifts of $M$ and the set of modular
cuts of $M^{*}$. It will be helpful to describe this bijection in terms of the
primal matroid $M$ rather than its dual $M^{*}$.

A set $X\subset E$ is said to be cyclic in $M$ if it is the union of circuits
of $M$. For our purposes, it will make sense to consider the empty set as a
cyclic set. Let ${\rm cyc}_{N}(X)$ be the largest cyclic subset of $X$, i.e.,
the set obtained from $X$ by removing the coloops in $M|_{X}$. The poset of
all cyclic sets in $M$ ordered by set inclusion forms a lattice by setting the
join and the meet of $C_{1}$ and $C_{2}$ to be $C_{1}\cup C_{2}$ and ${\rm
cyc}_{M}(C_{1}\cap C_{2})$, respectively.

We say that a family ${\cal C}$ of cyclic subsets of $E$ is a modular cyclic
family if ${\cal C}$ is down-closed (in the lattice of cyclic sets) and, for
every modular pair $X,Y$ in $\cal C$, $X\cup Y\in{\cal C}$. Note that since
modular cyclic families are down-closed and we consider $\emptyset$ to be
cyclic, we have $\emptyset\in{\cal C}$ for every modular cyclic family $\cal
C$.

The following result gives a bijection between the modular cuts of $M^{*}$ and
the modular cyclic families in $M$.

######  Proposition 2.1.

Let ${\cal C}$ be a family of subsets of $E$. Then ${\cal C}$ is a modular
cyclic family in $M$ if and only if $\\{E\setminus C:C\in{\cal C}\\}$ is a
modular cut in $M^{*}$.

###### Proof.

Recall that $X$ is a circuit in $M$ if and only if $E\setminus X$ is a
hyperplane in $M^{*}$. Since every flat is the intersection of hyperplanes,
$X$ is cyclic in $M$ if and only if $E\setminus X$ is a flat in $M^{*}$. In
addition, a direct computation shows that $X,Y$ is a modular pair in $M$ if
and only if $E\setminus X,E\setminus Y$ is a modular pair in $M^{*}$. ∎

Proposition 2.1 and the preceding discussion give a bijection between the set
of elementary lifts of $M$ and the set of modular cyclic families in $M$, and
allow us to define $N$ to be the elementary lift of $M$ with respect to the
modular cyclic family $\cal C$ of $M$ if and only if $N^{*}$ is the elementary
quotient of $M^{*}$ with respect to the modular cut $\\{E\setminus C:C\in{\cal
C}\\}$ of $M^{*}$. Moreover, we can use (1), Proposition 2.1, and the fact
that ${\rm cyc}_{M}(X)=E\setminus{\rm cl}_{M^{*}}(E\setminus X)$ for
$X\subseteq E$ to deduce that the elementary lift $N$ of $M$ with respect to
the modular cyclic family ${\cal C}$ in $M$ has the following rank function:

$r_{N}(X)=\begin{cases}r_{M}(X)&\mbox{if ${\rm cyc}_{M}(X)\in{\cal C}$}\\\
r_{M}(X)+1&\mbox{if ${\rm cyc}_{M}(X)\not\in{\cal
C}$}\end{cases}\qquad(X\subseteq E(N)).$ (2)

This formula implies that the above mentioned bijection is an (order
reversing) isomorphism between the lattice of elementary lifts of $M$, ordered
by the weak order of matroids, and the lattice of modular cyclic families in
$M$, ordered by inclusion. (The meet and join of two cyclic families in this
lattice are given by the intersection of the two families, and the smallest
modular cyclic family containing their union, respectively.)

#### Matroid erections.

Let $M$ and $N$ be matroids on the same ground set $E$ with $r_{M}(E)=k\leq
r_{N}(E)$. We say that $M$ is the truncation of $N$ to rank $k$ if
$r_{M}(X)=\min\\{r_{N}(X),k\\}$ for all $X\subseteq E(M)$. If $k=r_{N}(E)-1$,
$M$ is simply called the truncation of $N$. The inverse operation to
truncation was used by Crapo [8] and Knuth [28] to recursively generate all
the matroids on a given ground set from the rank zero matroid on this set.
Following Crapo, we say that $N$ is an erection of $M$ if $M$ is the
truncation of $N$. For a technical reason, $M$ is also considered to be an
erection of itself, and is referred to as the trivial erection.

Crapo [8] showed that the set of all erections of a matroid $M$ forms a
lattice under the weak order, where the bottom element corresponds to the
trivial erection. The top element in this lattice is called the free erection
of $M$. Las Vergnas [30] and Nguyen [36] independently gave a characterization
of the free erection of $M$. Duke [13] subsequently gave a clearer exposition
in terms of one-point extensions of the dual matroid $M^{*}$. We shall
describe Duke’s approach in terms of the primal matroid $M$.

Observe first that, if $M$ is a truncation of $N$, then (1) implies that $M$
is the elementary quotient of $N$ with respect to the modular cut ${\cal
F}=\\{E\\}$. This in turn implies that $N$ is a special kind of elementary
lift of $M$. Our next result characterizes which elementary lifts are
erections.

######  Theorem 2.2.

(A primal version of [13, Lemma 3.1].) Let ${\cal C}$ be a modular cyclic
family in a matroid $M$ and $N$ be the elementary lift of $M$ with respect to
${\cal C}$. Then $N$ is an erection of $M$ if and only if ${\cal C}$ contains
all cyclic flats of $M$, with the possible exception of $E$.

###### Proof.

We first assume that $N$ is an erection of $M$. Then $M$ is the truncation of
$N$. Let $C$ be a cyclic flat of $M$ with $C\not\in\cal C$. By (2) we have
$r_{N}(C)=r_{M}(C)+1$. Since $M$ is the truncation of $N$ this gives
$r_{M}(C)=r_{M}(E)$. Since $C$ is a flat of $M$, this implies that $C=E$.

We next assume that ${\cal C}$ contains all cyclic flats of $M$, with the
possible exception of $E$. Suppose $F$ is a flat of $M$ with
$r_{M}(F)<r_{M}(E)$. Then ${\rm cyc}_{M}(F)$ is a cyclic flat so ${\rm
cyc}_{M}(F)\in{\cal C}$. By (2), $r_{N}(F)=r_{M}(F)$. It follows that all sets
$X$ with $r_{N}(X)=r_{M}(X)+1$ have $r_{M}(X)=r_{M}(E)$. Hence $M$ is the
truncation of $N$. ∎

We saw above that the lattice of all elementary lifts of $M$ is isomorphic to
the lattice of modular cyclic families of $M$. Theorem 2.2 enables us to
determine the restriction of this isomorphism to the lattice of erections of
$M$. Given a family ${\cal C}_{0}$ of cyclic sets in $M$, we define its
modular cyclic closure as:

$\overline{{\cal C}}_{0}=\bigcap\\{{\cal C}:{\cal C}\text{ is a modular cyclic
family of $M$ with }{\cal C}_{0}\subseteq{\cal C}\\}.$

Let ${\cal CF}_{M}$ be the family of all non-spanning cyclic flats of $M$, and
${\cal C}_{M}$ be the family of all cyclic sets in $M$. Then Theorem 2.2
implies that the sublattice $[\overline{{\cal CF}}_{M},{\cal C}_{M}]$ in the
lattice of modular cyclic families corresponds to the lattice of erections of
$M$, where $\overline{{\cal CF}}_{M}$ corresponds to the free erection and
${\cal C}_{M}$ corresponds to the trivial erection. In particular we have:

######  Corollary 2.3.

A matroid $M$ has no non-trivial erection if and only if $\overline{{\cal
CF}}_{M}={\cal C}_{M}$, i.e., the only modular cyclic family of $M$ containing
${\cal CF}_{M}$ is the family of all cyclic sets in $M$.

By (2) we also have the following explicit rank formula for the free erection
of $M$.

######  Corollary 2.4.

Let $N$ be the free erection of $M$. Then

$r_{N}(X)=\begin{cases}r_{M}(X)&\mbox{ if ${\rm cyc}_{M}(X)\in\overline{{\cal
CF}}_{M}$}\\\ r_{M}(X)+1&\mbox{ if ${\rm cyc}_{M}(X)\not\in\overline{{\cal
CF}}_{M}$}\end{cases}\qquad(X\subseteq E).$ (3)

For a set $S$ of elements in a lattice, let $S^{\downarrow}$ be the lower
closure of $S$. In order to use Corollary 2.4 to determine the rank function
for the free erection of $M$, we need to be able to compute $\overline{{\cal
CF}}_{M}$ from ${\cal CF}_{M}$. An algorithm for constructing the smallest
modular cut containing a given set of flats is known (see, e.g., [13, page
367]). Dualizing this algorithm, we may use the following procedure to compute
$\overline{{\cal CF}}_{M}$ from ${\cal CF}_{M}$.

Algorithm 1

$\bullet$ Initialize ${\cal S}_{0}:={\cal CF}_{M}$.

$\bullet$ Repeatedly construct ${\cal S}_{i}$ from ${\cal S}_{i-1}$ by [-3mm]

${\cal S}_{i}:={\cal S}_{i-1}\cup\\{X\cup Y\mid X,Y\in{\cal
S}_{i-1}^{\downarrow}:\text{ $X$ and $Y$ form a modular pair in $M$}\\}.$

[-9mm]

$\bullet$ If ${\cal S}_{i}={\cal S}_{i-1}$, then ${\cal S}_{i}^{\downarrow}$
is $\overline{{\cal CF}}_{M}$.

Let $M$ be a matroid on a finite ground set, and let
$M=M_{0},M_{1},M_{2},\dots,M_{k}$ be a sequence of matroids starting from $M$
such that $M_{i}$ is a non-trivial erection of $M_{i-1}$ for all $1\leq i\leq
k$ and $M_{k}$ has no non-trivial erection. Since each non-trivial erection
increases the rank by one, and the rank is bounded above by $|E|$, the length
of any such sequence is bounded. We will refer to the last matroid $M_{k}$ in
such a sequence as an elevation of $M$. The free elevation of $M$ is the
elevation we obtain from $M$ by taking a maximal sequence of non-trivial free
erections.

##  3 Matroids generated by a set of circuits

Let ${\cal C}$ be a family of subsets of a finite set $E$. A matroid $M$ on
$E$ is said to be a ${\cal C}$-matroid if every member of ${\cal C}$ is a
circuit in $M$. We will be primarily concerned with matroids constructed by a
sequence of free erections from a given matroid. More specifically, let
$M_{0}$ be a matroid on a finite set $E$ and ${\cal C}_{0}$ be the family of
non-spanning circuits in $M_{0}$. Then every matroid obtained from $M_{0}$ by
a sequence of erections is a ${\cal C}_{0}$-matroid and, in particular, the
free elevation of $M_{0}$ is a ${\cal C}_{0}$-matroid. We will derive some
properties of the free elevation of $M_{0}$, which will be crucial tools in
the proof of our main theorem.

###  3.1 Maximality in the weak order

Let ${\cal C}$ be a family of subsets of a finite set $E$. We say that a
matroid $M$ is a maximal ${\cal C}$-matroid if it is maximal in the weak order
on the family of all ${\cal C}$-matroids on $E$.

######  Lemma 3.1.

Let $M_{0}$ be a matroid on $E$ and ${\cal C}_{0}$ be the family of all non-
spanning circuits in $M_{0}$. Then the free elevation of $M_{0}$ is a maximal
${\cal C}_{0}$-matroid on $E$.

###### Proof.

Let $k$ be the rank of $M_{0}$ and $M$ be the free elevation of $M_{0}$.
Suppose for a contradiction that $M\prec N$ for some ${\cal C}_{0}$-matroid
$N$ on $E$. We first prove:

######  Claim 3.2.

The truncation of $N$ to rank $k$ is equal to $M_{0}$.

###### Proof.

Let $N_{0}$ be the truncation of $N$ to rank $k$. The facts that $N$ is a
${\cal C}_{0}$-matroid and $M\prec N$ imply that ${\cal C}_{0}$ is the set of
non-spanning circuits of $N_{0}$. This in turn implies that a set $X\subseteq
E$ with $|X|=k$ is dependent in $M_{0}$ if and only if it is dependent in
$N_{0}$, and hence that $M_{0}$ and $N_{0}$ have the same set of bases. ∎

Claim 3.2 implies that $M_{0}$ can be obtained from $N$ by a sequence of
truncations, and hence that $N$ can be obtained from $M_{0}$ by a sequence of
erections, say $M_{0}=N_{0},N_{1},\dots,N_{\ell}=N$. Let
$M_{0},M_{1},\dots,M_{m}=M$ be the sequence of free erections which construct
$M$ from $M_{0}$. Since $N\neq M$, we can choose a smallest possible $i$ such
that $N_{i}\neq M_{i}$. Then $i\geq 1$, $N_{j}=M_{j}$ for all $0\leq j\leq
i-1$ and $N_{i}$ is not the free erection of $M_{i-1}$. Since $M_{i}$ is the
maximum element in the lattice of all erections of $M_{i-1}$, there is a set
$X\subseteq E$ that is dependent in $N_{i}$ and independent in $M_{i}$. The
set $X$ remains independent in $M$ but will be dependent in $N$ as
$\operatorname{rank}_{N_{i}}(X)<\operatorname{rank}_{M_{i}}(X)\leq\operatorname{rank}(M_{i})=\operatorname{rank}(N_{i})$
and $N_{i}$ is obtained from $N$ by truncations. This contradicts the
hypothesis that $M\prec N$. ∎

Since the free erection of a matroid $M_{0}$ is the unique maximal element in
the lattice of all erections of $M_{0}$, it is tempting to guess that the free
elevation of $M_{0}$ will be the unique maximal element in the poset of all
matroids we can obtain from $M_{0}$ by taking sequences of erections. Sadly
this is not true in general – counterexamples are given in [4, Figure 7.9] and
[26, Theorem 5.4].

###  3.2 Rank upper bound

We next obtain an upper bound of the rank of any ${\cal C}$-matroid. Given a
sequence of circuits $(C_{1},\dots,C_{k})$ in a matroid $M$, we put $C_{\leq
i}=\bigcup_{j=1}^{i}C_{j}$ for all $1\leq i\leq k$ and $C_{\leq 0}=\emptyset$.
The sequence $(C_{1},\dots,C_{k})$ is said to be proper if $C_{i}\not\subseteq
C_{\leq i-1}$ for all $2\leq i\leq k$, and it is said to be a ${\cal
C}$-sequence (for a family of circuits ${\cal C}$) if each $C_{i}$ belong to
${\cal C}$. The following lemma is fundamental to our characterization of the
rank function of the maximal abstract 3-rigidity matroid.

######  Lemma 3.3.

Let $M$ be a matroid on a finite set $E$ with rank function $r$ and ${\cal C}$
be a family of circuits in $M$. Then for any $X\subseteq E$ and any proper
${\cal C}$-sequence $(C_{1},\dots,C_{t})$,

$r(X)\leq|X\cup C_{\leq t}|-t.$ (4)

Furthermore, if equality holds in (4), then $C_{\leq
t}\subseteq\operatorname{cl}(X)$ and each $e\in X{\setminus}C_{\leq t}$ is a
coloop of $M|_{X}$.

###### Proof.

We first use induction on $j$ to show that, for all $1\leq j\leq t$,

$r(C_{\leq j})\leq\sum_{i=1}^{j}(|C_{i}\setminus C_{\leq i-1}|-1).$ (5)

The base case when $j=1$ holds since $C_{1}$ is a circuit.

Suppose $j>1$. As the sequence is proper, $C_{j}\cap C_{\leq j-1}$ is a proper
subset of $C_{j}$, which is independent. Hence its rank is equal to its
cardinality. Thus

$\displaystyle r(C_{\leq j})$ $\displaystyle\leq r(C_{\leq
j-1})+r(C_{j})-r(C_{\leq j-1}\cap C_{j})\qquad(\text{by submodularity})$
$\displaystyle=r(C_{\leq j-1})+|C_{j}|-1-|C_{\leq j-1}\cap C_{j}|$
$\displaystyle\leq\sum_{i=1}^{j}(|C_{i}\setminus C_{\leq
i-1}|-1)\qquad(\text{by induction})$

and (5) holds.

Putting $j=t$ in (5) gives $r(C_{\leq t})\leq|C_{\leq t}|-t$. We can now use
submodularity and the monotonicity of $r$ to deduce that

$r(X)\leq r(X\setminus C_{\leq t})+r(C_{\leq t})\leq|X\setminus C_{\leq
t}|+|C_{\leq t}|-t=|X\cup C_{\leq t}|-t.$

This completes the proof of the first part of the lemma.

To prove the second part, we assume that $r(X)=|X\cup C_{\leq t}|-t$ for some
$X\subseteq E$ and some proper $\cal C$-sequence $(C_{1},\ldots,C_{t})$. If
$e\in C_{\leq t}$ then, by the first part of the lemma, $r(X+e)\leq|(X+e)\cup
C_{\leq t}|-t=|X\cup C_{\leq t}|-t=r(X)$, and hence
$e\in\operatorname{cl}(X)$. Similarly, if $e\in X\setminus C_{\leq t}$ then,
by the first part of the lemma, $r(X-e)\leq|(X-e)\cup C_{\leq t}|-t=|X\cup
C_{\leq t}|-t-1=r(X)-1$, and hence $e$ is a coloop of $M|_{X}$. ∎

Let $M_{0}$ be a matroid on $E$ and ${\cal C}_{0}$ be the family of non-
spanning circuits in $M_{0}$. Then, for any ${\cal C}_{0}$-matroid $M$ on $E$,
Lemma 3.3 implies that the function $f_{{\cal
C}_{0}}:2^{E}\rightarrow\mathbb{Z}$ defined by

$f_{{\cal C}_{0}}(X)=\min\\{|X\cup C_{\leq t}|-t:\text{$(C_{1},\dots,C_{t})$
is a proper ${\cal C}_{0}$-sequence in $M$}\\}\qquad(X\subseteq E)$

gives an upper-bound for the rank function of $M$. It follows that, if
$f_{{\cal C}_{0}}$ is the rank function of some matroid on $E$, then this
matroid will be the unique maximal ${\cal C}_{0}$-matroid and hence will be
the free elevation of $M_{0}$ by Lemma 3.1. Since the poset of all elevations
of $M_{0}$ may not have a unique maximal element, $f_{{\cal C}_{0}}$ is not
always a matroid rank function. We believe that $f_{{\cal C}_{0}}$ is a
matroid rank function whenever there is a unique maximal ${\cal
C}_{0}$-matroid on $E$.

######  Conjecture 3.4.

Let $M_{0}$ be a matroid on a finite set $E$ and let ${\cal C}_{0}$ be the
family of non-spanning circuits in $M_{0}$. Suppose that there is a unique
maximal ${\cal C}_{0}$-matroid on $E$. Then $f_{{\cal C}_{0}}$ is the rank
function of this maximal ${\cal C}_{0}$-matroid.

Our main result verifies Conjecture 3.4 when $M_{0}$ is the rank 10 matroid on
$E(K_{n})$ in which the set of non-spanning circuits ${\cal C}_{0}$ is the set
of copies of $K_{5}$ in $K_{n}$. (We already showed in [6] that the cofactor
matroid $\mathcal{C}^{1}_{2}(K_{n})$ is the unique maximal $K_{5}$-matroid on
$E(K_{n})$ and Theorem 5.7 below verifies that $f_{{\cal C}_{0}}$ is its rank
function.) The conjecture is verified for several other matroids on $E(K_{n})$
in [26].

###  3.3 A covering lemma

We will use the algorithm for constructing a free elevation given in Section 2
to show that every cyclic flat in the free elevation of a matroid $M_{0}$ can
be covered by the non-spanning circuits of $M_{0}$ (Lemma 3.8 below). This
will be a key tool in proving that Conjecture 3.4 holds for the maximal
$K_{5}$-matroid on $E(K_{n})$.

Recall that ${\cal CF}_{M}$ denotes the family of non-spanning cyclic flats in
a matroid $M$, and that $\overline{\cal CF}_{M}$ denotes its modular cyclic
closure. We will need the following characterization of the cyclic hyperplanes
in the free erection of $M$.

######  Lemma 3.5.

Suppose $M$ is a matroid on a finite set $E$, $N$ is the free erection of $M$,
and $N\neq M$. Let $Z\subseteq E$. Then $Z$ is a cyclic hyperplane in $N$ if
and only if $Z$ is a spanning set in $M$ and a maximal element in
$\overline{\cal CF}_{M}$.

###### Proof.

Suppose that $Z$ is spanning in $M$ and a maximal element in $\overline{\cal
CF}_{M}$. Then $Z$ is cyclic in both $M$ and $N$, and
$r_{M}(Z)=r_{N}(Z)=r_{N}(E)-1$ by (3). It remains to show that $Z$ is a flat
in $N$. To see this, choose a base $I$ of $M$ with $I\subseteq Z$. Then for
any $e\notin Z$, $I+e$ contains a circuit $C$ of $M$ with $e\in C$. As $Z\cup
C=Z+e$, $Z+e$ is cyclic in $M$, and the maximality of $Z$ in $\overline{\cal
CF}_{M}$ now gives $Z+e\notin\overline{\cal CF}_{M}$. Hence
$r_{N}(Z+e)>r_{N}(Z)$ for all $e\notin Z$, which means that $Z$ is a flat in
$N$.

Conversely, suppose that $Z$ is a cyclic hyperplane in $N$. Then $Z$ is a non-
spanning cyclic set in $N$ so $Z\in\overline{\cal CF}_{M}$. By the definition
of truncation, $Z$ is a spanning set in $M$. If $Z$ is not maximal in
$\overline{\cal CF}_{M}$, then there is a maximal set $Y\in\overline{\cal
CF}_{M}$ with $Z\subsetneq Y$. Then by the first part of the proof, $Y$ would
be a hyperplane in $N$, which is a contradiction since $Z\subsetneq Y$. ∎

Our covering lemma for free elevations will follow by recursively applying our
next result at each step in the sequence of free erections used to construct a
free elevation.

######  Lemma 3.6.

Let $M$ be a matroid on a finite set $E$, ${\cal C}$ be a family of non-
spanning circuits of $M$, and $N$ be the free erection of $M$. Suppose that
each cyclic flat in $M$ is the union of circuits in ${\cal C}$. Then each
cyclic flat in $N$ is the union of circuits in ${\cal C}$.

###### Proof.

The theorem is trivially true if $M=N$, so we may assume that $M\neq N$. This
implies that some spanning circuit of $M$ becomes a base of $N$. Hence $M$ has
no coloops, $E$ is a cyclic flat of $M$ and, by hypothesis, each $e\in E$
belongs to a circuit in $\cal C$. We first prove the following.

######  Claim 3.7.

For each $Z\in\overline{\cal CF}_{M}$, there is a $Z^{\prime}\in\overline{\cal
CF}_{M}$ such that $Z\subseteq Z^{\prime}$, $r_{M}(Z)=r_{M}(Z^{\prime})$, and
$Z^{\prime}$ is the union of circuits in ${\cal C}$.

###### Proof.

Let ${\cal S}_{0},\dots,{\cal S}_{k}$ be the families of cyclic sets defined
in the construction of $\overline{\cal CF}_{M}$ from ${\cal CF}_{M}$ in
Algorithm 1. Since $Z\in\overline{\cal CF}_{M}$, $Z\in{\cal
S}_{j}^{\downarrow}$ for some $0\leq j\leq k$. We prove that the claim holds
for $Z$ by induction on $j$.

For the base case, we assume that $Z\in{\cal S}_{0}^{\downarrow}$. If
$Z\in{\cal S}_{0}={\cal CF}_{M}$, then $Z$ is a cyclic flat of $M$ and hence
is the union of circuits in ${\cal C}$ by our hypothesis on $M$. On the other
hand, if $Z\in{\cal S}_{0}^{\downarrow}\setminus{\cal S}_{0}$, then
$\operatorname{cl}_{M}(Z)\in{\cal S}_{0}$ and
$Z^{\prime}=\operatorname{cl}_{M}(Z)$ is the desired set for $Z$.

Suppose $Z\in{\cal S}_{j}^{\downarrow}{\setminus}{\cal S}_{j-1}^{\downarrow}$
for some $j\geq 1$. We first consider the case when $Z\in{\cal S}_{j}$. Then,
by Algorithm 1, $Z=A\cup B$ for some $A,B\in{\cal S}_{j-1}^{\downarrow}$ which
form a modular pair in $M$. By induction on $j$, there exist
$A^{\prime},B^{\prime}\in\overline{\cal CF}_{M}$ with $A\subseteq A^{\prime}$,
$B\subseteq B^{\prime}$, $r_{M}(A)=r_{M}(A^{\prime})$ and
$r_{M}(B)=r_{M}(B^{\prime})$, such that $A^{\prime}$ and $B^{\prime}$ are both
the union of sets in ${\cal C}$. We claim that $A^{\prime}$ and $B^{\prime}$
form a modular pair in $M$. This follows since

$\displaystyle r_{M}(A)+r_{M}(B)$
$\displaystyle=r_{M}(A^{\prime})+r_{M}(B^{\prime})$ $\displaystyle(\text{by
$r_{M}(A)=r_{M}(A^{\prime})$ and $r_{M}(B)=r_{M}(B^{\prime})$})$
$\displaystyle\geq r_{M}(A^{\prime}\cup B^{\prime})+r_{M}(A^{\prime}\cap
B^{\prime})$ $\displaystyle(\text{by submodularity})$ $\displaystyle\geq
r_{M}(A\cup B)+r_{M}(A\cap B)$ $\displaystyle(\text{by $A\subseteq
A^{\prime},B\subseteq B^{\prime}$})$ $\displaystyle=r_{M}(A)+r_{M}(B)$
$\displaystyle(\text{by modularity})$

and hence equality must hold in each inequality. Since $\overline{\cal
CF}_{M}$ is closed under the union of modular pairs, this gives
$A^{\prime}\cup B^{\prime}\in\overline{\cal CF}_{M}$. The fact that equality
holds throughout the above inequality also implies that $r_{M}(A^{\prime}\cup
B^{\prime})+r_{M}(A^{\prime}\cap B^{\prime})=r_{M}(A\cup B)+r_{M}(A\cap B)$.
This and the monotonicity of $r_{M}$ imply that $r_{M}(A^{\prime}\cup
B^{\prime})=r_{M}(A\cup B)=r_{M}(Z)$. Thus $Z^{\prime}=A^{\prime}\cup
B^{\prime}$ is the desired set for $Z$.

It remains to consider the case when $Z\in{\cal
S}_{j}^{\downarrow}\setminus({\cal S}_{j}\cup{\cal S}_{j-1}^{\downarrow})$.
Then ${\rm cl}_{M}(Z)\not\in{\cal CF}_{M}$ so $Z$ is a spanning set in $M$.
Choose a maximal element $\tilde{Z}$ of ${\cal S}_{j}^{\downarrow}$ with
$Z\subseteq\tilde{Z}$. Then $\tilde{Z}\in{\cal S}_{j}$, and hence there is a
set $\tilde{Z}^{\prime}$ for $\tilde{Z}$ by the preceding paragraph. Then
$r_{M}(\tilde{Z}^{\prime})=r_{M}(Z)$ since $Z$ is spanning in $M$ and
$Z^{\prime}=\tilde{Z}^{\prime}$ is the desired set for $Z$. This completes the
proof of the claim. ∎

The claim implies, in particular, that every maximal element in
$\overline{\cal CF}_{M}$ is the union of circuits in ${\cal C}$.

We can now complete the proof of the lemma. Choose a cyclic flat $Z$ of $N$.
If $Z$ is spanning in $N$, then $Z=E$ and the lemma follows since each element
in $E$ is contained in a circuit in ${\cal C}$. So we may assume that $Z$ is
not spanning in $N$. Then $N|_{Z}=M|_{Z}$ follows as $M$ is the truncation of
$N$. As $Z$ is cyclic in $N$, $Z$ is also cyclic in $M$. If
$r_{N}(Z)<r_{M}(E)$, then $Z$ is a non-spanning cyclic flat in $M$ and the
claim follows from the hypothesis on $M$. So we may further assume that
$r_{N}(Z)=r_{M}(E)=r_{N}(E)-1$. Then $Z$ is a hyperplane in $N$. Lemma 3.5 now
implies that $Z$ is a maximal element in $\overline{\cal CF}_{M}$, and hence
$Z$ is the union of circuits in ${\cal C}$ by Claim 3.7. This completes the
proof of the lemma. ∎

Lemma 3.6 and the fact that non-spanning circuits are preserved when we
construct a free erection immediately give:

######  Lemma 3.8.

Let $M$ be a matroid on a finite set $E$, ${\cal C}$ be a family of non-
spanning circuits of $M$, and $N$ be the free elevation of $M$. Suppose that
each cyclic flat in $M$ is the union of circuits in ${\cal C}$. Then each
cyclic flat in $N$ is the union of circuits in ${\cal C}$.

##  4 $K_{d+2}$-matroids and abstract $d$-rigidity

We will apply the preceding theory to abstract $d$-rigidity matroids. We will
see that abstract $d$-rigidity matroids are $K_{d+2}$-matroids, i.e. matroids
on $E(K_{n})$ in which the edge set of every copy of $K_{d+2}$ is a circuit,
and show that they have maximum possible rank over all such matroids. We will
then give two important examples of abstract $d$-rigidity matroids, generic
$d$-dimensional rigidity matroids and $C_{d-1}^{d-2}$-cofactor matroids, and
describe some related results and conjectures.

Let $G=(V,E)$ be a graph. For $X\subseteq V$, let $G[X]$ be the subgraph of
$G$ induced by $X$. For $F\subseteq E$, let $V(F)$ be the set of vertices
incident to $F$, and let $G[F]=(V(F),F)$. For $v\in V$, let $N_{G}(v)$ be the
set of neighbors of $v$ in $G$, and let $d_{G}(v)=|N_{G}(v)|$. For
$X=\\{v_{1},\dots,v_{k}\\}\subseteq V$, let $K(X)$ or $K(v_{1},\dots,v_{k})$
be the edge set of the complete graph on $X$.

Given a set $F$ in a matroid $M$ defined on $E(K_{n})$, we will often abuse
notation and use the same letter for both the set $F$ and the graph
$K_{n}[F]$. It will be clear from the context whether we are referring to an
edge set or a graph. In addition, we will refer to bases of $M|_{F}$ as bases
of $F$.

We first use Lemma 3.3 to obtain an upper bound on the rank of any
$K_{d+2}$-matroid. We say that a sequence $(C_{1},\dots,C_{t})$ of edge sets
in $K_{n}$ is a $K_{t}$-sequence if each $C_{i}$ induces a copy of $K_{t}$ in
$K_{n}$.

######  Lemma 4.1.

Let $M$ be a $K_{d+2}$-matroid on the edge set of the complete graph $K_{n}$
with $n\geq d+2$. Then its rank is at most $dn-{d+1\choose 2}$.

###### Proof.

It will suffice to construct a proper $K_{d+2}$-sequence which covers $K_{n}$
of length ${{n-d}\choose{2}}$ since Lemma 3.3 will then give
$r(M)\leq{{n}\choose{2}}-{{n-d}\choose{2}}=dn-{{d+1}\choose{2}}$. To this end,
we let $K_{n}=K(v_{1},v_{2},\ldots,v_{n})$ and construct a proper
$K_{d+2}$-sequence ${\cal K}_{i}$ of length ${{i-d}\choose{2}}$ which covers
$K(v_{1},v_{2},\ldots,v_{i})$ for all $d+2\leq i\leq n$, recursively. We first
put ${\cal K}_{d+2}=(K(v_{1},v_{2},\ldots,v_{d+2}))$. Then, for each $d+2\leq
i\leq n-1$, we construct a proper $K_{d+2}$-sequence ${\cal K}_{i+1}$ which
covers $K(v_{1},\dots,v_{i+1})$ by choosing a set $S_{i}$ of $d$ vertices in
$K(v_{1},v_{2},\ldots,v_{i})$, putting ${\cal
L}_{i+1}=(K(S_{i}+v_{j}+v_{i+1})\,:\,1\leq j\leq i\mbox{ and }j\not\in
S_{i})$, and then putting ${\cal K}_{i+1}=({\cal K}_{i},{\cal L}_{i+1})$. It
is straightforward to check that ${\cal K}_{i+1}$ has length
${{i+1-d}\choose{2}}$ and is proper (for any ordering of the $K_{d+2}$’s in
each subsequence ${\cal L}_{j}$). ∎

The graphic matroid of $K_{n}$ and the rank-two uniform matroid on $E(K_{n})$
are examples of $K_{3}$-matroids. In addition, the graphic matroid achieves
the upper bound on the rank given by Lemma 4.1.

Graver [20] defined an abstract $d$-rigidity matroid to be a matroid $M$ on
the edge set of the complete graph $K_{n}$ which satisfies the following two
axioms:

(A1)

If $E_{1},E_{2}\subseteq E(K_{n})$ with $|V(E_{1})\cap V(E_{2})|\leq d-1$,
then ${\rm cl}_{M}(E_{1}\cup E_{2})\subseteq K(V(E_{1}))\cup K(V(E_{2}))$;

(A2)

If $E_{1},E_{2}\subseteq E(K_{n})$ with ${\rm cl}_{M}(E_{1})=K(V(E_{1}))$,
${\rm cl}_{M}(E_{2})=K(V(E_{2}))$, and $|V(E_{1})\cap V(E_{2})|\geq d$, then
${\rm cl}_{M}(E_{1}\cup E_{2})=K(V(E_{1}\cup E_{2}))$.

These two conditions reflect two fundamental rigidity properties of generic
$d$-dimensional bar-joint frameworks. (See, for example, [21] for more
details.) Nguyen [37] obtained a simple characterization of abstract
$d$-rigidity matroids which immediately implies that they are special kinds of
$K_{d+2}$-matroids.

######  Theorem 4.2 (Nguyen[37, Theorem 2.2]).

Let $n,d$ be positive integers with $n\geq d+2$ and $M$ be a matroid on
$E(K_{n})$. Then $M$ is an abstract $d$-rigidity matroid if and only if $M$ is
a $K_{d+2}$-matroid with rank $dn-{d+1\choose 2}$.

Lemma 4.1 and Theorem 4.2 imply that abstract $d$-rigidity matroids are
precisely the $K_{d+2}$-matroids on $E(K_{n})$ which attain the maximum
possible rank.

###  4.1 Two fundamental examples

We describe two examples of abstract $d$-rigidity matroids which have been
extensively studied in the literature.

#### Generic rigidity matroids.

A $d$-dimensional framework is a pair $(G,p)$ consisting of a graph $G=(V,E)$
and a map $p:V\rightarrow\mathbb{R}^{d}$. An infinitesimal motion of $(G,p)$
is a map $q:V\rightarrow\mathbb{R}^{d}$ such that

$(p(u)-p(v))\cdot(q(u)-q(v))=0\qquad(uv\in E),$ (6)

where $\cdot$ denotes the Euclidean inner product. The rigidity matrix
$R(G,p)$ of $(G,p)$ is the matrix representing the linear system of equations
(6) in the variables $q$. Specifically, $R(G,p)$ is a matrix of size
$|E|\times d|V|$ in which each row is indexed by an edge, sets of $d$
consecutive columns are indexed by the vertices, and the row indexed by the
edge $e=uv$ has the form:

$\hbox{}\vbox{\kern 0.86108pt\hbox{$\kern 0.0pt\kern
2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
u$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle v$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\\\e=uv$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0\cdots 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle p(u)-p(v)$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\cdots 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle p(v)-p(u)$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\cdots 0$\hfil\kern 5.0pt\crcr}}}}\right]$}}.$

The framework $(G,p)$ is said to be infinitesimally rigid if
$\operatorname{rank}R(G,p)=dn-{d+1\choose 2}$.

The rigidity matroid of $(G,p)$ is the matroid on $E$ in which a set of edges
is independent if the corresponding rows of $R(G,p)$ are linearly independent.
The rigidity matroid of $(G,p)$ is the same for any generic
$p:V\to{\mathbb{R}}^{d}$ and we refer to this matroid as the generic
$d$-dimensional rigidity matroid ${\cal R}_{d}(G)$ of $G$. The generic
$d$-dimensional rigidity matroid of the complete graph $K_{n}$ is called the
generic $d$-dimensional rigidity matroid (on $n$ vertices) and is denoted by
${\cal R}_{d,n}$. A graph $G=(V,E)$ with $n$ vertices is said to be rigid in
${\mathbb{R}}^{d}$ if $E$ is a spanning set of ${\cal R}_{d,n}$ or
equivalently, when $n\geq d$, if the rank of $E$ is $dn-{d+1\choose 2}$.
Combinatorial characterizations of graphs which are rigid in
${\mathbb{R}}^{d}$ exist for $d=1,2$. Obtaining an analogous characterization
for $d\geq 3$ is the central open problem in graph rigidity.

#### Generic cofactor matroids.

Let $G=(V,E)$ be a graph and $p:V\to{\mathbb{R}}^{2}$ such that
$p(v_{i})=(x_{i},y_{i})$ for all $v_{i}\in V$. We assume that the vertices are
ordered as $v_{1},v_{2},\ldots,v_{n}$. As given in the introduction, the
$C^{s-1}_{s}$-cofactor matrix of $(G,p)$, denoted by $C_{s}^{s-1}(G,p)$, is a
matrix of size $|E|\times(s+1)|V|$ in which each row is indexed by an edge,
sets of $(s+1)$ consecutive columns are indexed by the vertices, and the row
associated to the edge $e=v_{i}v_{j}$ with $i<j$ is

$\hbox{}\vbox{\kern 0.86108pt\hbox{$\kern 0.0pt\kern
2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{i}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle v_{j}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\\\e=v_{i}v_{j}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\cdots 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle D_{ij}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0\cdots 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle-D_{ij}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\cdots 0$\hfil\kern 5.0pt\crcr}}}}\right]$}},$

where
$D_{i,j}=((x_{i}-x_{j})^{s},(x_{i}-x_{j})^{s-1}(y_{i}-y_{j}),\dots,(x_{i}-x_{j})(y_{i}-y_{j})^{s-1},(y_{i}-y_{j})^{s})\in\mathbb{R}^{s+1}$.
(Our definition is slightly different to that given by Whiteley [50], but the
two definitions are equivalent up to elementary column operations.) When
$s\geq 1$, the space $S_{s}^{s-1}(\Delta)$ of bivariate $C_{s}^{s-1}$-splines
over $\Delta$ is linearly isomorphic to the left kernel of $C_{s}^{s-1}(G,p)$
if $(G,p)$ is the 1-skeleton of a subdivision $\Delta$ of a polygonal domain
in the plane, see, e.g., [50] for more details. Note that, when $s=0$,
$D_{i,j}\equiv 1$ and $C_{s}^{s-1}(G,p)$ is just the edge/vertex incidence
matrix of $G$.

The generic $C_{s}^{s-1}$-cofactor matroid ${\cal C}_{s,n}^{s-1}$ is defined
to be the row matroid of $C_{s}^{s-1}(K_{n},p)$ for any generic $p$. Whiteley
[50] showed that ${\cal C}_{d-1,n}^{d-2}$ is an abstract $d$-rigidity matroid
for all $d\geq 1$. It follows immediately from the definitions of the rigidity
and cofactor matrices that ${\cal C}_{d-1,n}^{d-2}={\cal R}_{d,n}$ when
$d=1,2$. Whiteley [50] showed that that ${\cal C}_{d-1,n}^{d-2}\neq{\cal
R}_{d,n}$ when $d\geq 4$ and $n\geq 2d+2$ and conjectured that the two
matroids are equal when $d=3$.

###  4.2 Maximality conjectures

As noted above, abstract $d$-rigidity matroids are $K_{d+2}$-matroids which
attain the maximum possible rank. Graver [20] conjectured further that the
generic $d$-dimensional rigidity matroid is the unique maximal matroid in the
weak order poset of all abstract $d$-rigidity matroids on $E(K_{n})$, and
verified his conjecture when $d=1,2$. N. J. Thurston (see, [21, page 150])
subsequently showed that Graver’s conjecture is false when $d\geq 4$. The
conjecture remains as a long-standing open problem for $d=3$.

######  Conjecture 4.3 (Graver’s maximality conjecture [20]).

The generic $3$-dimensional rigidity matroid is the unique maximal abstract
$3$-rigidity matroid on $E(K_{n})$.

Whiteley [50] developed a theory for $C_{d-1}^{d-2}$-cofactor matroids which
is analogous to that for $d$-dimensional rigidity matroids. In particular, he
provided further counterexamples to Graver’s maximality conjecture by noting
that the edge set of the complete bipartite graph $K_{d+2,d+2}$ is dependent
in ${\cal R}_{d,n}$ for all $d\geq 1$ but independent in $C_{d-1,n}^{d-2}$
when $d\geq 4$. This led him to make the following modified conjecture.

######  Conjecture 4.4 (Whiteley’s maximality conjecture [50, Conjecture
11.5.1]).

The generic $C_{d-1}^{d-2}$-cofactor matroid ${\cal C}_{d-1,n}^{d-2}$ is the
unique maximal abstract $d$-rigidity matroid on $E(K_{n})$ for all $d\geq 1$.

The conjecture holds for $d=1,2$, since Graver’s conjecture holds for $d=1,2$
and the generic cofactor and rigidity matroids are the same for these values
of $d$. The main result of our first paper in this series [6] verifies
Whiteley’s maximality conjecture when $d=3$.

######  Theorem 4.5.

The generic $C_{2}^{1}$-cofactor matroid ${\cal C}^{1}_{2,n}$ is the unique
maximal $K_{5}$-matroid on $E(K_{n})$.

Theorem 4.5 is stronger than Whiteley’s conjecture since it holds for the
larger class of $K_{5}$-matroids. We can use a similar proof technique to that
given by Graver to show that analogous results hold when $d=1,2$: the generic
1-dimensional rigidity matroid is the unique maximal $K_{3}$-matroid and the
generic 2-dimensional rigidity matroid is the unique maximal $K_{4}$-matroid
on $E(K_{n})$. Whiteley’s conjecture, and the corresponding strengthening to
the larger class of $K_{d+2}$-matroids, remain open for all $d\geq 4$.

###  4.3 Inductive constructions

Inductive constructions are frequently used to solve problems in rigidity. The
most common operations in this context are $k$-extensions, which are defined
as follows. Given integers $k$ and $d$ with $0\leq k\leq d$, a $d$-dimensional
$k$-extension of a graph $G$ constructs a new graph by deleting $k$ edges from
$G$ and then adding a new vertex $v_{0}$ and $d+k$ new edges incident to
$v_{0}$, with the proviso that each end-vertex of a deleted edge is a neighbor
of $v_{0}$. See Figure 1 for an example.

Figure 1: An example of 3-dimensional 2-extension (X-replacement).

It is well-known that, if $G$ is rigid in ${\mathbb{R}}^{d}$ and $k=0,1$, then
any graph obtained from $G$ by a $k$-extension is rigid in ${\mathbb{R}}^{d}$,
see for example [50]. This fact was used by Pollaczek-Geiringer [39] to show
that Maxwell’s necessary condition for rigidity (given in the introduction) is
also sufficient in dimension two.

The situation becomes more complicated when $k\geq 2$. In particular, we can
distinguish two types of $2$-extensions, depending on whether or not the two
deleted edges are adjacent: a $2$-extension is called a V-replacement if the
deleted edges are adjacent, and otherwise is called an X-replacement. See
Figure 1. It is conjectured that 3-dimensional X-replacement preserves
rigidity in ${\mathbb{R}}^{3}$.

######  Conjecture 4.6 (X-replacement conjecture [46]).

Suppose that $G$ and $H$ are graphs and that $H$ can be obtained from $G$ by a
$3$-dimensional X-replacement. If $G$ is rigid in ${\mathbb{R}}^{3}$, then $H$
is rigid in ${\mathbb{R}}^{3}$.

See [10] for more details about this conjecture. Maehara [33] pointed out that
the analogous statement for 4-dimensional $X$-replacement does not hold in
general.

The $d$-dimensional $k$-extension operation can be applied to any graph and
hence can be used to investigate independence properties of any matroid $M$
defined on the edge set of $K_{n}$. We say that $M$ has the $d$-dimensional
$k$-extension property if every edge set obtained from an independent set by a
$d$-dimensional $k$-extension operation remains independent.

A basic fact about abstract $d$-rigidity matroids is that any abstract
$d$-rigidity matroid has the $d$-dimensional 0-extension property [21]. As
noted above, the generic $d$-dimensional rigidity matroid also has the
$d$-dimensional 1-extension property. For $C_{d-1}^{d-2}$-cofactor matroids,
Whiteley [50, Theorem 11.4.1] proved the following:

######  Theorem 4.7.

The generic $C_{d-1}^{d-2}$-cofactor matroid has the $d$-dimensional
$1$-extension property for all $d\geq 1$, and the $d$-dimensional
X-replacement property for all $d\geq 2$.

Theorem 4.7 is an important ingredient in our proof of Theorem 4.5. The fact
that the generic $3$-dimensional rigidity matroid is not known to have the
$3$-dimensional X-replacement property is a major barrier to applying the same
proof technique to solve Graver’s Maximality Conjecture.

##  5 Combinatorial characterization

We saw in the last section that ${\cal C}_{2,n}^{1}$ is the unique maximal
abstract 3-rigidity matroid on $E(K_{n})$. In this section, we obtain a co-NP
type characterization of its rank function. Since ${\cal C}_{2,n}^{1}$ is the
free matroid on $E(K_{n})$ when $n\leq 4$, we assume throughout this section
that $n\geq 5$.

Theorem 4.2 implies that the rank 10 truncation of any abstract 3-rigidity
matroid on $E(K_{n})$ is the matroid $R_{n}$ on $E(K_{n})$ of rank $10$ in
which the non-spanning circuits are the edge sets of the copies of $K_{5}$ in
$K_{n}$. We can use this observation, together with other results from
Sections 3 and 4 to derive two fundamental properties of ${\cal C}^{1}_{2,n}$.

######  Theorem 5.1.

The generic $C_{2}^{1}$-cofactor matroid ${\cal C}_{2,n}^{1}$ is the free
elevation of $R_{n}$.

###### Proof.

Theorem 4.5 tells us that the generic cofactor matroid ${\cal C}^{1}_{2,n}$ is
the unique maximal $K_{5}$-matroid on $E(K_{n})$. Lemma 3.1 now implies that
${\cal C}^{1}_{2,n}$ is the free elevation of $R_{n}$. ∎

######  Corollary 5.2.

Every cyclic flat of ${\cal C}^{1}_{2,n}$ is the union of copies of $K_{5}$.

###### Proof.

This follows from Theorem 5.1, Lemma 3.8, and the facts that each non-spanning
cyclic flat of $R_{n}$ is a copy of $K_{5}$ and $E(K_{n})$ can be covered by
copies of $K_{5}$. ∎

###  5.1 Matroids on the edge set of a graph

Our derivation of the rank function of ${\cal C}^{1}_{2,n}$ uses the property
that each of its cyclic flats has a base which induces a subgraph of $K_{n}$
of minimum degree at most four. We will deduce this property from the more
general results given in this subsection. We first need to introduce the
matroidal concepts of connectivity and ear decomposition.

A matroid ${M}$ with ground set $E$ is said to be connected if, for every pair
$e,f\in E$ with $e\neq f$, $M$ has a circuit containing both $e$ and $f$. A
set $X\subseteq E$ is said to be connected if $M|_{X}$ is connected. We can
define an equivalence relation on $X$ by saying that $e_{1},e_{2}\in X$ are
related if either $e_{1}=e_{2}$ or there is a circuit of $M$ in $X$ which
contains both $e_{1}$ and $e_{2}$. The corresponding equivalence classes
$X_{1},X_{2}\ldots,X_{k}$ are the maximal connected subsets of $X$. We will
refer to these equivalence classes as the connected components of $X$ in $M$.
We have $X_{i}\cap X_{j}=\emptyset$ for all $1\leq i<j\leq k$ and
$r(X)=\sum_{i=1}^{k}r(X_{i})$.

A partial ear decomposition of ${M}$ is a sequence $(C_{1},C_{2}\dots,C_{t})$
of circuits of $M$ such that, for all $2\leq i\leq t$:

  * •

$C_{i}\cap C_{\leq i-1}\neq\emptyset$;

  * •

$C_{i}\setminus C_{\leq i-1}\neq\emptyset$;

  * •

if some circuit $C$ of $M$ satisfies $C\cap C_{\leq i-1}\neq\emptyset\neq
C\setminus C_{\leq i-1}$ then $C\setminus C_{\leq i-1}$ is not a proper subset
of $C_{i}\setminus C_{\leq i-1}$.

An ear decomposition of $M$ is a partial ear decomposition with the additional
property that $C_{\leq t}=E$. More generally, an ear decomposition of a set
$X\subseteq E$ is a partial ear decomposition with the additional property
that $C_{\leq t}=X$. Ear decompositions of matroids were introduced by
Coullard and Hellerstein [7]. They showed:

######  Theorem 5.3.

A matroid $M$ with at least two elements is connected if and only if it has an
ear decomposition. Furthermore, if $M$ is connected, then any partial ear
decomposition of $M$ can be extended to an ear decomposition of $M$.

We will use an ear decomposition of a connected set $X$ in a matroid $M$
defined on the edge set of a graph $G$ to show that, subject to a mild
condition on the circuits of $M$, some base of $X$ induces a subgraph of $G$
of low minimum degree. More precisely, we use induction on the number of
circuits in the ear decomposition to show that the average minimum degree over
all bases of $X$ is at most $2\frac{r(X)+1}{|V(X)|}-1$. For the inductive step
we will need the following result which follows easily from the definition of
an ear decomposition.

######  Lemma 5.4.

Let $(C_{1},C_{2},\ldots,C_{t})$ be a partial ear decomposition in a matroid
$M$. Then $r(C_{\leq i})=r(C_{\leq i-1})+|C_{i}\setminus C_{\leq i-1}|-1$ for
all $2\leq i\leq t$. Furthermore, if $B_{i-1}$ is any base of $C_{\leq i-1}$
and $Y$ is any subset of $C_{i}\setminus C_{\leq i-1}$ of size
$|C_{i}\setminus C_{\leq i-1}|-1$ then $B_{i}=B_{i-1}\cup Y$ is a base of
$C_{\leq i}$.

######  Lemma 5.5.

Let $M$ be a matroid defined on the edge set of a graph $G=(V,E)$ and
$X\subseteq E$ be a connected set in $M$. Suppose that every circuit of $M$
induces a $2$-connected subgraph of $G$. Then

$f(X):=\sum_{v\in V(X)}\min\\{d_{B}(v):\mbox{$B$ is a base of $X$}\\}\leq
2(r(X)+1)-|V(X)|.$

###### Proof.

We use induction on $|X|$. The lemma holds when $X$ is a coloop since we have
$r(X)=|X|=1$ and $|V(X)|\leq 2$. Hence we may suppose that $|X|\geq 2$ so $X$
is a cyclic set in $M$. Let $n=|V(X)|$.

We first consider the case when $X$ is a circuit of $M$. Then $r(X)=|X|-1$.
For each $v\in V(X)$, we can construct a base of $X$ which contains
$d_{X}(v)-1$ edges incident to $v$, so the contribution of $v$ to $f(X)$ is
$d_{X}(v)-1$. Hence

$f(X)=\sum_{v\in V(X)}(d_{X}(v)-1)=2|X|-n=2(r(X)+1)-n$

as required. Thus we may assume that $X$ is not a circuit.

Let $(C_{1},C_{2},\ldots,C_{m})$ be an ear decomposition of $X$ and put
$Z=C_{m}{\setminus}C_{\leq m-1}$. By Lemma 5.4, $r(X)=r(C_{\leq m-1})+|Z|-1$
holds and, for every base $B^{\prime}$ of $C_{\leq m-1}$ and every subset $Y$
of $Z$ of cardinality $|Z|-1$, $B=B^{\prime}\cup Y$ is a base of $X$.

We will obtain an upper bound on $f(X)$ by considering the separate
contributions of the vertices in $V_{1}=V(C_{\leq m-1})$ and
$V_{2}=V(X){\setminus}V_{1}$. To this end, we let $n_{1}=|V_{1}|$,
$n_{2}=|V_{2}|$, $Z_{1}$ and $Z_{2}$ be the sets of edges in $Z$ which belong
to the subgraphs of $X$ induced by $V_{1}$ and $V_{2}$, respectively, and put
$Z_{1,2}=Z{\setminus}(Z_{1}\cup Z_{2})$.

We first consider the contribution of the vertices in $V_{1}$ to $f(X)$. By
Theorem 5.3 and Lemma 5.4, $C_{\leq m-1}$ is connected in $M$ and $r(C_{\leq
m-1})=r(X)-|Z|+1$. Hence, by induction,

$f(C_{\leq m-1})\leq 2(r(X)-|Z|+2)-n_{1}.$ (7)

For each $v\in V_{1}$ which is incident to an edge of $Z$ and each base
$B^{\prime}$ of $C_{\leq m-1}$, we can construct a base $B$ of $X$ with
$d_{B}(v)=d_{B^{\prime}}(v)+d_{Z}(v)-1$. This implies that the contribution of
the vertices of $V_{1}$ to $f(X)$ is at most

$f(C_{\leq m-1})+2|Z_{1}|+|Z_{1,2}|-|V(Z)\cap V_{1}|.$ (8)

We next consider the contribution of the vertices of $V_{2}$ to $f(X)$. Choose
$v\in V_{2}$. Then $v$ is only incident to edges of $Z$ in $X$. Since we can
construct a base of $X$ which contains $d_{X}(v)-1$ edges incident to $v$, the
contribution of $v$ to $f(X)$ is $d_{X}(v)-1$. So the total contribution of
the vertices of $V_{2}$ to $f(X)$ is

$\sum_{v\in V_{2}}(d_{X}(v)-1)=2|Z_{2}|+|Z_{1,2}|-n_{2}.$ (9)

Note that the previous sentence remains valid when $V_{2}=\emptyset$ since the
contribution given by (9) is zero in this case.

We may now combine (7), (8) and (9) with $|Z|=|Z_{1}|+|Z_{2}|+|Z_{12}|$ and
$n=n_{1}+n_{2}$ to obtain

$\displaystyle f(X)$ $\displaystyle\leq$ $\displaystyle
2(r(X)-|Z|+2)-n_{1}+2|Z_{1}|+|Z_{1,2}|-|V(Z)\cap
V_{1}|+2|Z_{2}|+|Z_{1,2}|-n_{2}$ $\displaystyle=$ $\displaystyle
2r(X)-|V(Z)\cap V_{1}|-n+4.$

Finally we use the hypothesis that the subgraph of $G$ induced by a circuit is
2-connected. This and $C_{m}\cap C_{\leq m-1}\neq\emptyset$ imply that
$|V(Z)\cap V_{1}|\geq 2$, and we obtain $f(X)\leq 2(r(X)+1)-n$ as required. ∎

Suppose $M$ is a $K_{d+2}$-matroid with $d\geq 2$. Then Lemma 4.1 implies that
$r_{M}(X)\leq d|V(X)|-{{d+1}\choose{2}}$ for any connected set $X$ in $M$ and
we can now use Lemma 5.5 to deduce that $X$ has a base of minimum degree at
most $2d-2$. We next extend this observation to the case when $M$ is an
abstract $d$-rigidity matroid and $X$ is cyclic but not necessarily connected.

######  Lemma 5.6.

Suppose $M$ is an abstract $d$-rigidity matroid defined on $E(K_{n})$ for some
$d\geq 2$ and $X$ is a nonempty cyclic set in $M$. Then every base of $X$ has
minimum degree at least $d$, and some base of $X$ has minimum degree at most
$2d-2$.

###### Proof.

Since $M$ is an abstract $d$-rigidity matroid, the 0-extension property holds
for $M$ and hence each circuit of $M$ induces a subgraph of minimum degree at
least $d+1$. Since $X$ is cyclic, this implies that each vertex of $K_{n}[X]$
has degree at least $d+1$.

Suppose $d_{B}(v)\leq d-1$ for some base $B$ of $X$ and some $v\in V(X)$. Then
we can use the 0-extension property to extend $B-v$ to an independent set of
size $|B|+1$ in $X$ by adding $d$ edges incident to $v$, contradicting the
fact that $B$ is a base of $X$. Hence $d_{B}(v)\geq d$ for all bases $B$ of
$X$ and all $v\in V(X)$.

It remains to show that some base of $X$ has minimum degree at most $2d-2$.
Let $X_{1},X_{2}\ldots,X_{q}$ be the connected components of $X$ in $M$. Then
each $X_{i}$ is a cyclic set in $M$, $X_{i}\cap X_{j}=\emptyset$ for $i\neq j$
and, for any set of bases $B_{i}$ of $X_{i}$, $B=\bigcup_{i=1}^{q}B_{i}$ is a
base of $X$. For $v\in V(X)$, let $a(v)$ be the number of components $X_{i}$
for which $v\in V(X_{i})$. Let $U=\\{v\in V(X):a(v)\geq 2\\}$ and let
$b(X_{i})=|U\cap V(X_{i})|$ for all $1\leq i\leq q$. Let $n=|V(X)|$ and
$n_{i}=|V(X_{i})|$ for all $1\leq i\leq q$. Then
$\sum_{i=1}^{q}n_{i}=n+\sum_{u\in U}(a(u)-1)$ and $\sum_{u\in
U}a(u)=\sum_{i=1}^{q}b(X_{i})$. We may apply Lemmas 4.1 and 5.5 to each
$X_{i}$ to deduce that

$f(X_{i})\leq(2d-1)n_{i}-(d-1)(d+2).$ (10)

Suppose that $b(X_{i})\leq d+1$ for some $1\leq i\leq q$. We can use the
argument in the first paragraph to deduce that $d_{B_{i}}(v)\geq d$ for all
bases $B_{i}$ of $X_{i}$ and all $v\in V(X_{i})$. Together with (10) and the
hypothesis that $d\geq 2$, this implies that there are at least $d+2$ vertices
$v\in V(X_{i})$ such that $v$ has degree at most $2d-2$ in some base of
$X_{i}$. Since $b(X_{i})\leq d+1$, we can choose $v\in V(X_{i})\setminus U$
such that $v$ has degree at most $2d-2$ in some base $B_{i}$ of $X_{i}$. We
can now extend $B_{i}$ to a base $B$ of $X$. Since $v\not\in U$, $v$ will have
degree at most $2d-2$ in $B$.

Hence we may assume that $b(X_{i})\geq d+2$ for all $1\leq i\leq q$. Since the
union of any collection of bases of the $X_{i}$ gives a base of $X$,
$f(X)=\sum_{i=1}^{q}f(X_{i})$. We may now use Lemma 5.5, (10) and the fact
that $\sum_{i=1}^{q}n_{i}=n+\sum_{u\in U}(a(u)-1)$ to deduce that

$\displaystyle(2d-1)n-f(X)$ $\displaystyle=$
$\displaystyle(2d-1)n-\sum_{i=1}^{q}f(X_{i})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{q}((2d-1)n_{i}-f(X_{i}))-(2d-1)\sum_{u\in
U}(a(u)-1)$ $\displaystyle\geq$ $\displaystyle
2\sum_{i=1}^{q}(dn_{i}-r(X_{i})-1)-(2d-1)\sum_{u\in U}(a(u)-1)$
$\displaystyle=$ $\displaystyle 2(dn-r(X)-q)+\sum_{u\in U}(a(u)-1)$
$\displaystyle=$ $\displaystyle 2(dn-r(X))-2q-|U|+\sum_{u\in U}a(u).$

Since $a(u)\geq 2$ for all $u\in U$ and $b(X_{i})\geq d+2\geq 5$ for all
$1\leq i\leq q$, we have $\sum_{u\in U}a(u)\geq 2|U|$ and $\sum_{u\in
U}a(u)=\sum_{i=1}^{q}b(X_{i})\geq 5q$. Since $r(X)<dn$ by Lemma 4.1, we have
$(2d-1)n-f(X)>0$ and $f(X)<(2d-1)n$. Hence some base of $X$ has minimum degree
at most $2d-2$. ∎

The bound on the minimum degree of a base in Lemma 5.6 is best possible since
the generic $d$-dimensional rigidity matroid contains circuits of minimum
degree $2d-1$ when $d\geq 2$. We will see in the next subsection, however,
that a stronger bound holds for cyclic flats in ${\cal C}^{1}_{2,n}$.

###  5.2 The rank function of ${\cal C}^{1}_{2,n}$

Theorem 5.1 and Lemma 3.3 tell us that we can bound the rank of any set $X$ in
$C_{2,n}^{1}$ by using proper $K_{5}$-sequences. More precisely, Theorem 5.1
tells us that $C_{2,n}^{1}$ is the free-elevation of the rank 10 matroid on
$E(K_{n})$ whose non-spanning circuits are the edge sets of all copies of
$K_{5}$, and Lemma 3.3 now implies that the rank of a set $X\subseteq
E(K_{n})$ in $C_{2,n}^{1}$ is bounded above by $|X\cup C_{\leq t}|-t$ for any
proper $K_{5}$-sequence $(C_{1},\dots,C_{t})$. Our next result shows that this
bound is tight for some proper $K_{5}$-sequence in $K_{n}$. It also
establishes an important structural property of cyclic flats in $C_{2,n}^{1}$,
that they always contain a simplicial vertex i.e. a vertex whose neighbor set
induces a complete subgraph. Its proof uses a simultaneous induction on both
statements.

To simplify notation we put

${\rm val}(F,{\cal C}):=|F\cup C_{\leq t}|-t$

for all $F\subseteq E(K_{n})$ and all proper $K_{5}$-sequences ${\cal
C}=(C_{1},\dots,C_{t})$ contained in $K_{n}$.

######  Theorem 5.7.

Suppose $X\subseteq E(K_{n})$. (a) The rank of $X$ in ${\cal C}_{2,n}^{1}$ is
given by

$r(X)=\min\\{|X\cup C_{\leq t}|-t:\text{$(C_{1},\dots,C_{t})$ is a proper
$K_{5}$-sequence in $K_{n}$}\\}.$

(b) If $X$ is a cyclic flat in $C_{2,n}^{1}$, then there exists a vertex $v\in
V(X)$ such that $K(N_{X}(v))\subseteq X$, and $v$ has degree three in some
base of $X$.

###### Proof.

We proceed by contradiction. Suppose that the theorem does not hold for some
$X\subseteq E(K_{n})$. We may suppose that $X$ has been chosen such that
$r(X)$ is as small as possible and, subject to this condition, that $|X|$ is
as large as possible.

We first show that (b) holds for $X$ when $X$ is a cyclic flat. Choose a
vertex $v\in V(X)$ and a base $B$ of $X$ such that $d_{B}(v)$ is as small as
possible. Then $d_{B}(v)\in\\{3,4\\}$ by Lemma 5.6. Let
$N_{X}(v)=\\{v_{1},\dots,v_{k}\\}$. Note that $k\geq 4$ since $X$ is cyclic
and all circuits of ${\cal C}_{2,n}^{1}$ have minimum degree at least four.

Suppose that $d_{B}(v)=3$. If $K(N_{X}(v))\not\subseteq X$, then relabelling
if necessary, we have $e=v_{1}v_{2}\in K(N_{X}(v))\setminus X$, and $B-v+e$ is
independent since $X$ is a flat. Then
$B^{\prime}=(B-v)\cup\\{vv_{1},vv_{2},vv_{3},vv_{4}\\}$ is also independent
since it can be obtained from $B-v+e$ by a 1-extension. This contradicts the
choice of $B$, since $|B^{\prime}|>|B|$ and $B^{\prime}\subseteq X$. Hence
$K(N_{X}(v))\subset X$ and (b) holds for $X$.

It remains to consider the case when $d_{B}(v)=4$. Then $v$ has degree at
least four in all bases of $X$. We will refer to any base $B$ with the
property that $d_{B}(v)=4$ as a $v$-admissible base of $X$. We will show that
this case cannot occur by first showing that $v$ is a simplicial vertex in $X$
and then deducing that $v$ has degree three in some base of $X$.

######  Claim 5.8.

$r(X-v)=r(X)-4$.

###### Proof.

The fact that $X$ has a $v$-admissible base implies that $r(X-v)\geq r(X)-4$.
Let $B^{\prime}$ be a base of $X-v$. If $|B^{\prime}|>r(X)-4$, then
$B^{\prime}$ would extend to a base of $X$ in which $v$ has degree three and
would contradict our assumption that $v$ has degree at least four in all bases
of $X$. Hence $|B^{\prime}|=r(X-v)=r(X)-4$. ∎

As $X$ is a cyclic flat, Corollary 5.2 tells us that $X$ is the union of
copies of $K_{5}$. Hence we may choose $S_{1}\subseteq X$ such that $S_{1}$
induces a copy of $K_{5}$ which contains $v$. We may assume that
$V(S_{1})=\\{v,v_{1},v_{2},v_{3},v_{4}\\}$.

######  Claim 5.9.

There exists $Y\subseteq X$ such that $d_{Y}(v)=5$, $S_{1}\subseteq Y$ and
$Y-vv_{i}$ is a $v$-admissible base of $X$ for all $1\leq i\leq 4$.

###### Proof.

Choose a $v$-admissible base $B$ of $X$. We will use the term base exchange on
$B$ to mean the operation which constructs a new base $B+e-f$ by first adding
an edge $e\in X{\setminus}B$ to $B$ and then deleting an edge $f$ from the
fundamental circuit of $B+e$. If $vv_{i}\in B$ for all $1\leq i\leq 4$ then,
since $d_{B}(v)=4$, we could perform a sequence of base exchanges using the
edges of $S_{1}$ to construct a base of $X$ in which $v$ has degree less than
four. Hence we may assume that $vv_{4}\not\in B$. Since $d_{B}(v)=4$ and every
circuit of ${\cal C}_{2,n}^{1}$ has minimum degree at least four, we can also
use a sequence of base exchanges to ensure that $vv_{i}\in B$ for all $1\leq
i\leq 3$. We can now perform a further sequence of base exchanges using the
edges of $S_{1}$ to ensure that $S_{1}-vv_{4}\subseteq B$. Let $Y=B+vv_{4}$.
Then $S_{1}\subseteq Y$ and $Y-v_{1}v_{4}=B$ is a $v$-admissible base of $X$.
The fact that $S_{1}$ is the fundamental circuit of $B+vv_{4}$ now implies
that $Y-vv_{i}$ is a $v$-admissible base of $X$ for all $1\leq i\leq 4$. ∎

Since $d_{Y}(v)=5$, $Y$ has an edge $vv_{5}$ for some $v_{5}\notin V(S_{1})$.
In addition, $Y-v+v_{i}v_{5}$ is independent in ${\cal C}_{2,n}^{1}$ for some
$1\leq i\leq 4$, since otherwise $Y-vv_{1}$ would be dependent (as the closure
of $X-v$ would contain $K(v_{1},v_{2},\dots,v_{5})$ and $v$ is joined to
$\\{v_{1},v_{2},\dots,v_{5}\\}$ by four edges in $Y-vv_{1}$). Hence, we may
assume without loss of generality that $Y-v+v_{4}v_{5}$ is independent. Since
$Y-v$ is a base of $X-v$ by Claims 5.8 and 5.9, this gives

$r(X-v+v_{4}v_{5})=r(X-v)+1=r(X)-3.$ (11)

######  Claim 5.10.

$K(N_{X}(v))\subseteq{\rm cl}(X-v+v_{4}v_{5})$.

###### Proof.

We first show that, for all $u\in N_{X}(v)-v_{5}$,

$K(v_{1},v_{2},v_{3},u)\subseteq{\rm cl}(X-v+v_{4}v_{5})$. (12)

Suppose to the contrary that $uv_{i}\not\in{\rm cl}(X-v+v_{4}v_{5})$ for some
$u\in N_{X}(v)-v_{5}$ and some $1\leq i\leq 3$. Then $Y-v+v_{4}v_{5}+uv_{i}$
is independent in ${\cal C}_{2,n}^{1}$. Since
$K(v_{1},v_{2},v_{3},v_{4})\subseteq S_{1}\subseteq X$, $u\neq v_{4}$. Hence
$uv_{i}$ and $v_{4}v_{5}$ are disjoint, and we can perform an $X$-replacement
to deduce that $B^{\prime}=(Y-v)\cup\\{vu,vv_{i},vv_{4},vv_{5},vv_{j}\\}$ is
independent for any $1\leq j\leq 3$ with $j\neq i$. Since $|B^{\prime}|=|Y|$
and $B^{\prime}\subseteq X$, this would contradict the fact that $Y-vv_{1}$ is
a base of $X$.

We can now use (12) and axiom (A2) for abstract 3-rigidity from Section 4 to
deduce that ${\rm cl}(X-v+v_{4}v_{5})$ contains $K(N_{X}(v)-v_{5})$. The same
axiom implies that we can complete the proof of the claim by showing that $X$
contains at least three edges between $v_{5}$ and
$N_{X}(v)\setminus\\{v_{5}\\}$. To see this, recall that $X$ is the union of
copies of $K_{5}$. In particular we have $vv_{5}\in S_{2}$ for some copy
$S_{2}$ of $K_{5}$ in $X$. Since every vertex of $V(S_{2})\setminus\\{v\\}$ is
in $N_{X}(v)$, we have $|(V(S_{2})\setminus\\{v_{5},v\\})\cap N_{X}(v)|=3$,
and $X$ contains the three edges from $v_{5}$ to the vertices of
$V(S_{2})\setminus\\{v_{5},v\\}$. ∎

Since $X$ is a counterexample with minimum rank and $r(X-v+v_{4}v_{5})<r(X)$
by (11), we can apply part (a) of the theorem to ${\rm cl}(X-v+v_{4}v_{5})$ to
obtain a proper $K_{5}$-sequence ${\cal C}=(C_{1},\dots,C_{t})$ with

$r(X-v+v_{4}v_{5})={\rm val}(\operatorname{cl}(X-v+v_{4}v_{5}),{\cal C}).$
(13)

Since $K(N_{X}(v))\subseteq\operatorname{cl}(X-v+v_{4}v_{5})$ by Claim 5.10,
no $e\in K(N_{X}(v))$ can be a coloop in the matroid induced by
$\operatorname{cl}(X-v+v_{4}v_{5})$ and hence $K(N_{X}(v))\subseteq C_{\leq
t}$ by Lemma 3.3.

Recall that $N_{X}(v)=\\{v_{1},\dots,v_{k}\\}$. Let $C_{t+i}$ be a copy of
$K_{5}$ on $\\{v,v_{i},v_{i+1},v_{i+2},v_{i+3}\\}$ for $i=1,\dots,k-3$, and
let ${\cal
C}^{\prime\prime}=(C_{1},C_{2},\ldots,C_{t},C_{t+1},\ldots,C_{t+k-3})$ be the
$K_{5}$-sequence obtained by appending $(C_{t+1},\ldots,C_{t+k-3})$ to $\cal
C$. Since $K(N_{X}(v))\subseteq C_{\leq t}$, we have

${\rm val}(X,{\cal C}^{\prime\prime})={\rm val}(X-v,{\cal C})+k-(k-3)={\rm
val}(X-v,{\cal C})+3={\rm val}(X-v+v_{4}v_{5},{\cal C})+3.$

This gives

$\displaystyle{\rm val}(X,{\cal C}^{\prime\prime})$ $\displaystyle={\rm
val}(X-v+v_{4}v_{5},{\cal C})+3$ $\displaystyle\leq{\rm
val}(\operatorname{cl}(X-v+v_{4}v_{5}),{\cal C})+3$
$\displaystyle=r(X-v+v_{4}v_{5})+3$ $\displaystyle(\text{by
(\ref{eq:clique4})})$ $\displaystyle=r(X)$ $\displaystyle(\text{by
(\ref{eq:cliquerankX-v+v4v5})}).$

We may now use Lemma 3.3 to deduce that equality must hold throughout and that
$C_{\leq t+k-3}\subseteq{\rm cl}(X)$. Since $X$ is a flat and
$K(N_{X}(v))\subseteq C_{\leq t}$, we have $K(N_{X}(v))\subseteq X$ and hence
$v$ is a simplicial vertex of $K_{n}[X]$.

We complete the proof that (b) holds for $X$ by showing that $v$ has degree
three in some base of $X$. Choose a base $B^{\prime}$ of $X-v$ such that
$B^{\prime}$ contains a base of $K(N_{X}(v))$. Then $B^{\prime}$ can be
extended to a base $B$ of $X$. The facts that $B^{\prime}$ contains a base of
$K(N_{X}(v))$ and $|N_{X}(v)|\geq 4$ (since $X$ is cyclic), imply that $B$
will contain exactly three edges incident to $v$. Hence (b) holds for $X$.

By Lemma 3.3, $r(X)\leq|X\cup C_{\leq t}|-t$ holds for any proper
$K_{5}$-sequence $(C_{1},\dots,C_{t})$. Since $X$ is a counterexample to the
theorem, (a) does not hold for $X$ and hence

$r(X)<{\rm val}(X,{\cal C})$ for all proper $K_{5}$-sequences ${\cal C}$ of
$K_{n}$. (14)

Since $r(X)={\rm val}(X,\emptyset)$ when $|X|\leq 1$, (14) implies that
$|X|\geq 2$.

######  Claim 5.11.

$X$ is a cyclic flat in ${\cal C}_{2,n}^{1}$ and $d_{X}(v)\geq 4$ for all
$v\in V(X)$.

###### Proof.

Suppose $X$ is not a flat. Then $r(X+e)=r(X)$ for some $e\in E(K_{n})\setminus
X$. This implies that $V(X+e)=V(X)$, since the 0-extension property holds for
${\cal C}^{1}_{2,n}$, and the maximality of $|X|$ now gives $r(X)=r(X+e)={\rm
val}(X+e,{\cal C})\geq{\rm val}(X,{\cal C})$ for some proper $K_{5}$-sequence
$\cal C$ of $K_{n}$. This contradicts (14). Hence $X$ is a flat.

Suppose $X$ is not cyclic. Then $r(X-e)=r(X)-1$ for some $e\in X$. By the
minimality of $r(X)$, there is a proper $K_{5}$-sequence ${\cal
C}=(C_{1},\dots,C_{t})$ such that $r(X-e)={\rm val}(X-e,{\cal C})$. Since
$e\not\in\operatorname{cl}(X-e)$, $e\not\in C_{\leq t}$ by Lemma 3.3, and
hence $r(X)=r(X-e)+1={\rm val}(X-e,{\cal C})+1={\rm val}(X,{\cal C})$. This
again contradicts (14). Hence $X$ is cyclic.

The assertion that $d_{X}(v)\geq 4$ for all $v\in V(X)$ now follows since all
circuits in ${\cal C}_{2,n}^{1}$ have minimum degree at least four. ∎

Since $X$ is a cyclic flat by Claim 5.11, (b) holds for $X$ and hence there
exists a vertex $v\in V(X)$ such that $K(N_{X}(v))\subseteq X$, and $v$ has
degree three in some base of $X$. Then $r(X-v)=r(X)-3$ and we may apply (a) to
$X-v$ to obtain a proper $K_{5}$-sequence ${\cal C}=(C_{1},\dots,C_{t})$ with
$r(X-v)={\rm val}(X-v,{\cal C})$.

Let $N_{X}(v)=\\{v_{1},\dots,v_{k}\\}$ and let $C_{t+i}$ be a copy of $K_{5}$
on $\\{v,v_{i},v_{i+1},v_{i+2},v_{i+3}\\}$ for $i=1,\dots,k-3$. Let ${\cal
C}^{\prime\prime}=(C_{1},C_{2},\ldots,C_{t},C_{t+1},\ldots,C_{t+k-3})$ be the
$K_{5}$-sequence obtained by appending $C_{t+i}$ to $\cal C$ for
$i=1,\dots,k-3$. Since $K(N_{X}(v))\subseteq X-v$, we have

${\rm val}(X,{\cal C}^{\prime\prime})={\rm val}(X-v,{\cal C})+k-(k-3)={\rm
val}(X-v,{\cal C})+3=r(X-v)+3=r(X).$

This contradicts (14) and completes the proof of the theorem. ∎

######  Corollary 5.12.

The problem of deciding whether a given set $X\subseteq E(K_{n})$ is
independent in ${\cal C}_{2,n}^{1}$ is in ${\sf NP}\cap{\sf coNP}$.

###### Proof.

Theorem 5.7 immediately implies that the problem belongs to ${\sf coNP}$. The
fact that it also belongs to ${\sf NP}$ follows by applying either the
Schwartz-Zippel Lemma [41, 51], or the more elementary coordinate fixing
argument of Fekete and Jordán [16] to the $C_{2}^{1}$-cofactor matrix. ∎

##  6 Shellable covers

We use Theorem 5.7 to obtain an alternative formula for the rank function of
${\cal C}_{2,n}^{1}$ which is closely related to existing conjectures on the
rank functions of the generic 3-dimensional rigidity matroid [14, 24, 22] and
the generic 2-dimensional matrix completion matroid [25].

Let ${\mathcal{X}}$ be a family of subsets of $V(K_{n})$. A hinge of
${\mathcal{X}}$ is a pair of vertices $\\{x,y\\}$ with $X_{i}\cap
X_{j}=\\{x,y\\}$ for two distinct $X_{i},X_{j}\in{\mathcal{X}}$. Let
$H({\mathcal{X}})$ be the set of all hinges of ${\mathcal{X}}$. The degree
$\deg_{\mathcal{X}}(h)$ of a hinge $h$ of ${\mathcal{X}}$ is the number of
sets in ${\mathcal{X}}$ which contain $h$. The family ${\mathcal{X}}$ is said
to be $t$-thin if $|X_{i}\cap X_{j}|\leq t$ for all distinct
$X_{i},X_{j}\in{\mathcal{X}}$.

For $F\subseteq E(K_{n})$, we say that ${\mathcal{X}}$ is a cover of $F$ if
each set in ${\mathcal{X}}$ has cardinality at least five and each edge of $F$
is induced by at least one set in ${\mathcal{X}}$. Dress et al [14]
conjectured that 2-thin covers could be used to characterize the rank function
of ${\cal R}_{3,n}$. More specifically they defined the value of a family
${\mathcal{X}}$ as

${\rm val}_{\rm
D}({\mathcal{X}})=\sum_{X\in{\mathcal{X}}}(3|X|-6)\,-\sum_{h\in
H({\mathcal{X}})}(\deg_{\mathcal{X}}(h)-1)$

and conjectured that the rank of any $F\subseteq E(K_{n})$ in ${\cal R}_{3,n}$
is given by $\min\\{|F_{0}|+{{\rm val}_{\rm D}}({\mathcal{X}})\\}$ where the
minimum is taken over all $F_{0}\subseteq F$ and all 2-thin covers
${\mathcal{X}}$ of $F\setminus F_{0}$ with sets of size at least three. This
conjecture was shown to be false in [23] by giving an example of a 2-thin
family ${\mathcal{X}}$ with a negative value. Modified conjectures were given
in [24, 22] which placed further restrictions on the type of cover used to
obtain the minimum. We will show that these restricted 2-thin covers can be
used to characterize the rank function of the maximal abstract 3-rigidity
matroid ${\cal C}^{1}_{2,n}$.

A family ${\mathcal{X}}$ of subsets of $V(K_{n})$ is said to be $k$-shellable
if its elements can be ordered as a sequence $(X_{1},X_{2},\ldots,X_{m})$ so
that, for all $2\leq i\leq m$, $|X_{i}\cap\bigcup_{j=1}^{i-1}X_{j}|\leq k$.
Similarly, ${\mathcal{X}}$ is said to be $k$-degenerate if its elements can be
ordered as a sequence $(X_{1},X_{2},\ldots,X_{m})$ so that, for all $2\leq
i\leq m$, the set of hinges of the subfamily $\\{X_{1},X_{2},\ldots,X_{i}\\}$
which are contained in $X_{i}$ has size at most $k$. The two concepts are
related since every $k$-shellable family is ${{k}\choose{2}}$-degenerate.

######  Theorem 6.1.

Suppose $r$ is the rank function of ${\cal C}^{1}_{2,n}$ and $F\subseteq
E(K_{n})$. Then

$r(F)=\min\left\\{|F_{0}|+{\rm val}_{\rm D}({\mathcal{X}})\right\\},$ (15)

where the minimum is taken over all $F_{0}\subseteq F$ and all $4$-shellable,
$2$-thin covers ${\mathcal{X}}$ of $F\setminus F_{0}$ with sets of size at
least five.

It was conjectured in [22] that the expression on the right hand side of (15)
determines the rank function of ${\cal R}_{3,n}$ when the minimum is taken
over all $9$-degenerate 2-thin covers of $F\setminus F_{0}$ with sets of size
at least three. Theorem 6.1 solves the $C_{2}^{1}$-rigidity counterpart of
this conjecture (since 4-shellable covers are 6-degenerate).

The proof of Theorem 6.1 will take up the remainder of this section. Our first
result (Lemma 6.2) implies that both 4-shellable covers and 9-degenerate
covers give an upper bound on the rank function of any $K_{5}$-matroid.

Given a matroid $M$ on $E(K_{n})$ we say that a family ${\mathcal{X}}$ of
subsets of $V(K_{n})$ is $M$-degenerate if its elements can be ordered as a
sequence $(X_{1},X_{2},\ldots,X_{m})$ so that, for all $2\leq i\leq m$, the
set of hinges of the subfamily $\\{X_{1},X_{2},\ldots,X_{i}\\}$ which are
contained in $X_{i}$ is independent in $M$ (when viewed as a set of edges of
$K_{n}$).

######  Lemma 6.2.

Let $M$ be a $K_{5}$-matroid defined on $E(K_{n})$ and $r$ be its rank
function. Suppose $F\subseteq E(K_{n})$ and ${\mathcal{X}}$ is an
$M$-degenerate cover of $F$ with sets of size at least five. Then
$r(F)\leq{\rm val}_{\rm D}({\mathcal{X}})$.

###### Proof.

We use induction on $|{\mathcal{X}}|$. If ${\mathcal{X}}=\\{X\\}$ then
$H({\mathcal{X}})=\emptyset$ and Lemma 4.1 gives

$r(F)\leq\max\\{3|V(F)|-6,1\\}\leq 3|X|-6={\rm val}_{\rm D}({\mathcal{X}})$

since $V(F)\subseteq X$ and $|X|\geq 5$. Hence suppose that
$|{\mathcal{X}}|\geq 2$.

Let $H$ be the set of all edges of $K_{n}$ which are induced by a hinge of
$\cal X$. We may assume that $H\subseteq F$ since adding edges of $H$ to $F$
will not change ${\rm val}_{\rm D}({\mathcal{X}})$ or the fact that
${\mathcal{X}}$ is an $M$-degenerate cover of $F$, and can only increase
$r(F)$. Since ${\mathcal{X}}$ is $M$-degenerate, we can choose an ordering
$(X_{1},X_{2},\ldots,X_{m})$ of ${\mathcal{X}}$ so that, for all $2\leq i\leq
m$, the set of hinges of the subfamily $\\{X_{1},X_{2},\ldots,X_{i}\\}$ which
are contained in $X_{i}$ are independent in $M$ (when viewed as a set of edges
of $K_{n}$). Let $F_{m}$ be the set of edges in $F$ covered by $X_{m}$,
$H_{m}=F_{m}\cap H$ and $F^{\prime}=F\setminus(F_{m}{\setminus}H_{m})$. Since
$H_{m}$ is independent in $M$, we may choose a maximum independent subset
$B^{\prime}$ of $F^{\prime}$ with $H_{m}\subseteq B^{\prime}$. Since
${\mathcal{X}}^{\prime}={\mathcal{X}}\setminus\\{X_{m}\\}$ is an
$M$-degenerate cover of $F^{\prime}$, we may use induction to deduce that
$|B^{\prime}|\leq{\rm val}_{\rm D}({\mathcal{X}}^{\prime})$. Let $B$ be a
maximum independent subset of $F$ which contains $B^{\prime}$. Then $|B\cap
F_{m}|\leq 3|X_{m}|-6$ and hence $|B\setminus B^{\prime}|\leq
3|X_{m}|-6-|H_{m}|$. This gives

$r(F)=|B|=|B^{\prime}|+|B\setminus B^{\prime}|\leq{\rm val}_{\rm
D}({\mathcal{X}}^{\prime})+3|X_{m}|-6-|H_{m}|={\rm val}_{\rm
D}({\mathcal{X}}).$

∎

Lemma 6.2 and the facts that 4-shellable covers are $M$-degenerate in any
$K_{5}$-matroid on $E(K_{n})$ and $r(F)\leq|F_{0}|+r(F\setminus F_{0})$ for
all $F_{0}\subseteq F\subseteq E(K_{n})$, imply that the right hand side of
(15) gives an upper bound on $r(F)$. It follows that we may complete the proof
of Theorem 6.1 by exhibiting a set $F_{0}\subseteq F$ and a 4-shellable,
2-thin cover ${\mathcal{X}}$ of $F\setminus F_{0}$ with sets of size at least
five, such that $r(F)=|F_{0}|+{\rm val}_{\rm D}({\mathcal{X}})$. To do this,
we will choose sets $F_{0}$ and ${\mathcal{X}}$ suggested by a second
conjecture of Dress, see [9, 21, 44].

Given a graph $G=(V,E)$, a maximal clique of $G$ is a maximal subset
$X\subseteq V$ such that $G[X]$ is a complete graph. Suppose that $F\subseteq
E(K_{n})$ is a flat in ${\cal R}_{3,n}$. Let ${\mathcal{X}}^{*}$ be the set of
all maximal cliques in $K_{n}[F]$ of size at least three, and $F_{0}$ be the
set of edges in $F$ which are not covered by ${\mathcal{X}}^{*}$. Dress’s
second conjecture is that the rank of $F$ in ${\cal R}_{3,n}$ is equal to
$|F_{0}|+{\rm val}_{\rm D}({\mathcal{X}}^{*})$. We will show that a slightly
modified form of this conjecture holds for ${\cal C}_{2,n}^{1}$.

######  Theorem 6.3.

Suppose that $F\subseteq E(K_{n})$ is a flat in ${\mathcal{C}}_{2,n}^{1}$. Let
${\mathcal{X}}^{*}$ be the set of all maximal cliques in $K_{n}[F]$ of size at
least five, and $F_{0}$ be the set of edges in $F$ which are not covered by
${\mathcal{X}}^{*}$. Then ${\mathcal{X}}^{*}$ is a $4$-shellable, $2$-thin
cover of $F\setminus F_{0}$ and

$r(F)=|F_{0}|+{\rm val}_{\rm D}({\mathcal{X}}^{*}).$ (16)

###### Proof.

We proceed by contradiction. Suppose that the theorem does not hold for some
$F\subseteq E(K_{n})$ and that $F$ has been chosen to be as small as possible.
The hypothesis that $F$ is a flat and the axiom (A2) of abstract 3-rigidity
imply that ${\mathcal{X}}^{*}$ is 2-thin. We will obtain a contradiction by
showing that ${\mathcal{X}}^{*}$ is $4$-shellable and $r(F)=|F_{0}|+{\rm
val}_{\rm D}({\mathcal{X}}^{*})$.

We first show that $F$ is a cyclic set in ${\cal C}_{2,n}^{1}$. Suppose to the
contrary that some $e\in F$ is a coloop in ${\cal C}_{2,n}^{1}|_{F}$. Then
$e\in F_{0}$. Since $F$ is a flat, $F-e$ is a flat and ${\mathcal{X}}^{*}$ is
the set of all maximal cliques in $K_{n}[F-e]$ of size at least five. By the
minimality of $F$, ${\mathcal{X}}^{*}$ is 4-shellable and we have

$r(F)=r(F-e)+1=|F_{0}-e|+{\rm val}_{\rm D}({\mathcal{X}}^{*})+1=|F_{0}|+{\rm
val}_{\rm D}({\mathcal{X}}^{*}).$

This contradicts the choice of $F$. Hence $F$ is cyclic. Corollary 5.2 now
implies that $F_{0}=\emptyset$.

By Theorem 5.7(b), there exists a base $B$ of $F$ and a vertex $v\in V(F)$
such that $d_{B}(v)=3$ and $K(N_{F}(v))\subseteq F$. Then $r(F-v)=r(F)-3$ and
$\operatorname{cl}(F-v)=\operatorname{cl}(F)-v=F-v$ so $F-v$ is a flat in
${\mathcal{C}}_{2,n}^{1}$. Since $K(N_{F}(v))\subseteq F$ and $d_{F}(v)\geq
4$, $v$ is contained in a unique maximal clique $X_{v}\in{\mathcal{X}}^{*}$.

Suppose that $d_{F}(v)\geq 5$ and let $X_{v}^{\prime}=X_{v}-v$. Then
$|X_{v}|\geq 6$, so $|X^{\prime}_{v}|\geq 5$,
${\mathcal{X}}^{\prime}={\mathcal{X}}^{*}-X_{v}+X_{v}^{\prime}$ is the set of
maximal cliques of $K_{n}[F-v]$, and
$H({\mathcal{X}}^{\prime})=H({\mathcal{X}}^{*})$. We can now use the
minimality of $F$ to deduce that ${\mathcal{X}}^{\prime}$ and
${\mathcal{X}}^{*}$ are 4-shellable and

$r(F)=r(F-v)+3={\rm val}_{\rm D}({\mathcal{X}}^{\prime})+3={\rm val}_{\rm
D}({\mathcal{X}}^{*}).$

This contradicts the choice of $F$.

It remains to consider the case when $d_{F}(v)=4$. Then $|X_{v}|=5$ and
${\mathcal{X}}^{\prime}={\mathcal{X}}^{*}-X_{v}$ is the set of maximal cliques
of $K_{n}[F-v]$ of size at least five. Furthermore, the set $F_{0}^{\prime}$
of edges of $F-v$ which do not belong to a clique in ${\mathcal{X}}^{\prime}$
is given by $K(N_{X}(v))\setminus H({\mathcal{X}}^{*})$. We can now use
induction to deduce that ${\mathcal{X}}^{\prime}$ is 4-shellable and
$r(F-v)=|F_{0}^{\prime}|+{\rm val}_{\rm D}({\mathcal{X}}^{\prime})$. Let
$(X_{1},X_{2},\ldots,X_{t})$ be a 4-shellable ordering of the cliques in
${\mathcal{X}}^{\prime}$. Since $|X_{v}\cap V(F-v)|=4$,
$(X_{1},X_{2},\ldots,X_{t},X_{v})$ will be a 4-shellable ordering of the
cliques in ${\mathcal{X}}^{*}$ and hence ${\mathcal{X}}^{*}$ is 4-shellable.
In addition

$r(F)=r(F-v)+3=|F_{0}^{\prime}|+{\rm val}_{\rm
D}({\mathcal{X}}^{\prime})+3={\rm val}_{\rm D}({\mathcal{X}}^{*}).$

This contradicts the choice of $F$ and completes the proof of the theorem. ∎

As noted above, Theorem 6.1 follows from Lemma 6.2 and Theorem 6.3: Lemma 6.2
implies that the minimum on the right hand side of (15) is an upper bound on
$r(F)$, and we may apply Theorem 6.3 to $\operatorname{cl}(F)$ to deduce that
equality is attained.

Jackson and Jordán introduced $M$-degenerate 2-thin covers as ‘iterated
$2$-thin covers’ in [24] and conjectured that they determine the rank function
of ${\cal R}_{3,n}$. Theorem 6.1, Lemma 6.2 and the fact that $4$-shellable
covers are $M$-degenerate for any $K_{5}$-matroid imply that the conjectured
rank formulae in [24, Conjectures 3.2, 3.3] hold for the $C_{2}^{1}$-cofactor
matroid.

Cheng and Sitharam introduced $k$-degenerate 2-thin covers in [5] as
‘generalized partial $k$-trees’. They used 3-degenerate 2-thin covers to show
that the number of edges in any maximal ‘(3,6)-sparse subgraph’ of a graph
gives an upper bound on its rank in ${\cal R}_{3,n}$.

##  7 Sufficient connectivity conditions for $C_{2}^{1}$-rigidity of graphs

We say that a graph $G=(V,E)$ with $n$ vertices is $C_{2}^{1}$-rigid if its
edge set spans ${\cal C}_{2,n}^{1}$. It is $k$-connected if $n\geq k+1$ and
$G-U$ is connected for all $U\subset V$ with $|U|\leq k-1$. We use the results
of the preceding section to obtain sufficient connectivity conditions for a
graph to be $C_{2}^{1}$-rigid.

Jackson and Jordán conjectured in [24, Example 2] that, if $G=(V,F)$ is
5-connected and $F$ is a circuit in ${\cal R}_{3,n}$, then $G$ is rigid in
${\mathbb{R}}^{3}$. Our first result implies that the $C_{2}^{1}$-rigidity
counterpart of this conjecture is true.

######  Theorem 7.1.

Suppose $G=(V,F)$ is a 5-connected graph on $n$ vertices and $F$ is a cyclic
set in ${\cal C}_{2,n}^{1}$. Then $G$ is $C_{2}^{1}$-rigid.

###### Proof.

We may assume without loss of generality that $F$ is a flat since replacing
$F$ by its closure will not affect the hypotheses or conclusion of the
theorem. Corollary 5.2 now implies that every edge of $G$ belongs to a copy of
$K_{5}$. Let ${\cal X}$ be the set of all maximal cliques of size at least
five in $H$. By Theorem 6.3, ${\cal X}$ is a 4-shellable cover of $F$. The
hypothesis that $G$ is $5$-connected now implies that $|{\cal X}|=1$. Hence
$G$ is a clique with at least six vertices and the theorem holds for $G$. ∎

Tay [43] gave examples of 4-connected graphs $G=(V,F)$ on $n$ vertices which
are not rigid in ${\mathbb{R}}^{3}$ and are such that $F$ is a circuit in
${\cal R}_{3,n}$. The same graphs also show that the connectivity condition of
Theorem 7.1 is best possible since they are not ${\cal C}_{2,n}^{1}$-rigid and
$F$ is a circuit in ${\cal C}_{2,n}^{1}$.

Lovász and Yemini [32] proved that every 6-connected graph is rigid in
${\mathbb{R}}^{2}$ and conjectured that every 12-connected graph is rigid in
${\mathbb{R}}^{3}$. Our second result solves the $C_{2}^{1}$-rigidity
counterpart of their conjecture.

######  Theorem 7.2.

Let $G=(V,F)$ be a $12$-connected graph on $n$ vertices and $S\subset E$ with
$|S|\leq 6$. Then $G-S$ is $C_{2}^{1}$-rigid.

###### Proof.

Suppose, for a contradiction, that $G-S$ is not $C_{2}^{1}$-rigid. We may
assume that $G$ and $S$ have been chosen to be a counterexample such that
$|V|$ is as small as possible and, subject to this condition, $|F\setminus S|$
is as large as possible. Then $F\setminus S$ is a flat in ${\cal C}_{2,n}^{1}$
since if $e\in\operatorname{cl}(F\setminus S)\setminus(F\setminus S)$, then we
may apply induction to $(F+e,S-e)$ to deduce that $G-S+e$ is $C_{2}^{1}$-rigid
and hence, since $e\in\operatorname{cl}(F\setminus S)$, $G-S$ is
$C_{2}^{1}$-rigid.

Let ${\cal X}$ be the set of all maximal cliques of size at least five in
$G-S$, $\hat{F}_{0}$ be the set of edges in $G-S$ not covered by any member of
${\cal X}$ and put $F_{0}=\hat{F}_{0}\cup S$. By Theorem 6.3, ${\cal X}$ is a
4-shellable 2-thin cover of $F\setminus F_{0}$ and $|\hat{F}_{0}|+{\rm
val}_{\rm D}({\cal X})=r(F\setminus S)<3|V(G)|-6$. Since $|S|\leq 6$ this
gives

$|F_{0}|+{\rm val}_{\rm D}({\cal X})<3|V(G)|.$ (17)

For each vertex $v\in V(F)$, let $F_{0}^{v}$ be the set of edges in $F_{0}$
incident to $v$, $k_{v}$ be the number and ${\cal
X}^{v}=\\{X_{1}^{v},\dots,X_{k_{v}}^{v}\\}$ be the set of cliques in $\cal X$
which contain $v$, and $H_{v}$ be the set of hinges of ${\cal X}^{v}$ that
contain $v$. Note that $H_{v}\subseteq H({\cal X})$ and ${\rm deg}_{{\cal
X}^{v}}(h)={\rm deg}_{\cal X}(h)$ for each $h\in H_{v}$.

######  Claim 7.3.

For each $v\in V(F)$, either $F_{0}^{v}\neq\emptyset$ or $k_{v}\geq 2$.

###### Proof.

Suppose that $F_{0}^{v}=\emptyset$ and $k_{v}=1$, i.e., $v$ is not incident to
an edge of $F_{0}$ and is contained in exactly one maximal clique
$X_{1}^{v}\in{\cal X}$. Since $\cal X$ covers $F{\setminus}F_{0}$, we have
$K(N_{G}(v))\subset G$ and either $G-v$ is 12-connected or $G=K_{13}$. Since
$K_{13}$ is $C_{2}^{1}$-rigid, the first alternative must occur, and we may
apply induction to deduce that $G-v-S$ is $C_{2}^{1}$-rigid. This and
$d_{G}(v)\geq 12$ in turn imply that $G$ is $C_{2}^{1}$-rigid, which is a
contradiction. ∎

The $C_{2}^{1}$-rigidity of $G-S$ will follow easily from our next claim.

######  Claim 7.4.

For all $v\in V(G)$,

$\frac{|F_{0}^{v}|}{2}+\sum_{i=1}^{k_{v}}\left(3-\frac{6}{|X_{i}^{v}|}\right)-\sum_{h\in
H_{v}}\left(\frac{{\rm deg}_{\cal X}(h)-1}{2}\right)\geq 3.$ (18)

###### Proof.

If $k_{v}=0$, then, by 12-connectivity, $|F_{0}^{v}|\geq 12$ holds, which
implies (18). Hence we may suppose that $k_{v}\geq 1$.

Suppose that $k_{v}=1$, i.e., ${\cal X}^{v}=\\{X_{1}^{v}\\}$. Then
$H_{v}=\emptyset$. By Claim 7.3, $|F_{0}^{v}|\geq 1$. Hence, if
$|X_{1}^{v}|\geq 12$, then (18) holds. It remains to consider the subcase when
$5\leq|X_{1}^{v}|\leq 11$. As $v$ has degree at least 12 in $G$, we have
$(|X_{1}^{v}|-1)+|F_{0}^{v}|\geq 12$. This implies that

$\frac{|F_{0}^{v}|}{2}+\left(3-\frac{6}{|X_{1}^{v}|}\right)\geq
9.5-\frac{|X_{1}^{v}|}{2}-\frac{6}{|X_{1}^{v}|}.$

When $5\leq|X_{1}^{v}|\leq 11$, the right side of this inequality is at least
$3$, and we get (18).

Hence we may assume that $k_{v}\geq 2$. Put $c_{1}=0$ and let
$c_{i}=\left|\left(\bigcup_{j=1}^{i-1}X_{j}^{v}\right)\cap X_{i}^{v}\right|-1$
for $2\leq i\leq k_{v}$. Then $c_{i}$ represents the contribution of
$X_{i}^{v}$ to the ‘hinge count’ at $v$ in ${\rm
val}_{D}(X_{1}^{v},\dots,X_{i}^{v})$ and we have

$\sum_{h\in H_{v}}({\rm deg}_{{\cal X}^{v}}(h)-1)=\sum_{i=1}^{k_{v}}c_{i}.$

Since ${\cal X}$ is 4-shellable, ${\cal X}^{v}$ is 4-shellable. Hence, by
reordering the sequence $(X_{1}^{v},\dots,X_{k_{v}}^{v})$ if necessary, we can
suppose that $c_{i}\leq 3$ for all $2\leq i\leq k_{v}$. Also, since ${\cal
X}^{v}$ is 2-thin, $c_{2}\leq 1$. Since $|X_{i}^{v}|\geq 5$ for all $1\leq
i\leq k_{v}$, we may deduce that

$\sum_{i=1}^{2}\left(3-\frac{6}{|X_{i}^{v}|}-\frac{c_{i}}{2}\right)\geq(3-\tfrac{6}{5})+(3-\tfrac{6}{5}-\tfrac{1}{2})>3,$

and, for all $3\leq i\leq k_{v}$,

$3-\frac{6}{|X_{i}^{v}|}-\frac{c_{i}}{2}\geq 3-\tfrac{6}{5}-\tfrac{3}{2}>0.$

Combining these inequalities, we obtain

$\frac{|F_{0}^{v}|}{2}+\sum_{i=1}^{k_{v}}\left(3-\frac{6}{|X_{i}^{v}|}\right)-\sum_{h\in
H_{v}}\left(\frac{{\rm deg}_{\cal
X}(h)-1}{2}\right)=\frac{|F_{0}^{v}|}{2}+\sum_{i=1}^{k_{v}}\left(3-\frac{6}{|X_{i}^{v}|}-\frac{c_{i}}{2}\right)>3.$

This completes the proof of the claim. ∎

Taking the sum of (18) over all vertices of $G$, we obtain

$|F_{0}|+{\rm val}_{\rm D}({\cal X})=|F_{0}|+\sum_{X\in{\cal
X}}(3|X|-6)-\sum_{h\in H({\cal X})}({\rm deg}_{\cal X}(h)-1)\geq 3|V(G)|.$

This contradicts (17) and completes the proof of the theorem. ∎

Lovász and Yemini [32] gave examples of 11-connected graphs $G=(V,F)$ which
are not rigid in ${\mathbb{R}}^{3}$. These graphs also show that the
connectivity condition of Theorem 7.2 is best possible since they are not
${\cal C}_{2,n}^{1}$-rigid. The 12-connected graph $G$ consisting of two large
complete graphs joined by a set $T$ of 12 disjoint edges fails to be ${\cal
C}_{2,n}^{1}$-rigid if we delete 7 edges from $T$. This shows that the bound
on $|S|$ in Theorem 7.2 is best possible.

##  8 Problems and Remarks

Many interesting problems remain.

  1. 1.

Developing a deterministic polynomial time algorithm to solve the
combinatorial optimization problem of evaluating the rank formulae in Theorems
5.7 and 6.1 is our most obvious open problem. These formuae imply that the
decision problem of determining whether the rank takes any given value is in
NP$\cap$co-NP, so it is likely that such an algorithm exists. But it is not
clear how to use the existing theory of submodular functions to design such an
algorithm since our rank formulae are significantly different to other known
matroid rank formulae.

  2. 2.

Let $M_{0}$ be the rank ${{d+2}\choose{2}}$ truncation of ${\cal R}_{d,n}$ (or
equivalently, of any other $K_{d+2}$-matroid on $E(K_{n}))$ for $n\geq d+2$.

######  Conjecture 8.1.

The rank function of the free elevation of $M_{0}$ is given by

$r(F)=\min\\{|F\cup C_{\leq t}|-t:(C_{1},\dots,C_{t})\text{ is a proper
$K_{d+2}$-sequence in $K_{n}$}\\}$

for all $F\subseteq E(K_{n})$.

This would imply that the free elevation of $M_{0}$ is the unique maximal
$K_{d+2}$-matroid on $K_{n}$, and hence verify Graver’s conjecture that there
exists a unique maximal abstract $d$-rigidity matroid. Conjecture 8.1 holds
for $d=3$ by Theorem 5.7. It is not difficult to see that it also holds for
for $d=1,2$, see for example [26].

Conjecture 8.1 would imply, in particular, that the free elevation of $M_{0}$
is an abstract $d$-rigidity matroid. This would follow from Theorem 4.2 if we
could show that the free elevation of $M_{0}$ has the 0-extension property.

  3. 3.

Testing generic 4-dimensional rigidity of graphs is recognized as being an
even more difficult problem than generic 3-dimensional rigidity. One reason
for this is Whiteley’s result that ${\cal R}_{4,n}$ is not the unique maximal
abstract 4-rigidity matroid since $K_{6,6}$ is independent in ${\cal
C}_{3,n}^{2}$ but not in ${\cal R}_{4,n}$. Even so, Conjecture 3.4 may still
be robust enough to deal with such bad examples.

######  Conjecture 8.2.

The rank function of ${\cal R}_{4,n}$ is given by

$r(F)=\min\\{|F\cup C_{\leq t}|-t:(C_{1},\dots,C_{t})\text{ is a proper
$\\{K_{6},K_{6,6}\\}$-sequence in $K_{n}$}\\}$

for all $F\subseteq E(K_{n})$.

This would imply that ${\cal R}_{4,n}$ is the free elevation of its rank 36
truncation, and also that ${\cal R}_{4,n}$ is the unique maximal
$\\{K_{6},K_{6,6}\\}$-matroid on $E(K_{n})$ i.e. the unique maximal matroid in
the poset of all matroids on $E(K_{n})$ in which every copy of $K_{6}$ and
$K_{6,6}$ is a circuit.

  4. 4.

A simpler example of a matroid in which all small circuits are copies of
complete or complete bipartite graphs arises in the context of the rank 2
completion of partially filled skew-symmetric matrices, see Bernstein [2]. All
copies of $K_{4}$ and $K_{3,3}$ are circuits in this matroid and we conjecture
that it is the unique maximal $\\{K_{4},K_{3,3}\\}$-matroid on $E(K_{n})$.
Combined with Conjecture 3.4, this would imply that its rank function is given
by

$r(F)=\min\\{|F\cup C_{\leq t}|-t:(C_{1},\dots,C_{t})\text{ is a proper
$\\{K_{4},K_{3,3}\\}$-sequence in $K_{n}$}\\}$

for all $F\subseteq E(K_{n})$.

#### Acknowledgement

We would like to thank Steve Noble for bringing our attention to the theory of
matroid erections and for helpful conversations on this topic. We also thank
the referee whose careful reading and detailed suggestions significantly
improved the presentation of this paper.

This work was supported by JST CREST Grant Number JPMJCR14D2, JSPS KAKENHI
Grant Number 18K11155 and EPSRC overseas travel grant EP/T030461/1.

## References

  * [1] L. Asimow and B. Roth, The rigidity of graphs, Trans. Amer. Math. Soc., 245 (1978), 279–289.
  * [2] D. I. Bernstein, Completion of tree metrics and rank 2 matrices, Linear Algebra Appl., 533,(2017), 1–13.
  * [3] L. J. Billera, Homology of smooth splines: generic triangulations and a conjecture of Strang, Trans. Amer. Math. Soc., 310 (1988), 325–340.
  * [4] T. Brylawski, Constructions, in Theory of Matroids, N.L. White ed., Cambridge Univ. Press, Cambridge 1986, 127–223.
  * [5] J. Cheng and M. Sitharam, Maxwell-independence: a new rank estimate for the 3-dimensional generic rigidity matroid, J. Comb. Theory, Ser. B., 105 (2014), 26–43.
  * [6] K. Clinch, B. Jackson and S. Tanigawa, Abstract 3-rigidity and bivariate $C_{2}^{1}$-splines I: Whiteley’s maximality conjecture, Discrete Analysis, to appear.
  * [7] C. R. Coullard and L. Hellerstein, Independence and port oracles for matroids, with an application to computational learning theory, Combinatorica, 16 (1996), 189–208.
  * [8] H. Crapo, Erecting geometries, Proc. 2nd Chapel Hill Conf. on Comb. Math, 1970, 74–99.
  * [9] H. Crapo, A. Dress and T.-S. Tay, Problem 4.2, in Matroid Theory (J.E. Bonin, J.G. Oxley and B. Servatius eds., Seattle, WA, 1995), Contemp. Math., 197, Amer. Math. Soc., Providence, RI, 1996, 414.
  * [10] J. Cruickshank, On spaces of infinitesimal motions and three dimensional Henneberg extensions, Discrete & Computational Geometry, 51 (2014), 702–721.
  * [11] J. Cruickshank, D. Kitson, and S. Power, The generic rigidity of triangulated spheres with blocks and holes, J. Combin. Theory Ser. B, 122 (2017), 550–577.
  * [12] J. Cruickshank, D. Kitson, and S. Power, The generic minimal rigidity of a partially triangulated torus, Proc. London Math. Soc., 118 (2019), 1277–1304.
  * [13] R. Duke, Matroid erection and duality, European Journal of Combinatorics, 8 (1987), 367–370.
  * [14] A. Dress, A. Drieding, and H. Haegi, Classification of mobile molecules by category theory, in Symmetries and Properties of Non-Rigid Molecules: A Comprehensive Study, J. Maruana, J. Serre (Eds.), Elsevier, Amsterdam, 1983, 39–58.
  * [15] J. Edmonds, Systems of discrete representatives and linear algebra, J. Res. Nat. Bur. Standards, 71B (1967), 241–247.
  * [16] Z. Fekete and T. Jordán, Rigid realizations of graphs on small grids, Computational Geometry, 32 (2005), 216-222.
  * [17] W. Finbow-Singh and W. Whiteley, Isostatic block and hole frameworks, SIAM J. Discrete Math., 27 (2013), 991-1020.
  * [18] A. L. Fogelsanger, The generic rigidity of minimal cycles, PhD Thesis, Cornell University, 1988.
  * [19] H. Gluck, Almost all simply connected closed surfaces are rigid, in Geometric topology (Proc. Conf., Park City, Utah, 1974), Lecture Notes in Math., Vol. 438, Springer, Berlin, 1975, 225–239.
  * [20] J. E. Graver, Rigidity matroids, SIAM Journal on Discrete Mathematics, 4 (1991), 355–368.
  * [21] J. E. Graver, B. Servatius, and H. Servatius, Combinatorial rigidity, Amer. Math. Soc., 1993.
  * [22] B. Jackson, Rigidity of graphs and frameworks, presentation at the DIMACS Workshop: Distance geometry: Theory and Applications, 2016, available at http://archive.dimacs.rutgers.edu/Workshops/Distance/Slides/jackson.pdf
  * [23] B. Jackson and T. Jordán, The Dress conjectures on rank in the 3-dimensional rigidity matroid, Adv. in Appl. Math., 35 (2005), 355–367.
  * [24] B. Jackson and T. Jordán, On the rank function of the 3-dimensional rigidity matroid, Int. J. Comput. Geometry Appl. 16 (2006), 415–430.
  * [25] B. Jackson, T. Jordán and S. Tanigawa, Combinatorial conditions for the unique completability of low rank matrices, SIAM J. Discrete Math., 28 (2014), 1797–1819.
  * [26] B. Jackson and S. Tanigawa, Maximal matroids in weak order posets, preprint available at https://arxiv.org/abs/2102.09901.
  * [27] N. Katoh and S. Tanigawa, A proof of the Molecular conjecture. Discrete Comput. Geom., 45 (2011), 647–700.
  * [28] D. Knuth, Random matroids, Discrete Math, 12 (1975), 341–358.
  * [29] G. Laman, On graphs and the rigidity of skeletal structures, J. Eng. Math., 4 (1970), 331–340.
  * [30] M. Las Vergnas, On certain constructions for matroids, Proc. 5th British Conf. on Combinatorics, Utilitas Math, 1976, 395–404.
  * [31] L. Lovász, Singular spaces of matrices and their application in combinatorics, Bulletin of the Brazilian Mathematical Society, 20 (1989), 87–99.
  * [32] L. Lovász and Y. Yemini, On generic rigidity in the plane, SIAM J. Algebraic Discrete Methods, 3 (1982), 91–98.
  * [33] H. Maehara, On Graver’s conjecture concerning the rigidity problem of graphs, Discrete Comput. Geom., 6 (1991), 339–342.
  * [34] J. C. Maxwell, On the calculation of the equilibrium and stiffness of frames, Philos. Mag., 27 (1864), 294–299.
  * [35] E. Nevo, On embeddability and stresses of graphs, Combinatorica, 27 (2007), 465–472.
  * [36] H. Nguyen, Constructing the free erection of a geometry, J. Comb. Theory, Ser. B., 27 (1979), 216–224.
  * [37] V. H. Nguyen, On abstract rigidity matroids, SIAM J. Discrete Math., 24 (2010), 363–369.
  * [38] J. G. Oxley, Matroid theory, 2nd edition, Oxford University Press, 2011.
  * [39] H. Pollaczek-Geiringer, Über die Gliederung ebener Fachwerke, Zeitschrift für Angewandte Mathematik und Mechanik (ZAMM), 7 (1927), 58–72.
  * [40] B. Schulze and W. Whiteley, Rigidity and scene anaysis, in Handbook of Discrete and Computational Geometry, J. E. Goodman, J. O’Rourke, and C. D. Tóth (editors), 3rd edition, CRC Press, Boca Raton, FL, 2017, 1593-1632.
  * [41] J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, Journal of the ACM, 27 (1980), 701–717.
  * [42] M. Sitharam, Recent developments in 3D bar-joint rigidity characterization, presentation at the BIRS Workshop: Advances in Combinatorial and Geometric Rigidity Theory, 2015, available at http://www.birs.ca/events/2015/5-day-workshops/15w5114/videos
  * [43] T.-S. Tay, On generically dependent bar frameworks in space, Structural Topology, 20 (1993), 27-48.
  * [44] T.-S. Tay, On the generic rigidity of bar frameworks, Adv. in Appl. Math., 23 (1999), 14–28.
  * [45] T.-S. Tay and W. Whiteley, Recent advances in the generic rigidity of structures, Structural Topology, 9 (1984), 31–38.
  * [46] T.-S. Tay and W. Whiteley, Generating isostatic frameworks, Structural Topology, 11 (1985), 20–69.
  * [47] W. T. Tutte, The factorization of linear graphs, J. London Math. Soc., 22 (1947), 107–111.
  * [48] W. Whiteley, The geometry of bivariate $C^{1}_{2}$-splines, technical report, 1990.
  * [49] W. Whiteley, Combinatorics of bivariate splines, in Applied Geometry and Discrete Mathematics — the Victor Klee Festschrift, DIMACS, vol. 4, AMS, 1991, 587–608.
  * [50] W. Whiteley, Some matroids from discrete applied geometry, in Matroid theory (Seattle, WA, 1995), 171–311, Contemp. Math., 197, Amer. Math. Soc., Providence, RI, 1996.
  * [51] R. Zippel, Probabilistic algorithms for sparse polynomials, in Proceedings of the International Symposium on Symbolic and Algebraic Computation, 1979, 216–226.