\documentstyle{article}

\newcounter{teolema}[section]
\setcounter{teolema}{0}

\newcommand{\qed}{\makebox[.5cm][r]{\rule{.15cm}{.15cm}}\par \vspace{.3cm}}
\newcommand{\qeds}{\makebox[.5cm][r]{\rule{.15cm}{.15cm}}\par}
\newcommand{\n}{\noindent}
\newcommand{\rotulo}[1]{\newcounter{#1}\setcounter{#1}{\value{teolema}}
\newcounter{#1!!}\setcounter{#1!!}{\value{section}}}
\newcommand{\recorde}[1]{{\bf (\the\value{#1!!}.\the\value{#1})}}

%\newtheorem{theoremlike}{}[section]

\newcommand{\bteo}{\vspace{1em} \noindent \addtocounter{teolema}{1}{\bf (\thesection.\theteolema)}}
\newcommand{\eteo}{\vspace{0.8em}  \par}

%\bteo\rotulo{rotulo}
%O rotulo deve ser um para cada teorema
%Escreve o texto do teorema.
%\eteo
%Para colocar uma referencia no texto \recorde{rotulo}.

%\textwidth 155mm

%\hoffset -15mm

%\textheight 235mm

%\voffset -30mm

\title{The reconstruction of a matroid from its connectivity function\footnote{The first author is partially supported by Conselho Nacional de Desenvolvimento Cient\'\i fico e Tecnol\'ogico (CNPq, Brazil).}}

\author{Manoel Lemos\\
        and\\
        S\'ergio Mota\\
        Departamento de Matem\'atica\\
        Universidade Federal de Pernambuco\\
        Cidade Universit\'aria\\
        Recife, PE, 50740-540, Brazil}

\date{e-mail: manoel@dmat.ufpe.br\\
              sma@dmat.ufpe.br}

\begin{document}

\maketitle

\begin{abstract}
In this paper, we shall present an algorithm to decide when a connected matroid $M$ is reconstructible from its connectivity function. When $M$ is not reconstructible, this algorithm gives all the matroids with the same connectivity fucntion as $M$.
\end{abstract}

\section{Introduction}

The matroid theory terminology used in this paper will follow Oxley [4]. The {\it connectivity function} of a matroid $M$ is defined as
$$\xi_M(X,Y)=r_M(X)+r_M(Y)-r(M)+1,$$
where $\{X,Y\}$ is a partition of $E(M)$. This function is invariant under duality, since it may be written as
$$\xi_M(X,Y)=r_M(X)+r_{M^*}(X)-|X|+1.$$
In particular, a matroid and its dual have the same connectivity function. When $M=M_1\oplus M_2$, then
$$\xi_M(X,Y)+1=\xi_{M_1}(X\cap E(M_1),Y\cap E(M_1))+\xi_{M_2}(X\cap E(M_2),Y\cap E(M_2)).$$
Thus, $M_1\oplus M_2$ and $M_1\oplus M_2^*$ have the same connectivity function.

In this paper, we shall adress the problem of determining all matroids with the same connectivity function. By the last identity, we may restrict our attention to connected matroids. In this case, Cunningham conjectured that, up to duality, a connected matroid is reconstructed from its connectivity functon, that is:
\vspace{0.3cm}

\noindent {\bf Cunningham conjecture.} If $M$ and $N$ are connected matroids over the same ground set having the same connectivity function, then $M=N$ or $M=N^*$.
\vspace{0.3cm}

In [5], Seymour proved the Cunningham conjecture for the class of binary matroids. In the same paper, Seymour gave a counter-example for it in general. In [1], Lemos proved that this conjecture is true provided that $r(M)\not=r(M^*)$. 

Note that 
$$r_M(X)+r_{M^*}(X)=r_N(X)+r_{N^*}(X),$$
for every $X\subseteq E$, when $M$ and $N$ are matroids over the same ground set $E$ having the same connectivity function. In general, we say that ${\bf M}=(M_1,M_2,M_3,$ $M_4)$ is a {\it quad} when $M_1,M_2,M_3$ and $M_4$ are matroids over the same ground set, which is denoted by $E({\bf M})$, such that
$$r_{M_1}(X)+r_{M_2}(X)=r_{M_3}(X)+r_{M_4}(X),$$
for every $X\subseteq E({\bf M})$. Moreover, when $M_1=M_2^*$ and $M_3=M_4^*$, ${\bf M}$ is said to be a {\it s-quad}.

We are setting a different notation from Lemos [1] to get a more compact description of the results. Whem ${\bf X}$ denotes a quad, $X_i$ denotes the $i$-th coordenate of this quad, for $i\in\{1,2,3,4\}$.

For a quad ${\bf M}$ and disjoint subsets $X$ and $Y$ of $E({\bf M})$, we define a {\it minor} of ${\bf M}$ as  
$${\bf M}\backslash X/Y=(M_1\backslash X/Y,M_2\backslash X/Y,M_3\backslash X/Y,M_4\backslash X/Y)$$
and the {\it dual} ${\bf M}^*$ of ${\bf M}$ as $(M_1^*,M_2^*,M_3^*,M_4^*)$. We shall use ${\bf M}|X$ to denote ${\bf M}\backslash (E({\bf M})\setminus X)$. In [1], Lemos have proved that 

\bteo\rotulo{ia}
(1.1, 1.2 and 1.3 of [1]) ${\bf M}\backslash X/Y$ and ${\bf M}^*$ are quads.\qeds
\eteo

When ${\bf M}$ and ${\bf N}$ are quads such that $E({\bf M})\cap E({\bf N})=\emptyset$, we denote by ${\bf M}\oplus {\bf N}$ the quad
$$(M_1\oplus N_1,M_2\oplus N_2,M_3\oplus N_3,M_4\oplus N_4).$$
Case $N_1=N_2=N_3=N_4=N$, ${\bf M}\oplus {\bf N}$ is also denoted by ${\bf M}\oplus N$. For a matroid $N$ such that $E(N)\cap E({\bf M})=\{e\}$, ${\bf M}\oplus_2 N$ denotes
$$(M_1\oplus_2 N,M_2\oplus_2 N,M_3\oplus_2 N,M_4\oplus_2 N),$$ 
which was proved to be a quad by Lemos in [1].

For a partitition $\{X,Y\}$ of $E({\bf M})$, we define
$$\xi_{\bf M}(X,Y)=\xi_{M_1}(X,Y)+\xi_{M_2}(X,Y).$$
When $\xi_{\bf M}(X,Y)=2$, then ${\bf M}=({\bf M}|X)\oplus ({\bf M}|Y)$. So, we can restrict our attention to quads satisfying $\xi_{\bf M}(X,Y)\ge 3$, for every partition $\{X,Y\}$ of $E({\bf M})$ such that $\min\{|X|,|Y|\}\ge 1$. Such quads are called {\it connected}. ${\bf M}$ is said to be {\it non-trivial}, when $\{M_1,M_2\}\not=\{M_3,M_4\}$. In [1], Lemos proved the following result:

\bteo\rotulo{ib}
Suppose that ${\bf M}$ is a non-trivial connected quad. Then,
\begin{description}

\item{(i)} (2.6 of [1]) $\xi_{\bf M}(X,Y)\ge 4$, for every partititon $\{X,Y\}$ of ${\bf M}$ such that $\min\{|X|,|Y|\}\ge 1$.

\item{(ii)} (2.7 of [1]) When $\xi_{M_1}(X,Y)=\xi_{M_2}(X,Y)=\xi_{M_3}(X,Y)=\xi_{M_4}(X,Y)=2$, for a partition $\{X,Y\}$ of $E({\bf M})$ such that $\min\{|X|,|Y|\}\ge 2$, then there is a matroid $N$ such that $E(N)=X\cup\{e\}$ or $E(N)=Y\cup\{e\}$, for an element $e\not\in E({\bf M})$, and a quad ${\bf N}$ such that $E({\bf N})=(E({\bf M})\setminus E(N))\cup\{e\}$ satisfying ${\bf M}={\bf N}\oplus_2 N$.\qeds
\end{description}
\eteo

%In view of \recorde{ib}, we say that a connected quad ${\bf M}$ is {\it irreducible} when, for every partition $\{X,Y\}$ of $E({\bf M})$ such that $\min\{|X|,|Y|\}\ge 2$, $\xi_{M_i}(X,Y)\not=1$, for some $i\in\{1,2,3,4\}$.

In [1], Lemos proved the next result which characterizes a quad:

\bteo\rotulo{ic}
(1.4 and 1.5 of [1]) Suppose that $M_i$ is a matroid having $E$ as its ground set, for every $i\in\{1,2,3,4\}$. $(M_1,M_2,M_3,M_4)$ is a quad if and only if 
$${\cal C}(M_1)\cup{\cal C}(M_2)={\cal C}(M_3)\cup{\cal C}(M_4)\hbox{ and }{\cal C}(M_1)\cap{\cal C}(M_2)={\cal C}(M_3)\cap{\cal C}(M_4).\hbox{\qeds}$$
\vspace{0.05cm}

This result is essential in Seymour's proof that a connected binary matroid is reconstructible from its connectivity function, up to duality, in the class of binary matroids. We shall state Seymour's original result, whose proof can be adapted to prove \recorde{ic}:
\vspace{0.3cm}

\noindent {\bf Theorem 1.} Suppose that $M$ and $N$ are matroids such that $E(M)=E(N)$. $M$ and $N$ have the same connectivity function if and only if 
$${\cal C}(M)\cup {\cal C}^*(M)={\cal C}(N)\cup {\cal C}^*(N)\hbox{ and }{\cal C}(M)\cap {\cal C}^*(M)={\cal C}(N)\cap {\cal C}^*(N).\hbox{\qeds}$$
\vspace{0.05cm}

So, from Seymour's result, a matroid $M$ is reconstructible from its connectivity function, when there is no subset ${\cal A}$ of ${\cal C}(M)\bigtriangleup {\cal C}^*(M)$ such that
\begin{description}

\item{\bf (F1)} ${\cal A}\not=\emptyset$ and ${\cal A}\not={\cal C}(M)\bigtriangleup {\cal C}^*(M)$;

\item{\bf (F2)} ${\cal C}={\cal C}(M)\bigtriangleup {\cal A}$ and ${\cal C}^*={\cal C}^*(M)\bigtriangleup {\cal A}$ are, respectively, the family of circuits and the family of cocircuits of a matroid.

\end{description}
A subset ${\cal A}$ of ${\cal C}(M)\bigtriangleup {\cal C}^*(M)$ is called {\it feasible} for $M$ when it satisfies {\bf (F1)} and {\bf (F2)}. Thus, we need to answer the following question: when does $M$ have a feasible set?

Clearly, a feasible set ${\cal A}$ for $M$ must satisfies:
\begin{description}

\item{\bf (A1)} $|\{X,Y\}\cap{\cal A}|\not=1$, for every $X,Y\in {\cal C}(M)\bigtriangleup {\cal C}^*(M)$ such that $X\subset Y$.

\item{\bf (A2)} $|\{X,Y\}\cap{\cal A}|\not=1$, for every $X,Y\in {\cal C}(M)\bigtriangleup {\cal C}^*(M)$ such that $|X\cap Y|=1$.

\end{description}
A subset ${\cal A}$ of ${\cal C}(M)\bigtriangleup {\cal C}^*(M)$ is called {\it admissible} for $M$ when it satisfies {\bf (F1)}, {\bf (A1)} and {\bf (A2)}. The next result determines which admissible sets are feasible.
\vspace{0.3cm}

\noindent {\bf Theorem 2.} Suppose that ${\cal A}$ is an admissible set for a connected matroid $M$ such that $r(M)=r(M^*)$. ${\cal A}$ is feasible if and only if $|\{X,Y\}\cap{\cal A}|\in\{0,2\}$, for every 
$$X,Y\in ({\cal C}(M)\cap {\cal I}(M^*))\cup({\cal C}(M^*)\cap {\cal I}(M))$$
such that $X\cap Y=\emptyset$.
\vspace{0.3cm}

Observe that one can easily determine all the feasible sets for $M$ using theorem 2, provided that the circuits and cocircuits of $M$ are know.

%Now, we shall prove the first result of this section.

%\bteo\rotulo{if}
%If ${\bf M}$ is a non-trivial connected quad, then
%$$({\cal C}(M_i)\setminus {\cal C}(M_{3-i}))\cap ({\cal C}(M_j)\setminus {\cal C}(M_{7-j}))\not=\emptyset,$$
%for every $i\in\{1,2\}$ and $j\in\{3,4\}$.
%\eteo

%\noindent {\bf Proof:} We shall argue by contradiction. If this result is not true, then every circuit of $M_i$ is a circuit of $M_{7-j}$ by \recorde{ic}. Thus, every independent of $M_{7-j}$ is also an indenpendent of $M_i$. As $M_i\not=M_{7-j}$, it follows that there is a circuit $C$ of $M_{7-j}$ which is not a circuit of $M_i$. Let $B$ be a basis of $M_{7-j}$ such that $|C\setminus B|=1$. Observe that $B\cup C$ is independent in $M_i$, since the unique circuit of $M_{7-j}$ which is contained in $B\cup C$ is $C$. So, $r(M_i)>r(M_{7-j})$ and we arrive at a contradiction by \recorde{id}.\qeds

\section{Almost preserving the rank function}

In this section, we shall improve the next result of Lemos [1]:

\bteo\rotulo{id}
(theorem 2 of [1]) If ${\bf M}$ is a non-trival connected quad, then
$$r(M_1)=r(M_2)=r(M_3)=r(M_4).\hbox{\qeds}$$
\vspace{0.05cm}

By \recorde{id}, the condition of the rank of $M$ in theorem 2 is not restricitive, since, for a connected matroid $M$, feasible sets exist only when $r(M)=r(M^*)$.

\bteo\rotulo{aa}
Suppose that ${\bf M}$ is a non-trivial connected quad. If $\{M_1|A,M_2|A\}\not=\{M_3|A,M_4|A\}$, then 
$$r_{M_1}(A)=r_{M_2}(A)=r_{M_3}(A)=r_{M_4}(A)$$
and there is a subset $B$ of $A$ such that 
\begin{description}

\item{(i)} ${\bf M}|A={\bf M}|B\oplus {\bf M}|(A\setminus B)$;

\item{(ii)} ${\bf M}|B$ is non-trivial and connected;

\item{(iii)} $M_1|(A\setminus B)=M_2|(A\setminus B)=M_3|(A\setminus B)=M_4|(A\setminus B)$.

\end{description}
\eteo

\noindent {\bf Proof:} We shall prove this result by induction on $|E({\bf M})|$. The result is vacuously true for $|E({\bf M})|=1$. When $E({\bf M})=A$, the first part of the result follows from \recorde{id} and for the second, we can take $B=A$. So, we may suppose that $E({\bf M})\setminus A\not=\emptyset$. Let $e$ be an element of $E({\bf M})\setminus A$.

When ${\bf M}\backslash e$ is connected, then the result follows by induction, since
$$\{M_1\backslash e,M_2\backslash e\}\not=\{M_3\backslash e,M_4\backslash e\}$$
because $\{M_1|A,M_2|A\}\not=\{M_3|A,M_4|A\}$.

When ${\bf M}\backslash e$ is not connected, then, by \recorde{ib}, there is a matroid $N$ and a quad ${\bf N}$ such that $E(N)=X\cup\{f\}$, for some $X\subset E({\bf M})$, $E({\bf N})=(E({\bf M})\setminus X)\cup\{f\}$ and ${\bf M}={\bf N}\oplus_2 N$, where $f\not\in E({\bf M})$ and $\{e,f\}$ is contained in a series class of $N$. As ${\bf M}$ is connected, it follows that ${\bf N}$ is a connected quad. Observe that ${\bf N}$ is a non-trivial quad, since 
$$M_i|A=M_i|(A\cap X)\oplus M_i|(A\setminus X)=N|(A\cap X)\oplus N_i|(A\setminus X).$$ 
By induction, the first part of the result holds for ${\bf N}$ and hence
$$r_{N_1}(A\setminus X)=r_{N_2}(A\setminus X)=r_{N_3}(A\setminus X)=r_{N_4}(A\setminus X).$$
As $r_{M_i}(A)=r_{N}(A\cap X)+r_{N_i}(A\setminus X)$, the first part of the result follows for ${\bf M}$. By induction, the second part of the result also holds for ${\bf N}$, and there is a subset $B$ of $A\setminus X$ such that 
\begin{description}

\item{(i)} ${\bf N}|(A\setminus X)={\bf N}|B\oplus {\bf N}|(A\setminus (X\cup B))$;

\item{(ii)} ${\bf N}|B$ is non-trivial and connected;

\item{(iii)} $N_1|(A\setminus (X\cup B))=N_2|(A\setminus (X\cup B))=N_3|(A\setminus (X\cup B))=N_4|(A\setminus (X\cup B))$.

\end{description}

The second part of the result also follows for ${\bf M}$ because ${\bf N}|B={\bf M}|B,{\bf N}|(A\setminus (B\cup X))={\bf M}|(A\setminus (B\cup X))$ and ${\bf N}|(A\setminus (B\cup X))\oplus {\bf M}|(A\cap X)={\bf M}|(A\setminus B)$.\qeds

\bteo\rotulo{ab}
If ${\bf M}$ is a non-trivial connected quad, then  $$\{r_{M_1}(A),r_{M_2}(A)\}=\{r_{M_3}(A),r_{M_4}(A)\},$$
for every $A\subseteq E({\bf M})$.
\eteo

\noindent {\bf Proof:} The result follows when $\{M_1|A,M_2|A\}=\{M_3|A,M_4|A\}$. So, we may suppose that this is not the case. By \recorde{aa}, it follows that $r_{M_1}(A)=r_{M_2}(A)=r_{M_3}(A)=r_{M_4}(A)$.\qed

Observe that the previous result says that the rank function is locally preserved in a non-trivial connected quad ${\bf M}$, that is,
$$\{r_{M_1}(A),r_{M_2}(A)\}=\{r_{M_3}(A),r_{M_4}(A)\},\hbox{ for every $A\subseteq E({\bf M})$}.$$
Cunningham conjecture may be extended to this context as: for a non-trivial connected quad ${\bf M}$, is it true that
$$\{r_{M_1},r_{M_2}\}=\{r_{M_3},r_{M_4}\}?$$
So, \recorde{ab} is the closest positive answer that we can get in general for Cunningham conjecture. 

In view of \recorde{ab}, when ${\bf M}$ is a non-trivial connected quad, then the rank functions of $M_3$ and $M_4$ are obtained mixing the rank functions of $M_1$ and $M_2$, that is, there is a family ${\cal R}$ of subsets of $E({\bf M})$ such that 
$$(r_{M_3}(X),r_{M_4}(X))=\left\{\begin{tabular}{ll}$(r_{M_1}(X),r_{M_2}(X))$&$\hbox{when }X\in {\cal R}$\\$(r_{M_2}(X),r_{M_1}(X))$&$\hbox{when }X\not\in {\cal R}$\end{tabular}\right.$$
In the next section, we shall define an operation of mix between the rank functions of two matroids, that is, we prove that for some ${\cal R}$ this identity gives rise to a pair of rank functions of matroids. This operation of mix will be enough to characterize the quads, as we shall prove in section four.

%\bteo\rotulo{ac}
%Suppose that ${\bf M}$ is a non-trivial connected quad. If $\{M_1|A,M_2|A\}\not=\{M_3|A,M_4|A\}$ and $A\subseteq X$, then 
%$$r_{M_1}(X)=r_{M_2}(X)=r_{M_3}(X)=r_{M_4}(X).$$
%\eteo

%\noindent {\bf Proof:} The result follows from \recorde{aa}, since $\{M_1|X,M_2|X\}\not=\{M_3|X,M_4|X\}$.\qeds

%\bteo\rotulo{ad}
%Suppose that ${\bf M}$ is a non-trivial connected quad. When $i\not=j$, $M_i$ and $M_j$ cannot have a common 1-separation.
%\eteo

%\noindent {\bf Proof:} Suppose that this result is not true and let $\{A,B\}$ be a 1-separation for both $M_i$ and $M_j$. As ${\bf M}$ is connected, it follows that $\{i,j\}\not=\{1,2\}$ and $\{i,j\}\not=\{3,4\}$. Without loss of generality, we may suppose that $i=1$ and $j=3$. 

%By \recorde{ie}, it follows that $M_1|A\not=M_3|A$ and $M_1|B\not=M_3|B$, otherwise $M_1$ and $M_3$ have a common connected component. 

%Suppose that $r_{M_1}(X)\not=r_{M_2}(X)$, for $X\in\{A,B\}$. So, $M_1|X=M_4|X$ and $M_2|X=M_3|X$ by \recorde{aa}. Hence $r_{M_1}(X)=r_{M_4}(X)$ and $r_{M_2}(X)=r_{M_3}(X)$. If $Y\in\{A,B\}\setminus\{X\}$, then $r_{M_1}(Y)\not=r_{M_2}(Y)$, otherwise $r_{M_1}(Y)=r_{M_2}(Y)=r_{M_3}(Y)=r_{M_4}(Y)$, by \recorde{ab}, and
%$$r_{M_1}(A)+r_{M_1}(B)-r(M_1)\not=r_{M_3}(A)+r_{M_3}(B)-r(M_3).$$
%So, $r_{M_1}(Y)=r_{M_4}(Y)$ and $r_{M_2}(Y)=r_{M_3}(Y)$. We arrive at a contradiction, since
%$$r_{M_1}(A)+r_{M_1}(B)-r(M_1)=r_{M_4}(A)+r_{M_4}(B)-r(M_4)$$
%and $\{A,B\}$ is also a 1-separation for $M_4$ and ${\bf M}$ is not connected.

%Suppose that $r_{M_1}(X)=r_{M_2}(X)$ for both $X\in\{A,B\}$. So, $\{A,B\}$ is a 1-separation for both $M_1$ and $M_2$, which is a contradiction to the fact that ${\bf M}$ is connected.\qeds

%\bteo\rotulo{ae}
%If ${\bf M}$ is a non-trivial connected quad, then ${\cal F}(M_1)\cap {\cal F}(M_2)={\cal F}(M_3)\cap {\cal F}(M_4)$ and ${\cal F}(M_1)\cup {\cal F}(M_2)={\cal F}(M_3)\cup {\cal F}(M_4)$.
%\eteo

%\noindent {\bf Proof:} Suppose that $A$ is closed in $M_1$ and $M_2$. By \recorde{ab}, it follows that $\{r_{M_1}(A),r_{M_2}(A)\}=\{r_{M_3}(A),r_{M_4}(A)\}$ and $\{r_{M_1}(A\cup e),r_{M_2}(A\cup e)\}=\{r_{M_3}(A\cup e),r_{M_4}(A\cup e)\}$, when $e\not\in A$. As $r_i(A\cup e)-r_i(A)$ is equal to 1 for $i\in\{1,2\}$, it follows that the same holds for $i\in\{3,4\}$ and $A$ is closed in both $M_3$ and $M_4$.

%Suppose that $A$ is closed in exactly one of $M_1$ or $M_2$, say $M_1$. By the previous paragraph, we arrive at a contradiction when $A$ is closed in both $M_3$ or $M_4$. So, we may suppose that this is not the case. Thus, $A$ is not closed in $M_3$ or in $M_4$. If $A$ is closed in one of them, then the result follows. Hence $A$ is not closed in both $M_3$ and $M_4$. So, there are $e$ and $f$ such that $\{e,f\}\cap A=\emptyset$ and 
%$$r_{M_3}(A\cup e)-r_{M_3}(A)=r_{M_4}(A\cup f)-r_{M_4}(A)=0.$$
%Observe that
%$$r_{M_1}(A\cup e)-r_{M_1}(A)+r_{M_2}(A\cup e)-r_{M_2}(A)=r_{M_3}(A\cup e)-r_{M_3}(A)+r_{M_4}(A\cup e)-r_{M_4}(A)$$
%and hence
%$$r_{M_1}(A\cup e)-r_{M_1}(A)=r_{M_4}(A\cup e)-r_{M_4}(A)=1$$
%$$r_{M_2}(A\cup e)-r_{M_2}(A)=r_{M_3}(A\cup e)-r_{M_3}(A)=0$$
%So, $e\not=f$, and similarlly we have that
%$$r_{M_1}(A\cup f)-r_{M_1}(A)=r_{M_3}(A\cup f)-r_{M_3}(A)=1$$
%$$r_{M_2}(A\cup f)-r_{M_2}(A)=r_{M_4}(A\cup f)-r_{M_4}(A)=0$$
%Hence
%$$r_{M_3}(A\cup\{e,f\})-r_{M_3}(A)=r_{M_4}(A\cup\{e,f\})-r_{M_4}(A)=1.$$
%We also have that 
%$$\begin{array}{l}
%(r_{M_1}(A\cup\{e,f\})-r_{M_1}(A))+(r_{M_2}(A\cup\{e,f\})-r_{M_2}(A))=\\
%=(r_{M_3}(A\cup\{e,f\})-r_{M_3}(A))+(r_{M_4}(A\cup\{e,f\})-r_{M_4}(A)).
%\end{array}$$
%So, 
%\begin{center}
%\begin{eqnarray*}
%r_{M_1}(A\cup\{e,f\})&=&r_{M_1}(A)+2\\
%r_{M_2}(A\cup\{e,f\})&=&r_{M_2}(A)\\
%\end{eqnarray*}
%\end{center}
%By \recorde{ab}, we may suppose that $r_{M_1}(A)=r_{M_3}(A)=r$. Hence $r_{M_1}(A\cup\{e,f\})=r_{M_4}(A\cup\{e,f\})=r+2$ and $r_{M_2}(A)=r_{M_4}(A)=r+1$. By \recorde{aa}, it follows that $M_2|(A\cup\{e,f\})=M_3|(A\cup\{e,f\})$. We arrive at a contradiction, because both $e$ and $f$ are spanned by $A$ in $M_2|(A\cup\{e,f\})$ and $e$ is not spanned in $M_4|(A\cup\{e,f\})$.\qeds

%\section{Structural results}

%\subsection{When $M_2$ is not connected}

%In this subsection, we shall suppose that ${\bf M}$ is a non-trivial connected quad and that $\{A,B\}$ is a partition of $E({\bf M})$ such that
%$$\xi_{M_1}(A,B)\ge 2\hbox{ and }\xi_{M_2}(A,B)=0.$$
%By \recorde{ad}, it follows that $\xi_{M_i}(A,B)\ge 1$, for every $i\in\{3,4\}$.

%\bteo\rotulo{bz}
%Let ${\bf N}$ be a quand and let $N$ be a matroid such that $\{e\}=E({\bf N})\cap E(N)$. If ${\bf M}={\bf N}\oplus_1 N$, then 
%\begin{description}

%\item{(i)} $N$ is connected and ${\bf N}$ is non-trivial and connected;

%\item{(ii)} $E(N)\subseteq A\cup\{e\}$ or $E(N)\subseteq B\cup\{e\}$, say $E(N)\subseteq A\cup\{e\}$;

%\item{(iii)} $\xi_{N_1}((A\setminus E(N))\cup\{e\},B)\ge 2$ and $\xi_{N_2}((A\setminus E(N))\cup\{e\},B)=0$. 

%\end{description} 

%\noindent {\bf Proof:} {\bf (i)} Observe that $N$ is connected because ${\bf M}$ is connected and a connected component of $N$ which does not contain the basis point for the 2-sum must be a connected component of every $M_i$. Similarlly, $N$ is connected. ${\bf N}$ must be non-trivial, since ${\bf M}$ is non-trivial.

%\noindent {\bf (ii)} As $\xi_{M_1}(A,B)\ge 2$ and $\xi_{M_2}(A,B)=0$, it follows that $E(N)\subseteq A\cup\{e\}$ or $E(N)\subseteq B\cup\{e\}$, since $M_2$ does not have a circuit intersecting both $A$ and $B$. 

%\noindent {\bf (iii)} Follows from \recorde{ib}(i).\qeds

%\bteo\rotulo{bd}
%$r_{M_1}(X)\ge r_{M_2}(X)$ for every $X\subseteq E({\bf M})$.
%\eteo

%\noindent {\bf Proof:} Suppose that the result is not true and choose a counter-example ${\bf M}$ such that $|E({\bf M})|$ is as small as possible. So, there is $X\subseteq E({\bf M})$ such that $r_{M_1}(X)<r_{M_2}(X)$. Choose $X$ such that $|X|$ is as small as possible. Let $Y$ be a basis of $X$ in $M_2$. As $r_{M_1}(Y)<r_{M_2}(Y)=|Y|$, it follows that $Y$ contains a circuit $C$ of $M_1$. Hence, $X=C$ by the choice of $X$. That is, $X$ is independent in $M_2$ and a circuit of $M_1$. 

%First, we shall prove that ${\bf M}$ is irreducible. When ${\bf M}$ is reducible, then there is a matroid $N$ and a quad ${\bf N}$ such that $E({\bf N})\cap E(N)=\{e\}$ and ${\bf N}={\bf N}\oplus_2 N$. If $X'=(X\cap E({\bf N}))\cup\{e\}$, then 
%$$r_{N_1}(X')<r_{N_2}(X')$$
%because $(X\cap E(N))\cup\{e\}$ is a circuit of $N$ and $(X\cap E({\bf N}))\cup\{e\}$ is a circuit of $N_1$ and is independent in $N_2$. We arrive at a contradiction by \recorde{bz} and by the choice of ${\bf M}$. Hence ${\bf M}$ is irreducible. Thus, ${\bf M}\backslash e$ and ${\bf M}/e$ are connected for every $e\in E({\bf M})$.

%Without loss of generality, we may suppose that $X$ is a circuit of $M_3$ and it is not a circuit of $M_4$, by \recorde{ic}. We define
%$${\cal C}=({\cal C}(M_2)\setminus {\cal C}(M_1))\cap {\cal C}(M_3).$$
%By \recorde{if}, ${\cal C}\not=\emptyset$.

%Now, we shall prove that $E({\bf M})\setminus X\subseteq C$, for every $C\in {\cal C}$. Suppose that this is not the case and let $e$ be an element of $E\setminus (X\cup C)$. As ${\bf M}\backslash e$ is connected, we arrive at a contradiction, by the choice of ${\bf M}$, because ${\bf M}\backslash e$ is non-trivial and, by \recorde{ib} and \recorde{id}, 
%$$\xi_{M_1\backslash e}(A\setminus e,B\setminus e)\ge 2\hbox{ and }\xi_{M_2\backslash e}(A\setminus e,B\setminus e)=0.$$

%As $E({\bf M})\setminus X$ is contained in a circuit of $M_2$, it follows that $E({\bf M})\setminus X\subseteq A$ or $E({\bf M})\setminus X\subseteq B$, say $E({\bf M})\setminus X\subseteq A$. Hence $B\subseteq X$ and $B$ is independent in $M_2$. So, every element of $B$ is a coloop of $M_2$. Thus, $M_3$ or $M_4$ has it as a coloop by \recorde{ic} and \recorde{ia}. We arrive at a contradiction by \recorde{ie}. \qeds

%\bteo\rotulo{ba}
%$M_1$ is connected. Moreover, $M_1$ is 3-connected, when ${\bf M}$ is irreducible.
%\eteo

%\noindent {\bf Proof:} By \recorde{id} and \recorde{bd}, it follows that
%$$\xi_{M_1}(X,Y)=r_{M_1}(X)+r_{M_1}(Y)-r(M_1)\ge r_{M_2}(X)+r_{M_2}(Y)-r(M_2)=\xi_{M_2}(X,Y).$$
%So, every 1-separation for $M_1$ is also a 1-separation for $M_2$. Hence $M_1$ is connected. By \recorde{ib}, every 2-separation for $M_1$ is also a 2-separation for $M_2$. Thus, $M_1$ is 3-connected when ${\bf M}$ is irreducible.\qeds

%\bteo\rotulo{bb}
%$M_2|A$ and $M_2|B$ are connected.
%\eteo

%\noindent {\bf Proof:} Suppose that $M_2|A$ or $M_2|B$ is not connected, say $M_2|A$, and choose a counter-example ${\bf M}$ such that $|E({\bf M})|$ is as small as possible. By \recorde{bz}, it follows that ${\bf M}$ is irreducible. Let $N$ be a connected component of $M_2|A$.

%As $M_2$ does not have a loop or a coloop, by \recorde{ic} and \recorde{ia}, it follows that $|E(N)|\ge 2$. We arrive at a contradiction, since ${\bf M}/e$ or ${\bf M}\backslash e$ is a quad contrary to the choice of ${\bf M}$ because $\xi_{M_1/e}(A\setminus\{e\},B)\ge 2$ or $\xi_{M_1\backslash e}(A\setminus\{e\},B)\ge 2$, for every $e\in A$.\qeds

%\bteo\rotulo{bc}
%$M_3$ and $M_4$ are connected.
%\eteo

%\noindent {\bf Proof:} Suppose that $M_3$ or $M_4$ is not connected, say $M_3$, and choose a counter-example ${\bf M}$ such that $|E({\bf M})|$ is as small as possible. By \recorde{bz}, it follows that ${\bf M}$ is irreducible. Let $N$ be a connected component of $M_3$.

%By \recorde{aa}, $M_2|A=M_3|A$ or $M_2|B=M_3|B$, say $M_2|A=M_3|A$. We may choose $N$ such that $E(N)\subseteq B$, since $M_3|A$ is conneceted by \recorde{bc}. As $M_1|B=M_3|B$, it follows that $B\setminus\{e\}$ spans $e$ in $M_1$, for every $e\in B$, since $|E(N)|\ge 2$ as it cannot be a loop or a coloop by \recorde{ic} and \recorde{ia}. Hence $\xi_{M_1\backslash e}(A,B\setminus\{e\})\ge 2$ and ${\bf M}\backslash e$ is contrary to the choice of ${\bf M}$.\qeds

\section{The mix of two matroids}

Suppose that $M_1$ and $M_2$ are matroids on the same ground set $E$ such that
$$\xi_{M_1}(X,Y)+\xi_{M_2}(X,Y)\ge 3,$$
for every partition $\{X,Y\}$ of $E$ satisfying $\min\{|X|,|Y|\}\ge 1$.

We define
$${\cal X}=\{X\subseteq E: r_{M_1}(X)\not=r_{M_2}(X)\}.$$
Let $G_{M_1,M_2}$ be a simple graph whose vertex set is ${\cal X}$ and, for $X,Y\in {\cal X}$, $XY$ is an edge of this graph if and only if 
\begin{description}

\item{(i)} $X\subset Y$; or 

\item{(ii)} $X\cap Y\not\in {\cal X},X\cup Y\not\in {\cal X}$ and $|X\bigtriangleup Y|=2$.

\end{description}
Let $\{{\cal A},{\cal B}\}$ be a partition of ${\cal X}$ such that $AB\not\in E(G_{M_1,M_2})$ for every $A\in {\cal A}$ and $B\in {\cal B}$. We define two functions:
$$r_3(X)=\left\{\begin{tabular}{ll}$r_{M_1}(X)$&$\hbox{when }X\not\in {\cal A}$\\$r_{M_2}(X)$&$\hbox{when }X\in {\cal A}$\end{tabular}\right.\hbox{ and }r_4(X)=\left\{\begin{tabular}{ll}$r_{M_2}(X)$&$\hbox{when }X\not\in {\cal A}$\\$r_{M_1}(X)$&$\hbox{when }X\in {\cal A}$\end{tabular}\right.$$
Observe that these functions are also given by
$$r_3(X)=\left\{\begin{tabular}{ll}$r_{M_1}(X)$&$\hbox{when }X\in {\cal B}$\\$r_{M_2}(X)$&$\hbox{when }X\not\in {\cal B}$\end{tabular}\right.\hbox{ and }r_4(X)=\left\{\begin{tabular}{ll}$r_{M_2}(X)$&$\hbox{when }X\in {\cal B}$\\$r_{M_1}(X)$&$\hbox{when }X\not\in {\cal B}$\end{tabular}\right.$$
Note that the definition of mix is algorithmic, but it depends on the rank functions of the matroids involved. In section five, we shall look to the mix in terms of circuits and hyperplanes, getting a more efficient algorithm for its computation. 

\bteo\rotulo{ca}
$r_3$ and $r_4$ are rank functions of matroids, which are denoted by $M_3$ and $M_4$, respectively.
\eteo

\noindent {\bf Proof:} By symmetry, it is enough to prove that $r_3$ is the rank function of a matroid. To demonstrate this, we need to verify the following (1.4.14 of [4]):
\begin{description}

\item{(1)} $r_3(\emptyset)=0$;

\item{(2)} $r_3(X)\le r_3(Y)$, when $X\subseteq Y$;

\item{(3)} $r_3(X\cup\{e\})\le r_3(X)+1$;

\item{(4)} $r_3(X\cup\{e,f\})=r_3(X)$, when $r_3(X\cup\{e\})=r_3(X\cup\{f\})=r_3(X)$.

\end{description}
First, observe that the next affirmation follows from the definition of $r_3$: 

\bteo\rotulo{aux}
When $X\in {\cal X}$ and $r_3(X)=r_{M_i}(X)$, for $i\in\{1,2\}$, then $r_3(Y)=r_{M_i}(Y)$ for every $Y$ such that $X\subseteq Y$ or $Y\subseteq X$.
\eteo

Observe that (1) is trivial. Now, we shall prove (2). Suppose that (2) is not true, that is, there are sets $X$ and $Y$ such that $X\subseteq Y$ and $r_3(X)>r_3(Y)$. By definition, $r_3(X)=r_{M_i}(X)$, for some $i\in\{1,2\}$. Thus, $r_3(Y)=r_{M_{3-i}}(Y)$. Hence
$$r_{M_{3-i}}(X)\le r_{M_{3-i}}(Y)=r_3(Y)<r_3(X)=r_{M_i}(X)\le r_{M_i}(Y).$$
So, $X$ and $Y$ belong to ${\cal X}$ and we arrive at a contradiction by \recorde{aux}.

Now, we shall stablish (3). When (3) fails, by (2), there is a set $X$ and an element $e$ such that $r_3(X\cup\{e\})>r_3(X)+1$. By definition, $r_3(X)=r_{M_i}(X)$, for some $i\in\{1,2\}$. Thus, $r_3(X\cup\{e\})=r_{M_{3-i}}(X\cup\{e\})$,
$r_3(X)\not=r_{M_{3-i}}(X)$ and $r_3(X\cup\{e\})\not=r_{M_{i}}(X\cup\{e\})$, otherwise $r_3(X\cup\{e\})-r_3(X)\in\{0,1\}$. Thus, $X,X\cup\{e\}\in {\cal X}$. We arrive at a contradiction, by \recorde{aux}.

In this paragraph, we shall prove (4). Suppose that (4) is not true, that is, there is a set $X$ and elements $e$ and $f$ such that $r_3(X\cup\{e,f\})\not=r_3(X)$ and $r_3(X\cup\{e\})=r_3(X\cup\{f\})=r_3(X)$. By \recorde{aux}, $X\not\in {\cal X}$ and $X\cup\{e,f\}\not\in {\cal X}$. So,
$$r_3(X)=r_{M_1}(X)=r_{M_2}(X)\hbox{ and }$$
$$r_3(X\cup\{e,f\})=r_{M_1}(X\cup\{e,f\})=r_{M_2}(X\cup\{e,f\}).$$  
Thus, $|cl_{M_i}(X)\cap\{e,f\}|=1$, for $i\in\{1,2\}$, and $r_3(X\cup\{e,f\})=r_3(X)+1$. Without loss of generality, we may suppose that
$$r_3(X)=r_3(X\cup\{e\})=r_{M_1}(X\cup\{e\})=r_{M_2}(X\cup\{e\})-1\hbox{ and }$$
$$r_3(X)=r_3(X\cup\{f\})=r_{M_2}(X\cup\{f\})=r_{M_1}(X\cup\{f\})-1.$$
We arrive at a contradiction, since $X\cup\{e\}$ and $X\cup\{f\}$ belong to ${\cal X}$ and $X$ and $X\cup\{e,f\}$ does not belong to ${\cal X}$. By definition, $(X\cup\{e\})(X\cup\{f\})$ is an edge of $G_{M_1,M_2}$.\qed

We say that $\{M_3,M_4\}$ is a {\it mix} of $\{M_1,M_2\}$ --- a pair of matroids $\{M_1,M_2\}$ can have more than one mix. Observe that $\{M_3,M_4\}=\{M_1,M_2\}$, when ${\cal A}=\emptyset$ or ${\cal B}=\emptyset$. This is always the case when $E\in {\cal X}$, since $EX$ is an edge of $G_{M_1,M_2}$, for every $X\in{\cal X}\setminus\{E\}$. By our construction, we have that

\bteo\rotulo{cb}
If $\{M_3,M_4\}$ is a mix of $\{M_1,M_2\}$, then $(M_1,M_2,M_3,M_4)$ is a connected quad.\qeds
\eteo

In the next section, we shall prove that all the quads can be obtained as in the previous proposition. 

\bteo\rotulo{cba}
Suppose that $\{M_3,M_4\}$ is a mix of $\{M_1,M_2\}$, $M_1=M_2^*$ and  $r(M_1)=r(M_2)$. Then, $X\in{\cal X}$ if and only if $E\setminus X\in{\cal X}$. 
\eteo

\noindent {\bf Proof:} As $M_1$ and $M_2$ have the same connectivity function, it follows that
$$r_{M_1}(X)+r_{M_1}(E\setminus X)-r(M_1)=r_{M_2}(X)+r_{M_2}(E\setminus X)-r(M_2).$$
Thus, 
$$r_{M_1}(X)-r_{M_2}(X)=r_{M_2}(E\setminus X)-r_{M_1}(E\setminus X)$$
and the result follows.\qeds

\bteo\rotulo{novo}
Suppose that $\{M_3,M_4\}$ is a mix of $\{M_1,M_2\}$, $M_1=M_2^*$ and $r(M_1)=r(M_2)$. Then, $M_3=M_4^*$ if and only if $|\{A,E\setminus A\}\cap {\cal A}|\in\{0,2\}$, for every $A\subseteq E$.
\eteo

\noindent {\bf Proof:} This result follows from the equivalence between the next affirmations:
\begin{description}

\item{(i)} $M_3=M^*_4$;

\item{(ii)} $r_{M_4}(X)=|X|+r_{M_3}(E\setminus X)-r(M_3)$, for every $X\subseteq E$;

\item{(iii)} for every $X\subseteq E$, there is an $i\in\{1,2\}$ such that $r_{M_3}(X)=r_{M_i}(X)$ and $r_{M_3}(E\setminus X)=r_{M_i}(E\setminus X)$;

\item{(iv)} $|\{X,E\setminus X\}\cap {\cal A}|\in\{0,2\}$, for every $X\subseteq E$.

\end{description}
The equivalences between (i) and (ii) is immediate and between (iii) and (iv) follows from \recorde{cba}.

In this paragraph, we shall prove that (ii) and (iii) are equivalent. For $X\subseteq E$, we have that 
$$|X|+r_{M_3}(E\setminus X)-r(M_3)=|X|+r_{M_i}(E\setminus X)-r(M_i)=r_{M_{3-i}}(X),$$
for some $i\in\{1,2\}$, where the last identity occurs because $M_1=M_2^*$. Thus, by \recorde{cba}, $r_{M_3}(X)=r_{M_i}(X)$ if and only if $r_{M_4}(X)=r_{M_{3-i}}(X)$. Hence, we have the equivalence between (ii) and (iii).\qed

We say that $\{M_3,M_4\}$ is a {\it s-mix} of $\{M_1,M_2\}$, when $M_1=M_2^*,r(M_1)=r(M_2),{\cal A}\not=\emptyset,{\cal A}\not={\cal X}$ and  $A\in{\cal A}$ if and only if $E\setminus A\in{\cal A}$, for every $A\subseteq {\cal X}$. So, by \recorde{novo},

\bteo\rotulo{cc}
If $\{M_3,M_4\}$ is a s-mix of $\{M_1,M_2\}$, then $(M_1,M_2,M_3,M_4)$ is a connected non-trivial s-quad.\qeds
\eteo

\section{A characterization of connected quads}

In this section, we shall present a characterization of the non-trivial connected quads, using the construction of the mix which was defined in the previous section. 

\bteo\rotulo{da}
Suppose that $M_i$ is a matroid having $E$ as its ground set, for every $i\in\{1,2,3,4\}$. $(M_1,M_2,M_3,M_4)$ is a connected quad if and only if $\{M_3,M_4\}$ is a mix of $\{M_1,M_2\}$.
\eteo

\noindent {\bf Proof:} By \recorde{cb}, the ``if'' part of this result follows. So, we need to prove only the ``only if '' part. Suppose that $(M_1,M_2,M_3,M_4)$ is a connected quad. Observe that this quad must be non-trivial, otherwise $\{M_3,M_4\}$ is a mix of $\{M_1,M_2\}$. 

To conclude that $\{M_3,M_4\}$ is a mix of $\{M_1,M_2\}$, we just need to prove that:

\bteo\rotulo{db}
If $X,Y\in{\cal X},XY\in E(G_{M_1,M_2})$ and $r_{M_1}(X)=r_{M_j}(X)$, for $j\in\{3,4\}$, then $r_{M_1}(Y)=r_{M_j}(Y)$.
\eteo

By \recorde{aa}, \recorde{db} is true when $X\subseteq Y$ or $Y\subseteq X$. So, we may suppose that $X\setminus Y=\{e\},Y\setminus X=\{f\},X\cap Y\not\in {\cal X}$ and $X\cup Y\not\in{\cal X}$. When \recorde{db} does not hold, we must have that $r_{M_1}(Y)=r_{M_{7-j}}(Y)$. As $X\cap Y$ and $X\cup Y$ do not belong to ${\cal X}$, it follows that 
$$r_{M_1}(X\cap Y)=r_{M_2}(X\cap Y)=r\hbox{ and }r_{M_1}(X\cup Y)=r_{M_2}(X\cup Y)=s,$$
for some integers $r$ and $s$. Thus, 
$$\{r_{M_1}(X),r_{M_2}(X)\}=\{r_{M_1}(Y),r_{M_2}(Y)\}=\{r,r+1\},$$
since $|X\setminus Y|=|Y\setminus X|=1$ and $X,Y\in{\cal X}$. So, $s=r+1$. Without loss of generality, we may suppose that 
$$r_{M_1}(X)=r_{M_2}(Y)=r\hbox{ and }r_{M_1}(Y)=r_{M_2}(X)=r+1,$$
otherwise, there is an $i\in\{1,2\}$ such that 
$$r_{M_i}(X\cap Y)=r_{M_i}(X)=r_{M_i}(Y)=r_{M_i}(X\cup Y)-1,$$
which is contrary to the fact that $M_i$ is a matroid.

So, there is an $i\in\{3,4\}$ such that 
$$r_{M_i}(X\cap Y)=r_{M_i}(X)=r_{M_i}(Y)=r_{M_i}(X\cup Y)-1,$$
since $r_{M_1}(X)=r_{M_j}(X)$ and $r_{M_1}(Y)=r_{M_{7-j}}(Y)$. Again, we arrive at a contradiction.\qed

As a consequence of \recorde{id}, \recorde{novo}, \recorde{cc} and \recorde{da}, we have that:

\bteo\rotulo{dc}
Suppose that $M_i$ is a matroid having $E$ as its ground set, for every $i\in\{1,2,3,4\}$. $(M_1,M_2,M_3,M_4)$ is a connected non-trivial s-quad if and only if $\{M_3,M_4\}$ is a s-mix of $\{M_1,M_2\}$.\qeds
\eteo

By the previous result, a connected matroid $M$ is reconstructible from its connectivity function if and only if $\{M,M^*\}$ does not have a s-mix.

The explicit construction of all quads looks unlikely, since there are a lot of constructions which produce them, even in the case of s-quads (1-sum of s-quads, 2-sum of a s-quad with a identity self-dual matroid, the truncated lift of a s-quad --- replace every entry of the quad by its truncated lift). Moreover, the construction made by Seymour [5] can be extended for a large class of paving matroids, giving non-trivial examples of s-quads, where we can apply all these operations to get more exotic examples. 

\section{Another way to compute the mix}

In this section, we shall discuss the operation of mix as a permutation of circuits or hyperplanes of the two matroids involved in this operation. 

Suppose that $M_1$ and $M_2$ are matroids on the same ground set $E$ such that $r(M_1)=r(M_2)$ and 
$$\xi_{M_1}(X,Y)+\xi_{M_2}(X,Y)\ge 1$$
for every partition $\{X,Y\}$ of $E$ such that $\min\{|X|,|Y|\}\ge 1$. 

\bteo\rotulo{fa}
If $X$ is a maximal subset of $E$ such that $r_{M_1}(X)\not=r_{M_2}(X)$, then $X$ is spanning in $M_i$ and a hyperplane of $M_{3-i}$, for some $i\in\{1,2\}$.
\eteo

\noindent {\bf Proof:} Without loss of generality, we may suppose that $r_{M_1}(X)>r_{M_2}(X)$. As $r(M_1)=r(M_2)$, it follows that $X\not=E$. By the maximality of $X$, it follows that $r_{M_1}(X\cup\{e\})=r_{M_2}(X\cup\{e\})$, for every $e\in E({\bf M})\setminus X$. Thus, $r_{M_1}(X)=r_{M_2}(X)+1$, $X$ spans $e$ in $M_1$ and $X$ does not span $e$ in $M_2$. So, $X$ is a spanning set of $M_1$ and a hyperplane of $M_2$.\qed

We may write the dual of this result as:

\bteo\rotulo{fb}
If $X$ is a minimal subset of $E$ such that $r_{M_1}(X)\not=r_{M_2}(X)$, then $X$ is independent in $M_i$ and a circuit of $M_{3-i}$, for some $i\in\{1,2\}$.\qed
\eteo

We shall consider the following subsets of ${\cal X}$:
\begin{center}
\begin{eqnarray*}
{\cal H}&=&({\cal H}(M_1)\cap{\cal S}(M_2))\cup({\cal H}(M_2)\cap{\cal S}(M_1))\\
{\cal C}&=&({\cal C}(M_1)\cap{\cal I}(M_2))\cup({\cal C}(M_2)\cap{\cal I}(M_1))\\
\end{eqnarray*}
\end{center}
A sequence $v_0,v_1,v_2,\dots,v_n$ of vertices of a graph $G$ is said to be a {\it path} of $G$, when $v_iv_{i+1}\in E(G)$ for every $i\in\{0,1,2,\dots,n-1\}$. When $v_0,v_1,v_2,\dots,v_n$ and $w_0,w_1,w_2,\dots,w_m$ are paths of $G$ such that $v_n=w_0$, we say that 
$$v_0,v_1,v_2,\dots,v_n,w_1,w_2,\dots,w_m$$
is the {\it concatenation} of these paths.

%\bteo\rotulo{fbb}
%If $X\in{\cal C}\cap{\cal H}$, then $X$ is a circuit-hyperplane of $M_i$, for some $i\in\{1,2\}$.
%\eteo

%\noindent {\bf Proof:} There is an $i\in\{1,2\}$ such that $X\in{\cal C}(M_i)\cap{\cal I}(M_{3-i})$. Thus, $r_{M_i}(X)<r_{M_{3-i}}(X)$. As $X\in {\cal H}(M_j)\cap{\cal S}(M_{3-j})$, for some $j\in\{1,2\}$, it follows that $r_{M_j}(X)<r_{M_{3-}}(X)$. Hence $i=j$ and the result follows.\qeds

\bteo\rotulo{fc}
If $X,Y\in{\cal C}\cup{\cal H}$ belong to the same connected component of $G_{M_1,M_2}$, then there is a path joining $X$ to $Y$ in $G_{M_1,M_2}$ which is the concatenation of paths of the following types:
\begin{description}

\item{(i)} $C,H$, for $C\in{\cal C}$ and $H\in{\cal H}$;

\item{(ii)} $H,C$, for $C\in{\cal C}$ and $H\in{\cal H}$;

\item{(iii)} $H,A,B,H'$, for $H,H'\in{\cal H}$ and $A,B\in{\cal X}$ satisfying $A\subseteq H,B\subseteq H',AB\in E(G_{M_1,M_2})$ and $|A\setminus B|=|B\setminus A|=1$.

\end{description}

\noindent {\bf Proof:} Suppose that
$$X=X_0,X_1,X_2,X_3,\dots,X_{n-1},X_n=Y$$
is a path that joins $X$ to $Y$ in $G_{M_1,M_2}$. We shall insert vertices in this path in the following way:
\begin{description}

\item{(i)} When $X_i\subset X_{i+1}$ or $X_{i+1}\subset X_i$, then, by \recorde{fa}, there is an $H_i\in{\cal H}$ such that $X_j\subseteq H_i$, for $j\in\{i,i+1\}$. Insert $H_i$ between $X_i$ and $X_{i+1}$.

\item{(ii)} When $H_i$ and $H_{i+1}$ do not exist, then, by \recorde{fa}, there is a $K_{i+1}\in{\cal H}$ such that $X_{i+1}\subseteq K_{i+1}$. Insert $K_{i+1},X_{i+1}$, in this order, between $X_{i+1}$ and $X_{i+2}$.

\item{(iii)} When $H_0$ does not exist, then, by \recorde{fa}, there is a $K_0\in{\cal H}$ such that $X_0\subseteq K_0$. Insert $X_0,K_0$, in this order, in the begining of the path.

\item{(iv)} When $H_{n-1}$ does not exist, then, by \recorde{fa}, there is a $K_n\in{\cal H}$ such that $X_n\subseteq K_n$. Insert $K_n,X_n$, in this order, in the end of the path.

\end{description}
When $H_{i-1}$ and $H_{i}$ exist, then, by \recorde{fb}, there is a $C_i\in {\cal C}$ such that $C_i\subseteq X_i$. Replace $X_i$ by $C_i$. Oberve that the path at the end of these constructions has the desired properties --- when $H_0$ exists and $X_0$ is a hyperplane, then $X_0=H_0$ and we ignore $X_0$; we may need to ignore $X_n$ also.\qed

Now, we shall define two new sets:
$${\cal H}'={\cal H}(M_1)\bigtriangleup{\cal H}(M_2)\hbox{ and }{\cal C}'={\cal C}(M_1)\bigtriangleup{\cal C}(M_2).$$
Observe that ${\cal C}\subseteq{\cal C}'$ and that ${\cal H}\subseteq{\cal H}'$. By \recorde{fa} and \recorde{fb}, when $C'\in{\cal C}'\setminus{\cal C}$ and $H'\in{\cal H}'\setminus{\cal H}$, then there is a $C\in{\cal C}$ such that $C\subset C'$ and a $H\in{\cal H}$ such that $H'\subset H$.

Let $H_{M_1,M_2}$ be a graph whose vertex set is equal to ${\cal C}'\cup{\cal H'}$ and $XY$ is an edge of this graph when
\begin{description}

\item{(i)} $X,Y\in{\cal C}'$ and $X\subset Y$;

\item{(ii)} $X,Y\in{\cal H}'$ and $X\subset Y$;

\item{(iii)} $X\in{\cal C},Y\in{\cal H}$ and $X\subseteq Y$;

\item{(iv)} $X,Y\in{\cal H},M_1|(X\cap Y)=M_2|(X\cap Y)$ and there is $e\in X\setminus Y$ and $f\in Y\setminus X$ such that $\{e,f\}\subseteq cl_{M_1}(X\cap Y)\bigtriangleup cl_{M_2}(X\cap Y)$.

\end{description}

\bteo\rotulo{fd}
If $X\in V(H_{M_1,M_2})\setminus V(G_{M_1,M_2})$, then $d_{H_{M_1,M_2}}(X)=1$.
\eteo

\noindent {\bf Proof:} As $X\not\in{\cal X}$, it follows that $X\in({\cal C}'\setminus{\cal C})\cup({\cal H}'\setminus{\cal H})$ and $r_{M_1}(X)=r_{M_2}(X)$. When $X\in{\cal C}(M_i)$, for some $i\in\{1,2\}$, then $X$ contains just one circuit of ${\cal C}(M_{3-i})$, since $X$ has the same rank in both $M_1$ and $M_2$. Hence $d_{H_{M_1,M_2}}(X)=1$. A similar argument holds when $X\in{\cal H}(M_i)$, for some $i\in\{1,2\}$.\qed

\bteo\rotulo{fe}
Suppose that $X$ and $Y$ belong to $V(H_{M_1,M_2})\cap V(G_{M_1,M_2})$. $X$ and $Y$ belong to the same connected component of $H_{M_1,M_2}$ if and only if $X$ and $Y$ belong to the same connected component of $G_{M_1,M_2}$.
\eteo  

\noindent {\bf Proof:} First, we shall prove the ``only if'' part of this result. Suppose that 
$$X=X_0,X_1,X_2,X_3,\dots,X_{n-1},X_n=Y$$
is a simple path which joins $X$ and $Y$ in $H_{M_1,M_2}$. By \recorde{fd}, it follows that $X_i\in V(G_{H_1,H_2})$ for every $i$. If $X_iX_{i+1}$ is not an edge of $G_{H_1,H_2}$, then $X_i,X_{i+1}\in{\cal H},M_1|(X_i\cap X_{i+1})=M_2|(X_i\cap X_{i+1})$ and there are $e\in X_i\setminus X_{i+1}$ and $f\in X_{i+1}\setminus X_i$ such that $\{e,f\}\subseteq cl_{M_1}(X_i\cap X_{i+1})\bigtriangleup cl_{M_2}(X_i\cap X_{i+1})$. So, $((X_i\cap X_{i+1})\cup\{e\})((X_i\cap X_{i+1})\cup\{f\})$ is an edge of $G_{M_1,M_2}$. When this happens, we insert between $X_i$ and $X_{i+1}$ the vertices $(X_i\cap X_{i+1})\cup\{e\},(X_i\cap X_{i+1})\cup\{f\}$ in this order. Repeat this operation for every $i$ in this situation. The final path is a paht in $G_{M_1,M_2}$ which joins $X$ to $Y$.

Now, we shall prove the ``if'' part of this result. Suppose that 
$$X=X_0,X_1,X_2,X_3,\dots,X_{n-1},X_n=Y$$
is a simple path which joins $X$ and $Y$ in $G_{M_1,M_2}$. By \recorde{fd}, we may choose this path such that it is a concanation of paths of the following types: (i) $C,H$, for $C\in{\cal C}$ and $H\in{\cal H}$; (ii) $H,C$, for $C\in{\cal C}$ and $H\in{\cal H}$; (iii) $H,A,B,H'$, for $H,H'\in{\cal H}$ and $A,B\in{\cal X}$ satisfying $|A\setminus B|=|B\setminus A|=1$. Observe that (i) and (ii) are paths of $H_{M_1,M_2}$. So, we shall replace every path of type (iii) by $H,H'$, when $M_1|(H\cap H')=M_3|(H\cap H')$, or by $H,X,H'$, for some $X\in{\cal C}$ such that $X\subseteq H\cap H'$. At the end, we get a path from $H_{M_1,M_2}$ which joins $X$ to $Y$.\qed

As a consequence of \recorde{fe}, we have the following:

\bteo\rotulo{ff}
$\{M_3,M_4\}$ is a mix of $\{M_1,M_2\}$ if and only if there is a partition $\{{\cal A},{\cal B}\}$ of $V(H_{M_1,M_2})$ such that $AB\not\in E(H_{M_1,M_2})$, for every $A\in{\cal A}$ and $B\in{\cal B}$, and
$${\cal C}(M_3)=({\cal C}(M_1)\setminus{\cal A})\cup({\cal C}(M_2)\cap{\cal B})\hbox{ and }C(M_4)=({\cal C}(M_1)\cap{\cal A})\cup({\cal C}(M_2)\setminus{\cal B}).\hbox{\qeds}$$

A similar result holds for hyperplanes. Now we shall prove theorem 2.
\vspace{0.3cm}

\noindent {\bf Proof of theorem 2:} By \recorde{fe} and \recorde{dc}, a s-mix is determineted by a partition $\{{\cal A},{\cal B}\}$ of the vertex set of $H_{M,M^*}$ such that ${\cal A}\not=\emptyset,{\cal B}\not=\emptyset$ and $AB\not\in E(H_{M,M^*}^s)$, for every $A\in{\cal A}$ and $B\in {\cal B}$, where $H_{M,M^*}^s$ is the graph obtained from $H_{M,M^*}$ by adding the edges $XY$, for every $X\in V(H_{M,M^*})$ and $Y=E(M)\setminus X$.

Now, we shall consider the following graph:
$$G_1=H_{M,M^*}^s/(E(H_{M,M^*}^s)\setminus E(H_{M,M^*})).$$
Observe that we can label naturaly the vertices of $G_1$ using the elements of ${\cal C}'$, since every edge that was contracted joins a vertex belonging to ${\cal C}'$ to its complement which belongs to ${\cal H}'$. Moreover, there is a natural bijection between the connected components of $G_1$ and $H_{M,M^*}^s$.

As ${\cal A}\cap V(G_1)$ is a feaseble set, it follows that it must be admissible and ${\bf (A2)}$ must hold. So, the graph $G_2$ obtained from $G_1$ by adding all the edges $XY$ such that $X,Y\in{\cal C}'$ and $|X\cap Y|=1$ has the same number of connected components as $G_1$.

Now, we shall prove that the graph $G_3$ obtained from $G_2$ by deleting all the edges $XY$ of $H_{M,M^*}$ such that $X,Y\in{\cal H},M|(X\cap Y)=M^*|(X\cap Y)$ and there is $e\in X\setminus Y$ and $f\in Y\setminus X$ such that $\{e,f\}\subseteq cl_{M}(X\cap Y)\bigtriangleup cl_{M^*}(X\cap Y)$ has the same number of connected components of $G_2$. 

Without loss of generality, we may suppose that $X$ is a hyperplane of $M$. Observe that $f\in cl_{M^*}(X\cap Y)$, otherwise there is a circuit $C_1$ of $M$ such that $f\in C_1\subseteq (X\cap Y)\cup\{f\}$ and $C_1\cap (E(M)\setminus X)=\{f\}$. So, there is a cocircuit $D$ of $M$ such that $f\in D\subseteq (X\cap Y)\cup\{f\}$. Hence, by hypothesis, there is a circuit $C$ of $M$ such that $e\in C\subseteq (X\cap Y)\cup\{e\}$. Thus, by orthogonality, $Y$ is a hyperplane of $M^*$.

We shall prove that $C,D\in {\cal C}$. Suppose that $C\not\in{\cal C}$ or $D\not\in{\cal C}$, say $C\not\in{\cal C}$. As $M|(X\cap Y)=M^*|(X\cap Y)$, it follows that $C$ is a cocircuit of $M$ or $C$ contains a cocircuit $D_1$ of $M$ such that $e\in D_1$. In both cases, we arrive at a contradiction, by orthogonality, since $(E(M)\setminus Y)\cap C=\{e\}$. 

By orthogonality, we have that $C'=E(M)\setminus Y$ and $D'=E(M)\setminus X$ both belong to ${\cal C}'$. Let $C''$ and $D''$ be elements of ${\cal C}$ such that $C''\subseteq C'$ and $D''\subseteq D'$. Observe that $C''C'$, when $C''\subset C'$, $D''D'$, when $D''\subset D'$, $C''D$, $D''C$, $C'C$ and $D'D$ are edges of $G_2$. As $XY$ is the edge $C'D'$ of $G_2$, we do not increase the number of connected components of $G_2$ when we delete it. 

Now, we shall describe the edges of $G_3$: (i) $XY$ such that $X\in {\cal C},Y\in{\cal C}'$ and $X\subset Y$; (ii) $XY$ such that $X,Y\in {\cal C}$ and $X\cap Y=\emptyset$; and (iii) $XY$ such that $X,Y\in{\cal C}'$ and $|X\cap Y|=1$. So, theorem 2 follows.\qeds

\section{References}

\begin{description}

\item{[1]} M.Lemos, {\it Matroids having the same connectivity function}, Discrete Mathematics 131 (1994) 153-161.

\item{[2]} M.Lemos, {\it On the connectivity function of a binary matroid}, submited.

\item{[3]} M.Lemos, {\it Uniqueness of the decomposition of the rank fuction of a 2-polimatroid}, submited.

\item{[4]} J.G.Oxley, {\it Matroid Theory}, Oxford University Press, Oxford, 1992.

\item{[5]} P.D.Seymour, {\it On the connectivity funcion of a matroid}, Journal of Combinatorial Theory Series B 45 (1988) 25-30.

\end{description}

\end{document}



***********************************************************************
*****************************************************************
***********************************************************


\section{Some examples}

Let $M_1,M_2,\dots,M_n$ be matroids such that $|C_i\cap C_j|\ge r+2$ for every circuit $C_k$ of $M_k$ for $k\in\{i,j\}\subseteq\{1,2,\dots,n\},i\not=j$ and $r(M_k)\le r$ for every $k\in\{1,2,\dots,n\}$. Suppose that $E(M_1)\cup E(M_2)\cup\cdots\cup E(M_n)\subseteq E$ and let ${\cal C}$ be the family of subset $X$ of $E$ which are circuits of $M_i$ for some $i$ or which has $r+1$ elements and does not contains a circuit of some $M_i$.

\bteo\rotulo{ba} 
${\cal C}$ is a set of circuits of a matroid.
\eteo

\noindent {\bf Proof:} Suppose that $C_1$ and $C_2$ are different elements of ${\cal C}$. Observe that $|C_1\cup C_2|\ge r+2$ or $C_1$ and $C_2$ are circuits of the same $M_i$. So, $C_1\cup C_2\setminus e$ contains a element of ${\cal C}$ for every $e\in C_1\cup C_2$.\qeds

\end{document}


\bteo\rotulo{bd}
If $\{X,Y\}$ is a 2-separation for $M_1$ such that $X\subset A$ or $X\subset B$, then $\{X,Y\}$ is a 2-separation for $M_i$ for every $i\in\{1,2,3,4\}$.
\eteo

\noindent {\bf Proof:} We need to prove that $\{X,Y\}$ is a 2-separation only for $M_2$. Suppose that $\{X,Y\}$ is not a 2-separation for $M_2$ and choose a counter-example $(M_1,M_2)$ such that $|E|$ is as small as possible. Without loss of generality, we may suppose that $X\subset A$.

First, we shall prove that $(M_1,M_2)$ is irredutible. Suppose that this is not the case, and let $N$ be as in the paragraph before \recorde{ba}. $E(N)\cap X\not=\emptyset$, otherwise $(N_1,N_2)$ is contrary to the choice of $(M_1,M_2)$. We also have that $X\setminus E(N)\not=\emptyset$, otherwise $\{X,E(N)\setminus X\}$ is a 2-separation for $N$ or $|E(N)\setminus X|=1$ and in both cases, $\{X,Y\}$ is a 2-separation for $M_2$. $E(N)\setminus X\not=\emptyset$, otherwise $(N_1,N_2)$ is contrary to the choice of $(M_1,M_2)$ --- in this case, we need to replace $X$ by $X'=(X\setminus E(N))\cup e$, where $e\in E(N)\cap E(N_1)$. As $E(N)\cap X\not=\emptyset$, it follows that $E(N)\cap B=\emptyset$ and hence $B\cap (E(N)\cup X)=\emptyset$. So, when $X'=E(N)\setminus e$ and $Y'=E\setminus E(N)$, the sets belonging to 
$${\cal F}=\{X\cap X', X\cap Y',Y\cap X',Y\cap Y'\}$$
are all non-empty. By a result of Lemos and Oxley, for every $Z\in {\cal F}$, there is a matroid $N_Z$ such that $E(N_Z)=\{e_Z\}\cup Z$ such that
$$M_1=N_{X\cap X'}\oplus_2 N_{X\cap Y'\}\oplus_2 N_{Y\cap X'}\oplus_2 N_{Y\cap Y'}\oplus_2 H,$$
where $H$ is a matroid such that $E(H)=\{e_{X\cap X'},e_{X\cap Y'},e_{Y\cap X'},e_{Y\cap Y'}\}$ and $H$ is isomorphic to $U_{3,4}$ or $U_{1,4}$.


\noindent {\bf Proof:} Suppose that $M_1$ is not connected and choose a counter-example $(M_1,M_2)$ such that $|E|$ is as small as possible. By the paragraph before \recorde{ba}, it follows that $(M_1,M_2)$ is irreducible. Let $N$ be a connected component of $M_1$. 

Suppose that $E(N)\subseteq A$. So, $\xi(M_1/e,A\setminus e,B)=2$ and $(M_1/e,M_2/e)\sim (M_3/e,M_4/e)$ is contrary to the choice of $(M_1,M_2)\sim (M_3,M_4)$. Hence $E(N)\cap B\not=\emptyset$ and similarly, $E(N)\cap A\not=\emptyset$. 

So, every connected component of $M_1$ intersects both $A$ and $B$. Thus, $M_1$ has just two connected components $N_1$ and $N_2$. Let $C_i$ be a circuit of $N_i$ which intersects both $A$ and $B$. Observe that $E(N_i)=C_i$, otherwise $(M_1\backslash e,M_2\backslash e)\sim (M_3\backslash e,M_4\backslash e)$ is contrary to the choice of $(M_1,M_2)\sim (M_3,M_4)$, for every $e\in E(N_i)\setminus C_i$ because $\xi(M_1\backslash e;A\setminus e,B\setminus e)=2$.

When $|C_i|>2$, it follows that $|C_i\cap A|\ge 2$ or $|C_i\cap B|\ge 2$, say $|C_i\cap A|\ge 2$. Choose $e\in C_i\cap A$. Observe that $(M_1/e,M_2/e)\sim (M_3/e,M_4/e)$ is contrary to the choice of $(M_1,M_2)\sim (M_3,M_4)$ because $\xi(M_1/e,A\setminus e,B)=2$. Hence $|C_1|=|C_2|=2$.

We arrive at a contradiction, because ${\cal C}(M_1)=\{\{a,b\},\{c,d\}\}$ and ${\cal C}(M_2)=\{\{a,c\},\{b,d\}\}$.\qeds



We shall prove now that $X$ is also a hyperplane in $M_1$. When $X$ spans an element $e$ of $E({\bf M})\setminus X$ in $M_1$, we arrive at a contradiction because ${\bf M}/e$ is connected and non-trivial. Thus, $X$ is closed in $M_1$. When $X$ spans an element $e$ of $E({\bf M})\setminus X$ in $M_2$, we arrive at a contradiction because ${\bf M}/e$ is connected and non-trivial. So, $X$ is spanning in $M_2$. Hence $X$ is a hyperplane in $M_1$.

In this paragraph, we shall prove that $E({\bf M})\setminus X$ is not a circuit of $M_1$. Suppose that $E({\bf M})\setminus X$ is a circuit of $M_1$. As $E({\bf M})\setminus X$ is properly contained in a circuit of $M_2$, it follows that
$$r_{M_1}(E({\bf M})\setminus X)<r_{M_2}(E({\bf M})\setminus X)$$
and by the choice of $X$, we must have 
$$r(M_2)=|X|\le |E({\bf M})\setminus X|\le r(M_2).$$
Thus, we can replace $X$ by $E({\bf M})\setminus X$ and hence $E({\bf M})\setminus X$ is a circuit-hyperplane of $M_1$. Let $e$ be an element of $X$. As ${\bf M}/e$ is trivial, it follows that $M_1/e=M_3/e$ and hence $(E({\bf M})\setminus X)\cup e$ is a circuit of $M_2$. So, $M_2$ is connected and we arrive at a contradiction. 

Suppose that $C\in {\cal C}(M_1)\setminus {\cal C}(M_2)$. Thus, $E({\bf M})\setminus X\subseteq C$. When $a\in C\cap X$, it follows that $M_1/a=M_3/a$ because ${\bf M}/a$ is trivial. Hence $C\setminus a$ is a circuit of $M_2$. We shall prove that $C=(E({\bf M})\setminus X)\cup a$. Suppose that this is not the case, and let $b\in (X\cap C)\setminus a$. So, $C\setminus b$ is also a circuit of $M_2$. We arrive at a contradiction, since $C\setminus\{a,b\}$ is a circuit of $M_2/a$ and $M_3/a$. So, $C=(E({\bf M})\setminus X)\cup a$.

