%%%%%%%%%% BEGIN TeX file  %%%%%%%%%%
%%% Final version  January 10, 2000 %%%%%%%%%%%%%%
\documentclass[10pt,reqno]{amsart}
%\usepackage[notcite]{show keys}
\usepackage{amssymb}
\swapnumbers
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{noname}[theorem]{}
\newtheorem{sublemma}{}[theorem]


%\theoremstyle{problem}
\newtheorem{problem}[theorem]{Problem}
%\newtheorem{example}[theorem]{Example}

%\theoremstyle{remark}
%\newtheorem{remark}[theorem]{Remark}

%\numberwithin{equation}{section}

\newcommand{\de}{\backslash}
\newcommand{\ag}{AG(2,3)}
\newcommand{\ba}{\backslash}
\newcommand{\sixrt}{\sqrt[6]{1}}
\newcommand{\co}{{\rm co}}
\newcommand{\si}{{\rm si}}
\newcommand{\cl}{{\rm cl}}
\newcommand{\utf}{U_{2,4}}
\newcommand{\mkf}{M(K_4)}


\begin{document}

\title[A sharp bound on the size of a connected matroid]{A sharp  
bound on the
size of a connected matroid}

\author{Manoel Lemos}
\address{Departamento de Matem\'atica\\
        Universidade Federal de Pernambuco\\
        Recife\\
        Pernambuco 50740-540\\
        Brazil}
\email{manoel@dmat.ufpe.br}

\author{James Oxley}
\address{Department of Mathematics\\
        Louisiana State University\\
        Baton Rouge\\
        Louisiana 70803--4918\\
        USA}
\email{oxley@math.lsu.edu}




\subjclass{05B35}
\date{}

\begin{abstract}
This paper proves that a connected matroid $M$ whose largest  
circuit and largest
cocircuit have $c$ and $c^*$ elements, respectively, has at most
$\frac{1}{2}cc^*$ elements.  It is also shown that if $e$ is an  
element of $M$
and $c_e$ and $c^*_e$ are the sizes of a largest circuit containing  
$e$ and a
largest cocircuit containing $e$, then $|E(M)| \le (c_e -1)(c^*_e -  
1) + 1$.
Both these bounds are sharp and the first is proved using the second.
The second inequality is an interesting companion to Lehman's  
width-length
inequality which asserts that the former inequality can be reversed  
for regular
matroids when $c_e$ and $c^*_e$ are replaced by the sizes of a  
smallest circuit
containing $e$ and a smallest cocircuit containing $e$. Moreover,  
it follows
from the second inequality that if $u$ and $v$ are distinct  
vertices in a
$2$-connected loopless graph $G$, then $|E(G)|$ cannot exceed the  
product of the
length of a longest $(u,v)$-path and the size of a largest minimal  
edge-cut
separating $u$ from $v$.

\end{abstract}

\maketitle
\section{Introduction}

At the 1991 Seattle conference on graph minors, Robin Thomas  
informally asked
the question as to whether every sufficiently large connected  
matroid has a big
circuit or a big cocircuit. This question was rapidly answered at  
that meeting
by Lov\'asz, Schrijver, and Seymour (see \cite{oxbook}) who proved  
the following
result.

\begin{theorem}
\label{lss}
Let $M$ be a connected matroid with at least two elements. If a  
largest circuit
of $M$ has $c$ elements and a largest cocircuit has $c^*$ elements,  
then $M$ has
at most $2^{c+c^*-1}$ elements.
\end{theorem}

An affirmative answer to Thomas's question can also be obtained  
from a result of
Tuza \cite{tuza} for set systems.
In response to Theorem \ref{lss}, a natural question is whether the  
bound in the
theorem can be improved, particularly if attention is restricted to  
certain
special classes of matroids.  For graphic matroids, the following  
dramatic
improvement was found by Pou-Lin Wu \cite{plw}.


\begin{theorem}
\label{pwu}
Let $G$ be a loopless  $2$--connected graph in which a largest  
cycle has $c$
edges and a largest bond has $c^*$ edges. Then $G$ has at most
$\frac{1}{2}\,cc^*$ edges.
\end{theorem}

Of course, $c$ is just the circumference of the graph $G$.
There is a wide gap between the graph bound in Theorem \ref{pwu}  
and the general
matroid bound in Theorem \ref{lss}. Reid \cite{tjr} partially  
closed  this gap.
He defined the {\it matroid Ramsey number} $n(s,t)$ to be the least  
positive
integer $n$ so that every $n$--element connected matroid has a  
circuit of size
at least $s$ or a cocircuit of size at least $t$. Reid showed that  
$n(s,t)$ has
several attractive properties that are analogous to properties of  
the classical
Ramsey numbers for graphs established by  Erd\H{o}s and Szekeres  
\cite{es}.
Using these, Reid proved the following improvement of Theorem~\ref{lss}.


\begin{theorem}
\label{tjr2}
If $M$ is a connected matroid with largest circuit of size $c$ and  
largest
cocircuit of size $c^*$, then
\[
|E(M)| \le \binom{c+c^*-2}{c-1} - 2
\]
provided both $c$ and $c^*$ exceed three.
\end{theorem}

Reid \cite{tjr} and Hurst and Reid \cite{hurst_reid} also  
determined some small
matroid Ramsey numbers including all $n(s,t)$ with $s$ or $t$ at  
most three.

The purpose of this paper is to prove that the bound that Pou-Lin  
Wu proved for
graphic matroids also holds for matroids in general.  The following  
is our main
result.

\begin{theorem}
\label{Theorem 7}
Let $M$ be a connected matroid with at least two elements. If a  
largest circuit
of $M$ has $c$ elements and a largest cocircuit has $c^*$ elements, then 
$$|E(M)|\le\left\lfloor\frac{cc^*}{2}\right\rfloor.$$
\end{theorem}

This theorem solves a problem raised by Oxley \cite{jgo_hun} and  
settles a
conjecture of Bonin, McNulty, and Reid \cite{bmr}.  For comparison,  
a lower
bound on $|E(M)|$ in terms of $c$ and $c^*$ that holds for all  
matroids $M$
having non-zero rank and corank is
\begin{equation}
\label{lower}
c + c^* - 2 \le |E(M)|.
\end{equation}
To see this, observe that $c \le r(M) + 1$ and $c^* \le r^*(M) +  
1$.  The bound
in (\ref{lower}) is sharp. It is attained by, for example, the  
whirls, all
uniform matroids of non-zero rank and corank, and, more generally,  
by all
matroids with both a free element and a cofree element.



The proof of Theorem~\ref{Theorem 7} will use another bound that is of 
independent interest.

\begin{theorem}
\label{Theorem 1}
Let $M$ be a connected matroid with at least two elements and let  
$e$ be an
element of $M$. If a largest circuit of $M$ containing $e$ has  
$c_e$ elements
and a largest cocircuit containing $e$ has $c^*_e$ elements, then
$$|E(M)|\le (c_e-1)(c_e^*-1)+1.$$
\end{theorem}

The last theorem has an attractive similarity to a bound derived  
from the {\it
width-length inequality}~\cite{leh,drf}.  In a matroid $M$, let $e$  
be an
element that is neither a loop nor a coloop. Let $\lambda(M) + 1$ and  
$\omega(M) + 1$ be the cardinalities of a smallest circuit  
containing $e$ and a
smallest cocircuit containing $e$. Lehman~\cite{leh} showed that if  
$M$ is
regular, then
\begin{equation}
\lambda(M)\omega(M) \le |E(M)| - 1.
\end{equation}
More generally, it follows from a  result of Seymour~\cite{mfmc}  
that the last
inequality  holds for all binary matroids that have no  
$F^*_7$-minor using $e$.
In fact, it also holds for $F^*_7$, although it fails, for example, for 
$AG(3,2)$.

A straightforward consequence of Theorem~\ref{Theorem 1} is the  
following result
for graphs.

\begin{corollary}
\label{longest}
Let $u$ and $v$ be distinct vertices in a $2$-connected loopless  
graph $G$.
Then $|E(G)|$ cannot exceed the product of the length of a longest  
$(u,v)$-path
and the size of a largest minimal edge-cut separating $u$ from $v$.
\end{corollary}



The bounds in Theorems~\ref{pwu}, ~\ref{Theorem 7}, and  
\ref{Theorem 1} are
sharp.  Pou-Lin Wu \cite{plw2} determined all graphs that attain  
the bound in
Theorem~\ref{pwu}. The cycle matroid of each such graph  attains  
the bound in
Theorem~\ref{Theorem 7} provided   $c$ or $c^*$ is even. A  
non-graphic matroid
attaining the bound in Theorem~\ref{Theorem 7}, which was noted by Reid 
\cite{tjr}, is $AG(3,2)$.  In Section 4, we shall describe all the  
matroids that
attain the bound in Theorem~\ref{Theorem 1}, noting that there is a  
close link
between these matroids and those found by Wu.

The matroid terminology used here will follow Oxley~\cite{oxbook}.  In 
particular, the set of circuits of a matroid $M$ will be denoted by  
${\mathcal
C}(M)$. Theorem~\ref{Theorem 1} will be deduced in the next section  
from a
stronger result, while Theorem~\ref{Theorem 7} will be proved in  
Section 3.




\section{Two strengthenings of Theorem~\ref{Theorem 1}}

Let $e$ be an element of a matroid $M$ and suppose that $e$ is not  
a coloop of
$M$. We define the {\it circumference of $M$ through} $e$ by
$$c_e(M)=\max\{|C|:e\in C\in {\mathcal C}(M)\},$$
that is, $c_e(M)$ is the size of a largest circuit that contains  
$e$. If $f$ is
an element of $M$ that is not a loop, we define  
$c_f^*(M)=c_f(M^*)$. The {\it
circumference} $c(M)$  of a non-free matroid is the size of a  
largest circuit of
$M$. If $r(M) > 0$, we define  $c^*(M) = c(M^*)$.

Let $C$ be a circuit of a matroid $M$. A subset  $P$ of $E(M)-C$ is  
a {\it
chord} of $C$ if $P\in{\mathcal C}(M/C)-{\mathcal C}(M)$.  
Equivalently, $P$ is a
chord of $C$ if and only if $P$ is disjoint from $C$ and $M|(C\cup  
P)$ is a
connected matroid having corank  two. In particular, when $P$ is a  
chord of $C$,
it is a series class of $M|(C\cup P)$.

The first strengthening of Theorem~\ref{Theorem 1}  will require  
some more
preliminaries.
Let $L$ be a subset of the ground set of a matroid $M$ and suppose  
that $L$ is
the union of a set of circuits of $M$ and $r^*(M|L)=2$. Then $L$ is  
what Tutte
\cite{wtt} has called a ``line'' of $M$.  We shall call $L$ a {\it  
Tutte-line}
since the word ``line'' is also commonly used in matroid theory to  
mean a rank-2
flat.  It is not difficult to see that every Tutte-line $L$ of a  
matroid $M$ has
a {\it canonical partition} $\{L_1,L_2,\dots,L_k\}$ such that a  
subset $C$ of
$L$  is a circuit of $M|L$  if and only if $C=L- L_i$ for some $i$ in 
$\{1,2,\dots,k\}$. A Tutte-line $L$ is {\it connected} if  $M|L$ is  
a connected
matroid. The {\it size} of a Tutte-line is the number of sets in  
its canonical
partition. Hence a Tutte-line is connected if and only if it has  
size at least
three.



\begin{theorem}
\label{Theorem 4}
Let $M$ be a connected matroid such that $|E(M)|>1$ and let $e$ be  
an element of
$M$.  Then
$$|E(M)|\le c_e(M)+\frac{1}{m-2}(c_e(M)-1)(c_e^*(M)-2)$$
for all  integers $m$ exceeding two such that every connected  
Tutte-line of $M$
has size at least $m$.
\end{theorem}

The dual of this theorem can be restated using the concept of a  
{\it coline} of
a matroid, a flat of rank two less than the matroid.

\begin{corollary}
\label{coline}
Let $M$ be a connected matroid such that $|E(M)|>1$ and let $e$ be  
an element of
$M$.  Suppose that $m$ is an integer exceeding two such that every  
coline of $M$
that is contained in more than two hyperplanes is contained in at  
least $m$
hyperplanes.  Then
$$|E(M)|\le c^*_e(M)+\frac{1}{m-2}(c^*_e(M)-1)(c_e(M)-2).$$
\end{corollary}




\begin{proof}[ Proof of Theorem~\ref{Theorem 1}] In all connected  
matroids with
at least two elements, every connected Tutte-line has size at least  
three.  The
theorem follows immediately by taking $m=3$ in Theorem~\ref{Theorem 4}.
\end{proof}

\begin{proof}[ Proof of Corollary~\ref{longest}] Add the edge $e$  
to $G$ so that
it joins $u$ and $v$.  Then the result follows immediately from
Theorem~\ref{Theorem 1}.
\end{proof}




\begin{proof}[ Proof of Theorem~\ref{Theorem 4}]
 We argue by induction on $|E(M)|$  noting that the result holds  
when $|E(M)| =
2$.  Assume it holds for $|E(M)| < k$ and let $|E(M)| = k \ge 3$.
Choose a circuit $C$ of $M$ such that $e\in C$ and $|C|=c_e(M)$.  
Observe that
the result holds when $E(M)=C$. Thus we may suppose that  
$E(M)\not=C$. Let
$M_1,M_2,\dots,M_n$ be the connected components of $M/C$.

For each element $f$ of $C-e$,  consider the connected component  
$N_f$ of $M/(C
- \{e,f\})$ that contains $f$. There is a set ${\mathcal P}_f$ of  
matroids such
that
\begin{enumerate}

\item[(i)] $N_f$ is the parallel connection of the matroids in  
${\mathcal P}_f$
across the basepoint  $e$; and

\item[(ii)] $N/e$ is connected for every $N$ in ${\mathcal P}_f$.

\end{enumerate}
Observe that $\{e,f\}$ is the ground set of a matroid that belongs  
to ${\mathcal
P}_f$. For each matroid $N$ in ${\mathcal P}_f$, let $C^*_N$ be a  
cocircuit of
$N$ such that $e\in C^*_N$ and $|C^*_N|=c_e^*(N)$. Let
$$C^*=\bigcup_{N\in{\mathcal P}_f}C^*_N.$$
Then $C^*$ contains $e$ and is a cocircuit of $N_f$ and hence of  
$M$. Thus
\begin{equation}
\label{(1)}
c_e^*(M)\ge |C^*|=1+\sum_{N\in{\mathcal P}_f}(c_e^*(N)-1).
\end{equation}
For each $f$ in $C - e$, view the set ${\mathcal P}_f$ as a  
multiset and let
${\mathcal P}$ be the multiset that is the union of all these multisets.
For each $i$ in $\{1,2,\dots,n\}$, let ${\mathcal Q}_i$ be the  
multiset of
matroids $N$ in ${\mathcal P}$ for which $N/e=M_i$.
Then ${\mathcal P}$ is the union of the multisets ${\mathcal Q}_1,  
{\mathcal
Q}_2, \ldots, {\mathcal Q}_n$ together with $|C|-1$ copies of  
$U_{1,2}$, the
ground sets of the latter being all sets of the form $\{e,f\}$ such  
that $f \in
C - e$.
For all $i$ in $\{1,2,\dots,n\}$, let $N_i$ be a  matroid in  
${\mathcal Q}_i$
for which
\begin{equation}
\label{(2)}
c_e^*(N_i)=\min\{c_e^*(N):N\in{\mathcal Q}_i\}.
\end{equation}

On summing (\ref{(1)}) over all $f$ in $C-e$, we get
$$(|C|-1)c_e^*(M)\ge (|C|-1)+\sum_{f\in C-e}\sum_{N\in{\mathcal
P}_f}(c_e^*(N)-1).$$
Therefore
\begin{equation}
\label{(2.2)}
(|C|-1)c_e^*(M)\ge (|C|-1)+\left[(|C|-1) +  
\sum_{i=1}^n\sum_{N\in{\mathcal
Q}_i}(c_e^*(N)-1)\right],
\end{equation}
where the extra $(|C |-1)$-term appears because, for every $f$ in  
$C-e$, there
is a matroid belonging to ${\mathcal P}_f$ having ground set  
$\{e,f\}$ and this
matroid does not belong to any ${\mathcal Q}_i$. Hence
\begin{equation}
\label{(2.1)}(|C|-1)(c_e^*(M)-2)\ge \sum_{i=1}^n|{\mathcal  
Q}_i|(c_e^*(N_i)-1).
\end{equation}
As $|C| = c_e(M)$, it follows that
\begin{equation}
\label{(3)}
(c_e(M)-1)(c_e^*(M)-2)\ge\sum_{i=1}^n|{\mathcal Q}_i|(c_e^*(N_i)-1).
\end{equation}

Next we obtain, for each $i$ in $\{1,2,\ldots,n\}$, a lower bound  
on $|{\mathcal
Q}_i|$. Let $P_i$ be a subset of $E(M_i)$ such that $P_i \cup e$ is  
a circuit of
$N_i$ of size $c_e(N_i)$.  Thus
\begin{equation}
\label{(4)}
|P_i| = c_e(N_i)-1.
\end{equation}
Moreover, $P_i$ is a chord of $C$, so
 $C\cup P_i$ is a connected Tutte-line $L_i$ of $M$. Let
$\{P_i,L_{i1},L_{i2},\dots,L_{in_i}\}$ be the canonical partition  
of $L_i$.
Without loss of generality, we may assume that $e\in L_{in_i}$. For  
all  $j$ in
$\{1,2,\dots,n_i-1\}$, the set $L_i-L_{ij}$ is a circuit of $M$   
containing
$e$. Thus
$$|C|\ge|L_i-L_{ij}|=|L_i|-|L_{ij}|.$$
But $$|C|=|L_i-P_i|=|L_i|-|P_i|.$$
Hence
\begin{equation}
\label{(4.1)}
|P_i|\le\min\{|L_{ij}|: 1 \le j \le n_i - 1\}.
\end{equation}
For all  $f$ in $\bigcup_{j=1}^{n_i-1} L_{ij}$, since $M_i$ and  
$N_f$ are the
connected components of $M/C$ and $M/(C - \{e,f\})$, respectively,  
containing
$P_i$, we deduce that $E(M_i) \subseteq E(N_f)$ and therefore  
${\mathcal P}_f$
contains a member $N$ of ${\mathcal Q}_i$. Thus
\begin{equation}
\label{(4.2)}
|{\mathcal Q}_i|\ge\sum_{j=1}^{n_i-1}|L_{ij}|\ge(n_i-1)|P_i|,
\end{equation}
where the second inequality follows by (\ref{(4.1)}).
Moreover, since $C \cup P_i$ is a connected Tutte-line  of $M$ of  
size $n_i +
1$, we have $n_i + 1 \ge m$.  Hence, using (\ref{(4.2)}) and  
(\ref{(4)}), we
deduce that
\begin{equation}
\label{(5)}
|{\mathcal Q}_i|\ge(m-2)|P_i|=(m-2)(c_e(N_i)-1).
\end{equation}

On combining (\ref{(3)}) and (\ref{(5)}), we get
\begin{equation}
\label{(6)}
(c_e(M)-1)(c_e^*(M)-2)\ge\sum_{i=1}^n(m-2)(c_e(N_i)-1)(c_e^*(N_i)-1).
\end{equation}

As $2 \le |E(N_i)| < |E(M)|$, the theorem holds for $N_i$.  In  
particular, since
every connected Tutte-line of $N_i$ has size at least three, it  
follows that
$$|E(N_i)|\le  c_e(N_i)+(c_e(N_i)-1)(c_e^*(N_i)-2).$$
But $|E(M_i)| = |E(N_i)| -1$, so
\begin{equation}
\label{(7)}
|E(M_i)|\le  (c_e(N_i)-1)(c_e^*(N_i)-1).
\end{equation}
On combining (\ref{(6)}) and (\ref{(7)}), we get
\begin{eqnarray*}
(c_e(M)-1)(c_e^*(M)-2)&\ge&\sum_{i=1}^n(m-2)|E(M_i)|\\
&\ge&(m-2)\sum_{i=1}^n|E(M_i)|=(m-2)|E(M)-C|.\\
\end{eqnarray*}
Rewriting the last inequality, using the fact that $c_e(M) = |C|$,  
we obtain
$$|E(M)|\le c_e(M)+\frac{1}{m-2}(c_e(M)-1)(c_e^*(M)-2)$$
and the theorem follows by induction. \end{proof}



As an immediate consequence of Corollary~\ref{coline}, we have the  
following
result.



\begin{corollary}
\label{Theorem 5}
Let $M$ be a connected matroid such that $|E(M)|>1$.   Suppose that  
$m$ is an
integer exceeding two such that every coline of $M$ that is  
contained in more
than two hyperplanes is contained in at least $m$ hyperplanes.  Then
$$|E(M)|\le c^*(M)+\frac{1}{m-2}(c^*(M)-1)(c(M)-2).$$
\end{corollary}

The bound in the last inequality is sharp, it being attained for  
every $m \ge 3$
by $U_{n-m+2,n}$ provided $n \ge m-1$.

After the original submission of this paper, Guoli Ding (private  
communication)
gave a short proof of Theorem~\ref{Theorem 1}.  A straightforward  
modification
of his argument yields our second strengthening of  
Theorem~\ref{Theorem 1}. This
result answers a question of Paul Seymour (private communication).

\begin{theorem}
\label{Theorem_sey}
Let $M$ be a connected matroid with at least two elements and let  
$e$ be an
element of $M$.  Then there are $c_e(M)-1$ cocircuits of $M$ each  
containing $e$
such that the union of these cocircuits is $E(M)$.
\end{theorem}

\begin{proof} We argue by induction on $c_e(M)$. If $c_e(M)=2$,  
then $M$ is a
uniform matroid having rank one, so $E(M)$ is a cocircuit of $M$  
and the result
follows. Now suppose that the theorem holds for $c_e(M) < n$ and  
let $c_e(M)=n
\ge 3$.

Let $C^*$ be a cocircuit of $M$ that contains $e$. Clearly $C^*  
\neq E(M)$. By a
well-known result of Tutte \cite{wtt} (see also \cite[Theorem  
4.3.1]{oxbook}),
for every element $z$ of a connected matroid, the deletion or  
contraction of $z$
leaves a connected matroid. Thus there is a partition $\{X,Y\}$ of  
$C^* - e$
such that $M\backslash X/Y$ is a connected matroid; call it $N$.   
As every
circuit of $M$ that contains $e$ must also meet $X$ or $Y$, it  
follows that
$$c_e(N)<c_e(M).$$
Since $C^* \neq E(M)$, the matroid $N$ has at least two elements.  
Thus, by the
induction assumption, for some  $k\le c_e(N)-1$, there are $k$  
cocircuits
$C^*_1,C^*_2,\dots,C^*_k$ of $N$ each containing $e$ such that the  
union of
these cocircuits is $E(N)$. For each $C^*_i$, there is a cocircuit  
$D^*_i$ of
$M$ such that $C^*_i=D^*_i -X$. Hence $C^*,D^*_1,D^*_2,\dots,D^*_k$ are 
cocircuits of $M$ each containing $e$ and
$$E(M)=E(N)\cup X\cup Y\subseteq C^*_1\cup C^*_2\cup\cdots\cup C^*_k\cup 
C^*\subseteq D^*_1\cup D^*_2\cup \cdots\cup D^*_k\cup C^*.$$
Thus we have a family of $k+1$ cocircuits of $M$ that covers  
$E(M)$. Since
$$k+1\le (c_e(N)-1)+1=c_e(N) \le c_e(M)-1,$$
the result follows by induction.
\end{proof}

We observe, from the last proof, that the family of $c_e(M) - 1$  
cocircuits that
covers $E(M)$ can be required to include any arbitrarily chosen  
cocircuit of $M$
that contains $e$.



\section{Proof of Theorem~\ref{Theorem 7}}

In this section, we shall prove Theorem~\ref{Theorem 7}.  In addition to 
Theorem~\ref{Theorem 1}, the proof will use two lemmas and we begin  
the section
by proving them. For a circuit $C$ of a matroid $M$ such that $|C|  
\ge 2$, we
define
$$c^*(C,M)=\max\{|D^*|:D^*\in{\mathcal   C}(M^*)\hbox{ and  
}|D^*\cap C|=2\}.$$


\begin{lemma}
\label{Lemma 1}
Suppose that $M$ is a connected matroid having a circuit $C$ such  
that  every
connected component of $M/C$ is a circuit. If $|E(M)|>1$, then
$$|E(M)|\le  
|C|+c(M)\left\lceil\frac{c^*(C,M)-2}{2}\right\rceil.\eqno{(*)}$$
\end{lemma}


\begin{proof} Suppose that $(*)$ is false and choose a  
counterexample $M$ such
that $|E(M)|$ is minimum. Observe that $E(M)\not=C$, otherwise  
$(*)$ holds.
Suppose that $M/e$ is connected  for some $e$ in $C$. Observe that  
$|E(M/e)|>1$
because $E(M)\not=C$. As $M/C=(M/e)/(C - e)$, it follows that the  
result holds
for the pair $(M/e,C - e)$, by the choice of $(M,C)$. In particular,
$$|E(M/e)|\le |C - e|+c(M/e)\left\lceil\frac{c^*(C -  
e,M/e)-2}{2}\right\rceil.$$
Observe that $c(M/e)\le c(M)$ and $c^*(C - e,M/e)\le c^*(C,M)$. Hence
$$|E(M)|-1\le |C|-1+c(M)\left\lceil\frac{c^*(C,M)-2}{2}\right\rceil$$
and we obtain the contradiction that $(*)$ holds for $M$. Thus $M/e$ is 
disconnected for every $e$ in $C$.

For all $e$ in $C$, let $P_e$ be a chord of $C$ such that $P_e$ is  
the ground
set of a connected component of $M/e$. If possible, choose the  
chords $P_e$ such
that $P_a\not=P_b$ for every 2-element subset $\{a,b\}$ of $C$.  
Suppose that
this choice is impossible. Then  $P_a=P_b$ for some distinct $a$  
and $b$ in $C$.
Therefore both $P_a \cup a$ and $P_a \cup b$ are circuits of $M$.   
Thus if $x
\in P_a$, then $M$ has a circuit contained in $(P_a - x) \cup  
\{a,b\}$.  Suppose
that $\{a,b\}$ is a proper subset of $C$.  Then, since $P_a - x$ is  
independent
in $M/C$, it follows that $(P_a - x) \cup \{a,b\}$ is independent  
in $M$; a
contradiction.  We conclude that
$C=\{a,b\}$. Moreover, since, by hypothesis, $P_a$ and $P_b$ cannot  
be chosen to
be different, $M$ is the cycle matroid of the graph consisting of  
two vertices
that are joined by $a$, $b$, and a path with edge set $P_a$. Thus
$$|E(M)|=|C|+|P_a| = 2 + |P_a|,$$
$c^*(C,M)=3$, and $c(M) = |P_a| + 1.$  Therefore
$$|C| + c(M)\left\lceil\frac{c^*(C,M)-2}{2}\right\rceil= 2 + c(M)=  
3 + |P_a|$$
and we obtain the  contradiction that $(*)$ holds for $M$.

We now know that if $a$ and $b$ are distinct elements of $C$, then
$P_a\not=P_b$. It follows that $M|[C \cup (\bigcup_{e\in C} P_e)]$  
is the cycle
matroid of the graph that can be obtained from a cycle with edge  
set $C$ by
adding an edge $e'$ in parallel with each edge $e$ and then  
subdividing $e'$ to
produce a path with edge set $P_e$.  Hence if $C' = \bigcup_{e\in  
C} P_e$, then
$C'$ is a circuit of $M$, so
\begin{equation}
\label{new1}
|C'|\le c(M).
\end{equation}
Moreover, $M\backslash C'$ is connected. Now, suppose that $D^*$ is  
a cocircuit
of $M$ such that $|D^*\cap C|=2$, say $D^*\cap C=\{a,b\}$. Observe  
that $D^*$
must intersect $P_a$ and $P_b$ because $P_a\cup a$ and $P_b\cup b$  
are circuits
of $M$. Thus
\begin{equation}
\label{new2}
c^*(C,M\backslash C')\le c^*(C,M)-2.
\end{equation}
By the choice of $M$, inequality $(*)$ holds for the pair  
$(M\backslash C',C)$,
that is,
$$|E(M\backslash C')|\le |C|+c(M\backslash  
C')\left\lceil\frac{c^*(C,M\backslash
C')-2}{2}\right\rceil.$$
As $c(M\backslash C')\le c(M)$, it follows using (\ref{new2}) that
$$|E(M)|-|C'|\le |C|+c(M)\left\lceil\frac{c^*(C,M)-4}{2}\right\rceil.$$
Hence
\begin{eqnarray*}
|E(M)|&\le&|C|+c(M)\left\lceil\frac{c^*(C,M)-2}{2}\right\rceil+|C'|-c(M)\\
&\le&|C|+c(M)\left\lceil\frac{c^*(C,M)-2}{2}\right\rceil.\\
\end{eqnarray*}
The last inequality, which holds by (\ref{new1}), gives the  
contradiction that
the lemma holds for $M$. \end{proof}



\begin{lemma}
\label{Lemma 2}
Suppose that $M$ is a connected matroid such that $|E(M)|>1$. If  
$C$ is a
circuit of $M$ such that $|C|=c(M)$, then
$$|E(M)|\le c(M)\left\lceil\frac{c^*(C,M)}{2}\right\rceil.\eqno{(**)}$$
\end{lemma}

\begin{proof} Let $M_1,M_2,\dots,M_n$ be the connected components  
of $M/C$.
Suppose that $(**)$ is false and choose a counterexample $M$ in  
which the number
of $M_i$ that are not circuits is a minimum. This number is  
non-zero,  otherwise
we get a contradiction to Lemma~\ref{Lemma 1}.  In particular,  
$E(M)\not=C$ and
we may assume that $M_1$ is not a circuit.

Let $P$ be a chord of $C$ that is contained in $E(M_1)$. Fix a  
circuit $C_1$ of
$M|(C\cup P)$ such that $C_1-C=P$. Observe that, since $P$ is a  
series class of
$M|(C\cup P)$, this matroid has a circuit $D_1$ containing $P \cup  
(C - C_1)$.
Then $|C_1| + |D_1| \le 2|C|.$  Moreover,
$|C_1| = |P| + |C \cap C_1|$ and $|D_1| \ge |P| + |C - C_1|$.  
Therefore$$|P| +
|C \cap C_1| + |P| + |C-C_1| \le |C_1| + |D_1| \le 2|C|,$$
that is, $2|P| + |C| \le 2|C|$, so
\begin{equation}
\label{(1')}
2|P| \le |C|.
\end{equation}

By definition,
$P$ is a circuit of the component $M_1$ of $M/C$.  Thus $P$ is a  
series class of
$(M/C)\backslash (E(M_1) - P)$. Hence
\begin{equation}
\label{(2')}
\hbox{$P$ is a series class of $M\backslash (E(M_1)-P)$.}
\end{equation}

For each 2-element subset $\{x,y\}$ of $C$, let $N_{xy}$ be the  
component of
$M/(C-\{x,y\})$ that contains $\{x,y\}$. Choose a 2-element subset  
$\{a,b\}$ of
$C$ such that $E(M_1)$ is contained in $E(N_{ab})$.  Then $M_1$ is  
a connected
component of $N_{ab}/a$.  Thus $N_{ab}$ can be decomposed as the  
parallel
connection of two matroids across $a$ such that, for one of these  
matroids,
$N_1$, we have $N_1/a = M_1$.
Among the 2-element subsets $\{a,b\}$ of $C$ for which $E(M_1) \subseteq 
E(N_{ab})$, choose one   such that
\begin{equation}
\label{(3')}
\hbox{$c_a^*(N_1)-1$ is a minimum.}
\end{equation}
Let $P_1$ be a chord of $C$ contained in $E(M_1)$ such that
 $|P_1|=c_a(N_1)-1$. By Theorem~\ref{Theorem 1}, we have that
\begin{equation}
\label{(4')}
|E(M_1)|=|E(N_1)|-1\le (c_{a}(N_1)-1)(c_a^*(N_1)-1).
\end{equation}

Now $M_1$ is not a circuit. By (\ref{(2')}), $P_1$ is a series class of 
$M\backslash (E(M_1)-P_1)$. Thus  $M\backslash (E(M_1)-P_1)$ is the  
2-sum, with
basepoint $p$, of a circuit with ground set $P_1 \cup p$ and a  
matroid $M'_1$
with ground set $(E(M) - E(M_1)) \cup p.$ We construct a new  
matroid $M'$ from
$M\backslash (E(M_1)-P_1)$ by placing $c_a^*(N_1)-2$ series classes  
 ``in
parallel'' with $P_1$, with each such series class having exactly  
$|P_1|$
elements. More formally, take $c_a^*(N_1)-2$ disjoint subsets of  
size $|P_1|$,
each disjoint from $E(M)$, and, for each such subset $X$, take a  
circuit with
ground set $X \cup p$. Then $M'$ is obtained by deleting $p$ from  
the parallel
connection, with basepoint $p$, of the collection of matroids  
consisting of all
these circuits, the circuit with ground set $P_1 \cup p$, and the  
matroid
$M'_1$. For each 2-element subset $\{x,y\}$ of $C$, let $N'_{xy}$ be the 
component of $M'/(C-\{x,y\})$ that contains $\{x,y\}$.  Then  
$E(N'_{ab})$
contains $P_1$.  Moreover, $N'_{ab}$ can be obtained from $N_{ab}$  
by replacing
$N_1$ by the parallel connection, with basepoint $a$, of $c_a^*(N_1)-1$ 
circuits, each having exactly $|P_1| + 1$ elements.  Thus
$$|E(M')|= |E(M)| - |E(N_1)| +|P_1|(c_a^*(N_1)-1) + 1.$$
Since $|P_1| = c_a(N_1)-1$ and $|E(M_1)| = |E(N_1)| - 1$, we deduce 
that$$|E(M')|- |E(M)| = (c_a(N_1)-1)(c_a^*(N_1)-1) - |E(M_1)|.$$
Therefore, by (\ref{(4')})   , $|E(M')|\ge|E(M)|$. Since $M'/C$ has  
fewer
components that are not circuits than does $M/C$, it will follow  
that $(**)$
holds for the pair $(M',C)$, provided we can show that
\begin{equation}
\label{(5')}
|C| = c(M').
\end{equation}
The proof of the lemma will be completed by proving this together  
with the
inequality
\begin{equation}
\label{(6')}
c^*(C,M')\le c^*(C,M).
\end{equation}


Suppose that $c(M')>|C|$. Then $M'$ has a circuit $C'$ such that  
$|C'|>|C|$.
Certainly  $C'$ meets $E(M')-E(M)$, otherwise $C'$ is a circuit of  
$M$; a
contradiction. If $C'\subseteq E(M')-E(M)$, then $C'$ is the union  
of two series
class of $M'$ each of which is contained in $E(M')-E(M)$ and has $|P_1|$ 
elements. Thus
$$|C'|=2|P_1|\le |C|$$
where the last inequality follows by (\ref{(1')})   . This  
contradiction implies
that $C'$ meets both $E(M')-E(M)$ and $E(M)\cap E(M')$. Thus $C'$  
contains a
series class $P'$ of $M'$ that is contained in $E(M')-E(M)$. Hence  
$(C'-P')\cup
P_1$ is also a circuit of $M'$ having the same cardinality as $C'$.  
This is a
contradiction because this circuit is also a circuit of $M$. Thus  
(\ref{(5')})
 holds.

Next we prove (\ref{(6')}). Suppose that $c^*(C,M')>c^*(C,M)$. Then  
there is a
2-element subset $\{g,h\}$ of $C$ such that
$$c_{gh}^*(C,M')>c_{gh}^*(C,M),$$
where
$$c_{gh}^*(C,M)=\max\{|D^*|:D^*\in{\mathcal   C}(M^*)\hbox{ and }D^*\cap 
C=\{g,h\}\}.$$
Then certainly $N_{gh} \neq N'_{gh}.$ Moreover, if $E(M_1)$ avoids  
$E(N_{gh})$,
then $M_1$ is a component of $M/(C-\{g,h\})$ and so $N_{gh} =  
N'_{gh}$; a
contradiction.  Thus
$E(M_1)$ meets, and so is contained in, $E(N_{gh})$. Hence $P_1$ is  
contained in
$E(N_{gh})$.

Each of $N_{gh}$ and $N'_{gh}$ can be obtained as a parallel  
connection across
$g$ of a certain set of matroids. For $N_{gh}$, this set ${\mathcal  
S}_g$
includes a matroid $N''_1$ for which $N''_1/g = M_1$. The set  
${\mathcal S}'_g$
for $N'_{gh}$ must contain ${\mathcal S}_g - \{N''_1\}$.

We show next that $P_1 \cup g$ is a circuit of $N''_1$.  Suppose  
not.  Then
$P_1$ is a circuit of $M/(C - \{g,h\})$ and hence of  $M'/(C -  
\{g,h\})$.  It
follows from the construction of $M'$ that $P_1$ is a component of  
$M'/(C -
\{g,h\})$ and that the elements of $E(M') - E(M)$ are partitioned into 
$c^*_a(N_1) - 2$ sets each a $|P_1|$-circuit that is a component of  
$M'/(C -
\{g,h\})$.  Thus  ${\mathcal S}'_g = {\mathcal S}_g - \{N''_1\}$ and so
 $c_{gh}^*(C,M')\le c_{gh}^*(C,M)$; a contradiction. Thus $P_1 \cup  
g$ is indeed
a circuit of $N''_1$.

The construction of $M'$ now implies that ${\mathcal S}'_g$ is  
obtained from
${\mathcal S}_g - \{N''_1\}$
 by adjoining $c_a^*(N_1)-1$ circuits, each of size $|P_1| + 1$. Thus
$$c_{gh}^*(C,M')-c_{gh}^*(C,M)=(c_a^*(N_1)-1)-(c_g^*(N''_1)-1).$$
But, by the choice of $N_1$, the right-hand side of this equation is not 
positive.  Hence $c_{gh}^*(C,M') \le c_{gh}^*(C,M)$; a  
contradiction.  We
conclude that  (\ref{(6')})    holds.

Since $(**)$ holds for $M'$ and $c(M) = |C| = c(M')$,
$$|E(M')|\le c(M)\left\lceil\frac{c^*(C,M')}{2}\right\rceil.$$
But $|E(M)| \le |E(M')|$ and $c^*(C,M')\le c^*(C,M).$
Hence
$$|E(M)|\le c(M)\left\lceil\frac{c^*(C,M)}{2}\right\rceil;$$
 a contradiction. \end{proof}

We are now ready to prove the main result of the paper.

\begin{proof}[Proof of Theorem~\ref{Theorem 7}.]
 Evidently, it suffices to prove that
$$|E(M)|\le\frac{c(M)c^*(M)}{2}.$$
We shall first prove this
 when $c^*(M)$ is even. By Lemma~\ref{Lemma 2},
$$|E(M)|\le c(M)\left\lceil\frac{c^*(C,M)}{2}\right\rceil,$$
for any circuit $C$ of $M$ such that $|C|=c(M)$. As $c^*(C,M)\le  
c^*(M)$, it
follows that
$$|E(M)|\le c(M)\left\lceil\frac{c^*(C,M)}{2}\right\rceil\le
c(M)\left\lceil\frac{c^*(M)}{2}\right\rceil=\frac{c(M)c^*(M)}{2},$$
where the last equality follows since $c^*(M)$ is an even integer.

When $c^*(M)$ is odd, let $M'$ be the matroid obtained from $M$ by  
inserting an
element in parallel with each element of the latter. Then  
$c^*(M')=2c^*(M)$.
Thus $c^*(M')$ is even and hence
$$|E(M')|\le\frac{c(M')c^*(M')}{2}.$$
As $|E(M')|=2|E(M)|$ and $c(M')=c(M)$, we get
$$2|E(M)|\le c(M)c^*(M)$$
and the result follows. \end{proof}

Reid \cite{tjr} noted that the matroid Ramsey numbers have the property 
that\linebreak $n(1,1) =1$ and  $n(s,t) = 2$ if $s$ or $t$ is in  
$\{1,2\}$
provided $(s,t) \neq (1,1)$. As a consequence of the last theorem,  
we can
determine $n(s,t)$ for all other pairs $(s,t)$. Before this result,  
for $s \le
t$, the Ramsey number with $s$ largest for which the exact value  
was known was
$n(6,6)$, which Bonin, McNulty, and Reid \cite{bmr} showed was  
equal to 13.

\begin{corollary}
\label{Corollary 8} For all integers $s$ and $t$ exceeding two,
$$n(s,t) = \left\lfloor\frac{(s-1)(t-1)}{2}\right\rfloor + 1.$$
\end{corollary}


\begin{proof}
 It follows immediately from Theorem~\ref{Theorem 7} that
$$n(s,t) \le \left\lfloor\frac{(s-1)(t-1)}{2}\right\rfloor + 1.$$
We shall show that equality holds here by giving, for all $s$ and  
$t$ exceeding
two, an example of a connected matroid $M$ with $c(M) = s-1$,  
$c^*(M) = t-1$,
and
$$|E(M)| = \left\lfloor\frac{(s-1)(t-1)}{2}\right\rfloor.$$
In each case, the matroid $M$ will be the cycle matroid of a graph  
$G$. If $t$
is odd, let $G$ be obtained from a cycle with $s-1$ edges by  
replacing each edge
by $\frac{t-1}{2}$ edges in parallel. If $s$ is odd, let $G$  
consist of two
vertices joined by $t-1$ internally disjoint paths each of length
$\frac{s-1}{2}$. Finally, if $s$ and $t$ are both even, let $G$ be  
constructed
by joining two vertices  by  three internally  disjoint paths, of  
lengths
$\frac{s-2}{2}$, $\frac{s-2}{2}$,  $\frac{s}{2}$,  and then  
replacing each edge
of the first and last paths by $\frac{t-2}{2}$ edges in parallel.  
\end{proof}



\section{The matroids attaining the bound of Theorem~\ref{Theorem 1}}

In this section, we characterize the matroids for which equality  
holds in  the
bound in Theorem~\ref{Theorem 1}.  In addition, we relate this  
class of matroids
to the graphs  that attain  the bound in Theorem~\ref{pwu}. We denote by 
${\mathcal B}_3$ the class of matroids that   attain the bound in
Theorem~\ref{Theorem 1}, that is, those matroids $M$ that have an  
element $e$
for which
$$|E(M)|=c_e(M)+(c_e(M)-1)(c_e^*(M)-2).$$
It is straightforward to check  that ${\mathcal   B}_3$ is closed  
under duality
and that every circuit with at least two elements including $e$  
belongs to
${\mathcal   B}_3$. In the next lemma, we shall prove that  
${\mathcal   B}_3$ is
closed under series connection, provided some conditions are  
satisfied. A
matroid $M$ is  {\it uniform with respect to} an element $f$ if  
every circuit
containing $f$ has the same cardinality $d$ and every cocircuit  
containing $f$
has the same cardinality $d^*$.
A matroid $M$ is a {\it uniform series connection} of $k$ matroids
$M_1,M_2,\dots,M_k$ for some $k \ge 2$ if the following hold:
\begin{noname}
\label{ser_def}
\begin{enumerate}
\item[(i)] $M_1,M_2,\dots,M_k$ are connected matroids each having  
at least two
elements;
\item[(ii)] $E(M_i)\cap E(M_j)=\{e\}$ for every $2$-subset $\{i,j\}$ of 
$\{1,2,\dots,k\}$;
\item[(iii)] $c_e^*(M_1)=c_e^*(M_2)=\cdots=c_e^*(M_k)$;
\item[(iv)] $M_1,M_2,\dots,M_k$ are uniform with respect to $e$; and
\item[(v)] $M$ is $S(M_1,M_2,\dots,M_k)$, the series connection  
with basepoint
$e$ of $M_1,\linebreak M_2,\dots,M_k$.
\end{enumerate}
\end{noname}




\begin{lemma}
\label{Lemma_eq1}
Let $M_1,M_2,\dots,M_k$ be matroids satisfying  
(\ref{ser_def})(i)--(ii).  Let
$M=\linebreak S(M_1,M_2,\dots,M_k)$. Then $M\in{\mathcal   B}_3$ if  
and only if
all of $M_1,M_2,\dots,M_k$ are in ${\mathcal   B}_3$ and  
(\ref{ser_def})(iii)
holds.
Moreover, $M$ is uniform with respect to $e$ if and only if  
(\ref{ser_def})(iii)
and (\ref{ser_def})(iv) hold.
\end{lemma}

\begin{proof}
Clearly
$$|E(M)| = 1+\sum_{i=1}^k(|E(M_i)|-1).$$
Thus, by applying Theorem~\ref{Theorem 1} to each $M_i$, we get
\begin{eqnarray*}
|E(M)|&\le&1+\sum_{i=1}^k\bigl[c_e(M_i)-1+(c_e(M_i)-1)(c_e^*(M_i)-2)\bigr]\\
&=&1+\sum_{i=1}^k(c_e(M_i)-1)+\sum_{i=1}^k(c_e(M_i)-1)(c_e^*(M_i)-2)\\
&\le&c_e(M)+\max\{c_e^*(M_i)-2:1\le i\le  
k\}\sum_{i=1}^k(c_e(M_i)-1)\\
&=&c_e(M)+\max\{c_e^*(M_i)-2:1\le i\le k\}(c_e(M)-1)\\
&=&c_e(M)+(c_e^*(M)-2)(c_e(M)-1).\\
\end{eqnarray*}
Thus $M\in{\mathcal   B}_3$ if and only if  equality occurs  
throughout the
above, that is, if and only if $M_1,M_2,\dots,M_k$ are all in  
${\mathcal
B}_3$,  and
$$c_e^*(M_1)=c_e^*(M_2)=\cdots=c_e^*(M_k).$$
Hence the first part of the lemma holds.  The second part follows
straightforwardly from the definition of series connection. \end{proof}


The proof of the characterization of the matroids attaining equality in 
Theorem~\ref{Theorem 1} will use two results of Seymour~\cite{sey}.  
 Because the
terminology of that paper is different from that used here, we have  
translated
Seymour's results into our terminology.  The first result is  
\cite[(3.7)]{sey},
restated in the special case that $Z$ is a circuit.

\begin{lemma}
\label{sey1}
Let $e$ be an element of  a circuit $C$  of a connected matroid $M$. If 
$M\backslash e$ is connected, then there is no partition  
$\{X_1,X_2\}$  of $E(M)
- e$ such that
\begin{enumerate}
\item[(i)] no chord of $C$ meets both $X_1$ and $X_2$; and
\item[(ii)] for each $i$ in $\{1,2\}$, if $P$ is a chord of $C$  
contained in
$X_i$, then $X_i$ contains a circuit containing $P$.
\end{enumerate}
\end{lemma}

The second lemma is a restatement of a special case of \cite[(3.8)]{sey}.

\begin{lemma}
\label{sey2}
Let $C$ and $D$ be  circuits of a  matroid $M$ such that $C \cap D  
= \{e\}$  and
$(C \cup D) - e$ is also a circuit of $M$.  Then either $(C \cup D)  
- e$ has a
chord $A$ that is different from $\{e\}$ and is not a chord of $C$  
or of $D$, or
there is a partition $\{X_1,X_2\}$ of $E(M\ba e)$ such that $X_1  
\supseteq C-e$
and $X_2 \supseteq D-e$, and
$$r(X_1) + r(X_2) - r(M\backslash e) = r(C - e) + r(D - e) - r((C  
\cup D) -
e)=1.$$
\end{lemma}



\begin{theorem}
\label{Theorem 2}
${\mathcal   B}_3$ is the minimal class ${\mathcal M}$ of matroids  
with the
following properties.
\begin{enumerate}
\item[(i)] Every circuit that contains $e$ and has at least two  
elements is in
${\mathcal M}$.
\item[(ii)] The dual of every member of ${\mathcal M}$ is in   
${\mathcal M}$.
\item[(iii)] The uniform series connection of a collection of members of 
${\mathcal M}$ is in ${\mathcal M}$.
\end{enumerate}
\end{theorem}


\begin{proof}
We noted above that ${\mathcal   B}_3$ contains all circuits with  
at least two
elements including $e$  and that ${\mathcal   B}_3$ is closed under  
both duality
and uniform series connection.  The proof will be completed by  
proving the
following, where the superfluous strength of the assertion will  
facilitate the
argument.

\begin{sublemma}
\label{A0}
If $M \in {\mathcal   B}_3$, then $M$ is  uniform with respect to  
$e$, and $M$
or its dual is a circuit or is a uniform series connection of a  
collection of
matroids in ${\mathcal   B}_3$.
\end{sublemma}

We shall argue by induction on $|E(M)|$ noting that the assertion  
holds when $M$
is a circuit. Thus we may assume that $M$ is not a circuit.


We shall use the same notation as in the proof of  
Theorem~\ref{Theorem 4} taking
$m = 3$. When a matroid attains equality in the bound in  
Theorem~\ref{Theorem
1},  equality must hold in all the inequalities that appear in the  
proof of
Theorem~\ref{Theorem 4}.

First, observe that, to achieve equality in (\ref{(2.1)}), we must  
have that,
for all $i$ in $\{1,2,\ldots,n\}$,
$$c_e^*(N_i)=c_e^*(N)$$
for every $N$ in ${\mathcal   Q}_i$. Thus $N_i$ can  be chosen  
arbitrarily in
${\mathcal   Q}_i$.

Equality must also hold in (\ref{(4.1)}), that is,
$$|P_i| = \min\{|L_{ij}|:1\le j\le n_i-1\},$$
so, for all $j$ in $\{1,2,\dots,n_i-1\}$,
\begin{equation}
\label{(7.05)}
|L_{ij}|=|P_i|.
\end{equation}


Since  equality must hold in (\ref{(4.2)}) and (\ref{(5)}), we   
have that, for
all $i$ in $\{1,2,\ldots,n\}$,
$$(n_i-1)|P_i| = |{\mathcal   Q}_i| = |P_i|.$$
Thus, for all such $i$,
\begin{equation}
\label{(7.1)}
n_i=2.
\end{equation}
As any $N$ in ${\mathcal   Q}_i$ can be taken to be $N_i$, and  
since equality
holds in (\ref{(7)}), we have that, for all $N$ in ${\mathcal   Q}_i$,
$$c_e(N)-1=\frac{|E(M_i)|}{c_e^*(N)-1}=\frac{|E(M_i)|}{c_e^*(N_i)-1}=c_e(N_i)-1.
$$
Hence
\begin{equation}
\label{(8)}
c_e(N_i)=c_e(N)
\end{equation}
for every $N$ in ${\mathcal   Q}_i$.

Again, since  equality holds in (\ref{(7)}),
$$|E(M_i)|=|E(N_i)|-1=(c_e(N_i)-1)(c_e^*(N_i)-1),$$
and so $N_i\in{\mathcal   B}_3$. Thus, by the induction assumption,  
we deduce
the following:
\begin{sublemma}
\label{A.5}
For all  $i$ in $\{1,2,\dots,n\}$, the matroid $N_i$ is  uniform  
with respect to
$e$.
\end{sublemma}

Next we observe that the chords of $C$ have the following property.
\begin{sublemma}
\label{A1}
For all  $i$ in $\{1,2,\dots,n\}$, every chord of $C$ contained in  
$E(M_i)$ has
cardinality equal to $|P_i|$.
\end{sublemma}

To see this, we note that, for such a chord $P$, the set $P \cup e$  
is a circuit
of $N$ for some $N$ in ${\mathcal   Q}_i$. As this $N$ can be taken  
to be $N_i$,
the assertion follows from (\ref{(4)}) and (\ref{(8)}) because  
$|P_i| = c_e(N_i)
- 1$ and $N_i$ is uniform with respect to $e$.

Next we show the following:
\begin{sublemma}
\label{A2}
Suppose $i\in\{1,2,\dots,n\}$. Let $P'_i$ be a chord of $C$ contained in 
$E(M_i)$ and let $C_i$ and $C'_i$ be the unique circuits of $M|(C  
\cup P_i)$ and
$M|(C \cup P'_i)$, respectively, that avoid $e$.  Then
$$C_i \cap C = L_{i1} = C'_i \cap C.$$
\end{sublemma}


By definition, ${\mathcal   Q}_i = \bigcup_{f \in C-e}\{N \in  
{\mathcal P}_f:
N/e = M_i\}.$ Also $|\{N \in {\mathcal P}_f: N/e = M_i\}|$ is $0$  
or $1$ for all
$f$ in $C - e$ and, by (\ref{(7.1)}), $n_i = 2$.  Therefore,  from  
the paragraph
between (\ref{(4.1)}) and (\ref{(4.2)}), we have that, for all $f$  
in $L_{i1}$,
there is a matroid $N$ in  ${\mathcal P}_f$  such that $N/e = M_i$.  Thus
\begin{eqnarray*}
|{\mathcal   Q}_i|& = &\hbox{$|\{f \in C-e: {\mathcal P}_f$  
contains a matroid
$N$ such that $N/e = M_i\}|$}\\
& \ge & |L_{i1}|.
\end{eqnarray*}
But equality holds in (\ref{(4.2)}) and therefore holds in the  
above.  Hence, as
$L_{i1} = C_i \cap C$, we have
\begin{equation}
\label{(9)}
\hbox{$C_i\cap C =\{f \in C-e: {\mathcal P}_f$ contains a matroid  
$N$ such that
$N/e = M_i\}$}.
\end{equation}

By (\ref{A1}), $|P'_i| = |P_i|$ and so $P'_i$ can be used in place  
of $P_i$
throughout the proof of Theorem~\ref{Theorem 4} and in the above.  
In particular,
$$C'_i\cap C =\{f \in C-e: {\mathcal P}_f \hbox{ contains a matroid  
$N$ such
that } N/e = M_i\}.$$
We conclude that
$$C_i \cap C = C'_i \cap C,$$
that is, (\ref{A2}) holds.

On combining (\ref{A2}) and (\ref{(7.05)}), we get that
\begin{equation}
\label{(10)}
|C_i \cap C| = |P_i|.
\end{equation}

We now show that two sets $C_i \cap C$ and $C_j \cap C$ are either  
disjoint or
are comparable.

\begin{sublemma}
\label{A3}
If $i$ and $j$ are distinct elements of $\{1,2,\dots,n\}$, then
\begin{enumerate}
\item[(i)] $C_i\cap C_j=\emptyset$; or
\item[(ii)] $C_i\cap C \subseteq C_j\cap C$; or
\item[(iii)] $C_j\cap C \subseteq C_i\cap C$.
\end{enumerate}
\end{sublemma}

By (\ref{(7.1)}), $n_i=n_j=2$. Thus each of the Tutte-lines $C \cup  
P_i$ and $C
\cup P_j$ has size three, so the matroids  $M|(C \cup P_i)$ and  
$M|(C \cup P_j)$
are binary.  It is a straightforward consequence of a result of
Lemos~\cite[(3.1)]{lem} that $M|(C \cup P_i \cup P_j)$ is also  
binary.  Assume
that none of (i)--(iii) holds.  Then $M|(C \cup P_i \cup P_j)$ is  
the cycle
matroid of the graph obtained from a cycle $C$ by adding two  
disjoint paths
$P_i$ and $P_j$ each with both endpoints on $C$ such that the  
resulting graph is
a subdivision of $K_4$.
Let $C' = P_i \cup P_j \cup (C_i \cap C_j \cap C) \cup (C - (C_i  
\cup C_j)).$
 Then $C'$ is a circuit of $M$ containing $e$ and
$$|C'|=|P_i|+|P_j|+|C_i\cap C_j\cap C|+|C-(C_i\cup C_j)|.$$
Thus, by (\ref{(10)}) and the fact that $\{C_i\cap C_j\cap C,  
C-(C_i\cup C_j),
(C_i\cap C) -  C_j, (C_j\cap C) -  C_i\}$ is a partition of $C$, we  
deduce that
$$|C'|=|C_i\cap C|+|C_j\cap C|+|C| - |(C_i\cap C) -  C_j| -  
|(C_j\cap C) -
C_i|.$$
As $C_i \cap C$ properly contains $(C_i\cap C) -  C_j$, and $C_j \cap C$ 
properly contains $(C_j\cap C) -  C_i$, we deduce that $|C'| > |C|$; a 
contradiction.  We conclude that (\ref{A3}) holds.

Let $Q_1,Q_2,\dots,Q_k$ be the distinct maximal sets in the family  
$\{C_i\cap
C:1\le i\le n\}$. Then, by (\ref{A3}), $Q_i\cap Q_j=\emptyset$ for all 
$2$-element subsets  $\{i,j\}$  of $\{1,2,\dots,k\}$. For each $j$ in  
$\{1,2,\dots,k\}$, let $Q'_j$ be the union of all $E(M_i)$ for  
which $C_i \cap C
\subseteq Q_j$.  Then   $\{Q'_1,Q'_2,\dots,Q'_k\}$ is a partition  
of $E(M) - C$.
 Letting $X_1 = Q_1 \cup Q'_1$ and $X_2 = E(M\ba e) - (Q_1 \cup  
Q'_1)$, we
deduce from Lemma~\ref{sey1} that either (a)  $M\ba e$ is  
disconnected, or (b)
$X_2$ is empty.  In the first case, $M$ is a series connection with  
basepoint
$e$ of a set of connected matroids each having at least two  
elements.  Since $M
\in {\mathcal B}_3$, it follows by Lemma~\ref{Lemma_eq1} and the  
induction
assumption that $M$ satisfies (\ref{A0}).  Thus we may assume that  
(ii) holds.
Hence
\begin{equation}
\label{(12)}
\hbox{$k =1$ and $Q_1 = C-e.$}
\end{equation}
Moreover, for some $i$ in $\{1,2,\ldots,n\}$, we have $Q_1 = C_i  
\cap C$, and,
by (\ref{(10)}), $|C_i \cap C| = |P_i|.$  Hence $|P_i| = |C| - 1$  
and so,
letting $D = P_i \cup e$, we have that $D$ is a circuit of $M$  
containing $e$
and having cardinality $|C|$, and $C \cup D$ is a Tutte-line of  
size three for
which the canonical partition is $\{\{e\}, C - e, D-e\}$.  Thus $(C  
\cup D) - e$
is a circuit of $M$.

Next we shall prove the following:
\begin{sublemma}
\label{A4}
Let $A$ be a chord of $(C \cup D) - e$.  Then $A = \{e\}$, or $A$  
is a chord of
$C$ or $D$.
\end{sublemma}

Suppose that $A \neq \{e\}$ and let $W=M|(C\cup D\cup A)$.
The proof of (\ref{A4}) will be broken into several steps the first  
of which is
as follows.

\begin{sublemma}
\label{A4.1}
 If $D_1$ and $D_2$ are circuits of $W$ and $e\in D_1\cap D_2$,  
then $D_1\cup
D_2$ is a proper subset of $E(W)$.
\end{sublemma}

Suppose that $E(W)= D_1\cup D_2$. Then
$$|D_1\cup D_2|=|E(W)|=|C\cup D\cup  
A|=|C|+|D-e|+|A|=2|C|-|\{e\}|+|A|\ge 2|C|.$$
As $e\in D_1\cap D_2$, it follows that $|D_1\cap D_2|\ge 1$. Thus
$$|D_1|+|D_2|=|D_1\cup D_2|+|D_1\cap D_2|\ge 2|C|+1.$$
Therefore $|D_1|>|C|$ or $|D_2|>|C|$. This is a contradiction because 
$|C|=c_e(M)$ and $e\in D_1\cap D_2$. We conclude that (\ref{A4.1}) holds.


Now consider $W^*$, which has rank three since  $W$ has corank   
three. Recall
that the {\it points} and {\it lines} of a matroid are its rank-1  
and rank-2
flats.

\begin{sublemma}
\label{A4.2}
$W^*$ has the following properties:
\begin{enumerate}
\item[(i)] $\{e\}$ and $A$ are points of $W^*$.
\item[(ii)] If $L_1$ and $L_2$ are lines of $W^*$ such that  
$e\not\in L_1\cup
L_2$, then $L_1\cap L_2\not=\emptyset$.
\item[(iii)] There are exactly three lines in $W^*$ that contain $A$.
\item[(iv)] The line which contains $e$ and $A$ does not contain  
another point.
\end{enumerate}
\end{sublemma}

Part (i) holds because  $\{e\}$ and $A$ are series classes of $W$.  
Part (ii)
follows immediately from (\ref{A4.1}) by duality. Parts (iii) and  
(iv) hold
because $E(W)-A$ contains exactly three circuits, and because  
$E(W)-(A\cup e)$
is the circuit $(C \cup D) - e$ of $W$. Thus (\ref{A4.2}) holds.


By (\ref{A4.2})(iii), $W^*$ has exactly three lines, say $L_1,L_2$,  
and $L_3$,
that contain $A$. By (\ref{A4.2})(iv), we may suppose that $L_1=A  
\cup e$. Next
we establish the following:


\begin{sublemma}
\label{A4.3}
$L_2$ or $L_3$ contains just one point different from $A$.
\end{sublemma}


For each $i$ in $\{2,3\}$, let $p_{i1}$ and $p_{i2}$ be distinct points 
contained in $L_i - A$. For each $j$ and $k$ in $\{1,2\}$, let  
$K_{jk}$ be the
line of $W^*$ that contains $p_{2j}$ and $p_{3k}$. Suppose that,  
for some
$i,j,k,$ and $l$ in $\{1,2\}$ such that $i \neq k$ and $j \neq l$,  
we have $e
\not \in K_{ij}\cup K_{kl}$. Then, by (\ref{A4.2})(ii),    
$K_{ij}\cap K_{kl} =
\{p\}$ for some point $p$. Clearly $p$ is not on $L_2$ or $L_3$ and, by 
(\ref{A4.2})(iv), it is not on $L_1$. Hence $p$ does not exist.  
Thus $K_{ij}$ or
$K_{kl}$ has $e$ as a point. Hence $e$ is on $K_{11}$ or $K_{22}$,  
and it is on
$K_{21}$ or $K_{12}$. Thus we have two distinct lines having two  
common points.
This contradiction implies that (\ref{A4.3}) holds.


By (\ref{A4.3}), we may suppose that $L_2 -A$ contains  a single  
point $Z$. Then
 $Z \cup e$ is the complement of $L_3$ and so is a circuit of $W$  
that  does not
intersect $A$. Hence $Z\cup e$ is  $C$ or $D$. Moreover, $A$ is a  
component of
$W^*\backslash [(C\cup D)-Z]$ and hence of $W/[(C\cup D)-Z]$. Thus  
$A$ is a
component of $[M|(C\cup D\cup A)]/[(C\cup D)-Z]$. But $A$ is a  
circuit of
$[M|(C\cup D\cup A)]/[C\cup D]$. Hence $A$ is a circuit of  
$M/[(C\cup D)-Z]$,
that is,
$A$ is a chord of $(C\cup D)-Z$. Hence $A$ is a chord  of $C$ or  
$D$, and
(\ref{A4}) holds.







By (\ref{A4}) and Lemma~\ref{sey2}, it follows that there is a partition 
$\{X_1,X_2\}$ of $E(M \ba e)$ such that $X_1 \supseteq C -e$ and  
$X_2 \supseteq
D - e$, and
$r(X_1) + r(X_2) - r(M\ba e) = 1.$
Since $e$ is in the closure of both $X_1$ and $X_2$, it follows  
that $M$ is the
parallel connection, with basepoint $e$, of matroids with ground  
sets $X_1 \cup
e$ and $X_2 \cup e$.  Thus $M^*$ is a series connection, with  
basepoint $e$, of
two matroids.  Since ${\mathcal B}_3$ is closed under duality, the  
theorem
follows using Lemma~\ref{Lemma_eq1} and the induction assumption.
\end{proof}

Evidently each of the matroids that attains the bound in   
Theorem~\ref{Theorem
1} is a series-parallel network. The following result is thus an  
immediate
consequence of Theorems~\ref{Theorem 1} and \ref{Theorem 2}.

\begin{corollary}
\label{Corollary 3}
Let $M$ be a connected matroid that is not a series-parallel  
network.  If $e\in
E(M)$, then
$$|E(M)|\le (c_e(M)-1)(c_e^*(M)-1).$$
\end{corollary}

We conclude by noting an interesting link between the matroids  
attaining the
bound in  Theorem~\ref{Theorem 1} and the graphs  attaining the bound in 
Theorem~\ref{pwu}.  The following result was proved by Wu~\cite{plw2}.

\begin{theorem}
\label{wu_eq}
Let $M$ be a connected graphic matroid with at least two elements.   
Then  $E(M)
= \frac{1}{2}c(M)c^*(M)$ if and only if, for some $k \ge 2$, there  
is a sequence
of positive integers $(m,n_1,n_2,\ldots,n_k)$ for which $n_i \le
\frac{1}{2}\sum_{j=1}^{k}n_j$ for all $i$  in \linebreak  
$\{1,2,\ldots,k\}$ such
that either $M$ or $M^*$ can be obtained by deleting $e$ from the  
parallel
connection, with basepoint $e$, of $k$ matroids  
$M_1,M_2,\ldots,M_k$, where each
$M_i$ is the cycle matroid of a graph that can be obtained from a  
$2$-cycle
containing $e$ by a sequence of the following operations:
\begin{enumerate}
\item[(a)] in a  cycle containing $e$, replacing every edge except  
$e$ by two
edges in parallel; and
\item[(b)] in a bond containing $e$, subdividing every edge except  
$e$ exactly
once;
\end{enumerate}
where this sequence consists of $n_i-1$ operations of type (a) and $m-1$ 
operations of type (b).
\end{theorem}

Using Theorem~\ref{Theorem 2}, one can show that the matroids in  
${\mathcal
B}_3$ can be characterized in a similar way. To prevent the paper  
from becoming
too long, we omit the details of the proof.

\begin{corollary}
\label{alt_eq}
Let $M$ be a  connected matroid with at least two elements and  
suppose $e \in
E(M)$.  Then  $|E(M)|=(c_e(M)-1)(c_e^*(M)-1)+1$ if and only if, for  
some $k \ge
1$, there is a sequence of positive integers  
$(m,n_1,n_2,\ldots,n_k)$  such that
 $M$  is the parallel connection, with basepoint $e$, of $k$ matroids 
$M_1,M_2,\ldots,M_k$, where each $M_i$ is the cycle matroid of a  
graph that can
be obtained from a $2$-cycle  containing $e$ by a sequence of the  
following
operations:
\begin{enumerate}
\item[(a)] in a  cycle containing $e$, replacing every edge except  
$e$ by two
edges in parallel; and
\item[(b)] in a bond containing $e$, subdividing every edge except  
$e$ exactly
once;
\end{enumerate}
where this sequence consists of $n_i-1$ operations of type (a) and $m-1$ 
operations of type (b).
\end{corollary}


\medskip

\section*{Acknowledgements}
The authors thank Guoli Ding for showing them a short proof of
Theorem~\ref{Theorem 1}. The first author was partially supported   
by CNPq,
CAPES, FINEP, and \linebreak PRONEX 107/97. The second author was  
partially
supported  by the National Security Agency.

\begin{thebibliography}{99}

\bibitem{bmr} Bonin, J., McNulty, J., and Reid, T.J., The matroid  
Ramsey number
$n(6,6)$, {\it Combin. Probab. Comput.} {\bf 8}(1999), 229--235.

\bibitem{den_reid} Denley, T. and Reid, T.J., On the number of  
elements in
matroids with small circuits and small cocircuits, {\it Combin. Probab. 
Comput.}, to appear.

\bibitem{es} Erd\H{o}s, P. and Szekeres, G., A combinatorial problem in 
geometry, {\em Compositio Math.} {\bf 2} (1935), 463--470.

\bibitem{drf} Fulkerson, D.R., Networks, frames, blocking sysyems,  
in {\it
Mathematics of the Decision Sciences, Part 1}, Lectures in Applied  
Math. Vol.
11, Amer. Math. Soc., Providence, R.I., 1968, pp. 303-334.

\bibitem{hurst_reid} Hurst, F. and Reid, T.J., Some small  
circuit-cocircuit
Ramsey numbers for matroids, {\it Combin. Probab. Comput.} {\bf 4}  
(1995),
67--80.

\bibitem{hurst_reid2} Hurst, F. and Reid, T.J.,  Ramsey numbers for  
cocircuits
in matroids, {\it Ars Combin.} {\bf 45} (1997), 181--192.

\bibitem{leh} Lehman, A., On the width-length inequality, {\it Math. 
Programming} {\bf 17} (1979), 403--417.

\bibitem{lem} Lemos, M., $k$-elimination property for circuits of  
matroids, {\it
J. Combin. Theory Ser. B} {\bf 51} (1991), 211--226.



\bibitem{oxbook} Oxley, J.G., {\em Matroid Theory,} Oxford  
University Press,
New York, 1992.

\bibitem{jgo_hun} Oxley, J.G., Unavoidable minors in graphs and  
matroids, in
{\it Graph theory and combinatorial biology (Balatonlelle, 1996)},   
Bolyai Soc.
Math. Stud. {\bf 7}, J\'anos Bolyai Math. Soc., Budapest, 1999, pp.  
279--305.

\bibitem{tjr} Reid, T.J., Ramsey numbers for matroids, {\it Europ.  
J. Combin}
{\bf 18} (1997), 589--595.

\bibitem{mfmc} Seymour, P.D., The matroids with the max-flow  
min-cut property,
{\it J. Combin. Theory Ser. B} {\bf 23} (1977), 189--222.



\bibitem{sey} Seymour, P.D., Decomposition of regular matroids,  
{\it J. Combin.
Theory Ser. B} {\bf 28} (1980), 305--354.


\bibitem{wtt} Tutte, W.T., Lectures on  matroids, {\em J. Res. Nat. Bur. 
Standards Sect. B} {\bf 69B} (1965), 1--47.

\bibitem{tuza} Tuza, Z., On two intersecting set systems and  
$k$-continuous
Boolean functions, {\em Discrete Appl. Math} {\bf 16} (1987), 183--185.




\bibitem{plw} Wu, P.-L., An upper bound on the number of edges of a 
$2$-connected graph, {\it Combin. Probab. Comput.} {\bf 6} (1997),  
107--113.

\bibitem{plw2} Wu, P.-L., Extremal graphs with prescribed  
circumference and
cocircumference, submitted.

\end{thebibliography}
\end{document}
