# Chordal Matroids arising from Generalized parallel connections

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

A graph is chordal if every cycle of length at least four has a chord. In
1961, Dirac characterized chordal graphs as those graphs that can be built
from complete graphs by repeated clique-sums. Generalizing this, we consider
the class of simple $GF(q)$-representable matroids that can be built from
projective geometries over $GF(q)$ by repeated generalized parallel
connections across projective geometries. We show that this class of matroids
is closed under induced minors. We characterize the class by its forbidden
induced minors; the case when $q=2$ is distinctive.

###### 1991 Mathematics Subject Classification:

05B35, 05C75

##  1\. Introduction

The notation and terminology in this paper will follow [7] for graphs and [12]
for matroids. Unless stated otherwise, all graphs and matroids considered here
are simple. Thus every contraction of a set from a matroid is immediately
followed by the simplification of the resulting matroid. A chord of a cycle
$C$ in a graph $G$ is an edge $e$ of $G$ that is not in $C$ such that both
vertices of $e$ are vertices of $C$. A graph is chordal if every cycle of
length at least four has a chord. Such graphs were called rigid circuit graphs
by Dirac [8] and triangulated graphs by Berge [2]. Let $G_{1}$ and $G_{2}$ be
graphs and $V(G_{1})\cap V(G_{2})=V$, say. Assume that $G_{1}[V]$ is a
complete graph $H$ and $G_{2}[V]$ has edge set $E(H)$. The clique-sum of
$G_{1}$ and $G_{2}$ is the graph with vertex set $V(G_{1})\cup V(G_{2})$ and
edge set $E(G_{1})\cup E(G_{2})$. Loosely speaking, the clique-sum is obtained
by gluing $G_{1}$ and $G_{2}$ together across the clique $H$. While there are
several characterizations of chordal graphs (see, for example, [13]), we
choose to focus on the following one of Dirac [8].

######  Theorem 1.1.

A graph $G$ is chordal if and only if $G$ can be constructed from complete
graphs by repeated clique-sums.

Let $M_{1}$ and $M_{2}$ be matroids whose ground sets intersect in a set $T$
such that $T$ is a modular flat of $M_{1}$, and $M_{1}|T=M_{2}|T=~{}N$. The
generalized parallel connection of $M_{1}$ and $M_{2}$ across $N$ is the
matroid with ground set $E(M_{1})\cup E(M_{2})$ whose flats are those subsets
$X$ of $E(M_{1})\cup E(M_{2})$ such that $X\cap E(M_{1})$ is a flat of
$M_{1}$, and $X\cap E(M_{2})$ is a flat of $M_{2}$. We denote this matroid by
$P_{N}(M_{1},M_{2})$ or $P_{T}(M_{1},M_{2})$. Note that $T$ may be empty, in
which case, $P_{T}(M_{1},M_{2})=M_{1}\oplus M_{2}$.

For a prime power $q$, we will denote the projective geometry $PG(r-1,q)$ by
$P_{r}$ when context makes the field clear. Let $\mathcal{M}_{q}$ be the class
of matroids that can be built from projective geometries over $GF(q)$ by a
sequence of generalized parallel connections across projective geometries over
$GF(q)$. A matroid $M$ is $GF(q)$-chordal if $M$ is a member of
$\mathcal{M}_{q}$. By [5], each member of $\mathcal{M}_{q}$ is
$GF(q)$-representable.

An induced minor of a graph $G$ is a graph $H$ that can be obtained from $G$
by a sequence of vertex deletions and edge contractions. Similarly, an induced
minor of a matroid $M$ is a matroid $N$ that can be obtained from $M$ by a
sequence of restrictions to flats and contractions, where each such
contraction is followed by a simplification. Evidently, the class of chordal
graphs is closed under vertex deletions, that is, it is closed under taking
induced subgraphs. The analogous property for the class $\mathcal{M}_{q}$ is
highlighted by the following result.

######  Theorem 1.2.

For all $q$, the class $\mathcal{M}_{q}$ is closed under taking induced
minors.

Our main results are the following characterizations of the forbidden induced
minors for the class $\mathcal{M}_{q}$, first for $q=2$ and then for $q>2$.

######  Theorem 1.3.

The set of forbidden induced minors for the class $\mathcal{M}_{2}$ is
$\\{M(K_{4}),U_{3,4}\\}$.

######  Theorem 1.4.

For each $q>2$, the set of forbidden induced minors for the class
$\mathcal{M}_{q}$ is $\\{U_{2,k}:2<k\leq q\\}\cup\\{U_{3,q+2}\\}$.

Several different notions of chordal matroids have been given over the last
forty years [1, 3, 6, 10, 17]. Each of these papers, with the exception of [6,
10], focuses primarily on binary matroids. Following Cordovil, Forge, and
Klein [6], we define a simple or non-simple matroid $M$ to be chordal if, for
each circuit $C$ that has at least four elements, there are circuits $C_{1}$
and $C_{2}$ and an element $e$ such that $C_{1}\cap C_{2}=\\{e\\}$ and
$C=(C_{1}\cup C_{2})-e$.

Cordovil, Forge, and Klein [6] and Mayhew and Probert [10] study the relation
between chordal graphs and supersolvable matroids. Such matroids were
originally introduced by Stanley [15]. A rank-$r$ matroid is supersolvable if
there is a chain of modular flats $F_{1}\subseteq F_{2}\subseteq\dots\subseteq
F_{r}$ in $M$ where the rank of $F_{i}$ is $i$ for each $i$ in $[r]$. The
class $\mathcal{M}_{q}$ is given in [10] as an example of a class of matroids
whose members are supersolvable and form a saturated class of matroids, where
a matroid $M$ is saturated if, for every modular flat $F$, the restriction
$M|F$ has no two disjoint cocircuits.

##  2\. Preliminaries

Before beginning the discussions of forbidden induced minors for the class
$\mathcal{M}_{q}$, we show that this class is closed under taking induced
minors. We shall use the following well-known property of generalized parallel
connections (see, for example, [12, 11.23]).

######  Lemma 2.1.

For every flat $F$ of $P_{N}(M_{1},M_{2})$,

$r(F)=r(F\cap E(M_{1}))+r(F\cap E(M_{2}))-r(F\cap E(N)).$

######  Lemma 2.2.

The class $\mathcal{M}_{q}$ of $GF(q)$-chordal matroids is closed under
induced restrictions.

###### Proof.

It is enough to show that the class $\mathcal{M}_{q}$ is closed under
restricting to a hyperplane. Let $M$ be a minimum-rank matroid in
$\mathcal{M}_{q}$ such that $M|H\not\in\mathcal{M}_{q}$ for some hyperplane
$H$ of $M$. Then $M$ is not a projective geometry, so $M=P_{N}(M_{1},M_{2})$
where $M_{1}$ and $M_{2}$ are in $\mathcal{M}_{q}$, and $N$ is a projective
geometry over $GF(q)$. Let $H_{i}=H\cap E(M_{i})$ for each $i$ in $\\{1,2\\}$
and let $H_{N}=H\cap E(N)$. Then, since $H$ is a both flat of a generalized
parallel connection and a hyperplane of $M$,

$r(M_{1})+r(M_{2})-r(N)-1=r(H)=r(H_{1})+r(H_{2})-r(H_{N}).$ (2.1)

Suppose $H$ contains all of $E(N)$. Then $r(H_{N})=r(N)$, so, from $(2.1)$, we
have

$r(M_{1})+r(M_{2})-1=r(H_{1})+r(H_{2}).$

This implies that, for some $i$ and $j$ such that $\\{i,j\\}=\\{1,2\\}$, the
hyperplane $H$ contains $E(M_{i})$, and $H_{j}$ is a hyperplane of $M_{j}$. It
follows by the minimality of $M$ that $M|H$ is in $\mathcal{M}_{q}$, a
contradiction.

We now assume that $H$ does not contain $E(N)$. Hence $H$ does not contain
$E(M_{1})$ or $E(M_{2})$. By [5], $E(M_{1})$ is a modular flat of
$P_{N}(M_{1},M_{2})$, so

$r(H)=r(H\cup E(M_{1}))+r(H_{1})-r(M_{1}).$ (2.2)

As $E(M_{1})\not\subseteq H$, we deduce that $r(H\cup E(M_{1}))>r(H)$, so
$r(H\cup E(M_{1}))=r(H)+1$. It follows from $(2.2)$ that
$r(H_{1})=r(M_{1})-1$. By symmetry, $r(H_{2})=r(M_{2})-1$. Hence $H_{i}$ is a
hyperplane of $M_{i}$ for each $i$ in $\\{1,2\\}$. Therefore, by $(2.1)$ and
$(2.2)$,

$\displaystyle r(M_{1})+r(M_{2})-r(N)-1=r(M_{1})-1+r(M_{2})-1-r(H_{N}).$

Thus $r(H_{N})=r(N)-1$. Hence $H_{N}$ is a hyperplane of $N$, so $M|H_{N}$ is
a projective geometry. By [5] (see also [12, Proposition 11.4.15]),
$M|H=P_{M|H_{N}}(M|H_{1},M|H_{2})$, so $M|H$ is a generalized parallel
connection of members of $\mathcal{M}_{q}$ along a projective geometry and is
therefore a member of $\mathcal{M}_{q}$, a contradiction. ∎

In the next result, where we show that $\mathcal{M}_{q}$ is closed under
contractions, we shall make repeated use of the fact that every contraction is
followed by a simplification. We observe that a consequence of this result is
that $\mathcal{M}_{q}$ is closed under parallel minors.

######  Lemma 2.3.

The class $\mathcal{M}_{q}$ of $GF(q)$-chordal matroids is closed under taking
contractions.

###### Proof.

Let $M$ be a $GF(q)$-chordal matroid. We argue by induction on $|E(M)|$ that
$M/e$ is a $GF(q)$-chordal matroid for all $e$ in $E(M)$. The result is
certainly true if $|E(M)|\leq 2$. Suppose the result holds when $|E(M)|<k$ and
let $|E(M)|=k$. The result holds if $M$ is a projective geometry, so we may
assume that $M=P_{N}(M_{1},M_{2})$, where $M_{1}$ and $M_{2}$ are in
$\mathcal{M}_{q}$, and $N$ is a projective geometry over $GF(q)$. Suppose that
$e\in E(M_{1})-E(N)$. Then $M_{1}/e$ is in $\mathcal{M}_{q}$ by the induction
hypothesis and $M_{1}/e$ has $N$ as a restriction. As
$M/e=P_{N}(M_{1}/e,M_{2})$, we deduce that $M/e$ is in $\mathcal{M}_{q}$. We
may now assume that $e\in E(N)$. This implies that $e$ is in both $E(M_{1})$
and $E(M_{2})$, and, by the induction hypothesis, $M_{1}/e$ and $M_{2}/e$ are
in $\mathcal{M}_{q}$ and contain the projective geometry $N/e$ as a
restriction. By [5], $M/e=P_{N/e}(M_{1}/e,M_{2}/e)$, and we again get that
$M/e$ is in $\mathcal{M}_{q}$. ∎

###### Proof of Theorem 1.2.

This is an immediate consequence of combining Lemmas 2.2 and 2.3. ∎

##  3\. Characterizing $GF(q)$-chordal matroids

In this section, we prove Theorems 1.3 and 1.4. An induced-minor-minimal
non-$GF(q)$-chordal matroid is a $GF(q)$-representable matroid that is not a
$GF(q)$-chordal matroid such that every proper induced minor of $M$ is a
$GF(q)$-chordal matroid. When $q=2$, the only rank-2 binary matroids are
$U_{2,2}$ and $U_{2,3}$ both of which are $GF(2)$-chordal. Clearly, neither
$M(K_{4})$ nor $U_{3,4}$ is $GF(2)$-chordal. It follows that each is an
induced-minor-minimal non-$GF(2)$-chordal matroid. When $q>2$, the matroids in
$\\{U_{2,3},U_{2,4},\dots,U_{2,q}\\}$ are induced-minor-minimal
non-$GF(q)$-chordal matroids.

For the remainder of this paper, it will be convenient to view a
$GF(q)$-representable matroid $M$ of rank $r$ as a restriction of $P_{r}$ by
coloring the elements of $E(M)$ green and coloring the other elements red.
Note that when we contract an element $e$ from $M$, we can obtain $M/e$ as
follows. Take a hyperplane $H$ of $P_{r}$ that avoids $e$. Then project from
$e$ onto $H$. Because $e$ is green, an element $z$ of $H$ is green in the
contraction precisely when there are at least two green points on the line
${\rm cl}_{P_{r}}(\\{e,z\\})$ of $P_{r}$.

For a positive integer $k$, a partition $(X,Y)$ of the ground set of a matroid
$M$ is a vertical $k$-separation of $M$ if $r(X)+r(Y)-r(M)\leq k-1$ and
$\min\\{r(X),r(Y)\\}\geq k$. This vertical $k$-separation is exact if
$r(X)+r(Y)-r(M)=k-1$.

######  Lemma 3.1.

Let $(X,Y)$ be a vertical $2$-separation in a matroid $M$ such that each of
$M|{\rm cl}(X)$ and $M|{\rm cl}(Y)$ is in $\mathcal{M}_{q}$. Then either

  1. (i)

$|{\rm cl}(X)\cap{\rm cl}(Y)|=1$ and $M\in\mathcal{M}_{q}$; or

  2. (ii)

$|{\rm cl}(X)\cap{\rm cl}(Y)|=0$ and $M$ has $U_{3,4}$ and $U_{2,3}$ as
induced minors.

###### Proof.

Observe that if $|{\rm cl}(X)\cap{\rm cl}(Y)|=1$, then $M$ is the parallel
connection of $M|{\rm cl}(X)$ and $M|{\rm cl}(Y)$, so $M\in\mathcal{M}_{q}$.
Now suppose that ${\rm cl}(X)\cap{\rm cl}(Y)=\emptyset$. Let $C$ and $D$ be
circuits of $M$ each of which meets both $X$ and $Y$ such that $|C\cap X|$ is
a minimum and $|D\cap Y|$ is a minimum. Because $M$ can be written as a
$2$-sum with basepoint $b$ of matroids with ground sets $X\cup b$ and $Y\cup
b$, it follows that $(C\cap X)\cup(D\cap Y)$ is a circuit of $M$. Clearly both
$M|{\rm cl}(C\cap X)$ and $M|{\rm cl}(D\cap Y)$ are in $\mathcal{M}_{q}$. Let
$X_{1}$ and $Y_{1}$ be subsets of $C\cap X$ and $D\cap Y$, respectively, such
that $|X_{1}|=|C\cap X|-2$ and $|Y_{1}|=|D\cap Y|-2$. Then each of $(M|{\rm
cl}(C\cap X))/X_{1}$ and $(M|{\rm cl}(D\cap Y))/Y_{1}$ is a rank-2 matroid in
$\mathcal{M}_{q}$. Moreover, in $M/X_{1}$, there is no element $x$ of $X$ that
is in the closure of $Y$ otherwise $(X_{1}\cup x)\cup(D\cap Y)$ contains a
circuit of $M$ that contains $x\cup(D\cap Y)$ and violates the choice of $C$.
Hence the rank-2 matroid $(M|{\rm cl}(C\cap X))/X_{1}$, which is in
$\mathcal{M}_{q}$, is not isomorphic to $U_{2,q+1}$. Thus it is isomorphic to
$U_{2,2}$. By symmetry, $(M|{\rm cl}(D\cap Y))/Y_{1}\cong U_{2,2}$. Hence
$(M|{\rm cl}((C\cap X)\cup(D\cap Y)))/(X_{1}\cup Y_{1})\cong U_{3,4}$. Thus
both $U_{3,4}$ and $U_{2,3}$ are induced minors of $M$. ∎

In the next result, we denote by $P_{r+1}\backslash P_{r-i}$ the matroid that
is obtained from $P_{r+1}$ by deleting the elements of a rank-$(r-i)$ flat.
Clearly this matroid does not depend on the choice of the rank-$(r-i)$ flat.

######  Lemma 3.2.

Let $M$ be a binary rank-$(r+1)$ matroid. Then $M/e\cong P_{r}$ for all $e$ in
$E(M)$ if and only if $M\cong P_{r+1}\backslash P_{r-i}$ for some $i$ in
$\\{0,1,\dots,r\\}$.

###### Proof.

If $M\cong P_{r+1}\backslash P_{r-i}$ for some $i$ in $\\{0,1,\dots,r\\}$,
then, by, for example, [12, Corollary 6.2.6], $M/e\cong P_{r}$ for all $e$ in
$E(M)$.

Now suppose $E(M)\cong P_{r}$ for each $e$ in $E(M)$. We may assume that
$|E(P_{r+1})-E(M)|\geq 2$ otherwise the result certainly holds. Let $x$ and
$y$ be distinct elements of $E(P_{r+1})-E(M)$. Then the third element $z$ on
the line of $P_{r+1}$ that is spanned by $\\{x,y\\}$ must also be in
$E(P_{r+1})-E(M)$ otherwise $M/z$ is not isomorphic to $P_{r}$. It follows
that, for a basis $X$ of $P_{r+1}\backslash E(M)$, by [11, Theorem 1], ${\rm
cl}_{P_{r+1}}(X)=E(P_{r+1})-E(M)$. Since $M$ has rank $r+1$, we deduce that
${\rm cl}_{P_{r+1}}(X)$ is a projective geometry of rank at most $r$. The
lemma follows. ∎

We omit the straightforward proof of the next result.

######  Lemma 3.3.

For $r\geq 3$, if $M$ is the binary matroid $P_{r}\backslash P_{r-i}$ for some
$i$ in the set $\\{1,2,\dots,r-1\\}$, then $M$ has a flat isomorphic to either
$M(K_{4})$ or $U_{3,4}$.

For all $q>2$, the only rank-2 members of $\mathcal{M}_{q}$ are $U_{2,2}$ and
$U_{2,q+1}$. Natural obstructions to membership of $\mathcal{M}_{q}$ are the
lines that contain more than two but fewer than $q+1$ points, that is, the
collection $\\{U_{2,i}:3\leq i\leq q\\}$. In rank three, the only matroid that
is not in $\mathcal{M}_{q}$ and has no member of $\\{U_{2,i}:3\leq i\leq q\\}$
as an induced minor is $U_{3,q+2}$. By Bose [4], we note that $U_{3,q+2}$ is
representable over $GF(q)$ if and only if $q$ is even. Therefore, the
collection $\mathcal{N}=\\{U_{2,3},U_{2,4},\dots,U_{2,q},U_{3,q+2}\\}$ is
contained in the collection of forbidden induced minors for the class
$\mathcal{M}_{q}$. The next result highlights some structure in matroids that
have members of $\mathcal{N}$ as induced minors.

######  Lemma 3.4.

For some $q>2$, let $M$ be a $GF(q)$-representable matroid having rank at
least three. Suppose that $M\not\cong P_{r}$ but that $M/e\cong P_{r-1}$ for
all $e$ in $E(M)$. Then $M$ has a member of $\mathcal{N}$ as an induced minor.

###### Proof.

Suppose $M$ has no member of $\mathcal{N}$ as an induced minor. Suppose
$r(M)=3$. Since the contraction of any element would result in a $(q+1)$-point
line, $E(M)$ must have at least $q+2$ elements. Moreover, since $M$ is not
$U_{3,q+2}$, we deduce that $M$ contains a triangle $\\{p_{1},p_{2},p_{3}\\}$.
This triangle must be contained in a full $(q+1)$-point line of $M$, otherwise
$M$ would contain a member of $\mathcal{N}$ as an induced restriction. Label
this line $\\{p_{1},p_{2},\dots,p_{q+1}\\}$. Since $|E(M)|\geq q+2$, we may
choose an element $e$ in $E(M)-\\{p_{1},p_{2},\dots,p_{q+1}\\}$. If $e$ is
unique, then $M/p_{1}$ is isomorphic to $U_{2,2}$, a contradiction. Without
loss of generality, suppose there is a third point on the line ${\rm
cl}(\\{e,p_{1}\\})$. Then this line is a full $(q+1)$-point line. Therefore,
there are two full lines meeting at $p_{1}$. If this were the entire matroid,
then $M/p_{1}$ consists of only two points. Hence there is an additional
element $f$ in $M$ not on either of the lines ${\rm cl}(\\{e,p_{1}\\})$ or
$\\{p_{1},p_{2},\dots,p_{q+1}\\}$. Each point of the line ${\rm
cl}(\\{e,p_{1}\\})$ together with $f$ defines a line that meets the line
$\\{p_{1},p_{2},\dots,p_{q+1}\\}$ in a distinct point and so each of these
lines is also full. This gives that every line is full except possibly the
line ${\rm cl}(\\{p_{1},f\\})$. If any of the points on the line ${\rm
cl}(\\{p_{1},f\\})$ is absent, then, for some $i$ in $[q+1]$, the line ${\rm
cl}(\\{e,p_{i}\\})$ contains only $q$ points, a contradiction. Therefore,
every line of $M$ is full and $M$ must be a projective geometry, a
contradiction. Thus the result holds when $r(M)=3$.

Now suppose the result holds for $r(M)<k$ and let $r(M)=k\geq 4$. Let $e$ be
an element of $M$. Since $M/e\cong P_{r-1}$, each of the lines of $P_{r}$ that
contains $e$ must contain a second point of $M$. There must be such a line,
say $L$, that contains exactly two points of $M$ otherwise every such line has
exactly $q+1$ points and $M\cong P_{r}$, a contradiction. Let $L=\\{e,f\\}$.
Take a point $g$ in $E(M)-L$ and consider the plane $Q={\rm
cl}_{M}(\\{e,f,g\\})$. Since $M/h\cong P_{r}$ for every point $h$ of this
plane, it follows that $Q/h\cong U_{2,q+1}$. It follows by the induction
assumption that $Q\cong P_{3}$. Hence $L$ is a $(q+1)$-point line, a
contradiction. We conclude, by induction, that the lemma holds. ∎

######  Lemma 3.5.

Let $M$ be a $GF(q)$-representable matroid and let $(X,Y)$ be an exact
vertical $k$-separation of $M$. Suppose that both $M|{\rm cl}_{M}(X)$ and
$M|{\rm cl}_{M}(Y)$ are in $\mathcal{M}_{q}$. Then either ${\rm
cl}_{M}(X)\cap{\rm cl}_{M}(Y)$ is a projective geometry of rank $k-1$, or $M$
has a member of $\mathcal{N}$ as an induced minor.

###### Proof.

This is immediate if $k=1$ and follows by Lemma 3.1 when $k=2$, so we may
assume that $k\geq 3$. Let $M$ be an induced-minor-minimal counterexample and
let $r(M)=r$. Suppose first that ${\rm cl}_{M}(X)\cap{\rm cl}_{M}(Y)$ is
empty. Then in the green-red coloring of $P_{r}$ corresponding to $M$, all of
the elements of ${\rm cl}_{P_{r}}(X)\cap{\rm cl}_{P_{r}}(Y)$ are red. Take $e$
in $X$ and suppose that $r(X)>k$. Then $M/e$ has an exact vertical
$k$-separation $(X^{\prime},Y^{\prime})$ corresponding to $(X-e,Y)$. By the
minimality of $M$, we deduce that ${\rm cl}_{M/e}(X^{\prime})\cap{\rm
cl}_{M/e}(Y^{\prime})$ is a projective geometry of rank $k-1$.

Since $k\geq 3$, there is a projective line $L$ contained in ${\rm
cl}_{P_{r}}(X)\cap{\rm cl}_{P_{r}}(Y)$. In the green-red coloring of $P_{r}$,
every element of $L$ is red. But every element of $L$ is green in the coloring
of $P_{r}/e$. Thus, in $P_{r}$, for each of the points
$z_{1},z_{2},\dots,z_{q+1}$ of $L$, there is a green point on the line ${\rm
cl}_{P_{r}}(\\{e,z_{i}\\})$ other than $e$. Thus, when $q=2$, we see that the
four green points in ${\rm cl}_{P_{r}}(L\cup e)$ form a 4-circuit, a
contradiction as $M|{\rm cl}_{M}(X)$ is $GF(2)$-chordal. When $q>2$, because
all of the elements of $L$ are red, the set of points in ${\rm
cl}_{P_{r}}(L\cup e)$ contains no line with more than $q$ points. Since
$M|{\rm cl}_{M}(X)$ is in $\mathcal{M}_{q}$, it follows that each line in
${\rm cl}_{P_{r}}(L\cup e)$ that contains at least two green points contains
exactly two green points. It follows that $M$ has $U_{3,q+2}$ as an induced
restriction, a contradiction.

We may now assume that $r(X)=k=r(Y)$. Since $(X,Y)$ is an exact
$k$-separation, $r(X)+r(Y)-r(M)=k-1$, so $r(M)=k+1$. As $M$ has at least $2k$
elements, it has an element $f$ that is not a coloop. Then the construction of
members of $\mathcal{M}_{q}$ implies that $f$ is on a $(q+1)$-point green line
of $M$. This line must meet ${\rm cl}_{P_{r}}(X)\cap{\rm cl}_{P_{r}}(Y)$ so
${\rm cl}_{P_{r}}(X)\cap{\rm cl}_{P_{r}}(Y)$ is not entirely red, a
contradiction.

We conclude ${\rm cl}_{M}(X)\cap{\rm cl}_{M}(Y)$ contains at least one point,
say $z$. In $M/z$, there is an exact vertical $(k-1)$-separation
$(X^{\prime\prime},Y^{\prime\prime})$ corresponding to $(X-z,Y-z)$. We deduce,
by the minimality of $M$, that ${\rm cl}_{P_{r}/z}(X^{\prime\prime})\cap{\rm
cl}_{P_{r}/z}(Y^{\prime\prime})$ is a projective geometry of rank $k-2$. By
Lemmas 3.3 and 3.4, we deduce that $M|\left({\rm cl}_{M}(X)\cap{\rm
cl}_{M}(Y)\right)$ must have, as an induced minor, a matroid that is not in
$\mathcal{M}_{q}$. ∎

######  Corollary 3.6.

For all $k\geq 1$, an induced-minor-minimal non-$GF(q)$-chordal matroid has no
vertical $k$-separations.

A matroid $M$ is round if $M$ has no two disjoint cocircuits. Equivalently,
$M$ is round if there is no $k$ for which $M$ has a vertical $k$-separation
(see, for example, [12, Lemma 8.6.2]). The following result is immediate from
the constructive definition of $GF(q)$-chordal matroids.

######  Lemma 3.7.

A rank-$r$ matroid $M$ in $\mathcal{M}_{q}$ is round if and only if $M\cong
P_{r}$.

The following is a straightforward consequence of the definition.

######  Lemma 3.8.

A simple binary matroid is chordal if and only if it does not have $U_{3,4}$
as an induced minor.

######  Lemma 3.9.

All $GF(2)$-chordal matroids are chordal matroids.

###### Proof.

Let $M$ be a $GF(2)$-chordal matroid. Since the class of $GF(2)$-chordal
matroids is closed under induced minors, $U_{3,4}$ is not an induced minor of
$M$, so $M$ is a chordal matroid. ∎

Since $M(K_{4})$ is chordal but not $GF(2)$-chordal, it is clear that the
class of binary matroids that are chordal properly contains the class of
$GF(2)$-chordal matroids.

We now give a common proof of the two main results of the paper.

###### Proof of Theorems 1.3 and 1.4.

Let $M$ be an induced-minor-minimal non-$GF(q)$-chordal matroid. By Corollary
3.6, $M$ is round. By Geelen, Gerards, and Whittle [9], $M/e$ is also round
for all $e$ in $E(M)$. Thus by Lemma 3.7, $M/e\cong P_{r-1}$ where $r(M)=r$.

First, let $q=2$. Then, by Lemma 3.2, $M\cong P_{r}\backslash P_{r-i}$ for
some $i$ in $\\{1,2,\dots,r-1\\}$. Moreover, since $M$ is not a
$GF(2)$-chordal matroid, $r\geq 3$. Then, by Lemma 3.3, $M$ has $M(K_{4})$ or
$U_{3,4}$ as an induced restriction. As each of these matroids is an induced-
minor-minimal non-$GF(2)$-chordal matroid, we deduce that $M$ is isomorphic to
$M(K_{4})$ or $U_{3,4}$.

Now assume that $q>2$. Since each member of $\mathcal{N}$ is an induced-minor-
minimal non-$GF(q)$-chordal matroid, we may assume that $M$ has no member of
$\mathcal{N}$ as an induced minor. Thus $r(M)\geq 3$. By Lemma 3.4, we get a
contradiction. ∎

##  4\. Dirac’s Other Characterization

In [8], another characterization is given of chordal graphs. In a graph $G$, a
vertex separator is a set of vertices whose deletion produces a graph with
more connected components than $G$.

######  Theorem 4.1.

A graph is chordal if and only if every minimal vertex separator induces a
clique.

It is shown in Lemma 3.5 that, if $M$ is a $GF(q)$-chordal matroid, then, for
every exact vertical $k$-separation $(X,Y)$ of $M$, the restriction $M|({\rm
cl}(X)\cap{\rm cl}(Y))\cong P_{k-1}$. However, the converse of this is not
true. For example, the matroid $P_{U_{2,3}}(M(K_{4}),M(K_{4}))$ is not
$GF(2)$-chordal, but the only exact vertical $k$-separation has $k=3$ and has
$U_{2,3}$ as the intersection of the closures of the two sides of the vertical
$3$-separation. A divider in a matroid is an exact vertical $k$-separation for
some $k$. A divider $(X,Y)$ is minimal if there is no vertical
$k^{\prime}$-separation $(X^{\prime},Y^{\prime})$ such that ${\rm
cl}(X^{\prime})\cap{\rm cl}(Y^{\prime})\subsetneqq{\rm cl}(X)\cap{\rm cl}(Y)$.
Recall that, for sets $X$ and $Y$ in a matroid $M$, the local connectivity
between $X$ and $Y$, denoted $\sqcap(X,Y)$ or $\sqcap_{M}(X,Y)$, is given by
$\sqcap(X,Y)=r(X)+r(Y)-r(X\cup Y)$. Let $\mathcal{N}_{q}$ be the class of
$GF(q)$-representable matroids $N$ such that, for every minimal divider
$(X,Y)$ of $N$, the matroid $N|({\rm cl}(X)\cap{\rm cl}(Y))$ is a projective
geometry of rank $\sqcap(X,Y)$. Since round matroids have no vertical
$k$-separations, all $GF(q)$-round matroids are in $\mathcal{N}_{q}$.

######  Lemma 4.2.

Let $(X,Y)$ be a minimal divider of a matroid $N$. Then ${\rm cl}(X)\cap{\rm
cl}(Y)={\rm cl}(X)\cap{\rm cl}(Y-{\rm cl}(X))$.

###### Proof.

Suppose $y\in{\rm cl}(X)\cap Y$. Then $r(Y)=r(Y-y)$; otherwise, $y$ is a
coloop of $N|Y$ and $(X\cup y,Y-y)$ is a divider with ${\rm cl}(X\cup
y)\cap{\rm cl}(Y-y)$ properly contained in ${\rm cl}(X)\cap{\rm cl}(Y)$, a
contradiction. We deduce that ${\rm cl}(Y)={\rm cl}(Y-{\rm cl}(X))$. ∎

The next theorem is an analog of Theorem 4.1.

######  Theorem 4.3.

A matroid $M$ is in $\mathcal{N}_{q}$ if and only if $M$ can be constructed
from round $GF(q)$-representable matroids by a sequence of generalized
parallel connections across projective geometries.

###### Proof.

Let $\mathcal{R}_{q}$ be the class of matroids that can be constructed from
round $GF(q)$-representable matroids by a sequence of generalized parallel
connections across projective geometries. It suffices to prove that a
connected matroid $M\in\mathcal{N}_{q}$ if and only if it is in
$\mathcal{R}_{q}$. Suppose $M\in\mathcal{N}_{q}$. If $M$ has no dividers, then
$M$ is round, so $M\in\mathcal{R}_{q}$. Hence, we may assume $M$ has a minimal
divider $(X,Y)$. Then $M|({\rm cl}(X)\cap{\rm cl}(Y))$ is a projective
geometry $N$ of rank $\sqcap(X,Y)$, and $M=P_{N}(M|{\rm cl}(X),M|{\rm
cl}(Y))$. Letting $M_{X}=M|{\rm cl}(X)$, we see that $M_{X}$ is either round
or has a minimal divider $(U,V)$, where $M_{X}|({\rm cl}(U)\cap{\rm cl}(V))$
is a projective geometry, $N^{\prime}$, of rank $\sqcap_{M_{X}}(U,V)$, and
$M_{X}$ is equal to $P_{N^{\prime}}(M_{X}|{\rm cl}(U),M_{X}|{\rm cl}(V))$.
Continuing in this way, we see that every matroid in $\mathcal{N}_{q}$ can be
obtained in the manner prescribed. Hence
$\mathcal{N}_{q}\subseteq\mathcal{R}_{q}$.

We will prove that $\mathcal{R}_{q}\subseteq\mathcal{N}_{q}$ by induction on
the number $n$ of round matroids used to construct a connected member $M$ of
$\mathcal{R}_{q}$. If $n=1$, then $M$ is round and so $M$ is in
$\mathcal{N}_{q}$. Now suppose that the result holds when $n\leq t-1$ and
assume that $M$ is constructed by using exactly $t$ round matroids. Then
$M\cong P_{N}(M_{1},M_{2})$, where $M_{2}$ is a round matroid and $N$ is a
projective geometry. Let $(X,Y)$ be a minimal divider of $M$ and let $F={\rm
cl}(X)\cap{\rm cl}(Y)$. We need to show that $M|F\cong P_{k}$ where $r(F)=k$.
Let $X_{N}=X\cap E(N)$ and $Y_{N}=Y\cap E(N)$. Also let $X_{i}=(X\cap
E(M_{i}))-X_{N}$ and $Y_{i}=(Y\cap E(M_{i}))-Y_{N}$ for each $i$ in
$\\{1,2\\}$. Since $N$ is a projective geometry, we may suppose that $X_{N}$
spans $Y_{N}$. Therefore ${\rm cl}(Y_{N})\subseteq F$. As $M_{2}$ is round and
has $(X_{N}\cup Y_{N}\cup X_{2},Y_{2})$ as a partition, either $X_{N}\cup
X_{2}$ spans $Y_{2}$, or $Y_{2}$ spans $M_{2}$. In the latter case, $Y$ spans
$E(N)$, so $E(N)\subseteq F$. Now, $(E(M_{1}),E(M_{2})-E(N))$ is a divider of
$M$ and ${\rm cl}(E(M_{1}))\cap{\rm cl}(E(M_{2})-E(N))=E(N)$. Because $(X,Y)$
is a minimal divider, we have $F=E(N)$, so $M|F\cong P_{k}$ where $r(F)=k$.

We deduce that $X_{N}\cup X_{2}$ spans $Y_{2}$. Then ${\rm cl}(X)$ contains
$E(M_{2})$ and, by Lemma 4.2, we may assume that $Y\subseteq E(M_{1})-E(N)$.
Thus

$F={\rm cl}(X)\cap{\rm cl}(Y)={\rm cl}_{M_{1}}(X\cap E(M_{1}))\cap{\rm
cl}_{M_{1}}(Y).$ (4.1)

We show next that $(X\cap E(M_{1}),Y)$ is a minimal divider of $M_{1}$. It is
a divider of $M_{1}$ unless $X\cap E(M_{1})$ or $Y$ spans $M_{1}$. In the
exceptional case, as $X$ does not span $M$, we see that $X\cap E(M_{1})$ does
not span $M_{1}$. Thus $Y$ spans $M_{1}$, so $E(N)\subseteq F$. Hence
$E(N)=F$, and $M|F\cong P_{k}$ as desired. Thus $(X\cap E(M_{1}),Y)$ is a
divider of $M_{1}$. Suppose it is not minimal. Then, by (4.1), $M_{1}$ has a
minimal divider $(X_{1},Y_{1})$ such that ${\rm cl}_{M_{1}}(X_{1})\cap{\rm
cl}_{M_{1}}(Y_{1})\subsetneqq F$. Now we may assume that ${\rm
cl}_{M_{1}}(X_{1})\supseteq E(N)$, so $({\rm cl}_{M_{1}}(X_{1}),Y_{1}-{\rm
cl}_{M_{1}}(X_{1}))$ is a minimal divider of $M_{1}$. It follows that
$(E(M_{2})\cup{\rm cl}_{M_{1}}(X_{1}))\cap{\rm cl}_{M}(Y_{1}-{\rm
cl}_{M_{1}}(X_{1}))={\rm cl}_{M_{1}}(X_{1})\cap{\rm
cl}_{M_{1}}(Y_{1})\subsetneqq F$, a contradiction. Hence $(X\cap E(M_{1}),Y)$
is a minimal divider of $M_{1}$. By the induction assumption, $M_{1}|F\cong
P_{k}$, so $M|F\cong P_{k}$, as desired. ∎

## References

  * [1] Barahona, F. and Grötschel, M., On the cycle polytope of a binary matroid, J. Combin. Theory Ser. B 40 (1986), 40–62.
  * [2] Berge, C., Some classes of perfect graphs, Graph Theory and Theoretical Physics, Academic Press, London, pp.155–165, 1967
  * [3] Bonin, J. and de Mier, A., $T$-uniqueness of some families of $k$-chordal matroids, Adv. in Appl. Math. 32 (2004), 10–30.
  * [4] Bose, R.C., Mathematical theory of the symmetrical factorial design, Sankyhā 8 (1947), 107–166.
  * [5] Brylawski, T.H., Modular constructions for combinatorial geometries, Trans. Amer. Math. Soc. 203 (1975), 1–44.
  * [6] Cordovil, R., Forge, D., and Klein, S., How is a chordal graph like a supersolvable binary matroid?, Discrete Math. 288 (2004), 167–172.
  * [7] Diestel, R., Graph Theory, Third Edition, Springer, Berlin, 2005.
  * [8] Dirac, G.A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961), 71–76.
  * [9] Geelen, J., Gerards, B., and Whittle, G., Disjoint cocircuits in matroids with large rank, J. Combin. Theory Ser. B, 87 (2003), 270–279.
  * [10] Mayhew, D. and Probert, A., Supersolvable saturated matroids and chordal graphs, https://arxiv.org/abs/2301.03776.
  * [11] Murty, U.S.R., Matroids with Sylvester property, Aequationes Math. 4 (1970), 44–50.
  * [12] Oxley, J., Matroid Theory, Second Edition, Oxford University Press, New York, 2011.
  * [13] Rose, D.J., Triangulated graphs and the elimination process, J. Math. Anal. Appl. 32 (1970), 597–609.
  * [14] Seymour, P.D. and Weaver, R.W., A generalization of chordal graphs, J. Graph Theory 8 (1984), 241–251.
  * [15] Stanley, R.P., Supersolvable lattices, Algebra Univ. 2 (1972), 197–217.
  * [16] Tutte, W.T., Menger’s Theorem for matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 49–53.
  * [17] Ziegler, G.M., Binary supersolvable matroids and modular constructions, Proc. Amer. Math. Soc. 113 (1991), 817–829.