# The smallest class of binary matroids closed under direct sums and
complements

James Oxley  Mathematics Department
Louisiana State University
Baton Rouge, Louisiana<EMAIL_ADDRESS>and  Jagdeep Singh  Mathematics
Department
Louisiana State University
Baton Rouge, Louisiana<EMAIL_ADDRESS>
###### Abstract.

The class of cographs or complement-reducible graphs is the class of graphs
that can be generated from $K_{1}$ using the operations of disjoint union and
complementation. By analogy, this paper introduces the class of binary
comatroids as the class of matroids that can be generated from the empty
matroid using the operations of direct sum and taking complements inside of
binary projective space. We show that a proper flat of a binary comatroid is a
binary comatroid. Our main result identifies those binary non-comatroids for
which every proper flat is a binary comatroid. The paper also proves the
corresponding results for ternary matroids.

###### 1991 Mathematics Subject Classification:

05B35, 05C25

##  1\. Introduction

The notation and terminology used in this paper follow [4] and [12] except
where otherwise indicated. All graphs and matroids considered here are simple.
A cograph is defined recursively as follows:

  1. (i)

$K_{1}$ is a cograph;

  2. (ii)

if $G_{1}$ and $G_{2}$ are cographs, then so is their disjoint union; and

  3. (iii)

if $G$ is a cograph, then so is its complement.

The class of cographs has been extensively studied over the last fifty years
(see, for example, [3, 6, 16]). In particular, there are numerous equivalent
characterizations of cographs including that a cograph is a graph in which
every connected induced subgraph has a disconnected complement.

Our goal in this paper is to give a matroid analogue of cographs by, loosely
speaking, considering the smallest class of matroids that is closed under
direct sums and complementation. One immediate obstacle to achieving this goal
is that matroids in general do not have complements. However, if $M$ is a
simple uniquely $GF(q)$-representable matroid and $k\geq r(M)$, the
$(GF(q),k)$-complement of $M$ is the matroid $PG(k-1,q)\backslash T$ where
$M\cong PG(k-1,q)|T$. Brylawski and Lucas [1] (see also [11, Proposition
10.1.7]) showed that this $(GF(q),k)$-complement of $M$ is well-defined. By
convention, we write $M^{c}$ for the $(GF(q),r(M))$-complement of $M$.
Although a $GF(q)$-representable matroid need not be uniquely representable
when $q\geq 4$, it is uniquely representable for $q$ in $\\{2,3\\}$. Thus we
only introduce analogues of cographs for binary and ternary matroids. In
particular, for $q$ in $\\{2,3\\}$, we define a $GF(q)$-comatroid recursively
as follows:

  1. (i)

$U_{0,0}$ is a $GF(q)$-comatroid;

  2. (ii)

if $M_{1}$ and $M_{2}$ are $GF(q)$-comatroids, then so is their direct sum;
and

  3. (iii)

if $M$ is a $GF(q)$-comatroid, then so is its $(GF(q),t)$-complement for all
$t\geq r(M)$.

As $PG(r-1,q)$ is the $(GF(q),r)$-complement of $U_{0,0}$, every projective
geometry $PG(r-1,q)$ for $r\geq-1$ is a $GF(q)$-comatroid. In particular, as
$U_{1,1}$ is $PG(0,q)$, we see that $U_{n,n}$ is a $GF(q)$-comatroid for all
$n\geq 0$. We sometimes call $GF(2)$\- and $GF(3)$-comatroids, binary and
ternary comatroids, respectively.

The following characterization of $GF(q)$-comatroids is particularly useful.

######  Theorem 1.1.

For $q$ in $\\{1,2\\}$, a simple $GF(q)$-representable matroid $M$ is a
$GF(q)$-comatroid if and only if $M$ is $U_{0,0}$ or, for all flats $F$ of
$PG(r(M)-1,q)$ with $r(F\cap E(M))=r(F-E(M))$, the restriction of
$PG(r(M)-1,q)$ to either $F\cap E(M)$ or $F-E(M)$ is disconnected.

Corneil, Lerchs, and Stewart [2] proved that a graph $G$ is a cograph if and
only if $G$ does not have the $4$-vertex path as an induced subgraph. The next
two theorems, which are our main results, prove matroid analogues of this
theorem for binary and ternary comatroids by using the fact that a set $X$ of
edges in a graph $H$ is the edge set of an induced subgraph of $H$ if and only
if $X$ is a flat of $M(H)$. The matroid $P(U_{3,4},U_{3,4})$, the parallel
connection of two $4$-circuits, is the cycle matroid of a $6$-cycle with a
single chord where this chord lies in two $4$-cycles.

######  Theorem 1.2.

A binary matroid $M$ is a binary comatroid if and only if neither $M$ nor
$M^{c}$ has a flat isomorphic to a circuit of size exceeding five, to
$P(U_{3,4},U_{3,4})$, or to the cycle matroid of one of the six $5$-vertex
graphs shown in Figure 1.

\begin{picture}(4634.0,2019.0)(180.0,-8083.0)\end{picture}

Figure 1. The cycle matroids of these graphs are induced-restriction-minimal
binary non-comatroids.

######  Theorem 1.3.

A ternary matroid $M$ is a ternary comatroid if and only if neither $M$ nor
$M^{c}$ has a flat isomorphic to a circuit of size exceeding three, to a
matroid that can be obtained from a circuit of size at least three by
$2$-summing a copy of $U_{2,4}$ to at least one of the elements of the
circuit, or to one of the five rank-$3$ matroids
$P(U_{2,3},U_{2,3}),U_{2,4}\oplus_{2}U_{2,4},P(U_{2,4},U_{2,3}),$ $M(K_{4}),$
and $\mathcal{W}^{3}$.

The proofs of these theorems are given in Sections 4 and 5, respectively. In
Section 2, we prove a number of preliminary results including Theorem 1.1. In
particular, we show that if we contract an element from a $GF(q)$-comatroid
and simplify the resulting matroid, then we get another $GF(q)$-comatroid. A
simple matroid $N$ is an induced minor of a simple matroid $M$ if $N$ can be
obtained from $M$ by a sequence of operations each of which consists of
restricting to a flat, or contracting an element and then simplifying. As
consequences of Theorems 1.2 and 1.3, we have the following characterizations
of binary and ternary comatroids in terms of forbidden induced minors.

######  Corollary 1.4.

A binary matroid is a binary comatroid if and only if it has no induced minor
isomorphic to the complement of a circuit of size exceeding five, to
$P(U_{3,4},U_{3,4})$, to the cycle matroid of one of the six $5$-vertex graphs
in Figure 1, or to the complements of these cycle matroids in $PG(3,2)$.

######  Corollary 1.5.

A ternary matroid is a ternary comatroid if and only if it has no induced
minor isomorphic to any of the following: the complements of all matroids that
can be obtained from a circuit of size at least three by $2$-summing a copy of
$U_{2,4}$ to some, possibly empty, set of elements of the circuit; the
matroids, $U_{3,4},$ $P(U_{2,3},U_{2,3}),$ $U_{2,4}\oplus_{2}U_{2,3},$
$U_{2,4}\oplus_{2}U_{2,4},$ $P(U_{2,4},U_{2,3}),$ $M(K_{4}),$ and
$\mathcal{W}^{3}$; or the complements of these matroids in $PG(2,3)$.

##  2\. Preliminaries

Throughout the paper, we call cocircuits, flats, and hyperplanes of
$PG(r-1,q)$ projective cocircuits, projective flats, and projective
hyperplanes, respectively. Viewing a $GF(q)$-representable matroid $M$ as a
restriction of $PG(r(M)-1,q)$, we color the elements of $E(M)$ green while
assigning the color red to the elements of $PG(r(M)-1,q)$ not in $E(M)$. We
will frequently use $G$ and $R$ to denote both the sets of green and red
elements and the matroids obtained by restricting $PG(r(M)-1,q)$ to these sets
of elements. The next lemma is an immediate consequence of the fact that the
elements of a projective geometry are not all contained in two hyperplanes.

######  Lemma 2.1.

For an arbitrary prime power $q$, let $(G,R)$ be a $2$-coloring of
$PG(r-1,q)$. Then $r(G)=r$ or $r(R)=r$.

######  Proposition 2.2.

For an arbitrary prime power $q$, let $(G,R)$ be a $2$-coloring of
$PG(r-1,q)$. Let $j$ and $k$ be the vertical connectivities of $G$ and $R$,
respectively. Then $j+k\geq r$ unless $(q,r)=(2,3)$ and
$\\{G,R\\}=\\{U_{3,3},U_{2,3}\oplus U_{1,1}\\}$.

###### Proof.

Assume that the result fails. If $R$ is empty, then $k=0$ and $j=r$, a
contradiction. Thus we may assume that $G$ and $R$ are both non-empty. Then
$j$ and $k$ are both non-zero, so we may assume that
$j,k\in\\{1,2,\dots,r-2\\}$. Observe that if $r(R)<r$, then $G$ contains
$AG(r-1,q)$ and hence $j\geq r-1$, a contradiction. Therefore $r(G)=r(R)=r$.
Thus $G$ has an exact vertical $j$-separation $(A,B)$ with $r(A)\geq r(B)$,
and $R$ has an exact vertical $k$-separation $(X,Y)$ with $r(X)\geq r(Y)$. Let
$r(A)=a$. Then

(2.1)
$|G|\leq\frac{q^{a}-1}{q-1}+\frac{q^{a}-1}{q-1}-\frac{q^{j-1}-1}{q-1}=\frac{2q^{a}-q^{j-1}-1}{q-1}.$

By symmetry, with $r(X)=x$, we have

(2.2) $|R|\leq\frac{2q^{x}-q^{k-1}-1}{q-1}.$

First suppose that $x=r-1$. Then $r(Y)=k$. Let $H_{X}$ be the projective
hyperplane spanned by $X$. Observe that the intersection of $H_{X}$ with the
projective flat $F_{Y}$ spanned by $Y$ is a projective flat of rank $k-1$.
Thus, as $R-H_{X}\subseteq F_{Y}-(F_{Y}\cap H_{X})$, we have

(2.3) $|R-H_{X}|\leq\frac{q^{k}-1}{q-1}-\frac{q^{k-1}-1}{q-1}=q^{k-1}.$

Suppose that $a=r-1$. Then $r(B)=j$ and so, as for (2.3), we have
$|G-H_{A}|\leq q^{j-1}$ where $H_{A}$ is the projective hyperplane spanned by
$A$. Note that $E(PG(r-1,q))-(H_{A}\cup H_{X})$ has at least $q^{r-2}$
elements and so it follows by (2.3) that $q^{k-1}+q^{j-1}\geq q^{r-2}$. Since
$j$ and $k$ are in $\\{1,2,\dots,r-2\\}$, this is a contradiction unless
$(q,r)=(2,3)$ and $k=1=j$ and $r=3$. In the exceptional case, it is
straightforward to check that $\\{G,R\\}=\\{U_{3,3},U_{2,3}\oplus U_{1,1}\\}$,
and we get the exceptional case noted in the proposition.

We may now assume that $a<r-1$. Let $F_{A}$ be the projective flat spanned by
$A$. Observe that $F_{A}\cap H_{X}$ is a projective flat of rank $a$ or $a-1$.
Thus

$\displaystyle|(R\cup G)-H_{X}|$ $\displaystyle=$
$\displaystyle|R-H_{X}|+|G-H_{X}|$ $\displaystyle\leq$
$\displaystyle|R-H_{X}|+|G|-|F_{A}\cap H_{X}|$ $\displaystyle\leq$
$\displaystyle q^{k-1}+\frac{2q^{a}-q^{j-1}-1}{q-1}-\frac{q^{a-1}-1}{q-1}$

where the last step follows by (2.3) and (2.1). As $|(R\cup
G)-H_{X}|=|E(AG(r-1,q)|=q^{r-1}$, we have
$q^{k-1}+\frac{2q^{a}-q^{j-1}-1}{q-1}-\frac{q^{a-1}-1}{q-1}\geq q^{r-1}$. As
the left-hand side of the last inequality is bounded above by
$q^{r-3}+\frac{q^{r-3}(2q-1)}{q-1}-\frac{q^{j-1}-1}{q-1}$, we deduce that
$1+\frac{2q-1}{q-1}>q^{2}$. This is a contradiction as $q\geq 2$. We conclude
that $x<r-1$. By symmetry, $a<r-1$. Then, by (2.2) and (2.1),
$|R|+|G|<\frac{q^{r}-1}{q-1}$, a contradiction. ∎

Next, we move towards proving Theorem 1.1. We omit the straightforward proof
of the following result.

######  Lemma 2.3.

Let $M$ be a simple $GF(q)$-representable matroid.

  1. (i)

If $q=2$ and $r(M)\leq 3$, then $M$ is a $GF(q)$-comatroid.

  2. (ii)

If $q=3$ and $r(M)\leq 2$, then $M$ is a $GF(q)$-comatroid.

######  Lemma 2.4.

Let $M$ be a $GF(q)$-comatroid and suppose that $M$ is disconnected. Then each
of its components is a $GF(q)$-comatroid.

###### Proof.

By Lemma 2.3, we may assume that $r(M)\geq 4$. Let $M=M_{1}\oplus M_{2}$. Take
a shortest sequence of direct sums and complements that shows that $M$ is a
$GF(q)$-comatroid. Assume that the final step in creating $M$ is not a direct
sum. Then this final step involves taking the $(GF(q),t)$-complement of some
matroid $N_{1}$ where $t\geq r(N_{1})$. As $M$ is disconnected,
$t=r(N_{1})\geq r(M)$, otherwise $M$ has $AG(t-1,q)$ as a restriction and so
is connected. Thus $N_{1}^{c}=M$. Moreover, as the vertical connectivity of
$M$ is one, Proposition 2.2 implies that $N_{1}$ is connected. Since
$N^{c}_{1}=M$, the predecessor of $N_{1}$ in the construction of $M$ is its
$(GF(q),s)$-complement $N_{2}$ for some $s\geq r(N_{1})+1$. Then $N_{2}$ has
$AG(s-1,q)$ as a restriction, so it is connected. The predecessor of $N_{2}$
in the production of $M$ must again be a connected matroid $N_{3}$ of rank
exceeding $r(N_{2})$. Tracing back the predecessors of $M$ in its creation as
a $GF(q)$-comatroid, we obtain an infinite sequence of matroids of increasing
ranks. This contradicts the fact that $M$ is created by a finite process. We
conclude that, when $M$ is a disconnected $GF(q)$-comatroid, the final step in
constructing it is taking the direct sum of two $GF(q)$-comatroids. Thus if
$M$ has exactly two components, then each component is a $GF(q)$-comatroid. We
now argue by induction on the number of components of $M$. As the final step
in creating $M$ is taking a direct sum of two $GF(q)$-comatroids, it follows
by induction that each component of $M$ is a $GF(q)$-comatroid. ∎

######  Lemma 2.5.

For $q$ in $\\{2,3\\}$, a $GF(q)$-representable matroid $M$ such that
$r(M)=r(M^{c})$ and both $M$ and $M^{c}$ are connected is not a
$GF(q)$-comatroid.

###### Proof.

For $M$ to satisfy the hypotheses of the lemma, we must have $r(M)\geq 3$.
Moreover, $r(M)\geq 4$ if $q=2$. Assume that $M$ is a $GF(q)$-comatroid. Again
we take a shortest sequence of direct sums and complements that shows that $M$
is a $GF(q)$-comatroid. Then the final step in creating $M$ must have been
taking a complement. As $r(M)=r(M^{c})$, for some $N_{0}$ in $\\{M,M^{c}\\}$,
the predecessor of $N_{0}$ in the creation of $M$ is the
$(GF(q),t)$-complement $N_{1}$ of $N_{0}$ for some $t>r(M)$. This matroid is
also connected. Its predecessor in the construction of $M$ is the
$(GF(q),s)$-complement $N_{2}$ of $N_{1}$ for some $s>r(N_{1})$. Again,
$N_{2}$ is connected and this process must continue indefinitely, a
contradiction. ∎

As an immediate consequence of the last lemma, we have the following.

######  Corollary 2.6.

A $k$-circuit is a $GF(q)$-comatroid if and only if $q+k\leq 6$.

######  Lemma 2.7.

The restriction of a $GF(q)$-comatroid to one of its flats is a
$GF(q)$-comatroid.

###### Proof.

We argue by induction on the rank of the $GF(q)$-comatroid $M$. The result
holds by Lemma 2.3 if $r(M)\leq 2$. Now assume it holds for every
$GF(q)$-comatroid of rank less than $n$ and let $M$ be a $GF(q)$-comatroid of
rank $n$ where $n\geq 3$. Then $M$ is obtained by taking complements and
direct sums. Let $F$ be a proper flat of $M$. Assume first that $M$ is
disconnected. Then, by Lemma 2.4 and the induction assumption, $M|(F\cap
E(M_{i}))$ is a $GF(q)$-comatroid for each component $M_{i}$ of $M$. Thus
$M|F$ is a $GF(q)$-comatroid. We may now assume that $M$ is connected. Suppose
$N=M^{c}$. Then $N$ is a $GF(q)$-comatroid. Let $F_{P}$ be the projective flat
of $PG(r(M)-1,q)$ that is spanned by $F$. Then $F_{P}-F$ is a flat of $N$. The
complement of $N|(F_{P}-F)$ in $F_{P}$ is $M|F$. Assume first that
$r(N)<r(M)$. Then, by the induction assumption, $N|(F_{P}-F)$ is a
$GF(q)$-comatroid. Thus $M|F$ is also a $GF(q)$-comatroid. Hence we may assume
that $r(N)=r(M)$. By Lemma 2.5, $N$ is not connected, so, by the induction
assumption, $N|(F_{P}-F)$ and hence $M|F$ is a $GF(q)$-comatroid. ∎

###### Proof of Theorem 1.1.

Suppose $M$ is a non-empty $GF(q)$-comatroid. By Lemma 2.7, if $F$ is a flat
of $PG(r(M)-1,q)$, then $M|(F\cap E(M))$ is a $GF(q)$-comatroid. Hence so is
its complement in $F$, namely $PG(r(M)-1,q)|(F-E(M))$. By Lemma 2.1, at least
one of $r(F\cap E(M))$ and $r(F-E(M))$ is $r(F)$. Thus, by Lemma 2.5, if
$r(F\cap E(M))=r(F-E(M))$, then the restriction of $PG(r(M)-1,q)$ to $F\cap
E(M)$ or $F-E(M)$ is disconnected.

Conversely, suppose that $M$ is non-empty and that, for all flats $F$ of
$PG(r(M)-1,q)$ with $r(F\cap E(M))=r(F-E(M))$, the restriction of
$PG(r(M)-1,q)$ to either $F\cap E(M)$ or $F-E(M)$ is disconnected. We argue by
induction on $r(M)$ that $M$ is a $GF(q)$-comatroid. By Lemma 2.3, this is
true if $r(M)\leq 2$. Assume it is true for $r(M)<n$ and let $r(M)=n$. If $M$
is disconnected, then, by the induction assumption, each component is a
$GF(q)$-comatroid. Hence so too is $M$. Thus $M$ is connected. Suppose
$r(M)=r(M^{c})$. Then, by the hypothesis, $M^{c}$ is disconnected. Since
$M^{c}$ obeys the same condition as $M$, each of its components is a
$GF(q)$-comatroid. Thus so is $M^{c}$. Hence $M$ is a $GF(q)$-comatroid. We
may now assume that $r(M)>r(M^{c})$. Take $F_{0}$ to be the flat of
$PG(r(M)-1,q)$ spanned by $M^{c}$. Let $F_{1}$ be a flat of $F_{0}$ with
$r(F_{1}\cap E(M^{c}))=r(F_{1}-E(M^{c}))$. Then $r(F_{1}\cap
E(M))=r(F_{1}-E(M))$ so the restriction of $PG(r(M)-1,q)$ to $F_{1}\cap E(M)$
or $F_{1}-E(M)$ is disconnected. Thus the restriction of $F_{0}$ to $F_{1}\cap
E(M^{c})$ or $F_{1}-E(M^{c})$ is disconnected. We conclude that $M^{c}$ obeys
the same condition as $M$, so, by the induction assumption, $M^{c}$ is a
$GF(q)$-comatroid. The $(GF(q),r(M))$-complement of $M^{c}$ is $M$ so it too
is a $GF(q)$-comatroid, as required. ∎

In the following result, we note that if a $GF(q)$-comatroid is connected, it
is highly connected.

######  Proposition 2.8.

Let $M$ be a connected $GF(q)$-comatroid of rank $r$. Then $M$ is vertically
$(r-1)$-connected.

###### Proof.

By Lemma 2.5, $M^{c}$ is either disconnected or has rank less than $r$. If
$M^{c}$ is disconnected, then, by Proposition 2.2, $M$ is vertically
$(r-1)$-connected. We may now assume that $M^{c}$ has rank less than $r$. Then
$M$ is an extension of $AG(r-1,q)$. Since this affine geometry is vertically
$(r-1)$-connected, the result follows. ∎

Next we show that the class of $GF(q)$-comatroids is closed under induced
minors. For a subset $X$ of the ground set of a simple $GF(q)$-representable
matroid $M$, we say $X$ is connected if $M|X$ is connected. When $X$ is a flat
of $M$, we denote by $X^{c}$ the matroid $(M|X)^{c}$ that is obtained from the
projective closure of $X$ by deleting $X$.

######  Proposition 2.9.

Every induced minor of a $GF(q)$-comatroid is a $GF(q)$-comatroid.

###### Proof.

By Lemma 2.7, the restriction of a $GF(q)$-comatroid to one of its flats is a
$GF(q)$-comatroid. Now take an element $e$ of $M$ and assume that ${\rm
si}(M/e)$ is not a $GF(q)$-comatroid. View ${\rm si}(M/e)$ as a restriction of
$PG(r(M)-2,q)$. Then, by Theorem 1.1, there is a flat $F$ of ${\rm si}(M/e)$
such that $F$ and $F^{c}$ are both connected and each has rank $k$, say.
Observe that ${\rm cl}_{M}(F\cup e)$ is a connected flat of $M$ of rank $k+1$
unless $e$ is a coloop of $M|(F\cup e)$. In the exceptional case, $F$ is a
flat of $M$ and, therefore, $M$ has a flat $F$ such that both $F$ and $F^{c}$
are connected of rank $k$, a contradiction. We deduce that ${\rm cl}_{M}(F\cup
e)$ is a connected flat of rank $k+1$. We complete the proof by establishing
the contradication that the complement of ${\rm cl}_{M}(F\cup e)$ is also
connected of rank $k+1$. To see this, note that, for each element $g$ of
$F^{c}$, all the elements apart from $e$ that are on the projective line
containing $\\{e,g\\}$ in $PG(r(M)-1,q)$ are in the complement of ${\rm
cl}_{M}(F\cup e)$. Thus this complement contains a set of rank $k+1$ that is a
union of interlocking $4$-circuits. Hence this complement is connected. ∎

##  3\. Connected hyperplanes

Kelmans [7] and Seymour (in [10]) independently established that if $M$ is a
simple connected binary matroid that has no cocircuits of size less than
three, then $M$ has a connected hyperplane. That theorem was extended in
several ways by McNulty and Wu [9]. In this section, we note two of these
extensions and prove an analogue for ternary matroids of the result of Kelmans
and Seymour. These results on connected hyperplanes will be crucial in proving
our characterizations of binary and ternary comatroids.

We begin the section by identifying when there is a free element in a binary
or ternary matroid, where an element $e$ is free in a matroid $M$ if $e$ is
not a coloop of $M$ and the only circuits that contain $e$ are spanning.
Doubtless, the results in the next lemma are known but we include the proofs
for completeness. In a rank-zero matroid, every element is free. In a rank-one
matroid, the free elements are the non-loops unless the matroid has a coloop
in which case there are no free elements. Thus the next result only considers
matroids $M$ of rank at least two noting that $e$ is free in $M$ if and only
if $e$ is free in ${\rm si}(M)$ and $e$ is in no $2$-circuits of $M$.

######  Lemma 3.1.

Let $M$ be a simple $GF(q)$-representable matroid of rank at least two and let
$e$ be a free element of $M$. Then

  * (i)

$M$ is a circuit when $q=2$; and

  * (ii)

when $q=3$, either $M\cong U_{2,4}$, or $M$ can be obtained from a circuit $C$
containing $e$ by, for some subset $D$ of $C-e$, $2$-summing a copy of
$U_{2,4}$ across each element of $D$.

###### Proof.

Since $e$ is free in $M$, there is a spanning circuit $C_{0}$ of $M$
containing $e$. Then $M|C_{0}$ is represented over $GF(q)$ by $[I_{r}|{\bf
1}]$ where ${\bf 1}$, the column of all ones, is labelled by $e$. When $q=2$,
we cannot add any further elements without creating either a $2$-circuit, or a
circuit that contains $e$ and has fewer than $r+1$ elements. Thus (i) holds.

Now suppose that $q=3$. If $r(M)=2$, then $M$ is isomorphic to $U_{2,3}$ or
$U_{2,4}$. Assume that $r(M)\geq 3$. Let $Z$ be a matrix representing $M$ over
$GF(3)$ and having $[I_{r}|{\bf 1}]$ as its first $r+1$ columns. We will write
the elements of $GF(3)$ as $0,1$, and $-1$. Let $f$ be a column of $Z$ other
than one of the first $r+1$ columns. As $M$ is simple, $f$ has at least two
non-zero entries. If $f$ has two non-zero entries with a common sign, then
there is a circuit containing $\\{e,f\\}$ having at most $r$ elements, a
contradiction. It follows that $f$ has exactly two non-zero entries and that
these entries have different signs. If columns $f$ and $g$ have their non-zero
entries in, respectively, rows $1$ and $2$, and rows $1$ and $3$, then $M$ has
an $r$-element circuit containing $\\{e,f,g\\}$. We conclude that two distinct
columns of $Z$ that are not columns of $[I_{r}|{\bf 1}]$ must have disjoint
sets of rows containing their non-zero entries. It follows that $M$ can be
obtained from a circuit $C$ containing $e$ by, for some subset $D$ of $C-e$,
$2$-summing a copy of $U_{2,4}$ across each element of $D$. To see this, for
each column of $Z$ with two entries of opposite signs, add an additional
column to $Z$ obtained by changing the sign of one of these entries. These
added elements form the basepoints of the 2-sums. ∎

The following technical result will be helpful in proving our results on
connected hyperplanes.

######  Lemma 3.2.

In a simple connected matroid $M$, let $e$ be an element and $A$ be a maximal
subset of $E(M)$ that is connected, non-spanning and contains $e$. Let $C$ be
a circuit of $M$ that meets both $A$ and $E(M)-A$ such that $C-A$ is minimal.
Then $A$ is a flat, $r(A\cup C)=r(M)$, the set $C-A$ is a series class of
$M|(A\cup C)$,

$r(M)=r(A)+|C-A|-1,$

and one of the following holds:

  * (i)

$A$ is a connected hyperplane of $M$; or

  * (ii)

$C-A$ is a series class of $M$ with at least three elements; or

  * (iii)

$|C-A|\geq 3$ and $E(M)-(A\cup C)$ is non-empty.

###### Proof.

The minimality of $C-A$ implies that, in $M|(A\cup C)$, a circuit that meets
$C-A$ must contain $C-A$, so $C-A$ is a series class. The maximality of $A$
implies that $A$ is a flat of $M$ and that $r(A\cup C)=r(M)$. Thus
$r(M)=r(A)+|C-A|-1$, so $|C-A|\geq 2$. If $|C-A|=2$, then $A$ is a connected
hyperplane of $M$. Thus we may assume that $|C-A|\geq 3$. In that case, (ii)
or (iii) holds. ∎

The next result extends the theorem of Kelmans and Seymour, borrowing much
from Seymour’s proof.

######  Theorem 3.3.

Let $e$ be an element of a simple connected binary matroid $M$. Then

  * (i)

$M$ is a circuit; or

  * (ii)

$M$ has a connected hyperplane containing $e$; or

  * (iii)

$M$ has a series class of size at least three that avoids $e$.

###### Proof.

Assume that the theorem fails. By Lemma 3.1, $e$ is not free in $M$. Thus $M$
has a subset $A$ that contains a circuit containing $e$ and is maximal with
respect to being connected and non-spanning. We take a circuit $C_{1}$ that
meets both $A$ and its complement such that $|C_{1}-A|$ is minimal. By Lemma
3.2, $|C_{1}-A|\geq 3$ and $E(M)-(C_{1}\cup A)$ contains an element, say $x$.
Moreover, for $y$ in $C_{1}-A$, the set $A\cup(C_{1}-y)$ contains a basis $B$
of $M$. Let $C_{2}=C(x,B)$. Then $C_{2}$ meets $A$ otherwise, as $M$ is
binary, $C_{1}\triangle C_{2}$ is a circuit that contradicts the choice of
$C_{1}$. Now $|C_{2}-A|\geq|C_{1}-A|$. Hence $C_{2}$ contains exactly
$|C_{1}-A|-1$ elements of $C_{1}-A$. Thus $C_{1}\triangle C_{2}$ contains a
circuit $D$ that contains $x$, meets $A$, and has exactly two elements not in
$A$. Then $D$ contradicts the choice of $C_{1}$. ∎

As an immediate consequence of this theorem, we have the following.

######  Corollary 3.4.

Let $M$ be a simple connected binary matroid $M$. Then

  * (i)

$M$ is a circuit; or

  * (ii)

$M$ has a connected hyperplane; or

  * (iii)

$M$ has at least two distinct series classes of size at least three.

The next two results of McNulty and Wu [9, Theorem 1.4 and Lemma 2.10] are
much more substantial extensions of the theorem of Kelmans and Seymour. Both
of these results will be used in the proof of Theorem 1.2.

######  Theorem 3.5.

Let $M$ be a simple connected binary matroid with no cocircuits of size less
than three. Then every element of $M$ is in at least two connected
hyperplanes; and $M$ has at least four connected hyperplanes.

######  Lemma 3.6.

Let $M$ be a $3$-connected binary matroid with at least four elements. Then,
for any two distinct elements $e$ and $f$ of $M$, there is a connected
hyperplane containing $e$ and avoiding $f$.

McNulty and Wu [9, Fig. 1] also showed that a simple connected binary matroid
with no cocircuits of size less than three may have exactly four connected
hyperplanes. In addition, they noted that Joseph Bonin has pointed out that
the dual of $PG(2,3)$ is a $3$-connected ternary matroid having no connected
hyperplanes. Of course, the same is true for the duals of all of the matroids
$PG(r-1,3)$ with $r\geq 3$. As another example of a simple connected ternary
matroid with no cocircuits of size less than three and no connected
hyperplanes, take a circuit with at least three elements and 2-sum a copy of
$U_{2,4}$ across each element. Each of these examples has numerous triads. As
we shall see, by confining our attention to simple connected ternary matroids
having no cocircuits of size less than four, we can establish the existence of
at least two connected hyperplanes. The next result is key to proving this.

######  Theorem 3.7.

Let $M$ be a simple connected matroid having no cocircuits of size less than
four. Assume that $M$ has no $U_{2,5}$-minor and no $U_{3,5}$-minor. Let $e$
be an element of $M$ that is not free. Then $M$ has a connected hyperplane
containing $e$.

###### Proof.

Since $e$ is not free, $E(M)$ has a subset $A$ that contains a circuit
containing $e$ and is maximal with respect to being connected and non-
spanning. Assume that the theorem fails.

As $M$ is connected, it has a circuit meeting both $A$ and its complement.
Choose such a circuit $C_{1}$ for which $|C_{1}-A|$ is a minimum. By Lemma
3.2, $A$ is a flat of $M$, while $C_{1}-A$ is a series class in $M|(A\cup
C_{1})$, and $r(A\cup C_{1})=r(M)$. Moreover,

######  3.7.1.

$r(M)=r(A)+|C_{1}-A|-1$.

As $M$ has no cocircuits of size less than four, $|E(M)-(A\cup C_{1})|\geq 2$.
Take $s$ in $C_{1}-A$. Then $M$ has a basis $B$ that contains $C_{1}-s$ and is
contained in $A\cup(C_{1}-s)$. Choose $x$ in $E(M)-(A\cup C_{1})$ and let
$C_{2}$ be $C(x,B)$.

Next we show the following.

######  3.7.2.

If $C_{2}\cap A=\emptyset$, then $|C_{2}|=3$.

Let $C_{1}\cap C_{2}=\\{y_{1},y_{2},\dots,y_{t}\\}$. By circuit elimination,
$M$ has a circuit $D_{i}$ that contains $x$ and not $y_{i}$ such that
$D_{i}\subseteq C_{1}\cup x$. Then $D_{i}\supseteq C_{1}-C_{2}$. Moreover, the
choice of $C_{1}$ implies that $D_{i}-A=((C_{1}-A)-y_{i})\cup x$. Thus
$D_{i}=(C_{1}-y_{i})\cup x$. From $M|(C_{1}\cup x)$, contract
$C_{1}-\\{y_{1},y_{2},\dots,y_{k},s\\}$. The resulting matroid $N$ has ground
set $\\{y_{1},y_{2},\dots,y_{k},s,x\\}$ and has every subset of size $k+1$ as
a circuit except possibly $\\{y_{1},y_{2},\dots,y_{k},x\\}$. If a proper
subset of $\\{y_{1},y_{2},\dots,y_{k},x\\}$ is a circuit of $N$, then this
circuit is a proper subset of a $(k+1)$-element circuit of $N$, a
contradiction. Thus $N\cong U_{k,k+2}$. As $M$ has no $U_{3,5}$-minor and $M$
is simple, we deduce that $k=2$, so $|C_{2}|=3$. Hence (3.7.2) holds.

Next we note that

######  3.7.3.

$|C_{1}-A|\geq 4$.

As the theorem fails, $|C_{1}-A|>2$, by 3.7.1. Assume that $|C_{1}-A|=3$. Thus
$r(M/A)=2$. Moreover, $|E(M/A)|\geq 5$ as $|E(M)-(A\cup C_{1})|\geq 2$. Since
$A$ is a flat of $M$, the matroid $M/A$ has no loops. Suppose it has a
$2$-circuit $\\{u,v\\}$. Then $M$ has a circuit $C^{\prime}$ such that
$\\{u,v\\}\subseteq C^{\prime}\subseteq\\{u,v\\}\cup A$. Thus $C^{\prime}$
contradicts the choice of $C_{1}$. We deduce that $M/A$ is simple, so $M/A$
has $U_{2,5}$ as a restriction, a contradiction. Thus 3.7.3 holds.

######  3.7.4.

For $x$ in $E(M)-(A\cup C_{1})$, there is an element $s$ of $C_{1}-A$ such
that $M$ has a triangle that contains $x$ and has its other two elements in
$C_{1}-(A\cup s)$.

Assume that $M$ has no such triangle. For $s$ in $C_{1}-A$, let $B_{s}$ be a
basis of $M$ containing $C_{1}-s$ and let $C_{s}=C(x,B_{s})$. By 3.7.2,
$C_{s}$ meets $A$. By the choice of $C_{1}$, we deduce that
$C_{s}-A=(C_{1}-A-s)\cup x$. Let $|C_{1}-A|=m$ and $N^{\prime}=M|(A\cup
C_{1}\cup x)$. Then, for every $m$-element subset $Y$ of $(C_{1}-A)\cup x$,
there is a circuit of $N^{\prime}$ that meets $(C_{1}-A)\cup x$ in $Y$ and
also meets $A$. Now $r(N^{\prime})=r(M)=r(A)+|C_{1}-A|-1$. Contracting $A$
from $N^{\prime}$ gives a matroid of rank $m-1$ having $m+1$ elements. Take an
$m$-element subset $Y$ of $(C_{1}-A)\cup x$. Then $Y$ contains a circuit
$Y^{\prime}$ of $N^{\prime}/A$. Thus $Y^{\prime}\cup A$ contains a circuit
$Y^{\prime\prime}$ of $M$ containing $Y^{\prime}$. Then $Y^{\prime\prime}$
meets $A$ otherwise $Y^{\prime\prime}=Y^{\prime}\subseteq Y$, a contradiction
as $Y$ is independent in $M$. Thus, by the choice of $C_{1}$, we must have
that $|Y^{\prime\prime}-A|=m$. Hence
$m=|Y|\geq|Y^{\prime}|\geq|Y^{\prime\prime}-A|\geq m$, so $Y^{\prime}=Y$ and
$Y$ is a circuit of $N^{\prime}/A$. Thus $N^{\prime}/A\cong U_{m-1,m+1}$. By
3.7.3, $m\geq 4$, so $M$ has a $U_{3,5}$-minor, a contradiction. Thus 3.7.4
holds.

######  3.7.5.

$M$ does not have a $4$-element subset $X$ with exactly two elements in
$C_{1}-A$ and exactly two elements in $E(M)-(A\cup C_{1})$ such that $M|X\cong
U_{2,4}$.

Assume that $\\{y_{1},y_{2},x_{1},x_{2}\\}$ is such a $4$-element subset $X$
of $E(M)$ where $\\{y_{1},y_{2}\\}\subseteq C_{1}-A$. Then
$r(A\cup(C_{1}-\\{y_{1},y_{2}\\}))=r(M)-1$ and $r(X)=2$. Thus, in $M|(A\cup
C_{1}\cup\\{x_{1},x_{2}\\})$, which is connected, $X$ is $2$-separating.
Therefore, $M|(A\cup C_{1}\cup\\{x_{1},x_{2}\\})$ is the $2$-sum, with
basepoint $p$ of connected matroids $M_{1}$ and $M_{2}$ with ground sets
$A\cup(C_{1}-\\{y_{1},y_{2}\\})\cup p$ and $X\cup p$. Since $|X\cup p|=5$ and
$M_{2}$ has rank $2$, we must have that $p$ is parallel to some element of $X$
otherwise $M$ has a $U_{2,5}$-minor. Thus a member of
$\\{y_{1},y_{2},x_{1},x_{2}\\}$ is in the closure of
$A\cup(C_{1}-\\{y_{1},y_{2}\\})$. Neither $y_{1}$ nor $y_{2}$ is in this
closure. If $x_{1}$ or $x_{2}$ is, then there is a circuit $D$ containing
$x_{i}$ for some $i$ in $\\{1,2\\}$ such that $D\subseteq
A\cup(C_{1}-\\{y_{1},y_{2}\\})\cup x_{i}$. The choice of $C_{1}$ implies that
$D$ does not meet $A$. Thus $D\subseteq(C_{1}-A)\cup x_{i}$. Then, by circuit
elimination, $(D\cup\\{x_{i},y_{1},y_{2}\\})-x_{i}$ contains a circuit. But
this circuit is properly contained in $C_{1}$, a contradiction. We conclude
that 3.7.5 holds.

######  3.7.6.

$M$ does not have two triangles $\\{y_{1},y_{2},x_{2}\\}$ and
$\\{y_{1},y_{3},x_{3}\\}$ where $y_{1},y_{2}$, and $y_{3}$ are distinct
elements of $C_{1}-A$, and $x_{2}$ and $x_{3}$ are distinct elements of
$E(M)-(A\cup C_{1})$.

Assume that $M$ does have two such triangles. Then $M$ has $(C_{1}-y_{1})\cup
x_{2}$ as a circuit, $C^{\prime}_{1}$ say. Thus
$\\{y_{2},x_{2},y_{3},x_{3}\\}$ is a circuit of $M$ having exactly three
elements in $C^{\prime}_{1}-A$. This is the fundamental circuit of $x_{3}$
with respect to a basis of $M$ that contains $C^{\prime}_{1}-t$ where $t\in
C^{\prime}_{1}-A-\\{x_{2},y_{2},y_{3}\\}$, the existence of such an element
$t$ being a consequence of 3.7.3. Thus, using $C^{\prime}_{1}$ in place of
$C_{1}$ in 3.7.2, we get a contradiction. Hence 3.7.6 holds.

By 3.7.4, for each element $x$ in $E(M)-(A\cup C_{1})$, there is a triangle of
$M$ that contains $x$ and two elements of $C_{1}-A$. Moreover, by 3.7.5 and
3.7.6, if $x_{1}$ and $x_{2}$ are distinct elements of $E(M)-(A\cup C_{1})$,
then the corresponding triangles are disjoint.

Suppose that there are exactly $k$ elements, $x_{1},x_{2},\dots,x_{k}$, in
$E(M)-(A\cup C_{1})$ and that the corresponding triangles are
$\\{x_{i},y_{i},z_{i}\\}$ for $1\leq i\leq k$ where
$\\{y_{i},z_{i}\\}\subseteq C_{1}-A$. Then $E(M)-(A\cup
C_{1})-\\{y_{1},z_{1}\\}$ has rank $r(M)-1$. The closure of this set contains
$\\{x_{2},x_{3},\dots,x_{k}\\}$. The complement of this closure is
$\\{x_{1},y_{1},z_{1}\\}$. Therefore $M$ has a triad. This contradiction
completes the proof of the theorem. ∎

######  Corollary 3.8.

Let $M$ be a simple connected ternary matroid having no cocircuits of size
less than four. Then $M$ has at least two connected hyperplanes.

###### Proof.

By Lemma 3.1(ii), since $M$ has no cocircuits of size less than four, $M$ has
no free elements. Let $e$ be an element of $M$. Then, by Theorem 3.7, $M$ has
a connected hyperplane $H_{e}$ containing $e$. For $f$ in $E(M)-H_{e}$, there
is a connected hyperplane $H_{f}$ containing $f$, so the corollary holds. ∎

In view of Theorem 3.5, it is of interest to specify the minimum number of
connected hyperplanes in a simple connected ternary matroid with no cocircuits
of size less than four. There are infinitely many examples of such matroids
with exactly four connected hyperplanes but we do not know if four is indeed
the minimum number of connected hyperplanes. To get a family of examples with
exactly four connected hyperplanes, first take a graph $G$ formed from two
vertex-disjoint paths $x_{1}x_{2}\dots x_{n}$ and $y_{1}y_{2}\dots y_{n}$ for
some $n\geq 1$ by adding the $n$ edges $x_{i}y_{i}$, the $n-1$ edges of the
form $x_{i}y_{i+1}$ for $1\leq i\leq n-1$, and the $n-1$ edges of the form
$x_{j+1}y_{j}$ for $1\leq j\leq n-1$. Then take two copies, $N_{1}$ and
$N_{2}$, of $M(K_{4})$, pick a point $p_{i}$ of $N_{i}$ and freely add a point
$q_{i}$ to one of the triangles of $N_{i}$ not containing $p_{i}$. Finally,
take the parallel connection of $N_{1}$ and $M(G)$ with respect to the
basepoints $p_{1}$ and $x_{1}y_{1}$, and then attach $N_{2}$ to the resulting
matroid via parallel connection with respect to the basepoints $x_{n}y_{n}$
and $p_{2}$. The resulting simple connected ternary matroid has $5n+8$
elements, rank $2n+3$, and has no cocircuits of size less than four. It also
has exactly four connected hyperplanes.

##  4\. Induced-restriction-minimal non-$GF(2)$-comatroids

An induced-restriction-minimal non-$GF(q)$-comatroid is a
$GF(q)$-representable matroid $M$ that is not a $GF(q)$-comatroid such that
every proper flat of $M$ is a $GF(q)$-comatroid. The collection of such
matroids $M$ will be denoted by $\mathcal{M}_{q}$. Clearly,
$M^{c}\in\mathcal{M}_{q}$ for every matroid $M$ in $\mathcal{M}_{q}$. This
section begins with some preliminary results that will be used in the proofs
of the main theorems. It concludes with proofs of Theorem 1.2 and Corollary
1.4.

######  Lemma 4.1.

For $q$ in $\\{2,3\\}$, let $X$ be a subset of $PG(r-1,q)$ having at least
$q^{r-1}+1$ elements. Then the matroid $PG(r-1,q)|X$ is connected and has rank
$r$.

###### Proof.

Observe that $X$ has more elements than a hyperplane of $PG(r-1,q)$, so
$PG(r-1,q)|X$ has rank $r$. Assume that $PG(r-1,q)|X$ is disconnected. Then,
for some $j$ with $1\leq j\leq r-1$, the matroid $PG(r-1,k)|X$ is contained in
$PG(j-1,q)\oplus PG(r-j-1,q)$. Thus
$|X|\leq\frac{q^{j}-1}{q-1}+\frac{q^{r-j}-1}{q-1}=\frac{q^{j}+q^{r-j}-2}{q-1}$.
This function of $j$ is maximized when $j$ is $1$ or $r-1$, so $|X|\leq
q^{r-1}$, a contradiction. ∎

######  Lemma 4.2.

For $q$ in $\\{2,3\\}$, let $N$ be the parallel connection of $PG(j-1,q)$ and
$PG(k-1,q)$ where $2\leq j\leq k$ and $k\geq 3$. Then the complement $N^{c}$
of $N$ has rank equal to $r(N)$.

###### Proof.

Assume that $r(N^{c})<r(N)$. Then $N$ has $AG(r(N)-1,q)$ as a restriction. Now
$AG(r(N)-1,q)$ is $3$-connected since $r(N)\geq 4$ so $N$ is $3$-connected, a
contradiction. ∎

The next result is from [13].

######  Theorem 4.3.

Let $n$ be an integer exceeding one and $X$ and $Y$ be subsets of the ground
set of a matroid $M$. Suppose $M|X$ and $M|Y$ are both vertically
$n$-connected and $r(X)+r(Y)-r(X\cup Y)\geq n-1$. Then $M|(X\cup Y)$ is
vertically $n$-connected.

The following is a straightforward consequence of Proposition 2.2.

######  Lemma 4.4.

Let $r\geq 4$. For an arbitrary prime power $q$, color the elements of
$PG(r-1,q)$ red or green. Then either $PG(r-1,q)|G$ or $PG(r-1,q)|R$ is
connected of rank $r$.

Recall that, for a flat $F$ in a simple $GF(q)$-represented matroid $M$, we
write $F^{c}$ for the matroid $(M|F)^{c}$.

######  Lemma 4.5.

Let $M$ be a matroid in $\mathcal{M}_{2}$ such that $r(M)\geq 5$ and $M$ has a
$2$-cocircuit. Then $M$ is isomorphic to a circuit or to $P(U_{3,4},U_{3,4})$.

###### Proof.

Assume that the result fails. Since $M$ has a $2$-cocircuit, it has a maximal
non-trivial series class $S$. Thus $M=M_{1}\oplus_{2}M_{2}$ where $M_{2}$ is a
circuit with ground set $S\cup p$, and $p$ is the basepoint of the $2$-sum. If
$p$ is parallel to an element $s$ in $M_{1}$, then we move $s$ into $M_{2}$ so
that it become parallel to $p$ there.

Suppose that $p$ is free in $M_{1}$. Then, by Lemma 3.1(i), $M_{1}$ is a
circuit. As $M$ is not a circuit and $r(M)\geq 5$, we deduce that the element
$s$ exists. Thus $M$ is the parallel connection of two circuits. By Corollary
2.6, neither of these circuits has more than four elements. Hence $M\cong
P(U_{3,4},U_{3,4})$, a contradiction. We deduce that $p$ is not free in
$M_{1}$. Thus $M_{1}$ has a non-spanning circuit $C_{p}$ that contains $p$. If
$r((C_{p}\cup S)-p)\geq 4$, then the closure, $F$, of $(C_{p}\cup S)-p$ is a
connected proper flat in $M$, Moreover, by Lemmas 2.2 and 4.2, $F^{c}$ is also
connected of rank $r(F)$. This contradicts the minimality of $M$. We deduce
that $r((C_{p}\cup S)-p)=3$. Hence every non-trivial series class of $M$ has
exactly two elements. Now, by Theorem 3.3, as $M_{1}$ is not a circuit and
does not have a series class of size at least three avoiding $p$, it has a
connected hyperplane $H$ containing $p$. Then ${\rm cl}_{M}((H\cup S)-p)$ is a
connected proper flat, $F$, of $M$ of rank $r(M)-1$. As above, $F^{c}$ is
connected of rank $r(F)$, a contradiction. ∎

######  Lemma 4.6.

Let $M$ be a matroid in $\mathcal{M}_{2}$ such that $r(M)\geq 5$. Then

  * (i)

$M$ is a circuit; or

  * (ii)

$M\cong P(U_{3,4},U_{3,4})$; or

  * (iii)

$M$ is $3$-connected.

###### Proof.

Assume that neither (i) nor (ii) holds. Then, by Lemma 4.5, we may assume that
$M$ is cosimple. Suppose that $M$ is not $3$-connected. Then
$M=M_{1}\oplus_{2}M_{2}$ where $r(M_{1})\geq r(M_{2})$ and one of $M_{1}$ and
$M_{2}$ may have an element parallel to the basepoint $p$ of the $2$-sum. When
this occurs, we may assume, by moving an element from $M_{2}$ to $M_{1}$ if
needed, that the element is parallel to $p$ in $M_{2}$. Since $M$ is cosimple,
neither $M_{1}$ nor $M_{2}$ is either a circuit or a circuit with an element
parallel to $p$. Hence $r(M_{2})\geq 3$. As $M_{2}$ is not a circuit, by Lemma
3.1, $M_{2}$ has a non-spanning circuit $C_{p}$ containing $p$. Then the
closure $F$ of $(E(M_{1})\cup C_{p})-p$ is a connected proper flat of $M$. By
Lemmas 2.2 and 4.2, $F^{c}$ is connected of rank $r(F)$, a contradiction. ∎

The next result shows that a matroid $M$ in $\mathcal{M}_{2}$ such that
neither $M$ nor $M^{c}$ is a circuit has rank at most five.

######  Theorem 4.7.

Let $M$ be a matroid in $\mathcal{M}_{2}$ such that $r(M)\geq 6$. Then $M$ or
$M^{c}$ is a circuit.

###### Proof.

Let $P_{r(M)}$ denote the binary projective geometry of rank $r(M)$ such that
the set $G$ of green elements of $P_{r(M)}$ corresponds to $M$ and the set $R$
of red elements of $P_{r(M)}$ corresponds to $M^{c}$. Observe that, for each
projective flat $F$ of $P_{r(M)}$ with $4\leq r(F)<r(M)$, it follows by Lemma
4.4 and the minimality of $M$ that exactly one of $F|R$ and $F|G$ is connected
of rank $r(F)$. We call $F$ red or green depending on whether $F|R$ or $F|G$
is connected of rank $r(F)$. We may assume that both $M$ and $M^{c}$ are
cosimple otherwise we have our result by Lemma 4.5. Let $F$ be a rank-$(r-2)$
flat of $P_{r(M)}$. Note that $F$ is contained in exactly three hyperplanes,
say $H_{1},H_{2}$, and $H_{3}$ of $P_{r(M)}$. We note the following.

######  4.7.1.

At least two of $H_{1}$, $H_{2}$, and $H_{3}$ have the same color as $F$.

Suppose that $F$ is green and assume that $H_{1}$ and $H_{2}$ are red. It
follows that each of $H_{1}-F$ and $H_{2}-F$ contains at most one green
element and so the green elements in $(H_{1}\cup H_{2})-F$ form a cocircuit of
$M$ with at most two elements, a contradiction. Similarly, if $F$ is red, we
get a cocircuit of $M^{c}$ of size at most two, a contradiction.

Now let $G_{1}$ and $R_{1}$ be the sets of green and red hyperplanes,
respectively, of $P_{r(M)}$. We note the following.

######  4.7.2.

At most one of the rank-$(r-2)$ projective flats contained in a projective
hyperplane $H$ has a color different from that of $H$.

Observe that if two rank-$(r-2)$ projective flats contained in $H$ have the
same color, then, by Theorem 4.3, their join is colored the same as the two
flats, a contradiction. Thus 4.7.2 holds.

Let $G_{2}$ and $R_{2}$ be the sets of green and red projective flats of
$P_{r(M)}$ of rank $r-2$. We consider the bipartite graph $B$ with vertex sets
$G_{1}\cup R_{1}$ and $G_{2}\cup R_{2}$ such that a vertex $X$ in $G_{1}\cup
R_{1}$ is adjacent to a vertex $Y$ in $G_{2}\cup R_{2}$ if $Y\subseteq X$. We
count the number of cross edges of this graph, that is, the $G_{1}R_{2}$-edges
and $G_{2}R_{1}$-edges. By 4.7.2, the number of $G_{1}R_{2}$-edges is at most
$|G_{1}|$, and the number of $G_{2}R_{1}$-edges is at most $|R_{1}|$. Observe
that each pair $\\{H_{G},H_{R}\\}$ where $H_{G}\in G_{1}$ and $H_{R}\in R_{1}$
corresponds to either a $G_{1}R_{2}$\- edge or a $G_{2}R_{1}$-edge $e$
depending on whether $H_{G}\cap H_{R}$ is red or green. Note that there is a
third projective hyperplane $H^{\prime}$ such that $H^{\prime}\cap
H_{G}=H^{\prime}\cap H_{R}$ and, by 4.7.1, has the same color as $H_{G}\cap
H_{R}$. Observe that either $\\{H^{\prime},H_{G}\\}$ or
$\\{H^{\prime},H_{R}\\}$ corresponds to the cross edge $e$ depending on
whether $H_{G}\cap H_{R}$ is red or green. Hence each cross edge corresponds
to exactly two pairs $\\{H_{G},H_{R}\\}$ where $H_{G}\in G_{1}$ and $H_{R}\in
R_{1}$. As the number of cross edges is bounded above by $|G_{1}|+|R_{1}|$ and
below by $\frac{1}{2}|G_{1}||R_{1}|$, we have
$\frac{1}{2}|G_{1}||R_{1}|\leq|G_{1}|+|R_{1}|$. We may assume that
$|R_{1}|\geq|G_{1}|$. Then $|G_{1}|\leq\frac{2|G_{1}|}{|R_{1}|}+2\leq 3$, a
contradiction to Theorem 3.5. ∎

It remains to determine the members of $\mathcal{M}_{2}$ of rank $4$ or $5$.
The next lemma takes care of the rank-$4$ case.

######  Lemma 4.8.

A rank-$4$ binary matroid $M$ is a member of $\mathcal{M}_{2}$ if and only if
$M$ or $M^{c}$ is the cycle matroid of one of the six graphs in Figure 1.

###### Proof.

First assume that $M\in\mathcal{M}_{2}$. We may assume that
$|E(M)|\leq|E(M^{c})|$, so $|E(M)|\leq 7$. If $M$ has a $5$-circuit, then $M$
is a $5$-circuit or a $1$\- or $2$-element extension thereof. One can now
check that $M$ is the cycle matroid of one of the graphs on the first line of
Figure 1. We may now assume that $M$ has no $5$-circuits. Thus $|E(M)|$ is $6$
or $7$. If $|E(M)|=6$, then $M^{*}$ is connected of rank two, so $M$ is the
cycle matroid of $K_{2,3}$. Finally, if $|E(M)|=7$, then $M$ is the cycle
matroid of the last graph in Figure 1. The proof of the converse is immediate
as every rank-$3$ binary matroid is a binary comatroid. ∎

The following result from [8] will be used to simplify the computational task
of finding the rank-$5$ members of $\mathcal{M}_{2}$. The matroids in this
theorem will only appear in the proof of Lemma 4.10 and they will be defined
there.

######  Theorem 4.9.

An internally $4$-connected binary matroid has no $M(K_{3,3})$\- minor if and
only if it is

  1. (i)

cographic; or

  2. (ii)

isomorphic to a triangular or triadic Möbius matroid; or

  3. (iii)

isomorphic to one of $18$ sporadic matroids of rank at most $11$.

######  Lemma 4.10.

Let $M$ be a matroid in $\mathcal{M}_{2}$ such that $r(M)=5$. Then $M$ or
$M^{c}$ is not cosimple.

###### Proof.

Assume that $M$ and $M^{c}$ are cosimple. Then, by Lemma 4.6, both $M$ and
$M^{c}$ are $3$-connected. By Lemma 4.4, for every hyperplane $H$ of $P_{5}$,
exactly one of $H|G$ or $H|R$ is connected. We call the $H$ red or green
depending on whether $H|R$ or $H|G$ is connected of rank four. We first show
that

######  4.10.1.

$E(M)$ has no set $X$ of rank $3$ such that $r(E(M)-X)=4$.

Denote $E(M)-X$ by $Y$ and assume that $r(X)=3$ and $r(Y)=4$. Let $Y_{P}$ and
$X_{P}$ denote the projective flats spanned by $Y$ and $X$, respectively.
Observe that $Y_{P}\cap X_{P}$ is a projective line, say, $L=\\{x,y,z\\}$. As
$M$ has no $2$-cocircuits, it follows that $E(M)-Y_{P}$ has at least three
elements, including say $b_{1},$ $b_{2},$ and $b_{3}$ such that
$\\{x,b_{1},b_{2}\\}$ is a projective line, say $L_{1}$. Let $M^{\prime}$ be
the matroid obtained from $M|Y_{P}$ by adding $x,y,$ and $z$ if they are not
already in $E(M)$. Note that, for $k$ in $\\{1,2\\}$, a $k$-separation of
$M^{\prime}$ induces a $k$-separation of $M$ and therefore $M^{\prime}$ is
$3$-connected. By Lemma 3.6, $M^{\prime}$ has a connected hyperplane $H$ that
contains $x$ but not $y$ or $z$. Observe that either $P(H,L_{1})$ or
$P(H,L_{1})\backslash x$ is a connected hyperplane $H^{\prime}$ of $M$
depending on whether or not $x$ is an element of $E(M)$. By Proposition 2.2
and Lemma 4.2, it follows that the complement of $H^{\prime}$ is connected of
rank four, a contradiction.

######  4.10.2.

A connected hyperplane of $M$ has at least seven elements.

Suppose such a connected hyperplane has at most six elements. Then its
complement in $PG(3,2)$ has at least nine elements. By Lemma 4.1, this
complement is connected of rank four, a contradiction. Thus 4.10.2 holds.

By 4.10.1, it follows that $M$ is internally $4$-connected and has no triads.
By Theorem 3.5, $M$ has a connected hyperplane, so $|E(M)|\geq 11$ by 4.10.2.

Suppose that $M$ has no $M(K_{3,3})$-minor. By Theorem 4.9, we first suppose
that $M$ is cographic and therefore $E(M)\leq 12$ [5]. Since $M$ has no
cocircuits of size less than four, it follows that every hyperplane of $M$ has
at most eight elements. Therefore, for a connected hyperplane $H$ of $M$, by
4.10.2, $|H|$ is either seven or eight. It follows that $H^{c}$ has seven or
eight elements. As this complement is either disconnected or has rank at most
three, it is either $F_{7}$ or $F_{7}\oplus U_{1,1}$. This implies that $H$
has $F_{7}^{*}$ as a restriction. Thus $M$ is not regular, a contradiction.

Next suppose that $M$ is a triangular or a triadic Möbius matroid. Since $M$
has no triads, $M$ is the rank-$5$ triangular Möbius matroid, $\Delta_{5}$,
and has the reduced representation [8] shown on the left of Figure 2. Observe
that $\\{e,j,k,l,m\\}$ is a connected hyperplane of $M$ of size five, a
contradiction to 4.10.2. We may now assume that $M$ is a rank-$5$ sporadic
matroid, so $M$ is isomorphic to a matroid in
$\\{M_{5,11},T_{12}/e,M_{5,12}^{a},M_{5,12}^{b},M_{5,13}\\}$ [8]. Since
$M_{5,11}$ has a triad, $M$ is not isomorphic to $M_{5,11}$. When $M$ is
isomorphic to $T_{12}/e$, it has the representation shown on the right of
Figure 2. Then $\\{f,g,h,i,j\\}$ is a connected hyperplane of $M$, a
contradiction to 4.10.2.

$\kern
126.44928pt\kern-7.08336pt\left[\kern-126.44928pt\vbox{\kern-55.1111pt\vbox{
\halign{$#$\hfil\kern
<EMAIL_ADDRESS>2.0pt\kern 7.08336&f&g&h&i&j&k&l&m\crcr\kern 2.0pt\cr a$\hfil\kern 2.0pt\kern
7.08336&1&0&0&0&1&0&0&1\cr b$\hfil\kern 2.0pt\kern 7.08336&0&1&0&0&1&1&0&0\cr
c$\hfil\kern 2.0pt\kern 7.08336&0&0&1&0&0&1&1&0\cr d$\hfil\kern 2.0pt\kern
7.08336&0&0&0&1&0&0&1&1\cr e$\hfil\kern 2.0pt\kern
7.08336&1&1&1&1&0&0&0&1\cr\cr}}\kern-12.0pt}\,\right]$

$\kern
92.6691pt\kern-7.08336pt\left[\kern-92.6691pt\vbox{\kern-55.1111pt\vbox{
\halign{$#$\hfil\kern
<EMAIL_ADDRESS>2.0pt\kern 7.08336&f&g&h&i&j&k\crcr\kern 2.0pt\cr a$\hfil\kern 2.0pt\kern
7.08336&1&0&0&0&1&1\cr b$\hfil\kern 2.0pt\kern 7.08336&1&1&0&0&0&1\cr
c$\hfil\kern 2.0pt\kern 7.08336&0&1&1&0&0&1\cr d$\hfil\kern 2.0pt\kern
7.08336&0&0&1&1&0&1\cr e$\hfil\kern 2.0pt\kern
7.08336&0&0&0&1&1&1\cr\cr}}\kern-12.0pt}\,\right]$

Figure 2. $\Delta_{5}$ and $T_{12}/e$.

If $M$ is isomorphic to $M_{5,12}^{a}$, then $M$ has the representation shown
on the left of Figure 3. Then $M$ has $\\{f,g,h,i,j,l\\}$ as a connected
hyperplane of $M$, contradicting 4.10.2. Similarly, if $M$ is isomorphic to
$M_{5,12}^{b}$, then $M$ has the representation shown on the right of Figure
3. Then $\\{f,g,h,i,j,l\\}$ is a connected hyperplane of $M$, again
contradicting 4.10.2.

$\kern
107.66913pt\kern-7.08336pt\left[\kern-107.66913pt\vbox{\kern-55.1111pt\vbox{
\halign{$#$\hfil\kern
<EMAIL_ADDRESS>2.0pt\kern 7.08336&f&g&h&i&j&k&l\crcr\kern 2.0pt\cr a$\hfil\kern 2.0pt\kern
7.08336&1&0&0&0&1&1&0\cr b$\hfil\kern 2.0pt\kern 7.08336&1&1&0&0&0&0&1\cr
c$\hfil\kern 2.0pt\kern 7.08336&0&1&1&0&0&1&0\cr d$\hfil\kern 2.0pt\kern
7.08336&0&0&1&1&0&0&1\cr e$\hfil\kern 2.0pt\kern
7.08336&0&0&0&1&1&1&0\cr\cr}}\kern-12.0pt}\,\right]$

$\kern
107.66913pt\kern-7.08336pt\left[\kern-107.66913pt\vbox{\kern-55.1111pt\vbox{
\halign{$#$\hfil\kern
<EMAIL_ADDRESS>2.0pt\kern 7.08336&f&g&h&i&j&k&l\crcr\kern 2.0pt\cr a$\hfil\kern 2.0pt\kern
7.08336&1&0&0&0&1&1&0\cr b$\hfil\kern 2.0pt\kern 7.08336&1&1&0&0&0&1&1\cr
c$\hfil\kern 2.0pt\kern 7.08336&0&1&1&0&0&1&1\cr d$\hfil\kern 2.0pt\kern
7.08336&0&0&1&1&0&1&1\cr e$\hfil\kern 2.0pt\kern
7.08336&0&0&0&1&1&1&1\cr\cr}}\kern-12.0pt}\,\right]$

Figure 3. $M_{5,12}^{a}$ and $M_{5,12}^{b}$.

We may now assume that $M$ is isomorphic to $M_{5,13}$ and therefore has the
representation in Figure 4. Observe that $\\{a,b,d,e,f,i,j\\}$ is a connected
hyperplane, $H$, of $M$ such that $H^{c}$ is also connected of rank $4$, a
contradiction. We conclude that $M$ is not one of the five rank-$5$ sporadic
matroids.

$\kern
126.44928pt\kern-7.08336pt\left[\kern-126.44928pt\vbox{\kern-55.1111pt\vbox{
\halign{$#$\hfil\kern
<EMAIL_ADDRESS>2.0pt\kern 7.08336&f&g&h&i&j&k&l&m\crcr\kern 2.0pt\cr a$\hfil\kern 2.0pt\kern
7.08336&1&0&0&0&1&1&0&1\cr b$\hfil\kern 2.0pt\kern 7.08336&1&1&0&0&0&1&1&1\cr
c$\hfil\kern 2.0pt\kern 7.08336&0&1&1&0&0&1&1&1\cr d$\hfil\kern 2.0pt\kern
7.08336&0&0&1&1&0&1&1&1\cr e$\hfil\kern 2.0pt\kern
7.08336&0&0&0&1&1&1&1&0\cr\cr}}\kern-12.0pt}\,\right]$
Figure 4. $M_{5,13}$.

We may now assume that $M$ has an $M(K_{3,3})$-minor and so $M$ is an
extension of $M(K_{3,3})$. By symmetry, $M^{c}$ is also an extension of
$M(K_{3,3})$. Since $P_{5}$ has $31$ hyperplanes and $M(K_{3,3})$ has six
connected hyperplanes, we deduce that

######  4.10.3.

$M$ has at most $25$ connected hyperplanes.

Figure 5 shows the vertex-edge incidence matrix of $K_{3,3}$, which is a
binary representation for $M(K_{3,3})$. Although $r(M(K_{3,3}))=5$, we use
this representation because it displays the symmetries of $M(K_{3,3})$ well.
The $P_{5}$ into which $M$ is embedded is spanned by
$\\{a,b,c,d,e,f,g,h,i\\}$.

$\blockarray{cccccccccc}&abcdefghi\\\ \block{c(ccccccccc)}v_{1}111000000\\\
v_{2}000111000\\\ v_{3}000000111\\\ v_{4}100100100\\\ v_{5}010010010\\\
v_{6}001001001\\\ $ Figure 5. The vertex-edge incidence matrix of $K_{3,3}$.

$d$$f$$e$$h$$i$$g$

Figure 6. The labelled $K_{2,3}$ corresponding to the hyperplane $H_{1}$.

For $1\leq i\leq 6$, let $H_{i}$ be the connected hyperplane of $M(K_{3,3})$
that is complementary to the vertex bond of $v_{i}$ in $K_{3,3}$, and let
$H^{\prime}_{i}$ be the hyperplane of $P_{5}$ spanned by $H_{i}$. As
$H^{\prime}_{1}|G$ is an extension of $M(K_{2,3})$, it follows that
$H^{\prime}_{1}|R$ is a restriction of the complement of $M(K_{2,3})$ in
$P_{4}$. This complement is isomorphic to $P(F_{7},U_{2,3})$, where $p$ is the
basepoint of the parallel connection. The $K_{2,3}$ corresponding to $H_{1}$
is shown in Figure 6. The matroid $P(F_{7},U_{2,3})$ that is the complement of
this $M(k_{2,3})$ is labelled as in Figure 7. Here elements are labelled by
the corresponding vectors. Because $H^{\prime}_{1}|R$ is not connected of rank
$4$, it is isomorphic to a restriction of either $U_{2,3}\oplus U_{2,3}$ or
$F_{7}\oplus U_{1,1}$. Assume the former. Then the red elements of
$H^{\prime}_{1}$ are contained in the $2$-separating triangle in
$P(F_{7},U_{2,3})$ and one of the four triangles of $F_{7}$ that avoid $p$,
where $p$ corresponds to the vector $d+g$. Thus we have the following four
cases:

  1. (i)

$e+g,e+i,$ and $d+i$ are green;

  2. (ii)

$e+g,g+i,$ and $e+f$ are green;

  3. (iii)

$d+e,g+i,$ and $e+i$ are green;

  4. (iv)

$d+e,d+i,$ and $e+f$ are green.

By permuting the vertices $v_{4},v_{5}$, and $v_{6}$, we see that the last
three cases are symmetric. Thus $M$ is an extension of one of the two matroids
whose representations are shown in Figure 8.

$e+g$$d+e+f$$g+h+i$$e+f$$e+i$$d+i$$g+i$$d+g$$d+e$

Figure 7. The labelled $P(F_{7},U_{2,3})$ corresponding to the complement of
$H_{1}$ in $P_{4}$.

$\kern
225.55577pt\kern-7.08336pt\left[\kern-225.55577pt\vbox{\kern-60.55554pt\vbox{
\halign{$#$\hfil\kern
<EMAIL_ADDRESS>2.0pt\kern 7.08336&a&b&c&d&e&f&g&h&i&g+e&d+i&i+e\crcr\kern 2.0pt\cr$\hfil\kern
2.0pt\kern 7.08336&1&1&1&0&0&0&0&0&0&0&0&0\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&0&1&1&1&0&0&0&1&1&1\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&0&0&0&0&1&1&1&1&1&1\cr$\hfil\kern 2.0pt\kern
7.08336&1&0&0&1&0&0&1&0&0&1&1&0\cr$\hfil\kern 2.0pt\kern
7.08336&0&1&0&0&1&0&0&1&0&1&0&1\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&1&0&0&1&0&0&1&0&1&1\cr\cr}}\kern-12.0pt}\,\right]$

$\kern
228.0065pt\kern-7.08336pt\left[\kern-228.0065pt\vbox{\kern-60.55554pt\vbox{
\halign{$#$\hfil\kern
<EMAIL_ADDRESS>2.0pt\kern 7.08336&a&b&c&d&e&f&g&h&i&g+e&g+i&e+f\crcr\kern 2.0pt\cr$\hfil\kern
2.0pt\kern 7.08336&1&1&1&0&0&0&0&0&0&0&0&0\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&0&1&1&1&0&0&0&1&0&0\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&0&0&0&0&1&1&1&1&0&0\cr$\hfil\kern 2.0pt\kern
7.08336&1&0&0&1&0&0&1&0&0&1&1&0\cr$\hfil\kern 2.0pt\kern
7.08336&0&1&0&0&1&0&0&1&0&1&0&1\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&1&0&0&1&0&0&1&0&1&1\cr\cr}}\kern-12.0pt}\,\right]$

Figure 8. Two extensions of $M(K_{3,3})$. Algorithm Counting hyperplanes of
$M$ and $M^{c}$

0: Input a simple binary matroid $N$ of rank five

Set $i\leftarrow 0$, $j\leftarrow 0$

for a subset $S$ of $P_{5}-E(N)$ do

Set $i\leftarrow 0$, $j\leftarrow 0$

Set $M=P_{5}|(E(N)\cup S)$

$i\leftarrow$ number of connected hyperplanes of $M$.

if $i<26$ then

$j\leftarrow$ number of connected hyperplanes of $M^{c}$.

if $i+j<32$ then

print $M$

Using SageMath [15], we apply the given hyperplane-counting algorithm to the
two matroids whose representations are given in Figure 8. This shows that, for
every extension of these matroids, either the number of green hyperplanes
exceeds $25$, a contradiction to 4.10.3; or the sum of the number of red and
green hyperplanes exceeds $31$, the number of hyperplanes of $P_{5}$, and
again we have a contradiction. Note that, when we run the above algorithm with
$|S|=10$, we do not obtain any matroids. Thus the search can be restricted to
sets $S$ with at most ten elements.

Next suppose that $H^{\prime}_{1}|R$ is a restriction of a copy of
$F_{7}\oplus U_{1,1}$. First we assume that these red elements are contained
in the union of the $2$-separating triangle of $P(F_{7},U_{2,3})$ with another
triangle through $p$ and one further point, $z$. Although there are three such
lines through $p$ and four choices for $z$ for each, permuting $v_{4},v_{5}$,
and $v_{6}$ reduces these twelve cases to the following two cases:

  1. (i)

$e+i,e+f,$ and $g+i$ are green;

  2. (ii)

$e+i,e+f$ and $d+i$ are green.

Thus $M$ is an extension of one of the two matroids whose representations are
shown in Figure 9. Again using SageMath [15] and applying the given
hyperplane-counting algorithm to these two matroids, we see that, for every
extension of these matroids, either the number of green hyperplanes exceeds
$25$, or the sum of the number of red and green hyperplanes exceeds $31$, so
we obtain a contradiction. As in the previous case check, we find that we can
restrict the search to sets $S$ with at most ten elements.

$\kern
226.32317pt\kern-7.08336pt\left[\kern-226.32317pt\vbox{\kern-60.55554pt\vbox{
\halign{$#$\hfil\kern
<EMAIL_ADDRESS>2.0pt\kern 7.08336&a&b&c&d&e&f&g&h&i&e+i&e+f&g+i\crcr\kern 2.0pt\cr$\hfil\kern
2.0pt\kern 7.08336&1&1&1&0&0&0&0&0&0&0&0&0\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&0&1&1&1&0&0&0&1&0&0\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&0&0&0&0&1&1&1&1&0&0\cr$\hfil\kern 2.0pt\kern
7.08336&1&0&0&1&0&0&1&0&0&0&0&1\cr$\hfil\kern 2.0pt\kern
7.08336&0&1&0&0&1&0&0&1&0&1&1&0\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&1&0&0&1&0&0&1&1&1&1\cr\cr}}\kern-12.0pt}\,\right]$

$\kern
226.39957pt\kern-7.08336pt\left[\kern-226.39957pt\vbox{\kern-60.55554pt\vbox{
\halign{$#$\hfil\kern
<EMAIL_ADDRESS>2.0pt\kern 7.08336&a&b&c&d&e&f&g&h&i&e+i&e+f&d+i\crcr\kern 2.0pt\cr$\hfil\kern
2.0pt\kern 7.08336&1&1&1&0&0&0&0&0&0&0&0&0\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&0&1&1&1&0&0&0&1&0&1\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&0&0&0&0&1&1&1&1&0&1\cr$\hfil\kern 2.0pt\kern
7.08336&1&0&0&1&0&0&1&0&0&0&0&1\cr$\hfil\kern 2.0pt\kern
7.08336&0&1&0&0&1&0&0&1&0&1&1&0\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&1&0&0&1&0&0&1&1&1&1\cr\cr}}\kern-12.0pt}\,\right]$

Figure 9. Two more extensions of $M(K_{3,3})$.

We may now assume that, for $1\leq i\leq 6$, each $H^{\prime}_{i}|R$ is a
restriction of $F_{7}\oplus U_{1,1}$ where the coloop in $F_{7}\oplus U_{1,1}$
is one of the elements $d+e+f$ or $g+h+i$. Then, for the red elements of each
of $H^{\prime}_{1},H^{\prime}_{2},H^{\prime}_{3}$ to behave in this way, we
must have at least two points in $\\{a+b+c,d+e+f,g+h+i\\}$ colored green.
Similarly, for $H^{\prime}_{4},H^{\prime}_{5},H^{\prime}_{6}$, we must have at
least two points in $\\{a+d+g,b+e+h,c+f+i\\}$ colored green. Using symmetry,
we may assume that $a+b+c,d+e+f,a+d+g,b+e+h$ are green. Thus $M$ is an
extension of the matroid whose representation is shown in Figure 10. Using
SageMath [15], we see that this matroid has exactly $27$ connected
hyperplanes, a contradiction. Hence the lemma holds. ∎

$\kern
192.35332pt\kern-7.08336pt\left[\kern-192.35332pt\vbox{\kern-60.55554pt\vbox{
\halign{$#$\hfil\kern
<EMAIL_ADDRESS>2.0pt\kern 7.08336&a&b&c&d&e&f&g&h&i&&&&\crcr\kern 2.0pt\cr$\hfil\kern
2.0pt\kern 7.08336&1&1&1&0&0&0&0&0&0&1&0&1&1\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&0&1&1&1&0&0&0&0&1&1&1\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&0&0&0&0&1&1&1&0&0&1&1\cr$\hfil\kern 2.0pt\kern
7.08336&1&0&0&1&0&0&1&0&0&1&1&1&0\cr$\hfil\kern 2.0pt\kern
7.08336&0&1&0&0&1&0&0&1&0&1&1&0&1\cr$\hfil\kern 2.0pt\kern
7.08336&0&0&1&0&0&1&0&0&1&1&1&0&0\cr\cr}}\kern-12.0pt}\,\right]$ Figure 10.
$M$ is an extension of this matroid whose last four columns are $a+b+c$,
$d+e+f$, $a+d+g$, and $b+e+h$.

We can now prove our main results for binary comatroids.

###### Proof of Theorem 1.2..

Let $M$ be a binary comatroid. Then, by Theorem 1.1, every flat of each of $M$
and $M^{c}$ is a binary comatroid. Thus, by Corollary 2.6, none of these flats
is a circuit of size exceeding five. By Proposition 2.2 and Lemma 4.2, none of
the flats is isomorphic to $P(U_{3,4},U_{3,4})$. Finally, by Lemma 4.8, none
of the flats is isomorphic to the cycle matroid of one of the six graphs in
Figure 1.

Conversely, suppose that $M$ is a binary matroid that is not a comatroid. Then
$M$ has a flat $N$ that is a member of $\mathcal{M}_{2}$. By Lemma 2.3,
$r(N)\geq 4$. By Lemma 4.8, if $r(N)=4$, then $N$ or $N^{c}$ is isomorphic to
the cycle matroid of one of the six graphs in Figure 1. Thus $M$ or $M^{c}$
has a flat that is isomorphic to one of these cycle matroids. We may now
assume that $r(N)\geq 5$. If $r(N)\geq 6$, then, by Theorem 4.7, $N$ or
$N^{c}$ is a circuit, so $M$ or $M^{c}$ has a circuit as a flat. Finally, if
$r(N)=5$, then, by Lemmas 4.6 and 4.10, we get that $M$ or $M^{c}$ has as a
flat either a circuit or $P(U_{3,4},U_{3,4})$. ∎

Because we are only dealing with simple matroids, in the next proof and from
now on, whenever we write $M/e$, we shall mean ${\rm si}(M/e)$.

###### Proof of Corollary 1.4..

By Lemma 2.3, every binary matroid of rank at most three is a comatroid. Thus,
in view of Theorem 1.2, it suffices to prove that $M$ is an induced-minor-
minimal binary non-comatroid when $M^{c}$ is either a circuit of size at least
six or is isomorphic to $P(U_{2,3},U_{2,3})$. Consider the first case. Since
both $M$ and $M^{c}$ are connected, $M$ is not a binary comatroid. Observe
that, for any proper flat $F$ of $M$, the matroid $(M|F)^{c}$ is free and so,
by Lemma 2.7, $M|F$ is a binary comatroid. Note that, in view of Lemma 2.7 and
Proposition 2.9, it is enough to show that $M/e$ is a binary comatroid for all
$e$ in $E(M)$. Because there is at most one red element on any line though
$e$, we see that $(M/e)^{c}$ has a most one point, so $M/e$ is a comatroid.

Now suppose that $M^{c}\cong P(U_{2,3},U_{2,3})$. Again, it is enough to show
that $M/e$ is a binary comatroid for all $e$ in $E(M)$. If $e$ is in the
projective closure of one of the $4$-circuits of $P(U_{2,3},U_{2,3})$, then
$(M/e)^{c}$ has a coloop. Thus $(M/e)^{c}$ is disconnected with each component
having rank at most three, so it is a comatroid. If $e$ is not in one of these
projective closures, then $(M/e)^{c}$ has a most one point and, again, $M/e$
is a comatroid. ∎

##  5\. Induced-restriction-minimal non-$GF(3)$-comatroids

In this section, we prove Theorem 1.3 and Corollary 1.5.

######  Lemma 5.1.

Let $M$ be a matroid in $\mathcal{M}_{3}$ such that $r(M)\geq 4$ and $M$ has a
cocircuit of size less than four. Then $M$ can be obtained from a circuit of
size at least three by $2$-summing a copy of $U_{2,4}$ to some, possibly
empty, set of elements of the circuit.

###### Proof.

First we show the following.

######  5.1.1.

$M$ has no non-spanning circuit $C$ of rank at least three such that $C$
intersects a cocircuit of $M$ of size less than four.

Assume that such a circuit $C$ exists and let $F$ be the projective flat
spanned by $C$. Observe that $F$ has a cocircuit $A_{F}$ that has at most
three green elements and so $F|R$ contains $A_{F}$ minus three points. Since
$A_{F}$ is a ternary affine geometry of rank at least three, $F|R$ is
connected of rank $r(F)$, a contradiction to the minimality of $M$. Thus 5.1.1
holds.

Now suppose that $M$ has a $2$-cocircuit $\\{a,b\\},$ say. Then
$M=N\oplus_{2}U_{2,3}$. If $N$ has an element $s$ parallel to the basepoint
$p$ of the $2$-sum, then we move $s$ so that it is parallel to $p$ in
$U_{2,3}$. Observe that if the basepoint $p$ is contained in a non-spanning
circuit $D$ of $N$, then there is a non-spanning circuit $D^{\prime}$ of $M$
that contains $\\{a,b\\}$ and has rank at least three, a contradiction to
5.1.1. Therefore $p$ is free in $N$. Thus, by Lemma 3.1(ii), $N$ is obtained
from a circuit of size at least three by $2$-summing a copy of $U_{2,4}$ to
some of the elements of the circuit. If $\\{a,b\\}$ is in a triangle of $M$,
then $M$ has a flat isomorphic to $N$. Thus $N$ is either a circuit of size at
least four, or $N$ breaks up as a $2$-sum. By Corollary 2.6, or by Proposition
2.2 and Lemma 4.2, $N$ is not a ternary comatroid, contradicting the
minimality of $M$. Thus $\\{a,b\\}$ is not in a triangle of $M$, so $M$
satisfies the lemma.

Next suppose that $M$ has a triad $\\{a,b,c\\},$ say. Observe that if
$\\{a,b,c\\}$ is a triangle, we get our result as above. We may now assume
that $\\{a,b,c\\}$ is independent. Let $\Pi$ be the projective plane spanned
by $\\{a,b,c\\}$ and let $H$ be the projective hyperplane spanned by
$E(M^{c})-\\{a,b,c\\}$. It is clear that $\Pi|R$ is connected of rank three.
Suppose that the projective lines spanned by $\\{a,b\\},\\{a,c\\},$ and
$\\{b,c\\}$ meet $H$ at $p,q,$ and $s$, respectively. Note that at most one of
the points in $\\{p,q,s\\}$ is green otherwise $\Pi|G$ is connected of rank
three, a contradiction. Thus we may assume that $q$ and $s$ are red. We may
also assume that $c$ is not free in $M$ otherwise we have the result by Lemma
3.1(ii). Let $D$ be a non-spanning circuit of $M$ containing $c$. By
orthogonality, $D$ contains either $a$ or $b$ and so $D$ has rank at least
three. The result now follows by 5.1.1. ∎

######  Lemma 5.2.

Let $M$ be a matroid in $\mathcal{M}_{3}$ such that $r(M)=4$. Then $M$ or
$M^{c}$ has a cocircuit of size less than four.

###### Proof.

Assume that neither $M$ nor $M^{c}$ has a cocircuit of size less than four.

######  5.2.1.

A rank-$3$ simple ternary matroid $N$ that is connected either has a connected
rank-$3$ ternary complement or is $AG(2,3)\backslash e$ or an extension of it.

Assume that $N^{c}$ is not connected or that $r(N^{c})<3$. Then $N^{c}$ is a
restiction of $U_{2,4}\oplus U_{1,1}$. Thus $N$ is $AG(2,3)\backslash e$ or an
extension of it. Hence 5.2.1 holds.

The next assertion is an immediate consequence of Corollary 3.8.

######  5.2.2.

Both $M$ and $M^{c}$ have a connected hyperplane.

By 5.2.1 and 5.2.2, it follows that we have both a red and a green triangle.
In the arguments that follow, we will frequently exploit the symmetry between
$R$ and $G$.

######  5.2.3.

If a red triangle $T$ is contained in exactly $t$ red hyperplanes, then
$|R|\geq 5t+3$.

By 5.2.1, each red hyperplane containing $T$ has at least five red points not
in the projective closure of $T$. The result is immediate.

######  5.2.4.

Every red triangle $T$ is contained in exactly three red hyperplanes.
Moreover, $|R|\geq 18$ and $|G|\geq 18$.

Note that $T$ is in at least two red hyperplanes otherwise we get a red
cocircuit of size less than four. Assume that $T$ is in exactly two red
hyperplanes, $H_{1}$ and $H_{2}$. Because each of $H_{1}$ and $H_{2}$ is
$AG(2,3)\backslash e$ or an extension of it, one can check that each element
$t$ of $T$ is in a red triangle $T_{i}$ in $H_{i}$ that meets $T$ in $t$. Now
consider the projective plane $\Pi$ that is spanned by $T_{1}$ and $T_{2}$.
There are two green planes that contain $T$. Each of these has
$AG(2,3)\backslash e$ as a restriction and meets $\Pi$ in a line through $t$.
This line contains at least two green points. Hence $\Pi$ contains both a red
$4$-circuit and a green $4$-circuit, a contradiction. We conclude that $T$ is
in at least three red hyperplanes. Thus, by 5.2.3, $|R|\geq 18$. By symmetry,
$|G|\geq 18$, so $|R|\leq 22$. Hence, by 5.2.3 again, $T$ is not in four red
hyperplanes. Therefore 5.2.4 holds.

######  5.2.5.

There is a red triangle that is not contained in a red $4$-point line.

Suppose every red triangle is contained in a red $4$-point line. As every red
hyperplane has $AG(2,3)\backslash e$ as a restriction, one easily checks that
every red hyperplane is a $PG(2,3)$. Since every red triangle is in three red
hyperplanes, it follows that $|R|\geq 31$, a contradiction to 5.2.4.

We now take a red triangle $T$ for which the fourth point, $g$, on the
projective line spanned by $T$ is green. Now $T$ is in exactly three red
hyperplanes, $R_{1},R_{2},$ and $R_{3},$ and one green hyperplane, $G_{0}$.
Because $G_{0}$ contains at most one red point not in $T$, there are three
lines, $G_{1},G_{2},$ and $G_{3}$, in $G_{0}$ that contain $g$ and at least
two other green points.

We may assume that $|R|\leq|G|$, so $|R|\in\\{18,19,20\\}$. We may also assume
that $|R_{1}-T|\geq|R_{2}-T|\geq|R_{3}-T|\geq 5$. As
$|R_{1}-T|+|R_{2}-T|+|R_{3}-T|\in\\{15,16,17\\}$, we see that $|R_{3}-T|=5,$
that $|R_{2}-T|\in\\{5,6\\},$ and that $|R_{1}-T|\in\\{5,6,7\\}$. Thus $R_{3}$
contains a green triangle $T_{1}$ containing $g$, so each of the projective
planes spanned by $T_{1}\cup G_{1},T_{1}\cup G_{2},$ and $T_{1}\cup G_{3}$
contains a green $4$-circuit. Moreover, each such plane meets each of $R_{1}$
and $R_{2}$ in a line through $g$. For each $i$ in $\\{1,2\\}$, the plane
$R_{i}$ has at most one line through $g$ that does not contain at least two
red points. Hence, for some $j$ in $\\{1,2,3\\}$, the projective plane spanned
by $T_{1}\cup G_{j}$ meets both $R_{1}$ and $R_{2}$ in a line through $g$
containing at least two red points. Then $T_{1}\cup G_{j}$ contains a red
$4$-circuit. As it contains a green $4$-circuit, we have a contradiction. ∎

######  Theorem 5.3.

Let $M$ be a matroid in $\mathcal{M}_{3}$ such that $r(M)\geq 4$. Then $M$ or
$M^{c}$ has a cocircuit of size less than four.

###### Proof.

By Lemma 5.2, the result holds when $r(M)=4$. Therefore we may assume that
$r(M)\geq 5$. Further assume that neither $M$ nor $M^{c}$ has a cocircuit of
size less than four. We now let $P_{r(M)}$ denote the ternary projective
geometry of rank $r(M)$. A flat $F$ of $P_{r(M)}$ with $3\leq r(F)<r(M)$ is
red or green depending on whether $F|R$ or $F|G$ is connected of rank $r(F)$.
Let $F$ be a rank-$(r-2)$ flat of $P_{r(M)}$. Then $F$ is contained in exactly
four hyperplanes, say $H_{1},H_{2}$, $H_{3}$, and $H_{4}$ of $P_{r(M)}$.
Moreover, as neither $M$ nor $M^{c}$ has a cocircuit of size less than four,
we deduce the following.

######  5.3.1.

At least two of $H_{1}$, $H_{2}$, $H_{3}$, and $H_{4}$ have the same color as
$F$.

Now let $G_{1}$ and $R_{1}$ be the sets of green and red hyperplanes,
respectively, of $P_{r(M)}$. The following is a straightforward consequence of
Theorem 4.3.

######  5.3.2.

If $H\in G_{1}$, then at most one of the rank-$(r-2)$ projective flats
contained in $H$ is red.

Let $G_{2}$ and $R_{2}$ be the sets of green and red projective flats of
$P_{r(M)}$ of rank $r-2$. We consider the bipartite graph $B$ with vertex
classes $G_{1}\cup R_{1}$ and $G_{2}\cup R_{2}$ such that a vertex $X$ in
$G_{1}\cup R_{1}$ is incident to a vertex $Y$ in $G_{2}\cup R_{2}$ if
$Y\subseteq X$. As in the proof of Theorem 4.7, by 5.3.2, the number of cross
edges of this graph is at most $|G_{1}|+|R_{1}|$.

Each pair $(H_{G},H_{R})$, where $H_{G}\in G_{1}$ and $H_{R}\in R_{1}$,
corresponds to a cross edge $e$. Note that at most three such pairs can
correspond to this edge $e$. Thus the number of cross edges is at least
$\frac{1}{3}|G_{1}||R_{1}|$, so
$\frac{1}{3}|G_{1}||R_{1}|\leq|G_{1}|+|R_{1}|$. By symmetry, we may suppose
that $|G_{1}|\geq|R_{1}|$. Thus $|R_{1}|\leq 3+\frac{3|R_{1}|}{|G_{1}|}\leq
6$. Since $|G_{1}|+|R_{1}|=\frac{3^{r(M)}-1}{2}$ and $r(M)\geq 5$, we see that
$|G_{1}|\geq 115$, so $|R_{1}|\leq 3+\frac{3|R_{1}|}{|G_{1}|}$. Hence
$|R_{1}|\leq 3$ and $|G_{1}|\geq 118$. Since every red projective flat of rank
$r(M)-2$ is contained in at least two red projective hyperplanes, it follows
that $|R_{2}|\leq 3$. By 5.3.1, a flat in $R_{2}$ is contained in at most two
hyperplanes in $G_{1}$ and so the number of $G_{1}R_{2}$-edges is at most six.
Thus $\frac{1}{3}|G_{1}||R_{1}|\leq|R_{1}|+6$, so
$|R_{1}|\leq\frac{3|R_{1}|+18}{|G_{1}|}$. As $|R_{1}|\leq 3$ and $|G_{1}|\geq
118$, it follows that $|R_{1}|=0$, a contradiction to Lemma 3.8. ∎

###### Proof of Theorem 1.3..

A routine check shows that, up to complementation, $U_{3,4},$ $P(U_{2,3},$
$U_{2,3}),$ $U_{2,4}\oplus_{2}U_{2,3},$ $R_{6},$ $P(U_{2,4},U_{2,3}),$
$M(K_{4}),$ and $\mathcal{W}^{3}$ are the only connected ternary matroids of
rank three whose complements are also connected of rank three. Theorem 1.3 now
follows from Lemma 2.3, Lemma 5.1, Lemma 5.2, and Theorem 5.3. ∎

###### Proof of Corollary 1.5..

In view of Lemma 2.3 and Theorem 1.3, it suffices to show that if $M^{c}$ is
obtained from a circuit of size at least three by $2$-summing a copy of
$U_{2,4}$ to some, possibly empty, set of elements of the circuit, then $M$ is
an induced-minor-minimal ternary non-comatroid. But, when $M^{c}$ is as
specified, $M/e$ has at most one point and so is a ternary comatroid. ∎

## Acknowledgement

The authors thank Guoli Ding for suggesting the study of comatroids.

## References

  * [1] T.H. Brylawski and D. Lucas, Uniquely representable combinatorial geometries, Teorie Combinatorie (Proc. 1973 Internat. Colloq.), pp. 83–104, Accademia Nazionale dei Lincei, Rome, 1976.
  * [2] D.G. Corneil, H. Lerchs, L. Stewart Burlingham, Complement reducible graphs, Discrete Appl. Math. 3 (1981), 163–174.
  * [3] D.G. Corneil, Y. Perl, L.K. Stewart, A linear recognition algorithm for cographs, SIAM J. Comput. 14 (1985), 926–934.
  * [4] R. Diestel Graph Theory, Third edition, Springer, Berlin, 2005.
  * [5] F. Jaeger, Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B, 26 (1979), 205–216.
  * [6] H.A. Jung, On a class of posets and the corresponding comparability graphs, J. Combin. Theory Ser. B 24 (1978), 125–133 .
  * [7] A.K. Kelmans, The concept of a vertex in a matroid, the nonseparating cycles of a graph and a new criterion for graph planarity, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), pp. 345–388, Colloq. Math. Soc. János Bolyai, 25, North-Holland, Amsterdam-New York, 1981.
  * [8] D. Mayhew, G. Royle and G. Whittle, The internally $4$-connected matroids with no $M(K_{3,3})$-minor, Mem. Amer. Math. Soc., (208) (2010), no. 981.
  * [9] J. McNulty and H. Wu, Connected hyperplanes in binary matroids, J. Combin. Theory Ser. B, 79 (2000), 87–97.
  * [10] J.G. Oxley, Cocircuit coverings and packings for binary matroids, Math. Proc. Cambridge Philos. Soc. 83 (1978), 347–351.
  * [11] J. Oxley, Matroid Theory, First Edition, Oxford University Press, New York, 1992.
  * [12] J. Oxley, Matroid Theory, Second Edition, Oxford University Press, New York, 2011.
  * [13] J. Oxley and H. Wu, On matroid connectivity, Discrete Math. 146 (1995), 321–324.
  * [14] J. Oxley and J. Singh, Generalizing cographs to 2-cographs, arxiv: 2103.00403.
  * [15] SageMath, the Sage Mathematics Software System (Version 8.2), The Sage Developers, 2019, http://www.sagemath.org.
  * [16] D. Seinsche, On a property of the class of $n$-colourable graphs, J. Combin. Theory Ser. B 16 (1974), 191–193 .