# Ordering circuits of matroids

Cameron Crenshaw James Oxley
Department of Mathematics
Louisiana State University
Baton Rouge, U.S.A
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The cycles of a graph give a natural cyclic ordering to their edge-sets, and
these orderings are consistent in that two edges are adjacent in one cycle if
and only if they are adjacent in every cycle in which they appear together. An
orderable matroid is one whose set of circuits admits such a consistent
ordering. In this paper, we consider the question of determining which
matroids are orderable. Although we are able to answer this question for non-
binary matroids, it remains open for binary matroids. We give examples to
provide insight into the potential difficulty of this question in general. We
also show that, by requiring that the ordering preserves the three arcs in
every theta-graph restriction of a binary matroid $M$, we guarantee that $M$
is orderable if and only if $M$ is graphic.

##  1 Introduction

In a graph, the edges of each cycle have an ordering on them. But this is not
true for the circuits of a matroid. The goal of this paper is to see to what
extent we can distinguish graphic matroids by an ordering condition that
mimics the ordering condition on the edges of the cycles of a graph.

A _reversible cyclic ordering_ of a finite set $X$ is an arrangement of the
elements of $X$ on the vertices of an $n$-gon with one element at each vertex.
Elements $x_{1}$ and $x_{2}$ of $X$ are _adjacent_ in the ordering when the
corresponding vertices of the $n$-gon lie on a common edge. Figure 1 shows an
example of such an ordering $(x_{1}\ x_{2}\ \dots\ x_{n})$. The same ordering
can also be denoted, for example, by $(x_{3}\ x_{2}\ x_{1}\ x_{n}\ \dots\
x_{4})$. Throughout this paper, all orderings are assumed to be reversible
cyclic orderings unless stated otherwise.

$x_{1}$$x_{2}$$x_{3}$$\dots$$x_{n-1}$$x_{n}$ Figure 1: A reversible cyclic
ordering.

In a graph, there is an associated ordering on the edge set of each cycle.
These orderings have the property that two edges are adjacent in an ordering
of a given cycle if and only if they are adjacent in the ordering of every
cycle in which the edges appear together.

Unlike the cycles of a graph, the circuits of a matroid are sets without
inherent order. We give a matroid $M$ an ordering by imposing an ordering on
each of its circuits. Such an ordering of $M$ is _consistent_ if, for every
pair $\\{e,f\\}$ of distinct elements of $E(M)$ and every pair
$\\{C,C^{\prime}\\}$ of circuits of $M$ with $\\{e,f\\}\subseteq C\cap
C^{\prime}$, if $e$ and $f$ are adjacent in the ordering of $C$, then $e$ and
$f$ are adjacent in the ordering of $C^{\prime}$. A matroid is called
_orderable_ if it has a consistent ordering.

The notation for matroids in this paper follows [5] with one modification. We
call a matroid $N$ a  _series extension_ of a matroid $M$ if $N$ can be
obtained from $M$ by a (possibly empty) sequence of single-element series
extensions; a _parallel extension_ is defined analogously.

The primary goal of this work is characterizing orderable matroids. As noted
above, our first examples of orderable matroids are graphic matroids.

######  Proposition 1.

If $M$ is a graphic matroid, then $M$ is orderable.

However, orderability is not enough to distinguish graphic matroids from non-
graphic matroids. Our main result specifies all non-binary orderable matroids.
The infinitely many such matroids are all built from $U_{2,n}$ for some
$n\geqslant 4$ by using two operations, which we now describe.

For a matroid $M$ without coloops, a series extension of $M$ is _balanced_ if,
for some integer $k$ exceeding one, each element of $M$ is replaced by $k$
elements in series. We call $k$ the _order_ of the balanced series extension.
The second operation is a generalization of the operation of adding an element
in parallel to another. A _theta-graph_ is a graph consisting of a pair of
distinct vertices and three internally disjoint paths between them. Now, let
$P$ be a nonempty subset of a series class of a matroid $M$. Fix an element
$t$ of $P$, contract $P-t$, and relabel $t$ as $t^{\prime}$ to obtain
$M^{\prime}$. Let $N$ be the cycle matroid of a theta-graph with series
classes $\\{t^{\prime}\\}$, $P$, and $P^{\prime}$, where $|P^{\prime}|=|P|$.
Finally, let $M^{\prime\prime}$ be the 2-sum of $M^{\prime}$ and $N$ with
basepoint $t^{\prime}$. The operation transforming $M$ into $M^{\prime\prime}$
is called _parallel-path addition_. The _size_ of this addition is $|P|$; we
call $P$ and $P^{\prime}$ _parallel paths_ of $M^{\prime\prime}$, and say that
$M^{\prime\prime}$ is obtained from $M$ by adding $P^{\prime}$ _in parallel_
to $P$. The following theorem is the main result of the paper.

######  Theorem 2.

Let $M$ be a connected non-binary matroid. Then $M$ is orderable if and only
if it can be obtained from $U_{2,n}$ for some $n\geqslant 4$ by a sequence of
the following operations:

  1. (i)

balanced series extension; and

  2. (ii)

parallel-path addition.

When we come to consider binary orderable matroids, we encounter considerable
difficulty. For example, as we show in the next section, $F_{7}^{\ast}$ and
$M^{\ast}(K_{5})$ are not orderable, yet each has an orderable series
extension. In view of this, it is natural to consider additional conditions
that one can add to orderability in order to distinguish graphic matroids
within binary matroids. The next theorem gives three equivalent such
additional conditions.

######  Theorem 3.

The following are equivalent for a binary matroid $M$:

  1. (i)

$M$ is graphic.

  2. (ii)

every minor of $M$ is orderable.

  3. (iii)

every series minor of $M$ is orderable.

  4. (iv)

every parallel minor of $M$ is orderable.

Although, as noted above, there are orderable binary matroids that are not
graphic, we know of no counterexample to the following.

######  Conjecture 4.

A $3$-connected orderable binary matroid is graphic.

We have, however, made the following progress.

######  Theorem 5.

A $4$-connected regular orderable matroid is graphic.

Another condition one can add to orderability to distinguish graphic matroids
within binary matroids involves the theta-graphs in a matroid $M$, where a
_theta-graph_ in $M$ is a restriction of $M$ that is isomorphic to the cycle
matroid of a theta-graph. Equivalently, it is a restriction of $M$ that is
isomorphic to a series extension of $U_{1,3}$. The series classes of a theta-
graph are called its _theta-arcs_. A subset $B$ of a circuit $C$ is a _block_
if there is a listing $b_{1},b_{2},\dots,b_{k}$ of the elements of $B$ such
that $b_{i}$ and $b_{i+1}$ are adjacent for all $i$ in $[k-1]$. A consistent
ordering of a matroid $M$ is a _theta-ordering_ if every theta-arc of every
theta-graph of $M$ is a block in the ordering; $M$ is _theta-orderable_ if it
has a theta-ordering.

Theta-orderability turns out to be equivalent to a concept introduced by
Wagner [9]. For distinct circuits $C$ and $D$ of a matroid $M$, an _arc_ of
$C$ is a minimal non-empty subset $A$ of $C$ such that $A\cup D$ contains at
least two circuits. A set $\\{A_{1},A_{2},A_{3}\\}$ of arcs of a common
circuit is _incompatible_ if $A_{1}\cap A_{2}\cap A_{3}\neq\emptyset$ and
$A_{i}-(A_{j}\cup A_{k})\neq\emptyset$ for all $i$, $j$, and $k$ such that
$\\{i,j,k\\}=\\{1,2,3\\}$. In Section 4, we prove the following
characterization of theta-orderable binary matroids. The equivalence of (i)
and (ii) is Wagner’s main result [9].

######  Theorem 6.

The following are equivalent for a binary matroid $M$:

  1. (i)

$M$ is graphic;

  2. (ii)

$M$ has no set of incompatible arcs; and

  3. (iii)

$M$ is theta-orderable.

The following characterization of theta-orderable non-binary matroids will
also be proved in Section 4.

######  Theorem 7.

Let $M$ be a connected non-binary matroid. Then $M$ is theta-orderable if and
only if $M$ is a parallel extension of a balanced series extension of
$U_{2,n}$ for some $n\geqslant 4$.

In Section 2, after some preliminaries, we prove Theorem 3. The proof of our
main result, Theorem 2, is in Section 3, and Theorem 5 is proved in Section 5.

##  2 Preliminaries

Our first proposition collects some basic properties of orderability. These
properties will be used frequently and often implicitly. We omit their
straightforward proofs.

######  Proposition 8.

Let $M$ be a matroid.

  1. (i)

If $M$ is orderable, then $M\backslash e$ is orderable for all $e\in E(M)$.

  2. (ii)

If $r(M)\leqslant 2$, then $M$ is orderable.

  3. (iii)

$M$ is orderable if and only if the connected components of $M$ are orderable.

  4. (iv)

$M$ is orderable if and only if $\operatorname{si}(M)$ is orderable.

Next, we note a partial converse to Proposition 1.

######  Proposition 9.

If $M$ is an orderable binary matroid with a spanning circuit, then $M$ is
graphic.

###### Proof.

Let $C$ be a spanning circuit of $M$ and $e$ be an element in $C$. Fix a
consistent ordering of $M$, and take a standard binary representation of $M$
with respect to the basis $C-e$. Now construct a graph $G$ beginning with a
cycle having edge set $C$, ordered consistently with the fixed ordering of
$M$. Now, for each element $f$ of $E(M)-C$, let $C_{f}$ be the fundamental
circuit of $f$ with respect to $C-e$. Because $C_{f}-f$ is a block in the
ordering, we may add an edge $f$ to $G$ as a chord of $C$ so that it forms a
cycle with edge set $C_{f}$. The result is a graph whose cycle matroid has
ground set $E(M)$, has $C-e$ as a basis, and has the same fundamental circuits
with respect to this basis as $M$. Since $M$ and $M(G)$ are binary, we deduce
that $M=M(G)$. ∎

We now note a necessary condition for a matroid to be orderable, along with
some consequences of this condition.

######  Proposition 10.

Let $M$ be a simple matroid and $X$ be a subset of $E(M)$ with $|X|\geqslant
3$. If there are elements $e$ and $f$ in $E(M)-X$ such that $X\cup e$ and
$X\cup f$ are both circuits of $M$, then $M$ is not orderable.

###### Proof.

Assume to the contrary that $M$ has a consistent ordering. Notice that the
ordering of $X\cup f$ is obtained from that of $X\cup e$ by replacing $f$ with
$e$. Let $a$ and $b$ be the elements in $X$ that are adjacent to $e$. Using
strong circuit elimination on $X\cup e$ and $X\cup f$, we obtain a circuit
$C\subseteq X\cup\\{e,f\\}$ containing $e$ but not $a$, and another
$C^{\prime}\subseteq X\cup\\{e,f\\}$ containing $f$ but not $b$.

As $C$ is not properly contained in either $X\cup e$ or $X\cup f$, it must
contain both $e$ and $f$. Further, $M$ is simple, so $C\cap X$ is nonempty.
Since $a$ and $b$ are the only elements in $X$ adjacent to $e$ or $f$, it
follows that $C=\\{e,f,b\\}$. By symmetry, $C^{\prime}=\\{e,f,a\\}$.

Circuit elimination applied to $C$ and $C^{\prime}$ now yields a circuit $D$
that does not contain $e$. Then $D\subseteq\\{a,b,f\\}$. Since $|X|\geqslant
3$, it follows that $D$ is a proper subset of $X\cup f$, a contradiction. ∎

######  Corollary 11.

Let $M$ be a matroid of rank at least three and $X$ be a circuit-hyperplane of
$M$. If $E(M)-X$ is not a parallel class of $M$, then the matroid obtained
from $M$ by relaxing $X$ is not orderable.

######  Corollary 12.

The only orderable whirl is $U_{2,4}$.

We now prove Theorem 3, whose proof relies on the next lemma and its
corollary. The following technical property facilitates the statements of
these results. A matroid $M$ has the $(e,f,g)$-_property_ if

  * (i)

$M$ has a circuit containing $\\{e,f,g\\}$;

  * (ii)

$e$, $f$, and $g$ are distinct; and

  * (iii)

$M$ has a circuit $D$ containing $f$ but neither $e$ nor $g$ and, with the
exception of at most one $d$ in $D$, there is a circuit of $M$ containing
$\\{e,f,g,d\\}$.

######  Lemma 13.

If a matroid $M$ has the $(e,f,g)$-property, then $f$ is not adjacent to both
$e$ and $g$ in a consistent ordering of $M$.

###### Proof.

Suppose $M$ has the $(e,f,g)$-property and $f$ is adjacent to both $e$ and
$g$. Then, in the circuit $D$ of condition (iii), $f$ is adjacent to elements
$d_{1}$ and $d_{2}$ of $D-f$. But $M$ has a circuit containing
$\\{e,f,g,d_{i}\\}$ for some $i$ in $\\{1,2\\}$, a contradiction. ∎

######  Corollary 14.

Let $C$ be a circuit of a matroid $M$. Suppose there is an element $c$ of $C$
so that $M$ has the $(e,c,g)$-property for every choice of $e$ and $g$ in
$C-c$. Then $M$ does not have a consistent ordering.

###### Proof of Theorem 3.

Since graphic matroids are orderable and the class of graphic matroids is
minor-closed, (i) implies (ii)-(iv). Let $\mathcal{S}$ be the set

$\\{F_{7},F_{7}^{\ast},M^{\ast}(K_{5}),M^{\ast}(K_{3,3}),M^{\ast}(K_{3,3}^{\prime}),M^{\ast}(K_{3,3}^{\prime\prime}),M^{\ast}(K_{3,3}^{\prime\prime\prime}),R_{10}\\}.$

By results of Tutte [8] and Bixby [1, 2], $\mathcal{S}$ contains all binary
matroids that are excluded minors, excluded series minors, or excluded
parallel minors for the class of graphic matroids. Thus we can prove that (i)
follows from each of (ii)-(iv) by showing that none of the matroids in
$\mathcal{S}$ is orderable.

$3$$1$$5$$7$$2$$6$$4$ Figure 2: The matroid $F_{7}$.

Let $F_{7}$ be labelled as in Figure 2. Using the element 1 in the circuit
$\\{1,2,3,4\\}$, Corollary 14 gives that $F_{7}$ has no consistent ordering.

1234567 Figure 3: The matroid $F_{7}^{\ast}$.

Let $F_{7}^{\ast}$ be labelled as in Figure 3. Consider the circuits
$C_{1}=\\{1,2,3,4\\}$, $C_{2}=\\{1,3,5,7\\}$, and $C_{3}=\\{2,4,5,7\\}$. The
ordering of a four-element circuit is uniquely determined by a single pair of
non-adjacent elements, and the automorphism group of $F_{7}^{\ast}$ is doubly
transitive. Thus we may assume that $C_{1}$ has the ordering $(1\ 2\ 3\ 4)$.

Since 1 and 3 are not adjacent in $C_{1}$, it follows that $C_{2}$ has the
ordering $(1\ 5\ 3\ 7)$. Thus 5 and 7 are non-adjacent, so $C_{3}$ has the
ordering $(2\ 5\ 4\ 7)$. However, the elements of the set $\\{1,2,5\\}$ are
now pairwise adjacent, so the circuit $\\{1,2,5,6\\}$ cannot be ordered. Thus
$F_{7}^{\ast}$ has no consistent ordering.

0123456789 Figure 4: The graph $K_{5}$.

Let $M^{\ast}(K_{5})$ be labelled as in Figure 4, and assume that
$M^{\ast}(K_{5})$ has a consistent ordering. Let $C$ be the circuit
$\\{1,2,3,4\\}$. By symmetry, we may assume its ordering is $(1\ 2\ 3\ 4)$.
This ordering and the circuit $\\{1,2,4,7,8,9\\}$ give that 1 and 8 are not
adjacent, so the circuit $\\{0,1,5,8\\}$ must be ordered $(0\ 1\ 5\ 8)$.
Similarly, the circuit $\\{1,2,3,5,6,7\\}$ gives that 2 and 6 are not
adjacent, so $\\{0,2,6,9\\}$ must be ordered $(0\ 2\ 9\ 6)$. Now 0 is adjacent
to 1, 6, and 8 in the circuit $\\{0,1,4,6,7,8\\}$, a contradiction.

123456789 Figure 5: The graph $K_{3,3}$.

Let $M^{\ast}(K_{3,3})$ be labelled as in Figure 5. We shall use Corollary 14
letting $c$ be the element 1 in the circuit $C=\\{1,3,5,8\\}$ of
$M^{\ast}(K_{3,3})$. The cases $\\{e,g\\}=\\{3,5\\}$ and $\\{e,g\\}=\\{3,8\\}$
are symmetric, and the circuits $C$ and $\\{1,3,5,7,9\\}$ certify that $M$ has
the $(3,1,5)$-property with $D=\\{1,4,8,9\\}$. The circuit $\\{1,5,6,8,9\\}$
certifies that $M$ has the $(5,1,8)$-property with $D=\\{1,2,6,9\\}$.
Corollary 14 now implies that $M^{\ast}(K_{3,3})$ has no consistent ordering.

123456789$a$ Figure 6: The graph $K_{3,3}^{\prime}$.

The next two cases will also use Corollary 14. Let
$M^{\ast}(K_{3,3}^{\prime})$ be labelled as in Figure 6, and let $c$ be the
element 3 in the circuit $C=\\{3,6,7,8\\}$ of $M^{\ast}(K_{3,3}^{\prime})$.
The cases $\\{e,g\\}=\\{6,7\\}$ and $\\{e,g\\}=\\{6,8\\}$ are symmetric, and
the circuit $\\{2,3,5,6,7,8\\}$ certifies that $M$ has the $(6,3,7)$-property
with $D=\\{1,2,3\\}$. The circuit $C$ certifies that $M$ has the
$(7,3,8)$-property with $D=\\{3,6,9\\}$. Corollary 14 now implies that
$M^{\ast}(K_{3,3}^{\prime})$ has no consistent ordering.

123456789$a$$b$ Figure 7: The graph $K_{3,3}^{\prime\prime}$.

Let $M^{\ast}(K_{3,3}^{\prime\prime})$ be labelled as in Figure 7, and let $c$
be the element 1 in the circuit $C=\\{1,3,5,8,a,b\\}$ of
$M^{\ast}(K_{3,3}^{\prime\prime})$. When $\\{e,g\\}\subseteq C-3$, the circuit
$C$ certifies that $M$ has the $(e,1,g)$-property with $D=\\{1,2,3\\}$. Each
of the remaining cases uses $D=\\{1,4,7,a\\}$. The cases $\\{e,g\\}=\\{3,5\\}$
and $\\{e,g\\}=\\{3,8\\}$ are symmetric, and the circuit $\\{1,3,5,7,9,a,b\\}$
certifies that $M$ has the $(3,1,5)$ property. The circuits
$\\{1,3,4,6,8,a,b\\}$ and $\\{1,3,5,7,9,a,b\\}$ certify the
$(3,1,a)$-property. Finally, the circuit $\\{1,3,4,6,8,a,b\\}$ certifies the
$(3,1,b)$-property. Corollary 14 now implies that
$M^{\ast}(K_{3,3}^{\prime\prime})$ has no consistent ordering.

123456789$a$$b$$c$ Figure 8: The graph $K_{3,3}^{\prime\prime\prime}$.

Let $M^{\ast}(K_{3,3}^{\prime\prime\prime})$ be labelled as in Figure 8. We
begin by noting that there must be at least one adjacent pair in the set
$\\{1,4,7\\}$ due to the circuit $\\{1,4,7,a,c\\}$. By symmetry, we may assume
that 1 and 4 are adjacent.

Combining this adjacent pair with the three-element circuits, we get that 2145
is a block in the circuit $\\{1,2,4,5,9,b,c\\}$. Therefore 4 is not adjacent
to 9, $b$, or $c$. This means that, in the circuit $\\{3,4,5,9,b,c\\}$, we
must have 4 adjacent to 3. Using the three-element circuit $\\{4,5,6\\}$, we
now have that 4 is adjacent to 1, 3, and 6. Therefore the circuit
$\\{1,3,4,6,8,a,b\\}$ cannot be ordered consistently, and
$M^{\ast}(K_{3,3}^{\prime\prime\prime})$ has no consistent ordering.

123456789 Figure 9: A graft corresponding to $R_{10}$.

Let $M$ be the graft matroid of $K_{3,3}$ where the graft element $e_{\gamma}$
corresponds to the set of boxed vertices in Figure 9. Then $M\cong R_{10}$.
Using Corollary 14 again, let $c$ be the element 1 in the circuit
$C=\\{1,2,4,5\\}$ of $M$. When $\\{e,g\\}=\\{2,4\\}$, the circuit
$\\{1,2,4,6,8,9\\}$ certifies the $(2,1,4)$-property when $D=\\{1,3,4,6\\}$.
When $\\{e,g\\}=\\{2,5\\}$, the circuit $\\{1,2,5,6,7,9\\}$ certifies the
$(2,1,5)$-property with $D=\\{1,3,7,9\\}$. Finally, when
$\\{e,g\\}=\\{4,5\\}$, the circuit $\\{1,4,5,6,7,e_{\gamma}\\}$ certifies the
$(4,1,5)$-property with $D=\\{1,6,8,e_{\gamma}\\}$. Corollary 14 now implies
that $R_{10}$ has no consistent ordering. ∎

We conclude this section with a pair of examples that indicate the potential
difficulty of characterizing orderable binary matroids.

######  Example 15.

This example describes a 12-element orderable series extension of
$F_{7}^{\ast}$, which we refer to as $O_{1}$. Thus, the pair $O_{1}$ and
$F_{7}^{\ast}$ demonstrates that the class of binary orderable matroids is not
closed under the taking of series minors. Let $F_{7}^{\ast}$ be labelled as in
Figure 3. We obtain $O_{1}$ by adding $1^{\prime}$, $2^{\prime}$, and
$7^{\prime}$ in series with 1, 2, and 7, respectively, and adding $4^{\prime}$
and $4^{\prime\prime}$ in series with 4. Figure 10 gives a consistent ordering
of the circuits of $O_{1}$.

$(1\ 5\ 1^{\prime}\ 2^{\prime}\ 6\ 2)$ $(1\ 5\ 1^{\prime}\ 7^{\prime}\ 3\ 7)$
$(2\ 6\ 2^{\prime}\ 7^{\prime}\ 3\ 7)$ $(3\ 4\ 5\ 4^{\prime}\ 6\
4^{\prime\prime})$

$(1\ 4^{\prime}\ 2^{\prime}\ 1^{\prime}\ 4\ 3\ 4^{\prime\prime}\ 2)$ $(1\ 7\
4\ 1^{\prime}\ 7^{\prime}\ 4^{\prime\prime}\ 6\ 4^{\prime})$ $(2\ 7\ 4\ 5\
4^{\prime}\ 2^{\prime}\ 7^{\prime}\ 4^{\prime\prime})$

Figure 10: A consistent ordering of $O_{1}$.

######  Example 16.

Let $K_{5}$ be labelled as in Figure 4. We obtain a regular, non-graphic
matroid $O_{2}$ from $M^{\ast}(K_{5})$ by adding elements $0^{\prime}$ and
$2^{\prime}$ in series with 0 and 2, respectively. Figure 11 gives a
consistent ordering of $O_{2}$.

$(4\ 6\ 5\ 7)$ $(2^{\prime}\ 1\ 2\ 6\ 5\ 8\ 9)$ $(0^{\prime}\ 1\ 0\ 9\ 3\ 4\
6)$ $(2^{\prime}\ 1\ 2\ 4\ 7\ 8\ 9)$

$(3\ 7\ 8\ 9)$ $(2\ 1\ 2^{\prime}\ 3\ 7\ 5\ 6)$ $(0^{\prime}\ 1\ 0\ 8\ 7\ 4\
6)$ $(0^{\prime}\ 1\ 0\ 9\ 3\ 7\ 5)$

$(0^{\prime}\ 2^{\prime}\ 3\ 4\ 2\ 0\ 8\ 5)$ $(0^{\prime}\ 2^{\prime}\ 9\ 0\
2\ 4\ 7\ 5)$ $(2^{\prime}\ 0^{\prime}\ 6\ 2\ 0\ 8\ 7\ 3)$

$(2\ 1\ 2^{\prime}\ 3\ 4)$ $(0\ 1\ 0^{\prime}\ 5\ 8)$ $(0\ 2\ 6\ 0^{\prime}\
2^{\prime}\ 9)$ $(3\ 4\ 6\ 5\ 8\ 9)$

Figure 11: A consistent ordering of $O_{2}$.

##  3 A Characterization of Non-Binary Orderable Matroids

In this section, we prove Theorem 2. We begin by finding the orderable series
extensions of uniform matroids and their consistent orderings. These results
allow us to characterize the non-binary orderable matroids that are
3-connected, from which we obtain the full characterization using the
canonical tree decomposition of Cunningham and Edmonds [3].

A uniform matroid is binary if and only if it is graphic. Thus, the binary
uniform matroids are certainly orderable, as are those whose rank is at most
two. Proposition 10 implies this list is complete.

######  Corollary 17.

A uniform matroid is orderable if and only if it is binary or has rank at most
two.

The next two results deduce the structure of a consistent ordering of a series
extension of a non-binary uniform matroid, and show that such an ordering can
be used to consistently order the underlying uniform matroid. For a non-coloop
element $e$ of a matroid $M$, we denote the series class of $M$ containing $e$
by $S_{e}$ or sometimes by $S_{e}(M)$.

Let $M$ be a matroid with a consistent ordering. Suppose $X$ and $Y$ are
disjoint subsets of a circuit $C$ of $M$. We say $X$ and $Y$ are _adjacent_ if
there is an adjacent pair of elements $x$ and $y$, where $x$ belongs to $X$
and $y$ belongs to $Y$. Let $\mathcal{B}$ be the union of a set of blocks that
belong to a common circuit of $M$. If there is a listing
$B_{1},B_{2},\dots,B_{k}$ of the blocks in $\mathcal{B}$ such that $B_{i}$ and
$B_{i+1}$ are adjacent for all $i$ in $[k-1]$, then $\mathcal{B}$ is a
_section_. Finally, let $S$ be a series class of $M$. If a block of $M$ is
contained in $S$ and is maximal with this property, then it is called an _$S$
-block_.

######  Lemma 18.

Let $M$ be an orderable series extension of a non-binary uniform matroid
$U_{r,n}$ and fix a consistent ordering of $M$. Let $C$ be a circuit of $M$,
and let $x$ and $y$ be elements of $C$ from distinct series classes of $M$.

  1. (i)

If a section $K$ in $C$ is adjacent to a pair of $S_{x}$-blocks, then $K$ must
contain an $S_{y}$-block.

  2. (ii)

Every series class $S$ of $M$ has the same number of $S$-blocks.

###### Proof.

For (i), suppose to the contrary that there is a section $K$ in $C$ that
contains no $S_{y}$-block and is adjacent to a pair of distinct
$S_{x}$-blocks. As $M$ is non-binary, $2\leqslant r\leqslant n-2$ and there is
a circuit $D_{x}$ of $M$ that contains $K$ and $S_{x}$ but avoids $S_{y}$. Let
$D_{y}=(D_{x}-S_{x})\cup S_{y}$. Observe that, since $M$ is a series extension
of $U_{r,n}$, the set $D_{y}$ is a circuit. The consistency of $D_{y}$ with
$C$ implies that $K$ is not adjacent to $S_{y}$-blocks in $D_{y}$, but the
consistency of $D_{y}$ with $D_{x}$ gives that $K$ can only be adjacent to
$S_{y}$-blocks in $D_{y}$, a contradiction.

We now deduce (ii) from (i). Let $S$ be a series class of $E(M)$ for which the
number of $S$-blocks is as large as possible. We may assume this number
exceeds one. In a circuit $C$ containing $S$, let $K$ be a minimal section
that is adjacent to a pair of distinct $S$-blocks. Note that the number of
such minimal sections in $C$ equals the number of $S$-blocks. Let $S^{\prime}$
be a series class of $M$ contained in $C$ that is distinct from $S$. Part (i)
implies there is an $S^{\prime}$-block in $K$ and, as $K$ contains no
$S$-blocks, (i) further implies that there is exactly one $S^{\prime}$-block
in $K$. Thus there are the same number of $S^{\prime}$-blocks as $S$-blocks.
Part (ii) now follows. ∎

######  Proposition 19.

Let $U_{r,n}$ be a non-binary uniform matroid. If a series extension of
$U_{r,n}$ is orderable, then so is $U_{r,n}$.

###### Proof.

Let $M$ be an orderable series extension of $U_{r,n}$ and fix a consistent
ordering of $M$. By Lemma 18(ii), there is an integer $k\geqslant 1$ such that
every series class of $M$ is divided into exactly $k$ blocks. If $k=1$, the
result follows immediately, so assume $k\geqslant 2$.

Let $[n]$ be the ground set of $U_{r,n}$. Consider the circuit $C$ of $M$ that
contains the set $\\{1,2,\dots,r+1\\}$. Label the $S_{1}$-blocks in $C$ as
$B_{1},B_{2},\dots,B_{k}$, such that $B_{i}$ and $B_{i+1}$ abut a section
$K_{i}$ that does not contain $S_{1}$-blocks, as in Figure 12.

$B_{1}$$K_{1}$$B_{2}$$K_{2}$$B_{3}$$\ddots$$B_{k}$$K_{k}$ Figure 12: The
circuit $C$ in the proof of Proposition 19.

Applying Lemma 18(i), we see that each section $K_{i}$ contains exactly one
$S_{j}$-block for all $j$ in $\\{2,3,\dots,r+1\\}$. Thus, $B_{i}\cup K_{i}$
defines a permutation of $\\{1,2,\dots,r+1\\}$ that begins with 1. We show
this permutation is the same for all $i$.

Without loss of generality, suppose the block in $K_{1}$ adjacent to $B_{1}$
is an $S_{2}$-block. If the block in $K_{2}$ adjacent to $B_{2}$ is an
$S_{j}$-block with $j\neq 2$, then the $S_{j}$-blocks in $K_{1}$ and $K_{2}$
abut a section that contains no $S_{2}$-block, contradicting Lemma 18(i). Thus
the block in $K_{2}$ adjacent to $B_{2}$ is an $S_{2}$-block. Repeating this
argument gives that $B_{1}\cup K_{1}$ and $B_{2}\cup K_{2}$ define the same
permutation on $\\{1,2,\dots,r+1\\}$. It follows that $B_{i}\cup K_{i}$
defines the same permutation on $\\{1,2,\dots,r+1\\}$ for all $i$ in $[n]$.
Thus $B_{i}\cup K_{i}\cup B_{i+1}$ defines the same reversible cyclic ordering
on $\\{1,2,\dots,r+1\\}$ for all $i$ in $[n]$; it is this reversible cyclic
ordering that we extract from $C$ and use to order the circuit
$\\{1,2,\dots,r+1\\}$ in $U_{r,n}$.

In this way, every circuit of $U_{r,n}$ is ordered using the corresponding
circuit of $M$. Since the ordering of $M$ is consistent, so too is the
ordering it gives to $U_{r,n}$. ∎

######  Theorem 20.

Let $U_{r,n}$ be a non-binary uniform matroid of rank at least three. If $M$
is a matroid with a series minor isomorphic to $U_{r,n}$, then $M$ is not
orderable.

###### Proof.

By [5, Proposition 5.4.2], we may write $U_{r,n}=M\backslash X/Y$ where each
element of $Y$ is in series with an element of $M\backslash X$ not in $Y$. By
Corollary 17, the matroid $U_{r,n}$ is not orderable. Therefore, by
Proposition 19, neither is its series extension $M\backslash X$. Thus, $M$ is
not orderable. ∎

Recall that, in a balanced series extension $N$ of a matroid $M$ without
coloops, each element of $M$ is replaced by $k$ elements in series for some
positive integer $k$.

######  Lemma 21.

Let $N$ be a balanced series extension of $U_{2,n}$ for some $n\geqslant 4$.
Then $N$ is orderable.

###### Proof.

Let $[n]$ be the ground set of $U_{2,n}$. For each $x$ in $E(U_{2,n})$, let
$\\{x_{0},x_{1},\dots,x_{k-1}\\}$ be the series class $S_{x}$ of $N$ that
corresponds to $x$. Subscript arithmetic will be done modulo $k$. Let
$\mathcal{C}_{1}$ be the set of circuits of $N$ containing $S_{1}$. For the
circuit $C=S_{1}\cup S_{x}\cup S_{y}$ in $\mathcal{C}_{1}$ with $x<y$, give
$C$ the ordering

$(y_{0}\ 1_{0}\ x_{0}\ y_{1}\ 1_{1}\ x_{1}\ \dots\ y_{k-1}\ 1_{k-1}\
x_{k-1}).$

To see that the circuits in $\mathcal{C}_{1}$ are consistent, suppose $e$ and
$f$ belong to common circuits in $\mathcal{C}_{1}$. Then at least one of $e$
and $f$, say $e$, is in $S_{1}$. If $f$ is in $S_{1}$, then $e$ and $f$ are
never adjacent. Otherwise, $f$ is in $S_{z}$ for some $z>1$, so $e=1_{s}$ and
$f=z_{t}$ for some $s$ and $t$. If $s=t$, then $e$ and $f$ are always
adjacent; if $s\neq t$, then $e$ and $f$ are never adjacent.

Now let $\mathcal{C}_{2}$ be the set of circuits of $N$ not containing
$S_{1}$. For the circuit $D=S_{x}\cup S_{y}\cup S_{z}$ in $\mathcal{C}_{2}$
with $1<x<y<z$, give $D$ the ordering

$(z_{1}\ x_{0}\ y_{1}\ z_{2}\ x_{1}\ y_{2}\ ...\ z_{0}\ x_{k-1}\ y_{0}).$

Note that $x_{i}$ is always adjacent to $y_{i+1}$ and $z_{i+1}$. Further, the
blocks $z_{i}x_{i-1}y_{i}$ are ordered so that $y_{i}$ is always adjacent to
$z_{i+1}$. Thus, the circuits in $\mathcal{C}_{2}$ are consistent with those
in $\mathcal{C}_{1}$.

Finally, the circuits in $\mathcal{C}_{2}$ are consistent. Suppose instead
that there are circuits $C$ and $D$ in $\mathcal{C}_{2}$ and elements $x_{s}$
and $y_{t}$ in $C\cap D$ so that $x_{s}$ and $y_{t}$ are adjacent in $C$ but
not in $D$. Assume $x<y$. From $C$, we have that $t=s+1$, but, from $D$, we
have that $t\neq s+1$, a contradiction. ∎

The following proposition specializes some of the results about uniform
matroids to $U_{2,n}$ with $n\geqslant 4$. These rank-two uniform matroids
will serve as the foundation from which all non-binary orderable matroids are
built.

######  Proposition 22.

Let $M$ be an orderable series extension of $U_{2,n}$ for some $n\geqslant 4$,
and fix a consistent ordering of $M$. Then

  1. (i)

for all series classes $S$ of $M$, every $S$-block of the ordering consists of
a single element; and

  2. (ii)

$M$ is a balanced series extension of $U_{2,n}$.

###### Proof.

Statement (ii) follows from combining (i) with Lemma 18(ii), so it suffices to
show (i). Let $E(U_{2,n})=[n]$. Suppose, to the contrary, that $M$ has an
$S_{1}$-block $B$ of size at least two.

Applying Lemma 18(i), we have that $B$ is adjacent to both an $S_{2}$-block
and an $S_{3}$-block in the circuit of $M$ containing $\\{1,2,3\\}$. Let
$1_{2}$ be the element of $B$ adjacent to the $S_{2}$-block and let $1_{3}$ be
the element of $B$ adjacent to the $S_{3}$-block, where $1_{2}$ and $1_{3}$
are necessarily distinct. In the circuit of $M$ containing $\\{1,2,4\\}$,
Lemma 18(i) now gives that $B$ is adjacent to both an $S_{2}$-block and an
$S_{4}$-block. Consistency dictates that $1_{2}$ is again adjacent to the
$S_{2}$-block. Therefore $1_{3}$ is now adjacent to the $S_{4}$-block.

Now consider the circuit of $M$ containing $\\{1,3,4\\}$. Consistency with the
two aforementioned circuits requires that $1_{3}$ be adjacent to both an
$S_{3}$-block and an $S_{4}$-block. As $|B|\geqslant 2$, this is a
contradiction. ∎

The next theorem identifies all orderable matroids that are 3-connected and
non-binary.

######  Theorem 23.

If $M$ is a $3$-connected non-binary orderable matroid, then $M\cong U_{2,n}$
for some $n\geqslant 4$.

The next two results will be used in the proof of this theorem.

######  Proposition 24.

If $M$ is an orderable matroid, then $M$ has no minor isomorphic to $U_{3,5}$.

###### Proof.

Assume instead that $M\backslash X/Y\cong U_{3,5}$, with $X$ coindependent and
$Y$ independent. Then $M^{\ast}/X\backslash Y\cong U_{2,5}$ where $M^{\ast}/X$
has rank two. Thus, after deleting a set $Z$ of loops from $M^{\ast}/X$, we
obtain a parallel extension of $U_{2,n}$ for some $n\geqslant 5$. This makes
$M\backslash(X\cup Z)$ an orderable series extension of $U_{n-2,n}$,
contradicting Theorem 20. ∎

######  Proposition 25.

If $M$ is an orderable matroid, then $M$ has no minor isomorphic to
$\mathcal{W}^{3}$.

The proof of this proposition will rely on the next lemma and its corollary.
This second pair of results will use the following modification of the
$(e,f,g)$-property. A matroid $M$ has the _series_ $(e,f,g)$-_property_ if

  * (i)

$M$ has a circuit containing $\\{e,f,g\\}$;

  * (ii)

$S_{f}(M)$ is distinct from both $S_{e}(M)$ and $S_{g}(M)$; and

  * (iii)

$M$ has a circuit $D$ containing $f$ but not $\\{e,g\\}$ and, for each $d$ in
$D$, there is a circuit of $M$ containing $\\{e,f,g,d\\}$.

Note that $e$ and $g$ may be equal in this definition.

######  Lemma 26.

Suppose that $M$ has the series $(e,f,g)$-property and that $N$ is a series
extension of $M$. Then, in a consistent ordering of $N$, if $S_{e}(N)\neq
S_{g}(N)$, then no $S_{f}(N)$-block is adjacent to both an $S_{e}(N)$-block
and an $S_{g}(N)$-block; and, if $S_{e}(N)=S_{g}(N)$, then no $S_{f}(N)$-block
is adjacent to two $S_{e}(N)$-blocks.

###### Proof.

Let $D$ be the circuit of $M$ whose existence is guaranteed by condition
(iii). Let $D^{\prime}$ be the circuit of $N$ corresponding to $D$, and let
$B_{f}$ be an $S_{f}(N)$-block. Notice $D$ must have an element $d$ not in
$\\{e,f,g\\}$, so $D^{\prime}-(S_{e}(N)\cup S_{f}(N)\cup S_{g}(N))$ is
nonempty. If $S_{e}(N)=S_{g}(N)$ and $B_{f}$ is adjacent to two
$S_{e}(N)$-blocks, then $e$ is not in $D$, so $B_{f}$ is not adjacent to any
elements of $D^{\prime}-B_{f}$, a contradiction. Now suppose $S_{e}(N)\neq
S_{g}(N)$ and, without loss of generality, suppose $e$ is in $D$ but $g$ is
not. If $B_{f}$ is adjacent to an $S_{e}(N)$-block and an $S_{g}(N)$-block,
then all of the elements in $D^{\prime}-B_{f}$ adjacent to $B_{f}$ are in
$S_{e}(N)$. This contradicts the fact that $B_{f}$ is adjacent to an
$S_{e}(N)$-block and an $S_{g}(N)$-block in a common circuit. ∎

######  Corollary 27.

Let $C$ be a circuit of a matroid $M$. Suppose that $C$ contains an element
$c$ so that $M$ has the series $(e,c,g)$-property for every choice of $e$ and
$g$ in $C-c$. Then no series extension of $M$ is orderable.

###### Proof of Proposition 25.

Assume instead that $M\backslash X/Y\cong\mathcal{W}^{3}$, with $X$
coindependent and $Y$ independent. Let $L$ be the set of loops of
$M^{\ast}/X$, and let $N$ denote $M^{\ast}/(X\cup L)$. Note that $N$ is a
loopless rank-3 extension of $\mathcal{W}^{3}$, so $\operatorname{si}(N)$ is
$3$-connected. Further, $N$ is a parallel extension of $\operatorname{si}(N)$,
which makes $N^{\ast}$ an orderable series extension of
$\operatorname{co}(N^{\ast})$.

######  27.1.

$\operatorname{si}(N)$ is ternary.

To see this, first note that, as $N^{\ast}$ is orderable, it has no
$U_{3,5}$-minor by Proposition 24. Thus, $\operatorname{si}(N)$ has no
$U_{2,5}$-minor. As $\operatorname{si}(N)$ is $3$-connected and its rank and
corank each exceed two, [5, Proposition 12.2.15] gives that
$\operatorname{si}(N)$ has no $U_{3,5}$-minor. The rank of $F_{7}^{\ast}$
exceeds three, so $\operatorname{si}(N)$ also has no $F_{7}^{\ast}$-minor.

Finally, suppose $\operatorname{si}(N)$ has an $F_{7}$-minor. Then
$\operatorname{si}(N)|Z\cong F_{7}$ for some set $Z$. As $F_{7}$ has no
$\mathcal{W}^{3}$-minor, $\operatorname{si}(N)$ has an element $e$ not in $Z$.
Then $\operatorname{si}(N)/e$ has a $U_{2,5}$-restriction, a contradiction. We
conclude that $\operatorname{si}(N)$ has no $F_{7}$-minor. Thus 27.1 holds.

By 27.1, $\operatorname{si}(N)$ has the form $PG(2,3)-K$, where $K$ is a
restriction of $O_{7}$, the complement of $\mathcal{W}^{3}$ in $PG(2,3)$. The
matroid $O_{7}$ is obtained from $M(K_{4})$ by adding a point freely to an
existing 3-point line; the fifteen restrictions of $O_{7}$ are given in Figure
13. In the remainder of the proof, we eliminate each possibility for $K$.

Number $n$ of elements | Restrictions of $O_{7}$ with $n$ elements
---|---
0 | $U_{0,0}$
1 | $U_{1,1}$
2 | $U_{2,2}$
3 |  $U_{2,3}$, $U_{3,3}$
4 |  $U_{2,4}$, $U_{3,4}$, $U_{2,3}\oplus U_{1,1}$
5 |  $U_{2,4}\oplus U_{1,1}$, $P(U_{2,3},U_{2,3})$, $U_{2,4}\oplus_{2}U_{2,3}$
6 |  $P(U_{2,4},U_{2,3})$, $M(K_{4})$, $\mathcal{W}^{3}$
7 | $O_{7}$
Figure 13: Choices for $K$, the complement of $\operatorname{si}(N)$ in
$PG(2,3)$. 123456789$a$$b$$c$$d$ Figure 14: The matroid $PG(2,3)$.

If $K=U_{0,0}$, then $\operatorname{si}(N)=PG(2,3)$. Let
$\operatorname{si}(N)$ be labelled as in Figure 14. Suppose $N^{\ast}$ has a
consistent ordering, and let $B_{x}$, $B_{y}$, and $B_{z}$ be $S_{x}$-,
$S_{y}$-, and $S_{z}$-blocks in a common circuit $C$ of $N^{\ast}$, where $x$,
$y$, and $z$ are elements of $E(\operatorname{si}(N))$. Assume also that
$B_{y}$ is adjacent to $B_{x}$ and $B_{z}$. Then, by Lemma 26,
$\operatorname{co}(N^{\ast})$ does not have the series $(x,y,z)$-property. We
show next that

######  27.2.

$x$, $y$, and $z$ are collinear in $\operatorname{si}(N)$, and $x\neq z$.

Suppose $x$, $y$, and $z$ are not collinear in $\operatorname{si}(N)$. Then
one easily finds circuits of $\operatorname{co}(N^{\ast})$ that verify the
series $(x,y,z)$-property in $\operatorname{co}(N^{\ast})$, a contradiction.
Similarly, when $x=z$ there are circuits of $\operatorname{co}(N^{\ast})$ that
verify the series $(x,y,z)$-property in $\operatorname{co}(N^{\ast})$, a
contradiction. Thus, 27.2 holds.

By symmetry, we may assume that $C$ is the circuit $\\{1,2,3,4,5,6,7,8,9\\}$
of $\operatorname{co}(N^{\ast})$; let $C^{\prime}$ be the corresponding
circuit of $N^{\ast}$. Consider an $S_{1}$-block $B$ in $C^{\prime}$. The
block $B$ is adjacent to an $S_{e}$\- and $S_{f}$-block for some $e$ and $f$
in $C-1$. By 27.2, the elements $1$, $e$, and $f$ are collinear in
$\operatorname{si}(N)$; without loss of generality, say $e=2$ and $f=3$. Let
$B_{3}$ be the $S_{3}$-block adjacent to $B$. By repeatedly applying 27.2, we
have that $B_{3}$ is adjacent to an $S_{2}$-block $B_{2}$, the block $B_{2}$
is adjacent to another $S_{1}$-block $B_{1}$, the block $B_{1}$ is adjacent to
another $S_{3}$-block, and so on. It follows that $C^{\prime}$ has a proper
subset $X$ of elements not adjacent to any element of $C^{\prime}-X$, a
contradiction.

123456789

132654879

Figure 15: Two geometric representations of the matroid $AG(2,3)$.

If $K=U_{2,4}$, then $\operatorname{si}(N)=AG(2,3)$. Figure 15 gives two
labelled copies of $\operatorname{si}(N)$ in order to illustrate some of the
symmetries of this matroid. Using Corollary 27, let $c$ be the element 1 in
the circuit $C=\\{1,2,3,4,5,6\\}$ of $\operatorname{co}(N^{\ast})$. When
$e=g=2$, the circuits $C$ and $\\{1,2,3,7,8,9\\}$ certify that
$\operatorname{co}(N^{\ast})$ has the series $(2,1,2)$-property with
$D=\\{1,3,4,6,7,9\\}$. Since $\operatorname{co}(N^{\ast})$ has a doubly
transitive automorphism group, it follows that $\operatorname{co}(N^{\ast})$
has the series $(e,1,e)$-property for each $e$ in $C$. When
$\\{e,g\\}=\\{2,3\\}$, the circuits $C$ and $\\{1,2,3,7,8,9\\}$ certify that
$\operatorname{co}(N^{\ast})$ has the series $(2,1,3)$-property with
$D=\\{1,3,4,6,7,9\\}$. The circuits $C$, $\\{1,2,4,5,7,8\\}$, and
$\\{1,2,4,6,8,9\\}$ certify that $\operatorname{co}(N^{\ast})$ has the series
$(2,1,4)$-property with $D=\\{1,3,4,6,7,9\\}$. A symmetric set of circuits
certifies that $\operatorname{co}(N^{\ast})$ has the series $(e,1,g)$-property
for each independent set $\\{e,1,g\\}$ contained in $C$. By Corollary 27,
$N^{\ast}$ is not orderable.

If $K=U_{2,4}\oplus U_{1,1}$, then $\operatorname{si}(N)=AG(2,3)\backslash 9$
with $AG(2,3)$ labelled as in Figure 15. Using Corollary 27 again, let $c$ be
the element 1 in the circuit $C=\\{1,2,3,7,8\\}$ of
$\operatorname{co}(N^{\ast})$. When $e=g=2$, the circuits $C$ and
$\\{1,2,4,6,8\\}$ certify that $\operatorname{co}(N^{\ast})$ has the series
$(2,1,2)$-property with $D=\\{1,3,4,6,7\\}$. A symmetric set of circuits
certifies that $\operatorname{co}(N^{\ast})$ has the series $(e,1,e)$-property
for each $e$ in $C-1$.

When $\\{e,g\\}=\\{2,3\\}$, the circuits $C$ and $\\{1,2,4,6,8\\}$ certify
that $\operatorname{co}(N^{\ast})$ has the series $(2,1,3)$-property with
$D=\\{1,3,4,6,7\\}$. From Figure 15, we see that the cases
$\\{e,g\\}=\\{2,7\\}$ and $\\{e,g\\}=\\{3,8\\}$ are symmetric; and the
circuits $C$ and $\\{1,2,4,5,7,8\\}$ certify that
$\operatorname{co}(N^{\ast})$ has the series $(2,1,7)$-property with
$D=\\{1,3,4,5,8\\}$. The cases $\\{e,g\\}=\\{2,8\\}$ and $\\{e,g\\}=\\{3,7\\}$
are also symmetric, and the circuits $C$ and $\\{1,2,4,6,8\\}$ certify that
$\operatorname{co}(N^{\ast})$ has the series $(2,1,8)$-property with
$D=\\{1,3,4,6,7\\}$. Finally, the circuits $\\{1,2,4,5,7,8\\}$ and
$\\{1,3,5,6,7,8\\}$ certify that $\operatorname{co}(N^{\ast})$ has the series
$(7,1,8)$-property with $D=\\{1,2,3,4,5,6\\}$. Corollary 27 now implies
$N^{\ast}$ is not orderable.

The next five cases make frequent use of Proposition 22(ii). The strategy is
to contract strategic parallel classes of $N$ to get parallel extensions of
$U_{2,4}$. These parallel extensions are dual to orderable series extensions
of $U_{2,4}$, and Proposition 22(ii) implies that the parallel classes of such
a parallel extension have the same size. For each case, we view
$\operatorname{si}(N)$ as a restriction of the labelled copy of $PG(2,3)$ in
Figure 14. For each element $e$ in $E(N)$, let $p_{e}$ be the size of the
parallel class of $N$ containing $e$.

If $K=U_{1,1}$, then $\operatorname{si}(N)=PG(2,3)\backslash d$. The following
equations are obtained by applying Proposition 22(ii) in the minors
$N/\operatorname{cl}(\\{a\\})$, $N/\operatorname{cl}(\\{b\\})$, and
$N/\operatorname{cl}(\\{c\\})$, respectively:

$p_{b}+p_{c}=p_{1}+p_{2}+p_{3}=p_{4}+p_{5}+p_{6}=p_{7}+p_{8}+p_{9};$
$p_{a}+p_{c}=p_{1}+p_{5}+p_{9}=p_{2}+p_{6}+p_{7}=p_{3}+p_{4}+p_{8};$
$p_{a}+p_{b}=p_{3}+p_{6}+p_{9}=p_{2}+p_{5}+p_{8}=p_{1}+p_{4}+p_{7}.$

Combining these equations, we obtain

$3(p_{a}+p_{b})+3(p_{a}+p_{c})+3(p_{b}+p_{c})=3(p_{1}+p_{2}+\cdots+p_{9}),$

which implies

$2(p_{a}+p_{b}+p_{c})=p_{1}+p_{2}+\cdots+p_{9},$

and therefore

$3(p_{a}+p_{b}+p_{c})=|E(N)|.$

We conclude that exactly one-third of the elements of $E(N)$ lie on the line
$\\{a,b,c\\}$. By symmetry, the same is true of the lines $\\{1,6,8\\}$,
$\\{3,5,7\\}$, and $\\{2,4,9\\}$, so now four disjoint lines each account for
one-third of the elements in $N$, a contradiction.

If $K=U_{2,3}$, then $\operatorname{si}(N)=PG(2,3)\backslash\\{b,c,d\\}$. The
following equations are obtained by applying Proposition 22(ii) in the minors
$N/\operatorname{cl}(\\{1\\})$, $N/\operatorname{cl}(\\{2\\})$, and
$N/\operatorname{cl}(\\{3\\})$, respectively:

$p_{2}+p_{3}+p_{a}=p_{4}+p_{7}=p_{6}+p_{8}=p_{5}+p_{9}=\frac{1}{4}\big{(}|E(N)|-p_{1}\big{)};$
(1)
$p_{1}+p_{3}+p_{a}=p_{4}+p_{9}=p_{5}+p_{8}=p_{6}+p_{7}=\frac{1}{4}\big{(}|E(N)|-p_{2}\big{)};$
(2)
$p_{1}+p_{2}+p_{a}=p_{5}+p_{7}=p_{6}+p_{9}=p_{4}+p_{8}=\frac{1}{4}(|E(N)|-p_{3}).$

Solving equations (1) and (2) for $|E(N)|$, we see that

$p_{1}+4p_{2}+4p_{3}=4p_{1}+p_{2}+4p_{3},$

so $p_{1}=p_{2}$. Through additional substitutions, it follows that
$p_{i}=p_{j}$ for each $i,j\neq a$. But now $p_{a}=0$, a contradiction.

If $K=P(U_{2,3},U_{2,4})$, then
$\operatorname{si}(N)=PG(2,3)\backslash\\{7,8,9,a,b,d\\}\cong P_{7}$. From the
minors $N/\operatorname{cl}(\\{1\\})$ and $N/\operatorname{cl}(\\{3\\})$ and
Proposition 22(ii), we get the equations

$\displaystyle p_{2}+p_{3}$ $\displaystyle=p_{4}+p_{c}=p_{5}=p_{6},$
$\displaystyle p_{1}+p_{2}$ $\displaystyle=p_{6}+p_{c}=p_{4}=p_{5}.$

It follows that $p_{c}=0$, a contradiction.

If $K=\mathcal{W}^{3}$, then
$\operatorname{si}(N)=PG(2,3)\backslash\\{6,8,9,b,c,d\\}\cong O_{7}$. From the
minors $N/\operatorname{cl}(\\{7\\})$ and $N/\operatorname{cl}(\\{5\\})$ we
get the equations

$p_{1}+p_{4}=p_{3}+p_{5}=p_{2}=p_{a},$ $p_{3}+p_{7}=p_{4}+p_{a}=p_{1}=p_{2}.$

It follows that $p_{4}=0$, a contradiction.

If $K=O_{7}$, then $\operatorname{si}(N)=PG(2,3)\backslash
6,8,9,a,b,c,d\cong\mathcal{W}^{3}$. From the minors
$N/\operatorname{cl}(\\{2\\})$ and $N/\operatorname{cl}(\\{4\\})$ we get the
equations

$p_{1}+p_{3}=p_{4}=p_{5}=p_{7},$ $p_{1}+p_{7}=p_{2}=p_{3}=p_{5},$

so $p_{1}=0$, a contradiction.

For the next six cases, we continue to view $N$ as a parallel extension of a
restriction of $PG(2,3)$, with $PG(2,3)$ labelled as in Figure 14. However, we
now represent the deletion of an element $e$ from $PG(2,3)$ by setting $p_{e}$
to be 0. Each of these cases is eliminated using the following assertion.

######  27.3.

Let $N$ be a restriction of $PG(2,3)$ such that

  * (i)

$p_{c}=p_{d}=0$;

  * (ii)

$p_{x}\neq 0$ for each $x$ in $\\{a,b,1\\}$;

  * (iii)

$\operatorname{si}(N/\operatorname{cl}(\\{x\\}))\cong U_{2,4}$ for each $x$ in
$\\{a,b,1\\}$; and

  * (iv)

$p_{2}$ and $p_{3}$ are not both zero.

Then $N^{\ast}$ is not orderable.

To see this, we first use the minors $N/\operatorname{cl}(\\{a\\})$ and
$N/\operatorname{cl}(\\{b\\})$ to establish the equations

$p_{b}=p_{1}+p_{2}+p_{3}=p_{4}+p_{5}+p_{6}=p_{7}+p_{8}+p_{9},$
$p_{a}=p_{2}+p_{6}+p_{7}=p_{1}+p_{5}+p_{9}=p_{3}+p_{4}+p_{8},$

from which we obtain

$3p_{a}=p_{1}+p_{2}+\cdots+p_{9}=3p_{b},$

so $p_{a}=p_{b}$, and $|E(N)|=5p_{a}$. Now, $N/\operatorname{cl}(\\{1\\})$
gives that

$|E(N)|-p_{1}=4(p_{2}+p_{3}+p_{a}),$

and substituting $5p_{a}$ for $|E(N)|$ produces

$p_{a}=p_{1}+4(p_{2}+p_{3}).$

Finally, since $p_{a}=p_{1}+p_{2}+p_{3}$, we deduce that $p_{2}+p_{3}=0$, a
contradiction. Thus 27.3 holds.

The six options for $K$ eliminated by 27.3 are the matroids $U_{2,2}$,
$U_{3,3}$, $U_{3,4}$, $U_{2,3}\oplus U_{1,1}$, $P(U_{2,3},U_{2,3})$, and
$U_{2,3}\oplus_{2}U_{2,4}$. It is straightforward to check that, for each $K$
in this list, we may set classes of $PG(2,3)$ equal to zero in such a way that
the zeroed classes form a restriction isomorphic to $K$, and the conditions of
27.3 hold. For example, $U_{2,3}\oplus_{2}U_{2,4}$ is produced when $p_{5}$,
$p_{7}$, $p_{9}$, $p_{c}$, and $p_{d}$ are the zeroed classes.

$3$$1$$5$$7$$2$$6$$4$ Figure 16: The matroid $F_{7}^{-}$.

In the final case, $K=M(K_{4})$ and $\operatorname{si}(N)=F_{7}^{-}$. Label
$F_{7}^{-}$ as in Figure 16, and, for each $e$ in $[7]$, let
$S_{e}=S_{e}(N^{\ast})$. Suppose $N^{\ast}$ has a consistent ordering, and let
$B$ be an $S_{1}$-block in the ordering. In $N^{\ast}$, there is a circuit
corresponding to each circuit $\\{1,2,3,5,7\\}$, $\\{1,3,4,5,7\\}$, and
$\\{1,3,5,6,7\\}$ of $\operatorname{co}(N^{\ast})$; let $\mathcal{X}$ be the
collection of these circuits of $N^{\ast}$. Similarly, let $\mathcal{Y}$ be
the collection of circuits of $N^{\ast}$ corresponding to the circuits
$\\{1,2,3,4\\}$, $\\{1,4,5,6\\}$, and $\\{1,2,6,7\\}$ of
$\operatorname{co}(N^{\ast})$.

Suppose $B$ is adjacent to an $S_{e}$-block for some $e$ in $\\{2,4,6\\}$.
Then the consistency of the circuits in $\mathcal{X}$ implies that $B$ is
adjacent to an $S_{e}$-block for every $e$ in $\\{2,4,6\\}$. The circuits in
$\mathcal{Y}$ now imply that $B$ is adjacent to an $S_{2}$-, $S_{4}$-, and
$S_{6}$-block. Further, $B$ is not adjacent to an $S_{e}$-block for any $e$ in
$\\{3,5,7\\}$. It follows that, in the circuit of $N^{\ast}$ corresponding to
$\\{1,2,3,5,7\\}$, the block $B$ must be adjacent to a pair of $S_{2}$-blocks,
contradicting the fact that $B$ is adjacent to both an $S_{2}$-block and an
$S_{4}$-block in the circuit of $N^{\ast}$ corresponding to $\\{1,2,3,4\\}$.

We now know that, for each $e$ in $\\{2,4,6\\}$, the block $B$ is not adjacent
to an $S_{e}$-block. The circuits in $\mathcal{Y}$ now imply that, in the
circuit of $N^{\ast}$ corresponding to $\\{1,2,3,5,7\\}$, the block $B$ is
adjacent to an $S_{e}$-block for every $e$ in $\\{3,5,7\\}$. This
contradiction implies $N^{\ast}$ is not orderable. ∎

The next proposition is a result of Oxley [4] (see also [5, Corollary
12.2.18]). We will use it to prove Theorem 23.

######  Proposition 28.

A $3$-connected non-binary matroid whose rank and corank exceed two has a
minor isomorphic to one of $\mathcal{W}^{3}$, $P_{6}$, $Q_{6}$, and $U_{3,6}$.

###### Proof of Theorem 23.

Assume that the theorem fails for $M$. Then $r(M)\geqslant 3$. As $P_{6}$,
$Q_{6}$, and $U_{3,6}$ each have $U_{3,5}$ as a minor, Proposition 28 and
Propositions 24 and 25 now imply that $r^{\ast}(M)\leqslant 2$, so
$r^{\ast}(M)=2$. As $M$ is 3-connected, it follows that $M\cong U_{n-2,n}$ for
some $n\geqslant 5$. Hence $M$ has a $U_{3,5}$-minor, a contradiction. ∎

If $\\{M_{1},M_{2},\dots,M_{n}\\}$ is a set of a matroids, then a _matroid-
labelled tree_ with vertex set $\\{M_{1},M_{2},\dots,M_{n}\\}$ is a tree $T$
such that

  1. (i)

if $e$ is an edge of $T$ with endpoints $M_{i}$ and $M_{j}$, then
$E(M_{i})\cap E(M_{j})=\\{e\\}$, and $\\{e\\}$ is not a separator of $M_{i}$
or $M_{j}$; and

  2. (ii)

$E(M_{i})\cap E(M_{j})$ is empty if $M_{i}$ and $M_{j}$ are non-adjacent.

The matroids $M_{1},M_{2},\dots,M_{n}$ are called the _vertex labels_ of $T$.
Now suppose $e$ is an edge of $T$ with endpoints $M_{1}$ and $M_{2}$. We
obtain a new matroid-labelled tree $T/e$ by contracting $e$ and relabelling
the resulting vertex with $M_{1}\oplus_{2}M_{2}$. As 2-sum is associative,
$T/X$ is well defined for all subsets $X$ of $E(T)$.

Let $T$ be a matroid-labelled tree with $V(T)=\\{M_{1},M_{2},\dots,M_{n}\\}$
and
$E(T)=\\{e_{1},e_{2},\dots,e_{n-1}\\}$. Then $T$ is a _tree decomposition_ of
a connected matroid $M$ if

  1. (i)

$E(M)=(E(M_{1})\cup E(M_{2})\cup\cdots\cup
E(M_{n}))-\\{e_{1},e_{2},\dots,e_{n-1}\\}$;

  2. (ii)

$|E(M_{i})|\geqslant 3$ for all $i$ unless $|E(M)|<3$, in which case $n=1$ and
$M=M_{1}$; and

  3. (iii)

$M$ labels the single vertex of $T/E(T)$.

In this case, the elements $\\{e_{1},e_{2},\dots,e_{n-1}\\}$ are the _edge
labels_ of $T$. The next theorem of Cunningham and Edmonds [3] (see also [5,
Theorem 8.3.10]) tells us that $M$ has a _canonical tree decomposition_ ,
unique to within relabelling of the edges.

######  Theorem 29.

Let $M$ be a $2$-connected matroid. Then $M$ has a tree decomposition $T$ in
which every vertex label is $3$-connected, a circuit, or a cocircuit, and
there are no two adjacent vertices that are both labelled by circuits or are
both labelled by cocircuits. Moreover, $T$ is unique to within relabelling of
its edges.

Let $T$ be a tree decomposition of a matroid $M$, and let $N$ and $p$ be a
vertex label and edge label of $T$, respectively. For the remainder of this
section, we define $M_{p,N}$ and $M_{p,N}^{\prime}$ to be the matroids such
that $M=M_{p,N}\oplus_{2}M_{p,N}^{\prime}$ with basepoint $p$, where
$E(M_{p,N})$ contains the subset of $E(M)$ corresponding to the component of
$T\backslash p$ containing $N$. Notice that if the vertex labels $M_{1}$ and
$M_{2}$ lie in different components of $T\backslash p$, then
$M_{p,M_{1}}=M_{p,M_{2}}^{\prime}$.

In the next four lemmas, $M$ is assumed to be a connected, orderable, non-
binary matroid whose canonical tree decomposition is $T$.

######  Lemma 30.

Suppose that $T$ has a vertex label $U$ that is isomorphic to $U_{2,n}$ for
some $n\geqslant 4$. Then, for all $e,f\in E(U)$,

  1. (i)

$e$ is an edge label of $T$, unless $M$ is a parallel extension of $U_{2,n}$;

  2. (ii)

all circuits of $M_{e,U}^{\prime}$ containing $e$ have the same size; and

  3. (iii)

the circuits of $M_{e,U}^{\prime}$ containing $e$ have the same size as the
circuits of $M_{f,U}^{\prime}$ containing $f$.

###### Proof.

We may assume that $M$ is not a parallel extension of $U_{2,n}$ otherwise (i)
holds. For each element $y$ of $E(U)$ that labels an edge of $T$, let $C_{y}$
be a circuit of $M_{y,U}^{\prime}$ that contains $y$. As $M$ is not a parallel
extension of $U_{2,n}$, we may assume that $|C_{x}|\geqslant 3$ for some
element $x$. Let $M^{\prime\prime}$ be the matroid that is obtained from $U$
by attaching each $C_{y}$ via 2-sum. This matroid is a restriction of $M$
having $C_{x}-x$ as a non-trivial series class. Moreover, $M^{\prime\prime}$
is a series extension of $U_{2,n}$ and it is orderable. Thus, by Proposition
22(ii), $M^{\prime\prime}$ is a balanced series extension of $U_{2,n}$. Hence
(i) holds. Furthermore, $|C_{x}|=|C_{y}|\geqslant 3$ for all $y$ in
$E(U)-\\{x\\}$. Parts (ii) and (iii) now follow without difficulty. ∎

The next lemma generalizes Lemma 30(ii) to arbitrary edges of $T$.

######  Lemma 31.

Suppose that $T$ has a vertex label $U$ that is isomorphic to $U_{2,n}$ for
some $n\geqslant 4$, and suppose $e$ is an edge label of $T$. Then the
circuits of $M_{e,U}^{\prime}$ that contain $e$ all have the same size.

###### Proof.

Let $N$ be the endpoint of $e$ in the same component of $T\backslash e$ as
$U$. If $U=N$, then the assertion holds by Lemma 30(ii), so assume otherwise.
Let $f$ be the label of the edge incident with $U$ that lies on the path
connecting $U$ to $N$ in $T$. Next, let $T^{\prime}$ be the subtree of
$T\backslash\\{e,f\\}$ containing $N$, and let $M^{\prime}$ be the matroid
with tree decomposition $T^{\prime}$.

Fix a circuit $C$ of $M^{\prime}$ that contains $e$ and $f$. Observe that, for
each circuit $D$ of $M_{e,N}^{\prime}$ that contains $e$, there is a circuit
$(D-e)\cup(C-e)$ of $M_{f,U}^{\prime}$ that contains $f$. By Lemma 30(ii), the
quantity $|(D-e)\cup(C-e)|$ is the same for each choice of $D$, so every such
circuit $D$ has the same size. ∎

######  Lemma 32.

The tree $T$ has exactly one $3$-connected non-binary vertex label, and this
label is isomorphic to $U_{2,n}$ for some $n\geqslant 4$.

###### Proof.

As $M$ is non-binary, it has at least one 3-connected non-binary vertex label
$N$. For each element $y$ of $E(N)$ that labels an edge of $T$, let $C_{y}$ be
a circuit of $M^{\prime}_{y,N}$ that contains $y$. Let $M^{\prime\prime}$ be
the matroid that is obtained from $N$ by attaching each $C_{y}$ via 2-sum.
Then $M^{\prime\prime}$ is a restriction of $M$. Thus $M^{\prime\prime}$ is an
orderable series extension of $N$. By Propositions 24, 25, and 28, $N\cong
U_{2,n}$ for some $n\geqslant 4$. Now suppose $T$ has a pair of 3-connected
non-binary vertex labels $N_{1}\cong U_{2,n_{1}}$ and $N_{2}\cong U_{2,n_{2}}$
with $n_{1},n_{2}\geqslant 4$. Let $e_{1}$ and $e_{2}$ be the edge labels of
$T$ incident with $N_{1}$ and $N_{2}$ that lie on the path connecting $N_{1}$
and $N_{2}$ in $T$.

By Lemma 30(ii), the circuits of $M_{e_{1},N_{1}}^{\prime}$ containing $e_{1}$
all have size $k$ and the circuits of $M_{e_{2},N_{2}}^{\prime}$ containing
$e_{2}$ all have size $\ell$, where $k$ and $\ell$ are integers exceeding one.
Let $\\{e_{1},x,y\\}$ be a circuit of $N_{1}$. By Lemma 30(i), $x$ and $y$ are
also edge labels of $T$; let $C_{x}$ be a circuit of $M_{x,N_{1}}^{\prime}$
containing $x$, and $C_{y}$ be a circuit of $M_{y,N_{1}}^{\prime}$ containing
$y$. Then $k=|C_{x}|=|C_{y}|$ by Lemma 30(iii). Now there is a circuit of
$M_{e_{2},N_{2}}^{\prime}$ containing $e_{2}$ that also contains $C_{x}-x$ and
$C_{y}-y$. Thus, $\ell\geqslant 2(k-1)+1$. A symmetric argument gives that
$k\geqslant 2(\ell-1)+1$, and substitution yields that $k\leqslant 1$, a
contradiction. ∎

The next lemma rules out 3-connected binary vertex labels that are not
circuits or cocircuits. It uses the following result of Seymour [6].

######  Proposition 33.

Let $M$ be a $3$-connected binary matroid with at least four elements. If
$e\in E(M)$, then $M$ has an $M(K_{4})$-minor using $e$.

######  Lemma 34.

No vertex of $T$ is labelled by a $3$-connected binary matroid with at least
four elements.

###### Proof.

Suppose $B$ is such a vertex label of $T$, let $U$ be the unique vertex label
with $U\cong U_{2,n}$ and $n\geqslant 4$ given by Lemma 32, and say
$E(U)=\\{e_{1},e_{2},\dots,e_{n}\\}$. Let $p\in E(B)$ and $e_{1}\in E(U)$ be
the labels of the edges incident with $B$ and $U$, respectively, that lie on
the path connecting $B$ to $U$ in $T$. By Proposition 33, $B$ has a minor
isomorphic to $M(K_{4})$ that uses $p$.

This minor can be written in the form $B/I\backslash I^{\ast}$, where $I$ is
independent in $B$ and $I^{\ast}$ is coindependent in $B$. This makes $B/I$ a
rank-three binary matroid with $M(K_{4})$ as a restriction, so after deleting
the loops from $B/I$, we obtain a parallel extension of either $M(K_{4})$ or
$F_{7}$. Dually, after deleting the coloops from $B\backslash I^{\ast}$, we
obtain a series extension of $M(K_{4})$ or $F_{7}^{\ast}$. Thus $B$ has a
restriction $N_{1}$ using $p$ that is a series extension of $M(K_{4})$ or
$F_{7}^{\ast}$.

Suppose $q$ is an edge label of $T$ that is used in $N_{1}$, and choose a
circuit $C_{q}$ of $M_{q,B}^{\prime}$ that contains $q$. Form the matroid
$N_{2}$ from $N_{1}$ by replacing $q$ with $C_{q}-q$ in $E(N_{1})$ for each
$q$ in $E(N_{1})-p$ that is an edge label of $T$. Then $N_{2}$ is a series
extension of $M(K_{4})$ or $F_{7}^{\ast}$ that appears as a restriction of
$M_{p,B}$. Now, for each $i$ in $\\{2,3\\}$, let $C_{e_{i}}$ be a circuit of
$M_{e_{i},U}^{\prime}$ that contains $e_{i}$. Then $M_{p,B}^{\prime}$ has a
circuit $C_{p}$ that contains $p$ and both $C_{e_{2}}-e_{2}$ and
$C_{e_{3}}-e_{3}$. Form the matroid $N$ from $N_{2}$ by taking the 2-sum of
$N_{2}$ and $C_{p}$ across the basepoint $p$. Then $N$ is a restriction of $M$
that is a series extension of $M(K_{4})$ or $F_{7}^{\ast}$. For each element
$x$ of $M(K_{4})$ or $F_{7}^{\ast}$, let $S_{x}$ be $S_{x}(N)$. By Lemma 31,
every circuit of $N_{2}$ that contains $p$ has the same size.

$p$$a$$b$$c$$d$$e$ Figure 17: $K_{4}$ in the proof of Lemma 34.

Suppose first that $N$ is a series extension of $M(K_{4})$ with $K_{4}$
labelled as in Figure 17. Thus, every circuit of $N$ that contains $S_{p}$ has
the same size. Since all circuits of $N$ containing $S_{p}$ have the same
size, $|S_{d}|+|S_{e}|=|S_{a}|+|S_{b}|+|S_{e}|$, so

$|S_{d}|=|S_{a}|+|S_{b}|.$ (3)

Similarly, $|S_{a}|+|S_{c}|=|S_{d}|+|S_{b}|+|S_{c}|$, so

$|S_{a}|=|S_{d}|+|S_{b}|.$ (4)

Equations (3) and (4) imply that $|S_{b}|=0$, a contradiction.

$p$234567 Figure 18: $F_{7}^{\ast}$ in the proof of Lemma 34.

Now suppose that $N$ is a series extension of $F_{7}^{\ast}$ with
$F_{7}^{\ast}$ labelled as in Figure 18. Since the circuits of $N$ containing
$S_{p}$ must have the same size,

$|S_{2}|+|S_{5}|=|S_{4}|+|S_{7}|,$ $|S_{2}|+|S_{6}|=|S_{3}|+|S_{7}|,$

and

$|S_{5}|+|S_{6}|=|S_{3}|+|S_{4}|.$

Together, these equations imply that

$|S_{2}|=|S_{7}|.$ (5)

Fix a consistent ordering of $M$. This induces a consistent ordering of $N$.
Consider the circuit $C=S_{p}\cup S_{2}\cup S_{3}\cup S_{4}$ of $N$. Notice
that $M$ has, as a restriction, a series extension $U^{\prime}$ of $U_{2,n}$
whose ground set contains $C$. Specifically, $C=S_{e_{1}}\cup S_{e_{2}}\cup
S_{e_{3}}$, where $S_{e_{i}}$ is $S_{e_{i}}(U^{\prime})$.

Let $t$ be an arbitrary member of the series class $S_{2}$ of $N$. In
$U^{\prime}$, the element $t$ belongs to the class $S_{e_{1}}$, so $\\{t\\}$
is an $S_{e_{1}}$-block in the ordering of $C$ by Proposition 22(i). Lemma
18(i) implies that $t$ is adjacent to some element $x\in S_{e_{2}}$ and some
$y\in S_{e_{3}}$; notice that, in $N$, the elements $x$ and $y$ both belong to
$S_{p}$. Thus, every element of $S_{2}$ is adjacent to a pair of elements from
$S_{p}$ in $C$. In particular, $t$ is not adjacent to any element of $S_{2}$
or of $S_{3}$. Now observe that $t$ is adjacent to this same pair $\\{x,y\\}$
in the circuit $S_{p}\cup S_{2}\cup S_{5}\cup S_{6}$ of $N$, so $t$ is also
not adjacent to any element of $S_{6}$. It follows that $t$ is adjacent to a
pair of elements from $S_{7}$ in the circuit $S_{2}\cup S_{3}\cup S_{6}\cup
S_{7}$ of $N$. Therefore $|S_{2}|<|S_{7}|$, contradicting (5). ∎

######  Proposition 35.

Let $M^{\prime\prime}$ be obtained from $M$ by parallel-path addition. Then
$M$ is orderable if and only if $M^{\prime\prime}$ is orderable.

###### Proof.

In forming $M^{\prime\prime}$ from $M$, let $P^{\prime}$ be added in parallel
to $P$. As $M^{\prime\prime}$ has $M$ as a restriction, $M$ is orderable if
$M^{\prime\prime}$ is. Conversely, fix a consistent ordering of $M$ and let
$C^{\prime\prime}$ be a circuit of $M^{\prime\prime}$. If $C^{\prime\prime}$
does not meet $P^{\prime}$, give $C^{\prime\prime}$ the same ordering in
$M^{\prime\prime}$ that it has in $M$. Otherwise, $C^{\prime\prime}$ contains
$P^{\prime}$ and either $C^{\prime\prime}=P\cup P^{\prime}$, or there is a
circuit $C$ of $M$ such that $C=(C^{\prime\prime}-P^{\prime})\cup P$. In the
the latter case, give $C^{\prime\prime}$ the same ordering in
$M^{\prime\prime}$ that $C$ has in $M$ by replacing every element $p\in P$ by
the corresponding element $p^{\prime}\in P^{\prime}$.

If $C^{\prime\prime}=P\cup P^{\prime\prime}$, take a circuit $D$ of $M$
containing $P$. Let $B_{1}$, $B_{2}$, …, $B_{k}$ be the $P$-blocks of $D$,
numbered sequentially as they appear in a traversal of the ordering of $D$ in
$M$. For each $i$ in $[k]$, let $B_{i}^{\prime}=\\{p^{\prime}:p\in B_{i}\\}$.
Now, order $C^{\prime\prime}$ as $B_{1}$, $B_{1}^{\prime}$, $B_{2}$,
$B_{2}^{\prime}$, …, $B_{k}$, $B_{k}^{\prime}$. It is straightforward to check
that this gives a consistent ordering of $M^{\prime\prime}$. ∎

######  Lemma 36.

Let $M$ and $N$ be matroids, and let $S$ be a sequence of balanced series
extensions and parallel-path additions by which $N$ is obtained from $M$.
Suppose that the operation $s_{1}$ immediately precedes the operation $s_{2}$
in $S$. Then

  * (i)

if $s_{1}$ and $s_{2}$ are balanced series extensions of orders $m_{1}$ and
$m_{2}$, then $s_{1}$ and $s_{2}$ may be replaced by a single balanced series
extension of order $m_{1}m_{2}$; and

  * (ii)

if $s_{1}$ is a parallel-path addition of size $k$, and $s_{2}$ is a balanced
series extension of order $m$, then, in $S$, the order of the operations
$s_{1}$ and $s_{2}$ can be reversed provided $s_{1}$ is replaced by a
corresponding parallel-path addition of size $km$.

###### Proof.

Part (i) is immediate. For part (ii), let $P_{1}$ be the $k$-element set that
is added in parallel to the subset $P_{2}$ of a series class at step $s_{1}$.
After the balanced series extension in step $s_{2}$ is performed, $P_{1}$ and
$P_{2}$ become parallel paths $P_{1}^{\prime}$ and $P_{2}^{\prime}$ of size
$mk$. Thus, the same result is obtained by first performing a balanced series
extension of order $m$, then adding the $mk$-element set $P_{1}^{\prime}$ in
parallel to the subset $P_{2}^{\prime}$ of a series class. ∎

We are now ready to prove the main result of the paper, which was given as
Theorem 2 in the introduction and is restated here for convenience.

######  Theorem 37.

Let $M$ be a connected non-binary matroid. Then $M$ is orderable if and only
if it can be obtained from $U_{2,n}$ for some $n\geqslant 4$ by a sequence of
the following operations:

  1. (i)

balanced series extension; and

  2. (ii)

parallel-path addition.

###### Proof.

Let $n$ be an integer exceeding three, and let $M$ be a matroid obtained from
$U_{2,n}$ by a sequence of balanced series extensions and parallel-path
additions. Lemma 36 implies that $M$ may be obtained from a balanced series
extension of $U_{2,n}$ by a sequence of parallel-path additions, so, by Lemmas
21 and 35, $M$ is orderable.

For the converse, we may assume that $M$ is simple, as adding an element in
parallel is a parallel-path addition of size one. If $M\cong U_{2,n}$, the
result holds, so assume otherwise. Let $T$ be the canonical tree decomposition
of $M$. Lemmas 32 and 34 imply that there is a single vertex label $U$ of $T$
for which $U\cong U_{2,n}$ and $n\geqslant 4$, and every vertex of $T-U$ is
labelled by a circuit or a cocircuit. By Lemma 30(i), each $e$ in $E(U)$
labels an edge of $T$. Let $T_{e}^{\prime}$ be the component of $T\backslash
e$ that does not have $U$ as a vertex. As $M$ is simple, the leaves of $T$ are
labelled by circuits. Therefore, if every $T_{e}^{\prime}$ has only one
vertex, then $M$ is a series extension of $U_{2,n}$, and the result holds by
Proposition 22(ii). We show that, if this is not the case, then each
$T_{e}^{\prime}$ can be reduced to a single vertex labelled by a circuit via a
sequence of deletions that can be undone by parallel-path additions.

Suppose $T_{e}^{\prime}$ has at least two vertices. Since only one vertex of
$T_{e}^{\prime}$ is adjacent to $U$, not all vertices of $T_{e}^{\prime}$ are
leaves of $T$. We now observe that

######  37.1.

$T_{e}^{\prime}$ has a vertex $v$ that

  1. (i)

is adjacent to a leaf of $T$; and

  2. (ii)

has exactly one neighbor that is not a leaf of $T$

If $L$ is the set of leaves of $T$, such a vertex $v$ can be found as a leaf
of $T-L$. Since the leaves of $T$ are labelled by circuits and $T$ is
canonical, $v$ is labelled by a cocircuit $C^{\ast}$. Lemma 31 now implies
that the circuits that label the leaves of $T$ adjacent to $C^{\ast}$ all have
the same size, and every element of $C^{\ast}$ must be used as a basepoint
labelling an edge of $T$.

We can delete all but one of the leaves, $C$ say, of $T$ that are adjacent to
$C^{\ast}$, along with the corresponding basepoints in $C^{\ast}$, since the
circuit that labels each deleted leaf can be added via a parallel-path
addition. As $C^{\ast}$ is now a pair of parallel elements, we can delete the
leaf labelled $C$ and relabel $v$ with $C$. At this point, $v$ is a leaf, and
is either adjacent to $U$, in which case the work on this subtree is complete,
or $v$ is adjacent to another vertex of $T_{e}^{\prime}$ labelled by a circuit
$C^{\prime}$. In the latter case, keep $T$ canonical by contracting the edge
of $T$ between $v$ and $C^{\prime}$ and labelling the resulting vertex with
the circuit that is the 2-sum of $C$ and $C^{\prime}$.

Provided the modification of $T_{e}^{\prime}$ continues to have at least two
vertices, condition 37.1 continues to hold, and the process described in the
previous paragraph can be repeated. Thus, we may assume $T_{e}^{\prime}$
consists of a single vertex labelled by a circuit. By applying this pruning
process on the other subtrees attached to $U$, the tree $T$ is reduced to the
decomposition tree of a balanced series extension of $U_{2,n}$. Thus, $M$ can
be obtained from a balanced series extension of $U_{2,n}$ by a sequence of
parallel-path additions. ∎

##  4 Theta-Orderability

Recall that theta-orderability of a matroid requires a consistent ordering of
the matroid with respect to the theta-graphs of that matroid. Each of the
elementary properties of orderability given in Proposition 8 also holds for
theta-orderability. Their straightforward proofs are omitted.

######  Proposition 38.

Let $M$ be a matroid.

  1. (i)

If $M$ is theta-orderable, then $M\backslash e$ is theta-orderable for all $e$
in $E(M)$.

  2. (ii)

If $r(M)\leqslant 2$, then $M$ is theta-orderable.

  3. (iii)

$M$ is theta-orderable if and only if the connected components of $M$ are
theta-orderable.

  4. (iv)

$M$ is theta-orderable if and only if $\operatorname{si}(M)$ is theta-
orderable.

Next we prove Theorem 6, a characterization of graphic theta-orderable
matroids.

###### Proof of Theorem 6.

It is clear that a graphic matroid is theta-orderable. Moreover, Wagner [9]
proved that a matroid is graphic if and only if it has no set of incompatible
arcs. Now suppose that $M$ has a circuit $C$ and a set
$\\{A_{1},A_{2},A_{3}\\}$ of incompatible arcs of $C$. It remains to show that
$M$ is not theta-orderable. Our proof of this is a straightforward
modification of Wagner’s proof that no graphic matroid has a set of
incompatible arcs [9, Lemma 2]. Assume that $M$ is theta-orderable. Because
each of $A_{1}$, $A_{2}$, and $A_{3}$ is an arc, for each $i$ in
$\\{1,2,3\\}$, there is a theta-graph of $M$ in which $A_{i}$ is a theta-arc.
As $M$ is theta-orderable, $A_{i}$ is a block in a consistent ordering of $M$.
As $\\{A_{1},A_{2},A_{3}\\}$ is an incompatible set, there are distinct
elements $e_{1}$, $e_{2}$, and $e_{3}$ of $C$ such that $e\in A_{1}\cap
A_{2}\cap A_{3}$ and $e_{i}\in A_{i}-(A_{j}\cup A_{k})$ for all
$\\{i,j,k\\}=\\{1,2,3\\}$. For each $h$ in $\\{2,3\\}$, the set $A_{1}\cup
A_{h}$ is a block in $C$ in which $e$ appears between $e_{1}$ and $e_{h}$.
Then $e$ does not appear between $e_{2}$ and $e_{3}$ in $A_{2}\cup A_{3}$, a
contradiction. ∎

To prove Theorem 7, we will establish the following equivalent version of it.

######  Theorem 39.

A simple connected non-binary matroid is theta-orderable if and only if it is
a balanced series extension of $U_{2,n}$ for some $n\geqslant 4$.

###### Proof.

First, for $n\geqslant 4$, the matroid $U_{2,n}$ and its series extensions
have no theta-graphs. Therefore, consistent orderings of these matroids are
also theta-orderings.

Conversely, suppose $M$ is a simple connected non-binary orderable matroid. By
Theorem 37 and Lemma 36, for some $n\geqslant 4$, we can obtain $M$ from a
balanced series extension $B$ of $U_{2,n}$ by a sequence of parallel-path
additions. It now suffices to show that the sequence of parallel-path
additions is empty.

Suppose to the contrary that $P^{\prime}$ is a set added in parallel to a
subset $P$ of a series class $S$ of $B$. Note $|P|\geqslant 2$ since $M$ is
simple. Now, by Proposition 22, each $S$-block in a consistent ordering of $B$
contains a single element. As $B$ is a restriction of $M$, this implies that
the elements of $P$ are not a block in a consistent ordering of $M$. Since $M$
has a theta-graph with $P$ and $P^{\prime}$ as theta-arcs, this is a
contradiction. ∎

##  5 Characterizing 3-Connected Orderable Binary Matroids

This section proves the following partial result towards Conjecture 4. Theorem
5 is an immediate consequence of this result.

######  Theorem 40.

A $4$-connected binary orderable matroid with no series minor isomorphic to
$F_{7}^{\ast}$ is graphic.

Our proof will require the next three results, the first of which is due to
Seymour [7]. Two elements are _opposite_ in $M(K_{4})$ if they form a matching
in the $K_{4}$.

######  Theorem 41.

Let $M$ be a $4$-connected binary matroid and let $e$ and $f$ be elements of
$M$. Suppose there is no $M(K_{4})$-minor of $M$ in which $e$ and $f$ are
opposite elements. Then there is a graph $G$ with $M=M(G)$ or $M^{\ast}(G)$,
and $e$ and $f$ are adjacent edges in $G$.

######  Proposition 42.

In a consistent ordering of a series extension $M$ of $M(K_{4})$, if two
elements correspond to opposite elements in the $M(K_{4})$, then they are not
adjacent.

$Y$$A$$X$$D$$B$$C$ Figure 19: $K_{4}$ in the proof of Proposition 42.

###### Proof.

Let $A$, $B$, $C$, $D$, $X$, and $Y$ be the series classes of $M$, labelled as
in Figure 19. Take elements $x$ in $X$ and $y$ in $Y$, and suppose $x$ and $y$
are adjacent in the given consistent ordering of $M$.

In the circuit $A\cup X\cup C\cup Y$, we have that $y$ is adjacent to at most
one member of $C$. Therefore, in $B\cup C\cup Y$, there must be an element,
$b_{y}$, of $B$ that is adjacent to $y$. Similarly, in $A\cup X\cup B$, there
must be an element, $b_{x}$, of $B$ adjacent to $x$. Now, in $B\cup X\cup
D\cup Y$, we have the block $b_{x}xyb_{y}$, so no member of $D$ is adjacent to
$y$. By symmetry, no member of $A$ is adjacent to $y$. Since $y$ is adjacent
to at most one element in $Y$, it follows that there is no second element of
$A\cup D\cup Y$ adjacent to $y$, a contradiction. ∎

######  Lemma 43.

Suppose $M$ is a binary matroid with no series minor isomorphic to
$F_{7}^{\ast}$. If $e$ and $f$ are opposite elements in an $M(K_{4})$-minor of
$M$, then $e$ and $f$ are not adjacent in any consistent ordering of $M$.

###### Proof.

Assume that $M$ has a consistent ordering in which $e$ and $f$ are adjacent.
Let $N$ be an $M(K_{4})$-minor of $M$ in which $e$ and $f$ are opposite
elements, and write $N=M\backslash X/Y$ with $X$ coindependent and $Y$
independent. Then $N^{\ast}=M^{\ast}/X\backslash Y$, where
$r(M^{\ast}/X)=r(N^{\ast})=3$. Since $M^{\ast}/X$ is binary and $N^{\ast}\cong
M(K_{4})$, if $L$ is the set of loops of $M^{\ast}/X$, then
$M^{\ast}/X\backslash L$ is a parallel extension of either $M(K_{4})$ or
$F_{7}$. It follows that $M\backslash(X\cup L)$ is a series extension of
$M(K_{4})$ or $F_{7}^{\ast}$. By assumption, $M$ has no series minor
isomorphic to $F_{7}^{\ast}$, so $M\backslash(X\cup L)$ is a series extension
of $M(K_{4})$. However, $e$ and $f$ are adjacent in the consistent ordering of
$M\backslash(X\cup L)$ inherited from $M$ and correspond to opposite elements
in $N$, a contradiction by Proposition 42. ∎

We now prove the main result of this section.

###### Proof of Theorem 40.

Let $M$ be a 4-connected binary orderable matroid that does not have
$F_{7}^{\ast}$ as a series minor. Take a consistent ordering of $M$ and assume
$M$ is not graphic. Suppose $M$ is cographic, letting $M=M^{\ast}(G)$ for some
graph $G$. Take an edge $e$ of $G$ with endpoints $u$ and $v$. Let $(x_{1}\
x_{2}\ \cdots\ x_{n}\ e)$ be the ordering on the edges meeting $u$, and let
$(e\ y_{1}\ y_{2}\ \cdots\ y_{m})$ be the ordering on the edges meeting $v$.
Then we may assume the ordering on the bond that is the symmetric difference
of these two vertex bonds is $(x_{1}\ x_{2}\ \cdots\ x_{n}\ y_{1}\ y_{2}\
\cdots\ y_{m})$, so $x_{n}$ and $y_{1}$ are adjacent. Combining Lemma 43 and
Theorem 41, we now have that $x_{n}$ and $y_{1}$ share an endpoint in $G$.
Hence, $\\{e,x_{n},y_{1}\\}$ is a triangle in $G$, a contradiction as $M$ is
4-connected.

We may now assume that $M$ is not cographic. Let $e$ and $f$ be adjacent
elements of $M$. By Theorem 41, $e$ and $f$ appear as opposite elements in
some $M(K_{4})$-minor of $M$. Lemma 43 now gives a contradiction. ∎

### Acknowledgements

The authors thank Jim Geelen for suggesting that [7] may be helpful in
resolving Conjecture 4.

## References

  * [1] Bixby, R. E., A strengthened form of Tutte’s characterization of regular matroids, _J. Combin. Theory Ser. B_ 20 (1976), 216–221.
  * [2] Bixby, R. E., Kuratowski’s and Wagner’s theorems for matroids, _J. Combin. Theory Ser. B_ 22 (1977), 31–53.
  * [3] Cunningham, W. H., A combinatorial decomposition theory, Ph.D. thesis, University of Waterloo, 1973.
  * [4] Oxley, J. G., On nonbinary 3-connected matroids, _Trans. Amer. Math. Soc._ 300 (1987), 663–679.
  * [5] Oxley, J. G., _Matroid Theory_ , 2nd ed., Oxford University Press, New York, 2011.
  * [6] Seymour, P. D., Minors of $3$-connected matroids, _European J. Combin._ 6 (1985), 375–382.
  * [7] Seymour, P. D., Adjacency in binary matroids, _European J. Combin._ 7 (1986), 171–176.
  * [8] Tutte, W. T., Matroids and graphs, _Trans. Amer. Math. Soc._ 90 (1959), 527–552.
  * [9] Wagner, D. K., A circuit characterization of graphic matroids, _J. Combin. Theory Ser. B_ 118 (2016), 284–290.
  * [10] Whitney, H., 2-isomorphic graphs, _Amer. J. Math._ 55 (1933), 245–254.