%===========Preamble for usual latex============================== \documentclass[12pt,letterpaper]{article} \usepackage[dvips]{graphicx} \def \idx #1{{\em #1\/}\index{#1}} %===========Preamble for pdflatex================================= %\documentclass[pdftex,12pt]{article} %\usepackage[pdftex]{graphicx} %\usepackage[hyperindex,colorlinks,backref]{hyperref} %\usepackage{varioref} %\def\AnchorColor{blue} %\def\LinkColor{red} %\def\LinkColorURL{cyan} %\def\LinkColorFile{yellow} %\def \idx #1{{\color{blue} \em #1\/}\index{#1}} %===========End of distinct preambles============================= %\usepackage{a4} \usepackage{makeidx} \setlength{\textwidth}{6truein} \setlength{\textheight}{9truein} \setlength{\oddsidemargin}{0pt} \setlength{\evensidemargin}{0pt} \setlength{\topmargin}{0pt} \makeindex \begin{document} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 8 (1998) \#R8\hfill} \thispagestyle{empty} %MACROS LATEX %=========================================================================== % % D‚finition de la commande 'newthe' en remplacement de 'newtheorem' % % \newthe{NOM}{NOM*}{TITRE}{COMPTEUR}{FONTE1}{FONTE2} % % lemma (num‚rot‚) lemma* (non num‚rot‚) % % usage: \begin{lemma} ou \begin{lemma}[commentaire] % ... ... % \end{lemma} \end{lemma} % %=========================================================================== \makeatletter \def\@@begthe#1{\@ifnextchar[{\@optbegthe#1}{\@begthe#1}} \def\@begthe#1{ #1} \def\@optbegthe#1[#2]{ {#2} #1} \newcommand{\newthe}[6]{ \def\nlni{\par\ifvmode\removelastskip\fi\vskip\baselineskip\noindent} \def\xxxend{\endgroup\vskip\baselineskip} \newenvironment{#1}{\nlni\begingroup\refstepcounter{#4}{#5#3 \thesection.\arabic{#4}}\@@begthe{#6}}{\xxxend} \newenvironment{#2}{\nlni\begingroup{#5#3}\@@begthe{#6}}{\xxxend}} \makeatother %=========================================================================== % % Un mˆme compteur lemmacount, bas‚ sur le num‚ro de section, % est utilis‚ pour tous les environnements de type th‚orŠme, % … l'exception de % % 'claim' et 'property' qui utilisent des compteurs propres % %=========================================================================== \newcounter{lemmacount}[section] \renewcommand{\thelemmacount}{\thesection.\arabic{lemmacount}} %=========================================================================== % % D‚finition des environnements de type th‚orŠme % % \newthe{NOM}{NOM*}{TITRE}{COMPTEUR}{FONTE1}{FONTE2} % %=========================================================================== \newthe{lemma}{lemma*}{Lemma}{lemmacount}{\bf}{\it} \newthe{lemme}{lemme*}{Lemme}{lemmacount}{\bf}{\it} \newthe{proposition}{proposition*}{Proposition}{lemmacount}{\bf}{\it} \newthe{theorem}{theorem*}{Theorem}{lemmacount}{\bf}{\it} \newthe{conjecture}{conjecture*}{Conjecture}{lemmacount}{\bf}{\it} \newthe{corollary}{corollary*}{Corollary}{lemmacount}{\bf}{\it} \newthe{axiom}{axiom*}{}{lemmacount}{\bf}{\it} \newthe{prop}{prop*}{Proposition}{lemmacount}{\bf}{\it} \newthe{statement}{statement*}{}{lemmacount}{\bf}{\it} \newthe{theoreme}{theoreme*}{Th\'eor\`eme}{lemmacount}{\bf}{\it} \newthe{corollaire}{corollaire*}{Corollaire}{lemmacount}{\bf}{\it} \newthe{problem}{problem*}{Problem}{lemmacount}{\bf}{\it} \newthe{solution}{solution*}{Solution}{lemmacount}{\bf}{\it} \newthe{exercise}{exercise*}{Exercise}{lemmacount}{\bf}{\rm} \newthe{exercice}{exercice*}{Exercice}{lemmacount}{\bf}{\rm} \newthe{construction}{construction*}{Construction}{lemmacount}{\bf}{\rm} \newthe{definition}{definition*}{Definition}{lemmacount}{\bf}{\rm} \newthe{deefinition}{deefinition*}{D\'efinition}{lemmacount}{\bf}{\rm} \newthe{example}{example*}{Example}{lemmacount}{\bf}{\rm} \newthe{exemple}{exemple*}{Exemple}{lemmacount}{\bf}{\rm} \newthe{remark}{remark*}{Remark}{lemmacount}{\bf}{\rm} \newthe{note}{note*}{Note}{lemmacount}{\bf}{\rm} \newthe{question}{question*}{Question}{lemmacount}{\bf}{\rm} \newthe{algorithm}{algorithm*}{Algorithm}{lemmacount}{\bf}{\tt} \newcounter{claimcount} \newenvironment{claim}{ \nlni\begingroup\refstepcounter{claimcount}{ \bf Claim \arabic{claimcount}.}\it }{\xxxend} \newenvironment{claim*}{ \nlni\begingroup{\bf Claim.}\it }{\xxxend} \newcounter{propertycount} \newenvironment{property}{ \nlni\begingroup\refstepcounter{propertycount}{ \bf Claim \arabic{propertycount}.}\it }{\xxxend} %=========================================================================== % % Environnements 'proof', 'preuve', 'proofof', 'preuvede' % Symbole de fin de preuve 'qed' % %========================================================================== \newenvironment{proof}{\nlni\begingroup{\it Proof. }\rm}{ \endgroup\vskip\baselineskip} \newenvironment{preuve}{\nlni\begingroup\noindent{\it Preuve. }\rm}{ \endgroup\vskip\baselineskip} \newenvironment{proofof}{\nlni\begingroup\noindent{\it Proof of }\rm}{ \endgroup\vskip\baselineskip} \newenvironment{preuvede}{\nlni\begingroup\noindent{\it Preuve de }\rm}{ \endgroup\vskip\baselineskip} \def\sq{\hbox{\rlap{$\sqcap$}$\sqcup$}} \def\qed{\ifmmode\sq\else{\unskip\nobreak\hfil \penalty50\hskip1em\null\nobreak\hfil\sq \parfillskip=0pt\finalhyphendemerits=0\endgraf}\fi} %=========================================================================== % % \numberlikearticle num‚ro d'‚quation sans num‚ro de chapitre % \numberlikebook " avec num‚ro de chapitre (defaut) % les num‚ros de tables et de figures suivent les mˆmes conventions % %=========================================================================== \def\numberlikearticle{\global\def\theequation{\thesection.\arabic{equation}} \global\def\thetable{\thesection.\arabic{table}} \global\def\thefigure{\thesection.\arabic{figure}}} \def\numberlikebook{\global\def\theequation{\thesection.\arabic{equation}} \global\def\thetable{\thesection.\arabic{table}} \global\def\thefigure{\thesection.\arabic{figure}}} % MACROS TEX %\font\sc = cmcsc10 \def \topic #1{\begingroup\medskip\noindent {\bf #1.}} \def \endtopic {\par\medskip\endgroup} \def \itm #1{ \item[{\rm (#1)}] } \def \resp #1{(resp. #1)} \def \ath #1{{\sc #1}} \def \wrt {with respect to } % % LOGIQUE % \def \forsome {\hbox{ for some }} \let \implique = \Longrightarrow \def \iff {if and only if } % % ENSEMBLES % \def \cardinal #1{ |#1| } \def \set #1{\{#1\}} \let \inter = \cap \let \union = \cup \let \ired \wedge \let \ured \vee % % OPERATIONS SUR FAMILLES % ET ENSEMBLES % \def \famille #1#2{(#1 : #2)} \def \maxind #1#2{\max_{#2} #1} \def \setof #1#2{\{#1 : #2\}} \def \sumind #1#2{\sum_{#2} #1} \def \unionind #1#2{\bigcup_{#2} #1} % % ALGEBRE % \def \N {\hbox{\bf N}} \def \R {\hbox{\bf R}} \def \Z {\hbox{\bf Z}} \def \restrict #1#2{#1_{|#2}} % % MATRICES % %\def \cof #1#2{#1_{#2}} %\def \up #1#2{#1^{#2}} %\def \upcof #1#2#3{#1^{#2}_{#3}} % % MATROIDES % \let \Mat = M \let \Matset = E \let \Matelm = x \let \Matrank = r \def \matrank #1{\Matrank(#1)} \let \Matbase = B \let \Circuit = C \let \contract = / \let \delete = \setminus \def \dual #1{#1^*} % % GRAPHES % \let \Graph = G \let \Vset = V \let \Wset = W \let \Vx = v \let \Vy = w \let \Edge = e \let \Hedge = h \def \vset #1{\Vset(#1)} \let \Half = h \def \half #1{\Half(#1)} \let \Ncomp = k \def \ncomp #1{\Ncomp(#1)} \let \Eultour = T \let \Allowed = U \def \rst #1#2{#1_{#2}} \def \detach #1#2{#1||#2} \def \open #1#2{#1|#2} % % SUPPORTS DE MULTIMATROIDES % \let \Mmset = U \let \Mmelm = x \let \Mmelmb = y \let \Mmpart = \Omega \let \Mmclass = \omega \def \Mmcarrier {(\Mmset, \Mmpart)} \let \Mmindset = V \let \Mmind = v \def \subtrans #1{{\cal S}(#1)} \let \Sbt = S \def \trans #1{{\cal T}(#1)} \let \Trs = T \def \skew #1#2{sk(#1,#2)} \def \rdunion{\setbox0=\hbox{$\cup$}% \mskip 4mu plus 2mu% \hbox to \wd0{$\cup$\kern-\wd0% \hfil\raise 2pt\hbox{${\scriptscriptstyle r}$}\hfil} \mskip 5mu plus 1mu} % % MULTIMATROIDES % \let \Mm = Q \def \mm #1{\Mm(#1)} \let \Mmrank = r \def \mmrank #1{\Mmrank(#1)} \def \Mmtriple {(\Mmset,\Mmpart,\Mmrank)} \def \Mmtripleprime {(\Mmset',\Mmpart',\Mmrank')} \def \mmrankprime #1{\Mmrank'(#1)} \def \Mmbaseset {{\cal \Mmbase}} \def \mmbaseset #1{\Mmbaseset(#1)} \let \Mmbase = B \def \mmbase #1{\Mmbase(#1)} \def \Mmindepset {{\cal \Mmindep}} \def \mmindepset #1{\Mmindepset(#1)} \let \Mmindep = I \let \Mmindepb = J \def \Mmcircuitset {{\cal \Mmcircuit}} \def \mmcircuitset #1{\Mmcircuitset(#1)} \let \Mmcircuit = C \let \Minor = | \def \minor #1#2{#1 \Minor #2} \def \rest #1#2{#1[#2]} \let \Trace = \cap \def \trace #1#2{#1 \Trace #2} \def \freesum #1#2{\mm{#1,#2}} \let \Proj = p \def \proj #1{\Proj(#1)} \def \cov #1{Cov(#1)} % % MULTIMATROIDES (ET SYSTEMES ISOTROPES) EULERIENS % \let \Spl = S \def \spl #1{\Spl(#1)} \let \Splb = T \let \Locspl = \Spl \let \Locsplb = \Splb \def \locspl #1{\Locspl_{#1}} \def \locsplb #1{\Locsplb_{#1}} \def \locsplpr #1{\Locspl'_{#1}} \def \locsplsec #1{\Locspl''_{#1}} \def \locsplbpr #1{\Locsplb'_{#1}} \def \locsplbsec #1{\Locsplb''_{#1}} % % DELTA-MATROIDES ET 2-MATROIDES % \let \Dm = D \def \dm #1{\Dm(#1)} \let \Dmset = V \let \Dmelm = v \let \Dmelma = v \let \Dmelmb = w \let \Dmbase = F \def \Dmbaseset {{\cal \Dmbase}} \def \Dmpair {(\Dmset, \Dmbaseset)} \let \Twist = \Delta \def \twist #1#2{#1 \Twist #2} \let \Twistset = X \def \Twistclass {Tw} \def \twistclass #1{\Twistclass(#1)} \def \upper #1{M(#1)} \def \lower #1{m(#1)} \let \Polyrank = R \def \polyrank #1{\Polyrank(#1)} %FIN MACROS TEX %============================================================================= \title{Multimatroids II. Orthogonality, minors and connectivity} \author{ Andr\'{e} Bouchet \\ D\'{e}partement d'Informatique \\ Universit\'{e} du Maine \\ 72017 Le Mans Cedex \\ France \\ {\small \tt bouchet@lium.univ-lemans.fr} } \date{\small Submitted: May 15, 1997. Accepted: November 20, 1997} \maketitle \begin{abstract} A multimatroid is a combinatorial structure that encompasses matroids, delta-matroids and isotropic systems. This structure has been introduced to unify a theorem of Edmonds on the coverings of a matroid by independent sets and a theorem of Jackson on the existence of pairwise compatible Euler tours in a 4-regular graph. Here we investigate some basic concepts and properties related with multimatroids: matroid orthogonality, minor operations and connectivity. {\bf Mathematical Reviews: 05B35} \end{abstract} \section{Introduction} In a preceding paper \cite {Bou:Mm1} we unified a theorem of \ath {Jackson} \cite {Jackson1}, on the existence of pairwise compatible Euler tours in a 4-regular graph, with a theorem of \ath {Edmonds} \cite {Edmonds:Cov}, on the minimum number of independent sets to cover the ground-set of a matroid. For this purpose we introduced a new combinatorial structure, called a multimatroid, which unifies matroids, delta-matroids and isotropic systems. We complete in the present paper and subsequent ones \cite {Bou:Mm3,Bou:Mm4} the basic properties of multimatroids. In Section \ref {S.Known} we review the results already proved in \cite {Bou:Mm1}. We also introduce the extended submodularity inequality, equivalent to a kind of supermodularity inequality used by \ath {Jackson} \cite {Jackson1}, and we relate it with the bisubmodularity inequality introduced by \ath {Kabadi} and \ath {Chandrasekaran} \cite {KabadiChandra}. In Section \ref {S.Orthog} we introduce an orthogonality relation between matroids, similar to the classical strong map relation, and we show that a multimatroid gives raise to orthogonal matroids. Conversely we derive in Section \ref {S.FreeSum} a multimatroid from a sequence of orthogonal matroids and we retrieve as a particular case the generalized matroids of \ath {Tardos} \cite {Tardos:gmat}. We introduce the minor operations and the separators in Sections \ref {S.Minors} and \ref {S.Separ}. Finally we study some relations between multimatroids and Eulerian graphs in Section \ref {S.CycSplit}. \section{A survey} \label{S.Known} \begingroup \let \Sbt = A \let \Sbtb = B Consider a partition $\Mmpart$ of a finite set $\Mmset$. Each class of $\Mmpart$ is called a \idx {skew class}. Each pair of distinct elements belonging to the same skew class is called a \idx {skew pair}. A \idx {subtransversal} \resp {\idx {transversal}} of $\Mmpart$ is a subset $\Sbt$ of $\Mmset$ such that $\cardinal {\Sbt \inter \Mmclass} \le 1$ \resp {$\cardinal {\Sbt \inter \Mmclass} = 1$} holds for every $\Mmclass$ in $\Mmpart$. Two subtransversals are \idx {compatible} if their union is also a subtransversal. We denote by $\subtrans \Mmpart$ \resp {$\trans \Mmpart$} the set of subtransversals \resp {transversals} of $\Mmpart$. A \idx {weak multimatroid} is a triple $\Mm = \Mmtriple$ with a partition $\Mmpart$ of a finite set $\Mmset$ and a \idx {rank function} $\Mmrank : \subtrans \Omega \to \N$ satisfying the three following axioms: \begin{statement} \label{mm1} $\mmrank \emptyset = 0$; \end{statement} \begin{statement} \label{mm2} $\mmrank \Sbt \le \mmrank {\Sbt + x} \le \mmrank \Sbt + 1$ is satisfied for every subtransversal $\Sbt$ of $\Mmpart$ and every $x$ in $\Mmset$ provided that $\Sbt$ is disjoint from the skew class containing $x$; \end{statement} \begin{statement} \label{mm3} {\bf Submodularity inequality:} $\mmrank \Sbt + \mmrank \Sbtb \ge \mmrank {\Sbt \union \Sbtb} + \mmrank {\Sbt \inter \Sbtb}$ is satisfied for every pair of compatible subtransversals $\Sbt$ and $\Sbtb$ of $\Mmpart$; \end{statement} \noindent The following axiom has also to be satisfied in order to derive interesting properties. Then $\Mm$ is called a \idx {multimatroid}. \begin{statement} \label{mm4} $\mmrank {\Sbt+x} - \mmrank \Sbt + \mmrank {\Sbt + y} - \mmrank \Sbt \ge 1$ is satisfied for every subtransversal $\Sbt$ of $\Mmpart$ and every skew pair $\set {x,y}$ provided that $\Sbt$ is disjoint from the skew class including $\set {x,y}$. \end{statement} If each skew class has cardinality equal to the positive integer $q$, then $\Mm$ a \idx {$q$-matroid}. An \idx {independent set} is a subtransversal $\Mmindep$ of $\Mmpart$ such that $\mmrank \Mmindep = \cardinal \Mmindep$, a \idx {base} is a maximal independent set, and a \idx {circuit} is a subtransversal $\Mmcircuit$ of $\Mmpart$ that is not independent and is minimal with this property. We denote by $\mmindepset \Mm$, $\mmbaseset \Mm$ and $\mmcircuitset \Mm$ the collections of independent sets, bases and circuits, respectively. If $\Sbt$ is a subtransversal of $\Mmpart$, then $\mmrank P$ is defined for every subset $P$ of $\Sbt$. The axioms \ref {mm1} to \ref {mm3} imply that the restriction of $\Mmrank$ to the power-set of $\Sbt$ is the rank function of a matroid on the set $\Sbt$, denoted by $\rest \Mm \Sbt$ and called the \idx {submatroid} induced on $\Sbt$. The independent sets \resp {circuits} of $\rest \Mm \Sbt$ are the independent sets \resp {circuits} of $\Mm$ included in $\Sbt$. If $\Mm$ is a 1-matroid, then $\Mmset$ is a transversal of $\Mmpart$ and we identify $\Mm$ to the matroid $\rest \Mm \Mmset$. The inverse construction that associates a 1-matroid to a matroid is obvious. The multimatroid $\Mm$ may be thought as the aggregation of the submatroids $\rest \Mm \Sbt$, when $\Sbt$ ranges in the collection of subtransversals of $\Mmpart$, which gives the name to the structure. A multimatroid $\Mm$ will often be given with a \idx {projection} onto a set $\Mmindset$: this is a surjective mapping $\Proj : \Mmset \to \Mmindset$ such that $\proj {\Mmelm_1} = \proj {\Mmelm_2}$ is satisfied \iff the elements $\Mmelm_1$ and $\Mmelm_2$ belong to the same skew class. We set $\Mmpart_\Mmind = \setof \Mmind {\proj \Mmelm = \Mmind}$ for every element $\Mmind$ in $\Mmindset$, so that $\Mmpart = \setof {\Mmpart_\Mmind} {\Mmind \in \Mmindset}$. We also say that $\Mm$ is \idx {indexed} on $\Mmindset$. For every transversal $\Trs$ of $\Mmpart$, the restriction $\restrict \Proj \Trs$ is a bijection from $\Trs$ onto $\Mmindset$. The isomorphic image of $\rest \Mm \Trs$ by $\restrict \Proj \Trs$ is called the projection of $\rest \Mm \Trs$ and is denoted by $\proj {\rest \Mm \Trs}$. \subsection*{Properties of the independent sets, circuits, and bases} Consider a, possibly weak, multimatroid $\Mm = \Mmtriple$. For every subtransversal $\Sbt$ of $\Mmpart$, the relation \[ \mmrank \Sbt = \maxind {\cardinal \Mmindep} {\Mmindep \subseteq \Sbt, \Mmindep \in \mmindepset \Mm} \] \noindent is satisfied. Therefore $\Mm$ is determined when either $\mmindepset \Mm$, $\mmbaseset \Mm$ or $\mmcircuitset \Mm$ is known. In the two following characterizations the properties (a) to (c) correspond to the axioms \ref {mm1} to \ref {mm3} and the property (d) corresponds to Axiom \ref {mm4}. A pair $\Mmcarrier$ with a finite set $\Mmset$ and a partition $\Mmpart$ is called a \idx {partitioned set}. \begin{prop} \label{P.AxiomIndep} {\rm \cite {Bou:Mm1}} Let $(\Mmset, \Mmpart)$ be a partitioned set. A subset $\Mmindepset$ of $\subtrans \Mmpart$ is the collection of independent sets of a multimatroid on $(\Mmset, \Mmpart)$ \iff the following properties are satisfied: \begin{enumerate} \itm a $\emptyset \in \Mmindepset$; \itm b If $\Mmindep \in \Mmindepset$ and $\Mmindepb \subseteq \Mmindep$ then $\Mmindepb \in \Mmindepset$; \itm c {\bf Augmentation:} If $\Mmindep, \Mmindepb \in \Mmindepset$ are compatible and $\cardinal \Mmindep < \cardinal \Mmindepb$ then $\Mmindep + x \in \Mmindep$ for some $x \in \Mmindepb \setminus \Mmindep$; \itm d If $\Mmindep \in \Mmindepset$ and $\set{x,y}$ is a pair included in a class of $\Mmpart$ disjoint from $\Mmindep$, then $\Mmindep + x \in \Mmindepset$ or $\Mmindep + y \in \Mmindepset$. \end{enumerate} \end{prop} \begin{prop} \label{P.AxiomCircuit} {\rm \cite {Bou:Mm1}} Let $(\Mmset, \Mmpart)$ be a partitioned set. A subset $\Mmcircuitset$ of $\subtrans \Mmpart$ is the collection of circuits of a multimatroid on $(\Mmset, \Mmpart)$ \iff the following properties are satisfied: \begin{enumerate} \itm a $\emptyset \not\in \Mmcircuitset$; \itm b If $\Mmcircuit_1, \Mmcircuit_2 \in \Mmcircuitset$ and $\Mmcircuit_1 \subseteq \Mmcircuit_2$ then $\Mmcircuit_1 = \Mmcircuit_2$; \itm c {\bf Elimination:} If $\Mmcircuit_1, \Mmcircuit_2 \in \Mmcircuitset$ are distinct and compatible and $x \in \Mmcircuit_1 \inter \Mmcircuit_2$, then $\Mmcircuit \subseteq (\Mmcircuit_1 \union \Mmcircuit_2) - x$ for some $\Mmcircuit \in \Mmcircuitset$; \itm d If $\Mmcircuit_1, \Mmcircuit_2 \in \Mmcircuitset$, then $\Mmcircuit_1 \union \Mmcircuit_2$ cannot include precisely one skew pair. \end{enumerate} \end{prop} A multimatroid is said to be \idx {nondegenerate} if each of its skew classes has at least cardinality 2. \begin{prop} \label {P.BaseIsTrans} The bases of a nondegenerate multimatroid are transversal. \end{prop} \begin{proof} Suppose indirectly that a base $\Mmbase$ of a nondegenerate multimatroid is not transversal. Consider a skew class $\Mmclass$ disjoint from $\Mmbase$. Since $\Mm$ is nondegenerate we can chose distinct elements $x$ and $y$ in $\Mmclass$. Proposition \ref {P.AxiomIndep}(d) implies that $\Mmbase + x$ or $\Mmbase + y$ is independent, and so $\Mmbase$ cannot be a base. \qed \end{proof} \begin{corollary} \label{C.BasesQmat} The bases of a $q$-matroid are transversal if $q \ge 2$. \end{corollary} Let $\Mmset'$ be a subset of $\Mmset$. The \idx {restriction} of $\Mm$ to $\Mmset'$ is $\rest \Mm {\Mmset'} = (\Mmset', \Mmpart', \Mmrank')$, where $\Mmpart' = \setof {\Mmclass \inter \Mmset'} {\Mmclass \in \Mmpart, \Mmclass \inter \Mmset' \neq \emptyset}$ and $\Mmrank'$ is the restriction of $\Mmrank$ to $\subtrans {\Mmpart'}$. Clearly $\rest \Mm {\Mmset'}$ is a multimatroid. We say that $\rest \Mm {\Mmset'}$ is \idx {spanning} if $\Mmset' \inter \Mmclass$ is nonempty for every skew class $\Mmclass$ of $\Mm$. \begin{prop} \label{P.SpanningRest} If $\rest \Mm {\Mmset'}$ is a nondegenerate spanning restriction of a (nondegenerate) multimatroid $\Mm$, then the bases of $\rest \Mm {\Mmset'}$ are the bases of $\Mm$ contained in $\Mmset'$. \end{prop} \begin{proof} Set $\Mm = \Mmtriple$ and $\Mm' = (\Mmset', \Mmpart', \Mmrank')$. Every base of $\Mm$ contained in $\Mmset'$ is obviously a base of $\Mm'$. Conversely let $\Mmbase'$ be a base of $\Mm'$. Then $\Mmbase'$ is an independent set of $\Mm$ contained in $\Mmset'$. Since $\rest \Mm {\Mmset'}$ is nondegenerate, $\Mmbase'$ is a transversal of $\Mmpart'$ by Proposition \ref {P.BaseIsTrans}. Since $\rest \Mm {\Mmset'}$ is spanning, $\Mmbase'$ is also a transversal of $\Mmpart$. Hence $\Mmbase'$ is a transversal independent set of $\Mm$, which is a base of $\Mm$. \qed \end{proof} Proposition \ref {P.BaseIsTrans} implies that the bases of a nondegenerate multimatroid are equicardinal. It is easy to construct a degenerate multimatroid where this property is false. Proposition \ref {P.SpanningRest} also is false when it is applied to a restriction that is degenerate or not spanning. \subsection*{Relation with delta-matroids} The structure of delta-matroid has been independently introduced by \ath {Dress} and \ath {Havel} \cite {DressHav:Metro}, \ath {Chandrasekaran} and \ath {Kabadi} \cite {Chandra:Pseudo}, and the author \cite {Bou:Delmat}. A \idx {delta-matroid} is a set-system $\Dm = \Dmpair$, where $\Dmset$ is a finite set and $\Dmbaseset$ is a nonempty collection of subsets of $\Dmset$, called the \idx {feasible sets} or \idx {bases}, satisfying the following \idx {symmetric exchange axiom}: \begin{axiom} \label{Dmaxiom} For $\Dmbase_1, \Dmbase_2 \in \Dmbaseset$, for $\Dmelma \in \Dmbase_1 \Delta \Dmbase_2$, there is $\Dmelmb \in \Dmbase_1 \Delta \Dmbase_2$ with $\Dmbase_1 \Delta \set {\Dmelma, \Dmelmb} \in \Dmbaseset$. \end{axiom} \begin{prop} {\rm \cite {Bou:Delmat}} A nonempty collection $\Dmbaseset$ of subsets of a finite set $\Dmset$ is the collection of bases of a matroid \iff $\Dmbaseset$ satisfies the symmetric exchange axiom and the members of $\Dmbaseset$ are equicardinal. \end{prop} Accordingly one identifies a matroid to a delta-matroid with equicardinal bases. For a set system $\Dm = \Dmpair$ and a subset $\Twistset$ of $\Dmset$, set $\twist \Dmbaseset \Twistset = \setof {\Dmbase \Delta \Twistset} {\Dmbase \in \Dmbaseset}$ and $\twist \Dm \Twistset = (\Dmset, \twist \Dmbaseset \Twistset)$. If $\Dmbaseset$ satisfies the symmetric exchange axiom then $\twist \Dmbaseset \Twistset$ also clearly satisfies the same axiom. Hence $\twist \Dm \Twistset$ is a delta-matroid if $\Dm$ is a delta-matroid. The transformation $\Dm \mapsto \twist \Dm \Twistset$ is called \idx {twisting}. If $\Dm$ is a matroid and $\Twistset = \Dmset$, then $\twist \Dm \Twistset$ is the matroid dual of $\Dm$. A \idx {paired set} is a pair $\Mmcarrier$ with a finite set $\Mmset$ and a partition $\Mmpart$ of $\Mmset$ into pairs. \begin{theorem} {\rm \cite {Bou:Mm1}} \label{T.2MatAndDelta} Let $\Mmcarrier$ be a paired set and let $\Trs$ be a transversal of $\Mmpart$. A nonempty collection $\Mmbaseset$ of transversals of $\Mmpart$ is the set of bases of a 2-matroid $\Mm$ defined on $\Mmcarrier$ \iff $\setof {\Mmbase \inter \Trs} {\Mmbase \in \Mmbaseset}$ is the collection of bases of a delta-matroid. \end{theorem} The delta-matroid of Theorem \ref {T.2MatAndDelta} is called the \idx {trace} of $\Mm$ on $\Trs$ and is denoted by $\trace \Mm \Trs$. Consider a projection $\Proj$ of $\Mm$ onto a set $\Mmindset$. The isomorphic image of $\trace \Mm \Trs$ by $\restrict \Proj \Trs$ is a delta-matroid on the ground-set $\Mmindset$, which we denote by $\proj {\trace \Mm \Trs}$. For every transversal $\Trs'$ of $\Mmpart$, we easily verify that \[ \proj {\trace \Mm {\Trs'}} = \twist {\proj {\trace \Mm {\Trs}}} \proj {\Trs \Delta \Trs'}. \] \noindent The subset $\Twistset = \proj {\Trs \Delta \Trs'}$ ranges in the power-set of $\Mmindset$ when $\Trs'$ ranges in the set of transversals of $\Mmpart$. Hence, if we fix $\Trs$ and we set $\Dm = \proj {\trace \Mm {\Trs}}$, the delta-matroid $\proj {\trace \Mm {\Trs'}} = \twist \Dm \Twistset$ ranges in the twisting class of $\Dm$. Conversely the following construction shows that every twisting class of delta-matroids can be derived from an indexed 2-matroid. \begin{construction} \label {Cons.Lift} Let $\Dm = \Dmpair$ be a delta-matroid. Set \begin{eqnarray*} \Dmset_i &=& \setof {\Dmelm_i} {\Dmelm \in \Dmset}, \,\, i = 1, 2, \\ \Mmset &=& \Dmset_1 + \Dmset_2 \\ \Mmpart_\Dmelm &=& \set {\Dmelm_1, \Dmelm_2}, \,\, \Dmelm \in \Dmset \\ \Mmpart &=& \setof {\Mmpart_\Dmelm} {\Dmelm \in \Dmset} \\ \Dmbase_i &=& \setof {\Dmelm_i} {\Dmelm \in \Dmbase}, \,\, \Dmbase \in \Dmbaseset, \,\, i = 1, 2, \\ \Mmbaseset &=& \setof {\Dmbase_1 \union (\Dmset_2 \setminus \Dmbase_2)} {\Dmbase \in \Dmbaseset}. \end{eqnarray*} \noindent Theorem \ref {T.2MatAndDelta} implies that $\Mmbaseset$ is the collection of bases of a 2-matroid $\Mm$ defined on $\Mmcarrier$. We have $\Dm = \proj {\trace \Mm {\Dmset_1}}$, where $\Proj$ is the projection of $\Mm$ onto $\Dmset$ defined by the relation $\proj {\Dmelm_1} = \proj {\Dmelm_2} = \Dmelm$ for every $\Dmelm$ in $\Dmset$. We call $\Mm$ the \idx {lift} of $\Dm$. \end{construction} \subsection*{Eulerian multimatroids} A graph (finite and undirected) $\Graph$ is said to be \idx {Eulerian} if each vertex has even degree. The number of components of $\Graph$ is denoted by $\ncomp \Graph$. We consider that each edge $\Edge$ of $\Graph$ is incident to two \idx {half-edges} $\Hedge_1$ and $\Hedge_2$, each of them incident to one vertex, the ends of $\Edge$ being the vertices incident to $\Hedge_1$ and $\Hedge_2$. The set of half-edges incident to a vertex $\Vx$ is denoted by $\half \Vx$. A pair of half-edges incident to the same vertex \resp {edge} is called a \idx {vertex-transition} \resp {\idx {edge-transition}}. Assume $\Graph$ is Eulerian. A \idx {local splitter} incident to $\Vx$ is a pair $\locspl \Vx = \set {\locsplpr \Vx, \locsplsec \Vx}$, where $\locsplpr \Vx$ and $\locsplsec \Vx$ are complementary subsets of $\half \Vx$ having even cardinalities. If $\locsplpr \Vx$ and $\locsplsec \Vx$ are nonempty, then $\locspl \Vx$ is said to be \idx {proper}. A \idx {splitter} is a set $\Spl = \setof {\locspl \Vx} {\Vx \in \Wset}$, where $\Wset$ is a subset of vertices, and $\locspl \Vx$ is a proper local splitter incident to $\Vx$. The splitter $\Spl$ is \idx {complete} if $\Wset$ is equal to the set of vertices of $\Graph$. To \idx {detach} the proper local splitter $\locspl \Vx$ is to replace the vertex $\Vx$ by two vertices $\Vx'$ and $\Vx''$ such that $\half {\Vx'} = \locsplpr \Vx$ and $\half {\Vx''} = \locsplsec \Vx$. The resulting graph, denoted by $\detach \Graph {\locspl \Vx}$, is still an Eulerian graph. To \idx {detach} the splitter $\Spl$ is to replace $\Graph$ by $\detach \Graph \Spl = \detach {\detach {\detach {\detach \Graph {\locspl {\Vx_1}}} {\locspl {\Vx_2}}} \cdots} {\locspl {\Vx_p}}$, where $(\Vx_1, \Vx_2, \cdots, \Vx_p)$ is an enumeration of $\Wset$. (Obviously $\detach \Graph \Spl$ does not depend on the actual enumeration.) The \idx {rank} of the splitter $\Spl$ is $\cardinal \Spl - \ncomp {\detach \Graph \Spl} + \ncomp \Graph$. Consider a subset $\Allowed$ of proper local splitters of $\Graph$. A splitter contained in $\Allowed$ is said to be \idx {allowed} and the pair $\rst \Graph \Allowed = (\Graph, \Allowed)$ is called a \idx {restricted Eulerian graph}. Denote by $\vset {\rst \Graph \Allowed} = \Vset$ the subset of vertices of $\Graph$ that are incident to some local splitter in $\Allowed$ and, for each $\Vx$ in $\Vset$, denote by $\Mmpart_\Vx$ the set of local splitters in $\Allowed$ incident to $\Vx$. The set $\Mmpart = \setof {\Mmpart_\Vx} {\Vx \in \Vset}$ is a partition of $\Allowed$ and $\subtrans \Mmpart$ is the set of allowed splitters. Denote by $\Mmrank$ the restriction of the splitter rank function to $\subtrans \Mmpart$ and set $\mm {\rst \Graph \Allowed} = \Mmtriple$. It is proved in \cite {Bou:Mm1} that $\mm {\rst \Graph \Allowed}$ is a weak multimatroid. It is a multimatroid if the following \idx {skewness condition} is satisfied: \begin{statement} If $\locspl \Vx = \set {\locsplpr \Vx, \locsplsec \Vx}$ and $\locsplb \Vx = \set {\locsplbpr \Vx, \locsplbsec \Vx}$ are distinct allowed local splitters incident to the same vertex $\Vx$, then $\cardinal {\locsplpr \Vx \inter \locsplbpr \Vx}$ is odd. \end{statement} \noindent Note that $\mm {\rst \Graph \Allowed}$ is naturally indexed on $\Vset$. We set $\mm \Graph = \mm {\rst \Graph \Allowed}$ when all splitters are allowed. The (weak) multimatroid $\mm {\rst \Graph \Allowed}$ is said to be \idx {Eulerian}. \subsection*{The 3-matroid of a 4-regular Graph} In the particular case where $\Graph$ is a 4-regular graph, every proper local splitter is made of two disjoint vertex-transitions. Accordingly it is also called a \idx {bitransition}. The skewness condition is satisfied because, if $\set {\locsplpr \Vx, \locsplsec \Vx}$ and $\set {\locsplbpr \Vx, \locsplbsec \Vx}$ are two bitransitions incident to the same vertex, we have $\cardinal {\locsplpr \Vx \inter \locsplbpr \Vx} = 1$. Moreover there are three bitransitions incident to each vertex. Hence $\mm \Graph$ is a 3-matroid. Assume $\Graph$ is connected. We describe an \idx {Euler tour} $\Eultour$ by an enumeration of the half-edges $\Half'_0 \Half''_0 \Half'_1 \Half''_1 \cdots \Half'_{m-1} \Half''_{m-1}$ such that $\set {\Half'_i, \Half''_i}$ is an edge-transition and $\set {\Half''_i, \Half'_{i+1}}$ is a vertex-transition, for $0 \le i < m$, with the convention $\Hedge'_{i+1} = \Hedge'_0$ when $i = m - 1$ \footnote{ An Euler tour is usually defined by means of an alternate sequence of edges and vertices. Note that the graph consisting of one vertex $\Vx$ incident to two loops $\Edge_1$ and $\Edge_2$, where $\Edge_i$ is incident to the half-edges $\Hedge'_i$ and $\Hedge''_i$, for $i = 1, 2$, has two Euler tours described by $\Hedge'_1 \Hedge'_2 \Hedge''_1 \Hedge''_2$ and $\Hedge'_1 \Hedge'_2 \Hedge''_2 \Hedge''_1$, whereas the usual definition gives only one Euler tour described by $\Vx \Edge_1 \Vx \Edge_2$. }. For each vertex $\Vx$ let $\Eultour_\Vx$ be the bitransition made of the two vertex-transitions incident to $\Vx$ and belonging to $\setof {\set {\Half''_i, \Half'_{i+1}}} {0 \le i < m}$. Then $\mmbase \Eultour := \setof {\Eultour_\Vx} {\Vx \in \Vset}$ is a complete splitter and $\detach \Graph {\mmbase \Eultour}$ is a regular graph of degree 2 that admits $\Eultour$ as a (unique) Euler tour. We have $\ncomp {\detach \Graph {\mmbase \Eultour}} = \ncomp \Graph = 1$, and so $\mmbase \Eultour$ is a base of the 3-matroid $\mm \Graph$. Conversely if $\Mmbase$ is a base of $\mm \Graph$, then the unique Euler tour $\Eultour$ of $\detach \Graph \Mmbase$ is also an Euler tour of $\Graph$ such that $\Mmbase = \mmbase \Eultour$. Hence there is a bijective correspondance between the Euler tours of $\Graph$ and the bases of $\mm \Graph$. \subsection*{Theorems of Jackson and Edmonds} \begingroup \def \Edgerank {\Mmrank_e} \def \edgerank #1{\Edgerank(#1)} \def \Splrank {\Mmrank_s} \def \splrank #1{\Splrank(#1)} \def \mrj #1{\Mmrank^j(#1)} Let $\Mm = \famille {\Mm^j} {j \in J}$ be a finite family of multimatroids defined on the same partitioned set $\Mmcarrier$. Denote by $\mmbaseset \Mm$ the set of families $\Mmbase = \famille {\Mmbase^j} {j \in J}$, where $\Mmbase^j$ is a base of $\Mm^j$. Set $\cov \Mmbase = \unionind {\Mmbase^j} {j \in J}$ for every $\Mmbase$ in $\mmbaseset \Mm$. The \idx {rank function} of $\Mm$ is the mapping $\Mmrank$, defined for $S$ in $\subtrans \Mmpart$ by the formula $\mmrank S = \sumind {\mrj S} {j \in J}$, where $\Mmrank^j$ is the rank function of $\Mm^j$. \begin{theorem} {\rm \cite{Bou:Mm1}} \label{T.CovMulti} A finite family $\Mm = \famille {\Mm^j} {j \in J}$ of multimatroids defined on the same partitioned set $\Mmcarrier$, with the rank function $\Mmrank$, satisfies \[ \max_{\Mmbase \in \mmbaseset \Mm} \cardinal {\cov \Mmbase} = \min_{S \in \subtrans \Mmpart} (\mmrank S + \cardinal {\Mmset \setminus S}), \] \noindent provided that each skew class $\Mmclass$ is such that $3 \le \cardinal \Mmclass \le \cardinal J$. A base $\Mmbase$ of $\Mm$ and a subtransversal $S$ of $\Mmpart$ satisfying the equality can be efficiently computed. \end{theorem} The theorem still holds when every skew class $\Mmclass$ satisfies $\cardinal \Mmclass = 1$: then each $\Mm^j$ is a matroid and the statement is a theorem of \ath {Edmonds} \cite {Edmonds:Cov}. However the theorem is false when $\cardinal J = 2$ and every skew class $\Mmclass$ satisfies $\cardinal \Mmclass = 2$: it is shown in \cite {Bou:Mm1} that the parity problem for matroids can be transformed into the problem of searching for $\Mmbase$ in $\mmbaseset \Mm$ maximizing $\cardinal {\cov \Mmbase}$ with these assumptions. Consider now a connected 4-regular graph $\Graph$. We say that a bitransition is \idx {covered} by an Euler tour $\Eultour$ if it belongs to $\mmbase \Eultour$. Set $J = \set {1, 2, 3}$ and apply Theorem \ref {T.CovMulti} to $\Mm = (\Mm^1, \Mm^2, \Mm^3)$, where $\Mm^1 = \Mm^2 = \Mm^3 = \mm \Graph$. We find that the maximal number of bitransitions covered by three Euler tours of $\Graph$ is equal to \[ \min_{\Spl \in \subtrans \Mmpart} ( 3 \cardinal \Vset + 2 \cardinal \Spl - 3 \ncomp {\detach \Graph \Spl} +3 ). \] \noindent In particular there are three Euler tours that cover all the bitransitions \iff \[ 2 \cardinal \Spl \ge 3\ncomp {\detach \Graph \Spl} - 1 \] \noindent holds for every splitter $\Spl$. This result has been originally proved by \ath {Jackson} \cite {Jackson1,Jackson2}, and a polynomial algorithm to find three Euler tours covering a maximal number of bitransitions is given in \cite {Bou:Compat}. \endgroup \subsection*{Extended submodularity inequality} Let $\Mm = \Mmtriple$ be a multimatroid. If $\Sbt_1$ and $\Sbt_2$ are subtransversals of $\Mmpart$ then $\skew {\Sbt_1} {\Sbt_2}$ denotes the number of skew pairs included in $\Sbt_1 \union \Sbt_2$, and $\Sbt_1 \rdunion \Sbt_2$ denotes the union of $\Sbt_1$ and $\Sbt_2$ less the union of the skew pairs included in $\Sbt_1 \union \Sbt_2$. A function $f : \subtrans \Mmpart \to \N$ is said to satisfy the \idx {extended submodularity inequality} if \begin{equation} \label{Eq.ExtSubmod} f(A) + f(B) \ge f(A \inter B) + f(A \rdunion B) + \skew A B \end{equation} \noindent holds for every pair of subtransversals $\Sbt_1$ and $\Sbt_2$. \begin{theorem} \label{T.ExtSubmo} A triple $\Mm = \Mmtriple$ is a multimatroid \iff $\Mmrank$ satisfies the axioms \ref {mm1} and \ref {mm2}, and the extended submodularity inequality. \end{theorem} We refer the reader to a paper of \ath {Allys} \cite {Allys:ExtSubmo} for a short proof of that theorem. A kind of extended submodularity inequality, obtained by inverting $\ge$ in the relation (\ref {Eq.ExtSubmod}), was introduced by \ath {jackson} \cite {Jackson1}. \subsection*{Bisubmodularity inequality} Denote by $3^\Dmset$ the set of ordered pairs $(P, Q)$, where $P$ and $Q$ are disjoint subsets of $\Dmset$. For $X_1 = (P_1, Q_1)$ and $X_2 = (P_2, Q_2)$ in $3^\Dmset$, set \begin{eqnarray*} X_1 \ired X_2 &=& (P_1 \inter P_2, Q_1 \inter Q_2), \\ X_1 \ured X_2 &=& ( (P_1 \union P_2) \setminus (Q_1 \union Q_2), (Q_1 \union Q_2) \setminus (P_1 \union P_2) ). \end{eqnarray*} \noindent A function $f : 3^\Dmset \to \R$ is said to be \idx {bisubmodular} if \begin{equation} \label{Eq.Bisub} f(X_1) + f(X_2) \ge f(X_1 \ired X_2) + f(X_1 \ured X_2) \end{equation} \noindent always holds. This inequality has been introduced by \ath {Chandrasekaran} and \ath {Kabadi} \cite {Chandra:Pseudo,KabadiChandra}. They proved that, for a delta-matroid $\Dm = \Dmpair$, the function $\Polyrank : 3^\Dmset \to \Z$, defined by \[ \polyrank {P, Q} = \maxind {( \cardinal {P \inter \Dmbase} - \cardinal {Q \inter (\Dmset \setminus \Dmbase)} )} {\Dmbase \in \Dmbaseset} \] \noindent is bisubmodular. Moreover the convex hull of the characteristic vectors of the bases of $\Dm$ is the set of vectors $x$ in $\R^\Dmset$ satisfying \[ x(P) - x(Q) \le \polyrank {P, Q}, \,\, (P, Q) \in 3^\Dmset, \] \noindent where the notation $x(W)$ stands for $\sumind {x_w} {w \in W}$. The integral bisubmodular functions, when they are allowed to take infinite values, have also been used by \ath {Bouchet} and \ath {Cunningham} \cite {BouCunn:Jump} to study the jump systems (a generalization of delta-matroids in $\Z^\Dmset$). The fact that $\Polyrank$ is bisubmodular can be retrieved as follows. Use Construction \ref {Cons.Lift} to lift $\Dm$ into a 2-matroid $\Mm = \Mmtriple$. It is easy to verify that $\Polyrank$ satisfies the bisubmodularity inequality (\ref {Eq.Bisub}) \iff the function $\Mmrank' : \subtrans \Mmpart \to \Z$, defined by the relation \[ \mmrankprime {P_1 \union Q_2} = \polyrank {P, Q} + \cardinal {Q}, \] \noindent satisfies the extended submodularity inequality (\ref {Eq.ExtSubmod}). Since the collection of bases of $\Mm$ is equal to $\setof {\Dmbase_1 \union (\Dmset_2 \setminus \Dmbase_2)} {\Dmbase \in \Dmbaseset}$, the rank of the subtransversal $P_1 \union Q_2$ is such that \begin{eqnarray*} \mmrank {P_1 \union Q_2} &=& \maxind { \cardinal { (P_1 \union Q_2) \inter (\Dmbase_1 \union (\Dmset_2 \setminus \Dmbase_2) } } {\Dmbase \in \Dmbaseset} \\ &=& \maxind {( \cardinal {P_1 \inter \Dmbase_1} + \cardinal {Q_2 \inter (\Dmset_2 \setminus \Dmbase_2)} )} {\Dmbase \in \Dmbaseset} \\ &=& \maxind {( \cardinal {P \inter \Dmbase} + \cardinal {Q \inter (\Dmset \setminus \Dmbase)} )} {\Dmbase \in \Dmbaseset} \\ &=& \polyrank {P, Q} + \cardinal Q \\ &=& \mmrankprime {P_1 \union Q_2}. \end{eqnarray*} \noindent The rank function $\Mmrank$ satisfies the extended submodularity inequality by Theorem \ref {T.ExtSubmo}. So we retrieve that $\Polyrank$ is bisubmodular. \endgroup \section{Orthogonality relation} \label{S.Orthog} \begingroup \let \Matrank = \Mmrank \def \Mmrankk #1{\Mmrank_{#1}} \def \mmrankk #1#2{\Mmrankk {#1}(#2)} \def \Matrankk #1{\Matrank_{#1}} \def \matrankk #1#2{\Matrankk {#1}(#2)} \def \Matcorankk #1{\Matrank^*_{#1}} \def \matcorankk #1#2{\Matcorankk {#1}(#2)} \def \copy #1#2{#1_{#2}} Let $\Mat \sb 1$ and $\Mat \sb 2$ be two matroids on the same set $\Matset$, with rank functions $\Matrankk 1$ and $\Matrankk 2$, respectively. The matroid $\Mat \sb 1$ is a \idx {strong map} of the matroid $\Mat \sb 2$ if $\Matrankk 1 - \Matrankk 2$ is an increasing function, that is \begin{equation} \label{Eq.DefStrong} \matrankk 1 X - \matrankk 2 X \le \matrankk 1 {X + x} - \matrankk 2 {X + x} \end{equation} \noindent holds whenever $X$ is a subset of $\Matset$ and $x$ is an element of $\Matset \setminus X$. The matroids $\Mat \sb 1$ and $\Mat \sb 2$ are \idx {orthogonal} if $\Mat \sb 1$ is a strong map of $\dual {\Mat \sb 2}$. In this section we show that, if $\Trs_1$ and $\Trs_2$ are disjoint transversals of a multimatroid $\Mm = \Mmtriple$ indexed on a set $\Mmindset$, then the projections of the submatroids $\rest \Mm {\Trs_1}$ and $\rest \Mm {\Trs_2}$ are orthogonal. The next proposition is known when it is expressed in terms of strong maps. We recall its proof for the reader's convenience. The properties (b) and (c) imply that the orthogonality relation is symmetric. \begin{prop} \label{P.EquivOrthog} Let $\Mat \sb 1$ and $\Mat \sb 2$ be two matroids on the same set $\Matset$, with rank functions $\Matrankk 1$ and $\Matrankk 2$, respectively. The following properties are equivalent: \begin{enumerate} \itm a $\Mat \sb 1$ is orthogonal to $\Mat \sb 2$; \itm b $\matrankk 1 {X \sb 1 + \Matelm} - \matrankk 1 {X \sb 1} + \matrankk 2 {X \sb 2 + \Matelm} - \matrankk 2 {X \sb 2} \ge 1 $ holds whenever $X \sb 1$ and $X \sb 2$ are disjoint subsets of $\Matset$, and $\Matelm$ belongs to $\Matset \setminus (X \sb 1 \union X \sb 2)$; \itm c $\cardinal {\Circuit \sb 1 \inter \Circuit \sb 2} \neq 1$ holds for every circuit $\Circuit \sb 1$ of $\Mat \sb 1$ and every circuit $\Circuit \sb 2$ of $\Mat \sb 2$. \end{enumerate} \end{prop} \begin{proof} (a) $\Longleftrightarrow$ (b). Let $\Matcorankk 2$ be the rank function of $\dual {\Mat \sb 2}$. The relation (\cite {Welsh:BookMatro} p. 35) \[ \matcorankk 2 A = \matrankk 2 {\Matset \setminus A} - \matrankk 2 \Matset + \cardinal A \] \noindent is satisfied for every subset $A$ of $\Matset$. The relation (\ref {Eq.DefStrong}), applied to $\Matrankk 1$ and $\Matcorankk 2$, implies that $\Mat \sb 1$ and $\Mat \sb 2$ are orthogonal \iff \begin{equation} \label{Eq.Orthog} \matrankk 1 {X + \Matelm} - \matrankk 1 X \ge \matrankk 2 {\Matset - X - \Matelm} - \matrankk 2 {\Matset - X} + 1 \end{equation} \noindent holds for every subset $X$ of $\Matset$ and every element $\Matelm$ in $\Matset \setminus X$. Set $Y = \Matset - X - \Matelm$. The relation (\ref {Eq.Orthog}) can be written \begin{equation} \label{Eq.Conseq} \matrankk 1 {X + \Matelm} - \matrankk 1 X + \matrankk 2 {Y + \Matelm} - \matrankk 2 Y \ge 1. \end{equation} \noindent Since $\Matrankk 1$ and $\Matrankk 2$ are submodular functions, the preceding inequality also holds when one replaces $X$ by a subset $X \sb 1$ of $X$ and $Y$ by a subset $X \sb 2$ of $Y$. This proves (b). Conversely (b) $\implique$ (\ref{Eq.Conseq}) $\implique$ (\ref{Eq.Orthog}) $\implique$ (\ref {Eq.DefStrong}). (b) $\implique$ (c). Assume $\cardinal {\Circuit \sb 1 \inter \Circuit \sb 2} = 1$ and consider the unique element $\Matelm$ in $\Circuit \sb 1 \inter \Circuit \sb 2$. Set $X \sb 1 = \Circuit \sb 1 - \Matelm$ and $X \sb 2 = \Circuit \sb 2 - \Matelm$. One has $\matrankk 1 {X \sb 1 + \Matelm} = \matrankk 1 {X \sb 1}$ and $\matrankk 2 {X \sb 2 + \Matelm} = \matrankk 2 {X \sb 2}$, which contradict (b). (c) $\implique$ (b). Assume (b) is false. Since $\Matrankk 1$ and $\Matrankk 2$ are increasing functions we have $\matrankk 1 {X \sb 1 + \Matelm} = \matrankk 1 {X \sb 1}$ and $\matrankk 2 {X \sb 2 + \Matelm} = \matrankk 2 {X \sb 2}$. The element $\Matelm$ belongs to the closure of $X \sb 1$ in $\Mat \sb 1$. So there is a circuit $\Circuit \sb 1$ of $\Mat \sb 1$ such that $\Matelm \in \Circuit \sb 1 \subseteq X \sb 1 + \Matelm$. Similarly there exists a circuit $\Circuit \sb 2$ of $\Mat \sb 2$ such that $\Matelm \in \Circuit \sb 2 \subseteq X \sb 2 + \Matelm$. These circuits contradict (c). \qed \end{proof} We informally represent a multimatroid $\Mm$ indexed on a set $\Mmindset$ by drawing $\Mmindset$ and some transversals of interest as horizontal lines. An element $\Mmind$ of $\Mmindset$ and the elements of $\Mmpart_\Mmind$ are placed on the same vertical line. We think of the projection associated to the indexing as an orthogonal projection onto $\Mmindset$. \begin{theorem} \label{T.OrthoProj} If $\Trs_1$ and $\Trs_2$ are disjoint transversals of a multimatroid $\Mm$ indexed on a set $\Mmindset$, then the projections of $\rest \Mm {\Trs_1}$ and $\rest \Mm {\Trs_2}$ are orthogonal matroids. \end{theorem} \begin{figure}[hbt] \hbox to \hsize{\hfil\includegraphics{mm2-1.mps}\hfil} \caption{Illustration of the proof of Theorem 3.2.} \label{F.IllusOrthoProj} \end{figure} \begin{proof} (See Figure \ref {F.IllusOrthoProj}) Let $\Matrankk i$ be the rank function of the projection of $\rest \Mm {\Trs_i}$, for $i = 1, 2$. According to Proposition \ref {P.EquivOrthog} we have to verify that, for every pair of disjoint subsets $X \sb 1$ and $X \sb 2$ of $\Mmindset$ and every element $\Mmind$ in $\Mmindset \setminus (X \sb 1 \union X \sb 2)$, we have \begin{equation} \label{Eq2.i} \matrankk 1 {X \sb 1 + \Mmind} - \matrankk 1 {X \sb 1} + \matrankk 2 {X \sb 2 + \Mmind} - \matrankk 2 {X \sb 2} \ge 1. \end{equation} \noindent Let $\Proj$ be the projection of $\Mm$ onto $\Mmindset$ and, for $i = 1, 2$, let $Y \sb i$ be the subset of $\Trs_i$ such that $\proj {Y \sb i} = X \sb i$ and let $\copy \Mmind i$ be the element of $\Trs_i$ such that $\proj {\copy \Mmind i} = \Mmind$. The inequality (\ref {Eq2.i}) is equivalent to \begin{equation} \label{Eq2.ii} \mmrank {Y \sb 1 + \copy \Mmind 1} - \mmrank {Y \sb 1} + \mmrank {Y \sb 2 + \copy \Mmind 2} - \mmrank {Y \sb 2} \ge 1. \end{equation} \noindent The set $Y = Y \sb 1 + Y \sb 2$ is a subtransversal of $\Mmpart$ and $\set {\copy \Mmind 1, \copy \Mmind 2}$ is a skew pair included in a skew class disjoint from $Y$. Axiom \ref {mm4} implies \[ \mmrank {Y + \copy \Mmind 1} - \mmrank Y + \mmrank {Y + \copy \Mmind 2} - \mmrank Y \ge 1. \] \noindent Since $Y \sb 1$ and $Y \sb 2$ are subsets of $Y$ and the restriction of $\Mmrank$ to the powerset of $Y$ is submodular by Axiom \ref {mm3}, the last inequality implies (\ref {Eq2.ii}). \qed \end{proof} Let $\Dm = \Dmpair$ be a delta-matroid. Denote by $\max(\Dmbaseset)$ and $\min(\Dmbaseset)$ the collections of (inclusionwise) maximal members and minimal members of $\Dmbaseset$, respectively. The set systems $\upper \Dm = (\Dmset, \max(\Dmbaseset))$ and $\lower \Dm = (\Dmset, \min(\Dmbaseset))$ are matroids \cite {Bou:Delmat,Bou:MapsAndDelta}, called the \idx {upper matroid} and \idx {lower matroid} of $\Dm$, respectively. \begin{theorem} If $\Dm$ is a delta-matroid, then $\upper \Dm$ is a strong map of $\lower \Dm$. \end{theorem} \begin{proof} Consider the lift of $\Dm$ arising from Construction \ref {Cons.Lift}. Set $\Dmbaseset_i = \setof {\Dmbase_i} {\Dmbase \in \Dmbaseset}$, for $i = 1, 2$. The equality $\mmbaseset \Mm = \setof {\Dmbase_1 \union (\Dmset_2 \setminus \Dmbase_2)} {\Dmbase \in \Dmbaseset}$ implies \[ \mmindepset \Mm = \setof {P_1 \union Q_2} { P \subseteq \Dmbase, Q \inter \Dmbase = \emptyset, \forsome \Dmbase \in \Dmbaseset }. \] \noindent The independent sets of the submatroid $\rest \Mm {\Dmset_1}$ are the independent sets of $\Mm$ included in $\Dmset_1$. Hence \[ \mmindepset {\rest \Mm {\Dmset_1}} = \setof {P_1} {P \subseteq \Dmbase, \forsome \Dmbase \in \Dmbaseset}, \] \noindent which implies \[ \mmbaseset {\rest \Mm {\Dmset_1}} = \max(\Dmbaseset_1). \] \noindent We similarly find \[ \mmbaseset {\rest \Mm {\Dmset_2}} = \max(\twist {\Dmbaseset_2} {\Dmset_2}). \] \noindent Therefore $\rest \Mm {\Dmset_1}$ and $\rest \Mm {\Dmset_2}$ are projected onto the set systems $\upper \Dm$ and \break $\twist {\lower \Dm} \Dmset$, respectively. So $\upper \Dm$ and $\twist {\lower \Dm} \Dmset$ are orthogonal matroids by Theorem \ref {T.OrthoProj}. (We also retrieve that $\upper \Dm$ and $\lower \Dm$ are actually matroids.) \qed \end{proof} \endgroup \section{Free sums of orthogonal matroids} \label{S.FreeSum} \begingroup \def \Mmrankk #1{\Mmrank_{#1}} \def \mmrankk #1#2{\Mmrankk {#1}(#2)} \def \Mmrankkpr #1{\Mmrank'_{#1}} \def \mmrankkpr #1#2{\Mmrankkpr {#1}(#2)} \def \Matrankk #1{\rho_{#1}} \def \matrankk #1#2{\Matrankk {#1}(#2)} \def \freesumsq #1#2{\mm{#1_1, #1_2, \cdots, #1_{#2}}} \def \Matcorankk #1{\rho^*_{#1}} \def \matcorankk #1#2{\Matcorankk {#1}(#2)} \def \copy #1#2{#1_{#2}} \def \setq {\set {1, 2, \cdots, q}} If $\Mm = \Mmtriple$ is a $q$-matroid indexed on a set $\Mmindset$, and $(\Mmindset \sb 1$, $\Mmindset \sb 2$, $\cdots$, $\Mmindset \sb q)$ is a partition of $\Mmset$ into transversals of $\Mmpart$, then $\rest \Mm {\Mmindset \sb 1}$, $\rest \Mm {\Mmindset \sb 2}$, $\cdots$, $\rest \Mm {\Mmindset \sb q}$ are projected onto pairwise orthogonal matroids, by Theorem \ref {T.OrthoProj}. Conversely, given a sequence $(\Mat \sb 1$, $\Mat \sb 2$, $\cdots$, $\Mat \sb q)$ of orthogonal matroids on the set $\Mmindset$, we construct here a $q$-matroid $\Mm = \freesumsq \Mat q$ and a partition $(\Mmindset \sb 1$, $\Mmindset \sb 2$, $\cdots$, $\Mmindset \sb q)$ of the ground-set of $\Mm$ into transversals such that $\rest \Mm {\Mmindset \sb 1}$, $\rest \Mm {\Mmindset \sb 2}$, $\cdots$, $\rest \Mm {\Mmindset \sb q}$ are projected onto $\Mat \sb 1$, $\Mat \sb 2$, $\cdots$, $\Mat \sb q$, respectively. A $q$-matroid $\Mm = \Mmtriple$ is \idx {free} if there exists a partition of $\Mmset$ into a sequence of transversals $(\Mmindset \sb 1$, $\Mmindset \sb 2$, $\cdots$, $\Mmindset \sb q)$ such that \[ \mmrank \Sbt = \sumind {\mmrank {\Sbt \inter \Mmindset \sb i}} {1 \le i \le q} \] \noindent holds for every subtransversal $\Sbt$ of $\Mmpart$. \begin{prop} \label{P.CaracFreeMul} Let $\Mm = \Mmtriple$ be a $q$-matroid and let $(\Mmindset \sb 1$, $\Mmindset \sb 2$, $\cdots$, $\Mmindset \sb q)$ be a partition of $\Mmset$ into transversals of $\Mmpart$. The following properties are equivalent: \begin{enumerate} \itm a $\Mm$ is free \wrt $(\Mmindset \sb 1$, $\Mmindset \sb 2$, $\cdots$, $\Mmindset \sb q)$; \itm b a subtransversal $\Mmindep$ of $\Mmpart$ is an independent set of $\Mm$ \iff $\Mmindep \inter \Mmindset \sb i$ is an independent set of $\rest \Mm {\Mmindset \sb i}$ for every $i$, $1 \le i \le q$; \itm c a subtransversal $\Mmcircuit$ of $\Mmpart$ is a circuit of $\Mm$ \iff $\Mmcircuit$ is a circuit of $\rest \Mm {\Mmindset \sb i}$ for some $i$, $1 \le i \le q$. \end{enumerate} \end{prop} \begin{proof} This readily follows from the definitions. \qed \end{proof} \begin{construction} \label{Cons.FreeSum} Let $\Mat \sb 1$, $\Mat \sb 2$, $\cdots$, $\Mat \sb q$ be pairwise orthogonal matroids on the set $\Mmindset$, with rank functions $\rho_1$, $\rho_2$, $\cdots$, $\rho_q$, respectively. Set \begin{eqnarray*} & &\Mmindset \sb i = \setof {\Mmind_i} {\Mmind \in \Mmindset}, \,\, 1 \le i \le q, \\ & &\Mmset = \unionind {\Mmindset \sb i} {1 \le i \le q}, \\ & &\Mmpart_\Mmind = \setof {\copy \Mmind i} {1 \le i \le q}, \,\, \Mmind \in \Mmindset, \\ & &\Mmpart = \setof {\Mmpart_\Mmind} {\Mmind \in \Mmindset}, \\ & &P_i = \setof {\Mmind_i} {\Mmind \in P} \hbox{ and } \mmrankk i {P_i} = \rho_i(P), \,\, P \subseteq \Mmindset, \,\, 1 \le i \le q, \\ & &\mmrank \Sbt = \sumind {\mmrankk i{\Sbt \inter \Mmindset_i}} {1 \le i \le q}, \,\, \Sbt \in \subtrans \Mmpart. \end{eqnarray*} \end{construction} \begin{prop} \label{P.FreeSum} The triple $\Mm = \Mmtriple$ arising from Construction \ref {Cons.FreeSum} is a free $q$-matroid and $\Mat \sb i$ is the projection of $\rest \Mm {\Mmindset \sb i}$, for $1 \le i \le q$. \end{prop} \begin{proof} We have to verify that $\Mmrank$ satisfies the axioms \ref {mm1} to \ref {mm4}. Axiom \ref {mm1} is obvious. Let us verify Axiom \ref {mm4}. (The verifications of the two remaining axioms are similar.) We have to prove that \begin{equation} \label{Eq.a} \mmrank {\Sbt + \Mmind_j} - \mmrank \Sbt + \mmrank {\Sbt + \Mmind_k} - \mmrank \Sbt \ge 1 \end{equation} \noindent holds for every subtransversal $\Sbt$ of $\Mmpart$ and every skew pair $\set {\Mmind_j, \Mmind_k}$ contained in a skew class $\Mmpart_\Mmind$ disjoint from $\Sbt$. \begin{figure}[hbt] \hbox to \hsize{\hfil\includegraphics{mm2-2.mps}\hfil} \caption{Verifying Axiom 1.1.4.} \label{F.Illus21} \end{figure} For $1 \le i \le q$, let $\Sbt(i)$ denote the subset of $\Mmindset$ that is equal to the projection of $\Sbt \inter \Mmindset_i$ (see Fig.~\ref {F.Illus21}). By the construction of $\Mm$ we have \begin{equation} \label{Eq.b} \mmrank \Sbt = \sumind {\matrankk i {\Sbt(i)}} {1 \le i \le q}, \end{equation} \noindent The subsets $\Sbt(j)$ and $\Sbt(k)$ are disjoint and do not contain $\Mmind$, and $\Mat \sb j$ and $\Mat \sb k$ are orthogonal. Therefore \[ \matrankk j {\Sbt(j) + \Mmind} - \matrankk j {\Sbt(j)} + \matrankk k {\Sbt(k) + \Mmind} - \matrankk k {\Sbt(k)} \ge 1 \] \noindent is satisfied by Proposition \ref {P.EquivOrthog}(b). The equality (\ref {Eq.b}) implies \begin{eqnarray*} \mmrank {\Sbt + \copy \Mmind j} &=& \mmrank {\Sbt} - \matrankk j {\Sbt(j)} + \matrankk j {\Sbt(j) + \Mmind}, \\ \mmrank {\Sbt + \copy \Mmind k} &=& \mmrank {\Sbt} - \matrankk k {\Sbt(k)} + \matrankk k {\Sbt(k) + \Mmind}. \end{eqnarray*} \noindent The three preceding relations imply the inequality (\ref {Eq.a}). \qed \end{proof} We denote by $\freesumsq \Mat q$ the multimatroid arising from Construction \ref {Cons.FreeSum} and we call it the \idx {free sum} of $\Mat \sb 1$, $\Mat \sb 2$, $\cdots$, $\Mat \sb q$. According to Proposition \ref {P.CaracFreeMul}, a subtransversal $\Mmindep$ of $\Mmpart$ is an independent set of $\Mm$ \iff $\Mmindep \inter \Mmindset \sb i$ is an independent set of the submatroid $\rest \Mm {\Mmindset \sb i}$, for $1 \le i \le q$. If $\Mm'$ is another $q$-matroid defined on the same partitioned set $\Mmcarrier$ and indexed on the same set $\Mmindset$, and such that $\rest {\Mm'} {\Mmindset \sb i} = \rest \Mm {\Mmindset \sb i}$ for $1 \le i \le q$, then every independent set $\Mmindep'$ of $\Mm'$ is such that $\Mmindep' \inter \Mmindset \sb i$ is an independent set of $\rest {\Mm'} {\Mmindset \sb i}$ for $1 \le i \le q$, and so $\Mmindep'$ is also an independent set of $\Mm$. Hence $\Mm$ is the 'most free' $q$-matroid among all the $q$-matroids that admit $(\Mat \sb 1$, $\Mat \sb 2$, $\cdots$, $\Mat \sb q)$ as a sequence of projected submatroids. If $\Mat_1$ and $\Mat_2$ are orthogonal matroids on the set $\Mmindset$, then the set system $\dm {\Mat_1, \Mat_2} = \Dmpair$, where \begin{eqnarray*} \Dmbaseset &=& \setof \Dmbase { \Dmbase \subseteq \Matbase_1, \Dmbase \inter \Matbase_2 = \emptyset \hbox{ for some } \Matbase_1 \in \mmbaseset {\Mat_1} \hbox{ and } \Matbase_2 \in \mmbaseset {\Mat_2} } \\ &=& \setof \Dmbase { \Dmbase \in \mmindepset {\Mat_1}, \Dmset \setminus \Dmbase \in \mmindepset {\Mat_2} }. \end{eqnarray*} \noindent has been introduced by \ath {Tardos} \cite {Tardos:gmat} under the name of \idx {generalized matroid}. Clearly $\dm {\Mat_2, \Mat_1} = \twist {\dm {\Mat_1, \Mat_2}} \Dmset$. We also note that $\dm {\Mat, {\dual \Mat}} = \Mat$, for every matroid $\Mat$. \begin{proposition} If $\Mat_1$ and $\Mat_2$ are orthogonal matroids on the set $\Dmset$, then $\dm {\Mat_1, \Mat_2}$ is equal to the projection of $\trace {\mm {\Mat_1, \Mat_2}} {\Mmindset \sb 1}$. \end{proposition} \begin{proof} Let $\Mm = \mm {\Mat_1, \Mat_2} = \Mmtriple$ and let $\Dm$ be the projection of $\trace \Mm {\Dmset_1}$. A subset $\Dmbase$ of $\Dmset$ is a feasible set of $\Dm$ \iff $\Dmbase_1 \union (\Dmset_2 \setminus \Dmbase_2)$ is a base of $\Mm$. According to Proposition \ref {P.CaracFreeMul} (b), this is equivalent to $\Dmbase_1$ and $\Dmset_2 \setminus \Dmbase_2$ being independent in $\rest \Mm {\Dmset_1}$ and $\rest \Mm {\Dmset_2}$, respectively. Since $\rest \Mm {\Dmset_1}$ and $\rest \Mm {\Dmset_2}$ are projected onto $\Mat_1$ and $\Mat_2$, respectively, this is equivalent to $\Dmbase$ and $\Dmset \setminus \Dmbase$ being independent sets of $\Mat_1$ and $\Mat_2$, respectively. \qed \end{proof} \begin{corollary} {\rm \cite {Bou:Delmat}} Generalized matroids are delta-matroids. \end{corollary} \begin{corollary} \label{C.BasesFreeSum} Let $\Mm = \freesum \Mat {\dual \Mat} = \Mmtriple$ be the free sum of two dual matroids on the set $\Mmindset$. The submatroids $\rest \Mm {\Mmindset_1}$ and $\rest \Mm {\Mmindset_2}$ are projected onto $\Mat$ and $\dual \Mat$, respectively. A transversal $\Mmbase$ of $\Mmpart$ is a base of $\Mm$ \iff $\Mmbase \inter \Mmindset_i$ is a base of $\rest \Mm {\Mmindset_i}$, for $i$ = 1, 2. \end{corollary} \endgroup \section{Minors} \label{S.Minors} \begingroup \let \Sbtminor = X \let \Sbtminorb = Y \def \Mmrankk #1{\Mmrank_{#1}} \def \mmrankk #1#2{\Mmrankk {#1}(#2)} \def \Mmrankkpr #1{\Mmrank'_{#1}} \def \mmrankkpr #1#2{\Mmrankkpr {#1}(#2)} \def \Matrankk #1{\Mmrank_{#1}} \def \matrankk #1#2{\Matrankk {#1}(#2)} \def \freesumsq #1#2{\mm{#1_1, #1_2, \cdots, #1_{#2}}} \def \freesum #1#2{\mm{#1,#2}} \def \Matcorankk #1{\rho^*_{#1}} \def \matcorankk #1#2{\Matcorankk {#1}(#2)} \def \copy #1#2{#1_{#2}} \def \setq {\set {1, 2, \cdots, q}} Consider a multimatroid $\Mm = \Mmtriple$ and a subtransversal $\Sbtminor$ of $\Mmpart$. Set \begin{eqnarray*} \Mmpart' &=& \setof {\Mmclass \in \Mmpart} {\Mmclass \inter \Sbtminor = \emptyset}, \\ \Mmset' &=& \unionind \Mmclass {\Mmclass \in \Mmpart'}, \\ \mmrankprime \Sbt &=& \mmrank {\Sbt + \Sbtminor} - \mmrank \Sbtminor, \,\, \Sbt \in \subtrans {\Mmpart'}. \end{eqnarray*} \noindent The triple $\Mmtripleprime$ is a multimatroid, which we denote by $\minor \Mm \Sbtminor$ and call a \idx {minor} of $\Mm$. If $\Sbtminor$ and $\Sbtminorb$ are disjoint compatible subtransversals, then $\minor {\minor \Mm \Sbtminor} \Sbtminorb = \minor {\minor \Mm \Sbtminorb} \Sbtminor = \minor \Mm {(\Sbtminor \union \Sbtminorb)}$. The minor $\minor \Mm \Sbtminor$ is \idx {proper} if $\Sbtminor \neq \emptyset$, \idx {elementary} if $\cardinal \Sbtminor = 1$. If $\cardinal \Sbtminor > 1$, then $\minor \Mm \Sbtminor = \minor {\minor {\minor {\minor \Mm {\Mmelm_1}} {\Mmelm_2}} \cdots} {\Mmelm_p}$, where $\Mmelm_1, \Mmelm_2, \cdots, \Mmelm_p$ is any enumeration of the elements of $\Sbtminor$. \let \Spl = \Sbtminor \begin{prop} \label{P.EulerMinor} Let $\mm {\rst \Graph \Allowed}$ be an Eulerian multimatroid. For every allowed splitter $\Spl$ we have \begin{equation} \label{Eq.EulerMinor1} \minor {\mm {\rst \Graph \Allowed}} \Spl = \mm {\rst {\Graph'} {\Allowed'}}, \end{equation} \noindent where $\Graph' = \detach \Graph \Spl$ and $\Allowed'$ is the set of allowed local splitters incident to the vertices of $\Graph'$. \end{prop} \begin{proof} The multimatroids $\Mm_1 = \minor {\mm {\rst \Graph \Allowed}} \Spl$ and $\Mm_2 = \mm {\rst {\Graph'} {\Allowed'}}$ are defined on the same partitioned set $(\Allowed', \Mmpart')$. Let $\Mmrank$ be the rank function of $\mm {\rst \Graph \Allowed}$ and let $\Mmrank_i$ be the rank function of $\Mm_i$, for $i = 1, 2$. For every subtransversal $\Sbt$ of $\Mmpart'$ we have \begin{eqnarray*} \Mmrank_1(\Sbt) &=& \mmrank {\Sbt + \Spl} - \mmrank \Spl \\ &=& \cardinal {\Sbt + \Spl} - \ncomp {\detach \Graph {(\Sbt + \Spl)}} + \ncomp \Graph - \cardinal \Spl + \ncomp {\detach \Graph \Spl} - \ncomp \Graph \\ &=& \cardinal {\Sbt} - \ncomp {\detach {(\detach \Graph \Spl)} \Sbt} + \ncomp {\detach \Graph \Spl} \\ &=& \Mmrank_2(\Sbt). \end{eqnarray*} \qed \end{proof} When $\Graph$ is a 4-regular graph, the graph $\Graph' = \detach \Graph \Spl$ in the relation (\ref {Eq.EulerMinor1}) has vertices of degree 2 that we may wish to erase in order to obtain another 4-regular graph. In general to \idx {erase} a vertex $\Vy$ of degree 2 in a graph $H$ is to delete $\Vy$ as well as the edges and half-edges incident to $\Vy$ then, if there remains two half-edges $\Half_1$ and $\Half_2$ that are no longer incident to an edge (which happens if $\Vy$ was not incident to a loop in $H$), to add a new edge and make it incident to $\Half_1$ and $\Half_2$. To \idx {open} $\Spl$ in $\Graph$ is to construct the detachment $\detach \Graph \Spl$, then to successively erase the vertices of degree 2. The new graph, denoted by $\open \Graph \Spl$, is a 4-regular graph if $\Graph$ is 4-regular. We have $\ncomp {\open \Graph \Spl} = \ncomp {\detach \Graph \Spl} - \Ncomp_2$, where $\Ncomp_2$ is the number of components of $\detach \Graph \Spl$ regular of degree 2, and $\mm {\detach \Graph \Spl} = \mm {\open \Graph \Spl}$. Set $\open {\rst \Graph \Allowed} \Spl = \rst {(\open \Graph \Spl)} {\Allowed'}$, where $\Allowed'$ is the set of allowed local splitters incident to the vertices of $\open \Graph \Spl$. Then the relation (\ref {Eq.EulerMinor1}) can be written \begin{equation} \label{Eq.EulerMinor2} \minor {\mm {\rst \Graph \Allowed}} \Spl = \mm {\open {\rst \Graph \Allowed} \Spl}. \end{equation} For a matroid $\Mat$ on the set $\Mmindset$ and an element $\Mmind$ of $\Mmindset$, we denote by $\Mat \delete \Mmind$ and $\Mat \contract \Mmind$ the matroids obtained by deleting $\Mmind$ and by contracting $\Mmind$, respectively. \begin{prop} Let $\Mm = \freesumsq \Mat q$ be a free sum of orthogonal matroids on a set $\Mmindset$. For every $\Mmind$ in $\Mmindset$ and every $j$ in $\setq$, we have $\minor \Mm {\copy \Mmind j} = \freesumsq {\Mat'} q$ with \begin{eqnarray*} \Mat' \sb j &=& \Mat \sb j \contract \Mmind, \\ \Mat' \sb k &=& \Mat \sb k \delete \Mmind, \,\, k \in \setq - j. \end{eqnarray*} \end{prop} \begin{proof} Set $\Mmtripleprime = \minor \Mm {\Mmind_j}$. We may assume $j = 1$. For every subtransversal $\Sbt$ of $\Mmpart'$ we have \begin{eqnarray*} \mmrankprime \Sbt &=& \mmrank {\Sbt + \Mmind_1} - \mmrank {\Mmind_1} \\ &=& \mmrankk 1 {\Sbt_1 + \Mmind_1} - \mmrankk 1 {\Mmind_1} + \sumind {\mmrankk j {\Sbt_j}} {2 \le j \le q} \\ &=& \mmrankkpr 1 {\Sbt_1} + \sumind {\mmrankkpr j {\Sbt_j}} {2 \le j \le q}, \end{eqnarray*} \noindent where $\Sbt_j$ is the projection of $\Sbt \inter \Mmindset \sb j$, $\Mmrankk j$ is the rank function of $\Mat \sb j$, $\Mmrankkpr j$ is the rank function of $\Mat \sb j \delete \Mmind$ if $j \neq 1$ and $\Mmrankkpr 1$ is the rank function of $\Mat \sb 1 \contract \Mmind$. \qed \end{proof} \begin{corollary} \label{C.MineurMatro} Let $\Mat$ be a matroid on a set $\Mmindset$ and let $\Mm = \freesum \Mat {\dual \Mat}$. For every element $\Mmind$ in $\Mmindset$ we have \begin{eqnarray*} \minor \Mm {\Mmind_1} &=& \freesum {\Mat \contract \Mmind} {\dual \Mat \delete \Mmind} = \freesum {\Mat \contract \Mmind} {\dual {(\Mat \contract \Mmind)}}, \\ \minor \Mm {\Mmind_2} &=& \freesum {\Mat \delete \Mmind} {\dual \Mat \contract \Mmind} = \freesum {\Mat \delete \Mmind} {\dual {(\Mat \delete \Mmind)}}. \end{eqnarray*} \end{corollary} An element $\Mmelm$ in $\Mmset$ is \idx {singular} if $\mmrank \Mmelm = 0$. A skew class that contains a singular element is \idx {singular}. \begin{prop} \label{P.SingUniq} A singular skew class contains precisely one singular element. \end{prop} \begin{proof} If there were distinct singular elements, $\Mmelm$ and $\Mmelmb$, in the same skew class of a multimatroid with rank function $\Mmrank$, we should have \[ \mmrank \Mmelm - \mmrank \emptyset + \mmrank \Mmelmb - \mmrank \emptyset = 0, \] \noindent contradicting Axiom \ref {mm4}. \qed \end{proof} \let \Mmelmc = z \begin{prop} \label{P.MinorUniq} If a skew class $\Mmclass$ of a multimatroid $\Mm$ is singular, then the elementary minor $\minor \Mm \Mmelm$ does not depend from the choice of $\Mmelmc$ in $\Mmclass$, namely $\minor \Mm \Mmelmc = \rest \Mm {\Mmset \setminus \Mmclass}$. \end{prop} \begin{proof} Let $\Mmrank$ be the rank function of $\Mm$ and let $\Mmelm$ be the singular element of $\Mmclass$. For every subtransversal $\Sbt$, disjoint from $\Mmclass$, the submodularity inequality \ref {mm3} implies \[ \mmrank {\Sbt + \Mmelm} - \mmrank \Sbt \le \mmrank \Mmelm - \mmrank \emptyset = 0. \] \noindent Since $\mmrank \Mmelm = 0$, it follows \begin{equation} \label{Eq.i} \mmrank {\Sbt + \Mmelm} - \mmrank \Mmelm = \mmrank \Sbt. \end{equation} \noindent For every element $\Mmelmb$ in $\Mmclass - \Mmelm$, Axiom \ref {mm4} implies \[ \mmrank {\Sbt + \Mmelmb} - \mmrank \Sbt + \mmrank {\Sbt + \Mmelm} - \mmrank \Sbt \ge 1. \] \noindent Since $\mmrank \Mmelmb = 1$, by Proposition \ref {P.SingUniq}, this implies \begin{equation} \label{Eq.ii} \mmrank {\Sbt + \Mmelmb} - \mmrank \Mmelmb = \mmrank \Sbt. \end{equation} \noindent The equations (\ref {Eq.i}) and (\ref {Eq.ii}) imply $\minor \Mm \Mmelm = \minor \Mm \Mmelmb = \rest \Mm {\Mmset \setminus \Mmclass}$. \qed \end{proof} \begin{theorem} \label{T.ScumMm} For every minor $\minor \Mm X$ of a nondegenerate multimatroid $\Mm$ there exists an independent set $Y$ such that $\minor \Mm Y = \minor \Mm X$. \end{theorem} \begin{proof} We use induction on $\cardinal X$. The property is trivial if $\cardinal X = 0$. Assume $\cardinal X > 0$ and consider an element $x$ in $X$. Set $\Mm' = \minor \Mm x$ and $X' = X - x$. By induction there exists an independent set $Y'$ of $\Mm'$ such that $\minor {\Mm'} {Y'} = \minor {\Mm'} {X'}$. This implies \[ \minor \Mm X = \minor {\minor \Mm x} {X'} = \minor {\minor \Mm x} {Y'} = \minor \Mm {(Y' + x)}. \] \noindent If $Y' + x$ is an independent set of $\Mm$ the proof is done. Assume $Y' + x$ is dependent and denote by $\Mmrank'$ the rank function of $\Mm'$. We have \[ \mmrank {Y' + x} \le \cardinal {Y'} \] \noindent and \[ \cardinal {Y'} = \mmrankprime {Y'} = \mmrank {Y' + x} - \mmrank x. \] \noindent These relations imply $\mmrank x = 0$, and so the skew class $\Mmclass$ that contains $x$ is singular. Consider an element $y$ in $\Mmclass - x$, which exists because $\Mm$ is nondegenerate. Proposition \ref {P.SingUniq} implies $\mmrank y = 1$, and Proposition \ref {P.MinorUniq} implies $\Mm' = \minor \Mm x = \minor \Mm y$. Set $Y = Y' + y$. We have \[ \minor \Mm X = \minor {\minor \Mm x} {X'} = \minor {\Mm'} {X'} = \minor {\Mm'} {Y'} = \minor {\minor \Mm y} {Y'} = \minor \Mm Y \] \noindent and \[ \mmrank Y = \mmrank {Y' + y} = \mmrankprime {Y'} + \mmrank y = \cardinal {Y'} + 1 = \cardinal Y, \] \noindent which completes the proof. \qed \end{proof} \bigskip The following result is often called the \idx {scum theorem} \cite {CrapoRota} \begin{corollary} \label{C.ScumMat} For every minor $\Mat'$ of a matroid $\Mat$ there exists an independent set $I$ of $\Mat$ and an independent set $J$ of $\dual \Mat$, such that $I \inter J = \emptyset$ and $\Mat' = \Mat \contract I \delete J$. \end{corollary} \begin{proof} Consider the free sums $\Mm = \freesum \Mat {\dual \Mat}$ and $\Mm' = \freesum {\Mat'} {\dual {\Mat'}}$. Corollary \ref {C.MineurMatro} implies that $\Mm'$ is a minor of $\Mm$. Theorem \ref {T.ScumMm} implies the existence of an independent set $Y$ of $\Mm$ such that $\Mm' = \minor \Mm Y$. For $i = 1, 2$, the set $Y \inter \Mmindset_i$ is an independent set of $\rest \Mm {\Mmindset_i}$. The projection $I$ of $Y \inter \Mmindset_1$ is an independent set of $\Mat$, and the projection $J$ of $Y \inter \Mmindset_2$ is an independent set of $\dual \Mat$. By using Corollary \ref {C.MineurMatro} again, we have \begin{eqnarray*} \freesum {\Mat'} {\dual {\Mat'}} &=& \minor \Mm Y \\ &=& \minor {\minor \Mm {(Y \inter \Mmindset_1)}} {(Y \inter \Mmindset_2)} \\ &=& \freesum {\Mat \contract I \delete J} {\dual \Mat \delete I \contract J}, \end{eqnarray*} \noindent and so $\Mat' = \Mat \contract I \delete J$. \qed \end{proof} \endgroup \section{Separators} \begingroup \label{S.Separ} \let \Separ = W \let \Weaksep = X \let \Matset = V Let us recall that a \idx {separator} of a matroid $\Mat$ on the set $\Matset$, with rank function $\Matrank$, is a subset $\Separ$ of $\Matset$ such that \begin{equation} \label{S.SeparMat} \matrank \Sbt = \matrank {\Sbt \inter \Separ} + \matrank {\Sbt \setminus \Separ} \end{equation} \noindent is satisfied for every subset $\Sbt$ of $\Matset$. We similarly define a \idx {separator of the elements} of a multimatroid $\Mm = \Mmtriple$ as a subset $\Separ$ of $\Mmset$ that is a union of skew classes and satisfies the equality (\ref {S.SeparMat}) for every subtransversal $\Sbt$ of $\Mmpart$. If $\Mm$ is indexed on a set $\Mmindset$, we define a \idx {separator of the indices} as a subset $\Separ$ of $\Mmindset$ such that $\unionind {\Mmpart_\Mmind} {\Mmind \in \Separ}$ is a separator of the elements. When using the term \idx {separator}, without specifying the elements or the indices, we implicitly refer to a separator of the indices if $\Mm$ is indexed, and to a separator of the elements if no indexing of $\Mm$ is specified. The multimatroid $\Mm$ is \idx {connected} if it has no proper separator. There is also a weaker notion of separator that has some interest: a subset $\Separ \subseteq \Mmset$ is a \idx {weak separator} if the equality (\ref {S.SeparMat}) holds for every subtransversal $\Sbt$ of $\Matset$ (but $\Separ$ is not necessarily a union of skew classes). For example in a free sum $\mm {\Mat_1, \Mat_2, \cdots, \Mat_q}$ of orthogonal matroids defined on a set $\Matset$, the transversals $\Matset_1$, $\Matset_2$, $\cdots$, $\Matset_q$ are weak separators. \begin{prop} \label{P.BoolSepar} The set of (weak) separators is closed under union, intersection, and complementation. \end{prop} \begin{proof} This readily follows from the definition and the submodularity of the rank function. \qed \end{proof} We recall the following basic relation between the separators and the circuits of a matroid. \begin{theorem} \label{T.Noncrossing} A subset $\Separ$ of the elements of a matroid $\Mat$ is a separator \iff every circuit of $\Mat$ is either included in $\Separ$ or disjoint from $\Separ$. \end{theorem} \begin{corollary} \label{C.WeakSepar} Let $\Mm = \Mmtriple$ be a multimatroid and let $\Weaksep$ be a subset of $\Mmset$. The following properties are equivalent: \begin{enumerate} \itm a $\Weaksep$ is a weak separator of $\Mm$; \itm b $\Weaksep \inter \Trs$ is a separator of the submatroid $\rest \Mm \Trs$ for every transversal $\Trs$ of $\Mmpart$; \itm c every circuit of $\Mm$ is either included in $\Weaksep$ or disjoint from $\Weaksep$. \end{enumerate} \end{corollary} \begin{proof} The equivalence of (a) and (b) readily follows from the definition. The equivalence of (b) and (c) is a simple consequence of Theorem \ref {T.Noncrossing}. \qed \end{proof} Although the class of connected matroids is clearly equal to the class of connected 1-matroids, many basic properties of connected matroids cannot be generalized to arbitrary multimatroids. For example a matroid is connected \iff every pair of elements of that matroid belong to the same circuit. That property no longer holds for a 2-matroid $\Mm = \Mmtriple$. Indeed let $\Mmset = \set {a, a', b, b', c, c', d, d'}$, let $\Mmpart = \set {aa', bb', cc', dd'}$, and let the set of circuits be equal to $\set {a'b'cd, a'bcd', ab'c'd, abc'd'}$ (we omit the braces around the elements of a powerset). There exists no proper subset $\Separ$ of $\Mmset$ such that every circuit is either included in $\Separ$ or disjoint from $\Separ$. Accordingly $\Mm$ is connected. However there is no circuit including $\set {a', c'}$. In a subsequent paper \cite {Bou:Mm3} we show that some basic properties of connected matroids can be generalized to the subclass of tight multimatroids. \endgroup \section{Cyclic splitters} \begingroup \label{S.CycSplit} \def \aug #1#2{(\detach #1 #2)^+} \def \Twocutpair {\set {\Edge_1, \Edge_2}} \def \Twocutreplace {\set {\Edge^1, \Edge^2}} \let \Cut = C \let \Cycle = \Gamma The cyclic splitters are particular splitters associated to the cycles of an Eulerian graph $\Graph$. We show that the circuits of $\mm \Graph$ are the minimal nonempty cyclic splitters. We define a transformation of $\Graph$ that preserves the cyclic splitters and we prove the existence of a connected Eulerian graph $\Graph'$ such that $\mm {\Graph'} = \mm \Graph$. \subsection*{Definitions and basic properties} \let \Cycle = \Gamma \let \Comp = X Let $\Cycle$ be a subset of edges of $\Graph$. The set of half-edges incident to the edges in $\Cycle$ is denoted by $\half \Cycle$. We recall that the set of half-edges incident to a vertex $\Vx$ is denoted by $\half \Vx$. The set $\Cycle$ is a \idx {cycle} of $\Graph$ if $\cardinal {\half \Cycle \inter \half \Vx}$ is even for every vertex $\Vx$. Set $\vset \Cycle = \setof {\Vx \in \Vset} {\emptyset \neq \half \Cycle \inter \half \Vx \neq \half \Vx}$ and $\spl \Cycle = \setof {{\spl \Cycle}_\Vx} {\Vx \in \vset \Cycle}$, where ${\spl \Cycle}_\Vx = \set {\half \Cycle \inter \half \Vx, \half \Vx \setminus \half \Cycle}$. So $\Cycle$ is a cycle \iff $\spl \Cycle$ is a splitter. Then we call $\spl \Cycle$ a \idx {cyclic splitter}. Figure \ref {F.1cycspl} depicts a cycle $\Cycle$, drawn with thick edges, and the detachment $\detach \Graph {\spl \Cycle}$. The following property is a direct consequence of the definitions. \begin{prop} \label{P.CompCyclic} If $\Cycle$ is a cycle of an Eulerian graph $\Graph$, then the edge-set of every component of $\detach \Graph {\spl \Cycle}$ is contained in $\Cycle$ or disjoint from $\Cycle$. \end{prop} \begin{figure}[hbt] \hbox to \hsize{\hfil\includegraphics{mm2-3.mps}\hfil} \caption{Detachment of a cyclic splitter} \label{F.1cycspl} \end{figure} A bicoloring of the half-edges, say in black and white, is \idx {compatible} with a splitter $\Spl = \setof {\locspl \Vx} {\Vx \in \Wset}$, $\locspl \Vx = \set {\locsplpr \Vx, \locsplsec \Vx}$, if the three following conditions are satisfied : \begin{statement} \label{S.CompCol0} two half-edges incident to a same edge have the same color; \end{statement} \begin{statement} \label{S.CompCol1} two half-edges incident to a same vertex $\Vx$ in $\Vset - \Wset$ have the same color; \end{statement} \begin{statement} \label{S.CompCol2} two half-edges incident to a same vertex $\Vx$ in $\Wset$ have the same color \iff both belong to either $\locsplpr \Vx$ or $\locsplsec \Vx$. \end{statement} \begin{prop} \label{P.CyclicCompat} A splitter $\Spl = \setof {\locspl \Vx} {\Vx \in \Wset}$ is cyclic \iff there is a bicoloring of the half-edges compatible with $\Spl$. \end{prop} \begin{proof} If $\Spl = \spl \Cycle$, for some cycle $\Cycle$, then we obtain a compatible bicoloring by letting the half-edges in $\half \Cycle$ be black and the other half-edges be white. Conversely if there is a compatible bicoloring , then the subset $\Cycle$ of the edges incident to the black half-edges is a cycle such that $\Spl = \spl \Cycle$. \qed \end{proof} If $H$ is a component of $\detach \Graph \Spl$, where $\Spl$ is a cyclic splitter, and if we consider a coloring of the half-edges compatible with $\Spl$, then Proposition \ref {P.CompCyclic} implies that the half-edges incident to $H$ have the same color, which we call the \idx {color} of $H$. \subsection*{Circuits of $\mm \Graph$} \begingroup \let \Cycle = \Gamma \let \Comp = X \let \Spl = S In view of the following properties we point out that a circuit of $\mm \Graph$ is not to be confused with a circuit of $\Graph$. The former is a splitter of $\Graph$ and the latter is a set of edges of $\Graph$. \begin{prop} \label{P.CycNotIndep} Let $\Graph$ be an Eulerian graph. A nonempty cyclic splitter $\Spl$ of $\Graph$ is dependent in $\mm \Graph$. \end{prop} \begin{proof} Set $\Spl = \setof {\locspl \Vx} {\Vx \in \Wset}$, $\locspl \Vx = \set {\locsplpr \Vx, \locsplsec \Vx}$. Consider a vertex $\Vx$ in $\Wset$ and the components $\Comp'$ and $\Comp''$ of $\detach \Graph \Spl$ that contain $\locsplpr \Vx$ and $\locsplsec \Vx$, respectively. In a bicoloring of the half-edges compatible with $\Spl$, the half-edges in $\locsplpr \Vx$ have not the same color as the half-edges in $\locsplsec \Vx$, by the condition \ref {S.CompCol2}. Hence $\Comp'$ and $\Comp''$ have distinct colors, and so $\Comp' \neq \Comp''$. If we reconstruct $\Graph$ from $\detach \Graph \Spl$ by identifying each pair of vertices of $\detach \Graph \Spl$ corresponding to the same vertex of $\Graph$, the components $\Comp'$ and $\Comp''$ are merged into the same component. Accordingly $\ncomp {\detach \Graph \Spl} > \ncomp \Graph$, and so $\Spl$ is dependent in $\mm \Graph$. \qed \end{proof} \begin{theorem} \label{T.CircuitIsCyclic} Let $\Graph$ be an Eulerian graph. The minimal nonempty cyclic splitters of $\Graph$ are the circuits of $\mm \Graph$. \end{theorem} \begin{proof} By the preceding proposition we know that every minimal nonempty cyclic splitter of $\Graph$ includes a circuit of $\mm \Graph$. It remains to prove that every circuit $\Mmcircuit$ of $\mm \Graph$ is a cyclic splitter. Set $\Mmcircuit = \setof {\Mmcircuit_\Vx} {\Vx \in \Wset}$, $\Mmcircuit_\Vx = \set {{\Mmcircuit'}_\Vx, {\Mmcircuit''}_\Vx}$, and denote by $\Vx'$ and $\Vx''$ the vertices of $\detach \Graph \Mmcircuit$ such that $\half {\Vx'} = {\Mmcircuit'}_\Vx$ and $\half {\Vx''} = {\Mmcircuit''}_\Vx$. Since $\Mmcircuit$ is a circuit of $\mm \Graph$ we have $\ncomp {\detach \Graph \Mmcircuit} - \ncomp \Graph = 1$ and $\ncomp {\detach \Graph \Mmcircuit} = \ncomp {\detach \Graph {(\Mmcircuit - \Mmcircuit_\Vx)}} + 1$ for every $\Vx$ in $\Wset$. \begin{claim*} For every $\Vx$ in $\Wset$, $\Vx'$ and $\Vx''$ are in different components of $\detach \Graph \Mmcircuit$. \end{claim*} \begin{proof} By identifying $\Vx'$ and $\Vx''$ in $\detach \Graph \Mmcircuit$ we obtain $\detach \Graph {(\Mmcircuit - \Mmcircuit_\Vx)}$. No component of $\detach \Graph \Mmcircuit$ is modified after this identification, except for the components $\Comp'$ and $\Comp''$ containing $\Vx'$ and $\Vx''$, respectively, which are merged together. If these components are equal, then the number of components is not modified by the identification, which contradicts the equality $\ncomp {\detach \Graph \Mmcircuit} = \ncomp {\detach \Graph {(\Mmcircuit - \Mmcircuit_\Vx)}} + 1$. \qed \end{proof} Let $\Graph^1$, $\Graph^2$, $\cdots$, $\Graph^k$ be the components of $\Graph$ and, for $1 \le j \le k$, let $\Mmcircuit^j = \setof {\Mmcircuit_\Vx} {\Vx \in \Wset \inter \vset {\Graph^j}}$. The detachment $\detach \Graph \Mmcircuit$ can be constructed by successively constructing each detachment $\detach {\Graph^j} {\Mmcircuit^j}$, for $j = 1, 2, \cdots, k$. Therefore \[ 1 = \ncomp {\detach \Graph \Mmcircuit} - \ncomp \Graph = \sum_{j = 1}^{j = k} (\ncomp {\detach {\Graph^j} {\Mmcircuit^j}} - 1). \] \noindent Accordingly we may assume $\detach {\Graph^j} {\Mmcircuit^j}$ is connected, for $2 \le j \le k$, and $\detach {\Graph^1} {\Mmcircuit^1}$ has two components, say $X'$ and $X''$. Each subset $\Mmcircuit^j$, $2 \le j \le k$, is empty. Indeed if there was a local splitter $\Mmcircuit_\Vx$ in $\Mmcircuit^j$, then $\Vx'$ and $\Vx''$ would be vertices of $\detach {\Graph^j} {\Mmcircuit^j}$, which is a component of $\detach \Graph \Mmcircuit$, contradicting the claim. So, for every $\Vx$ in $\Wset$, the vertices $\Vx'$ and $\Vx''$ belong to $\detach {\Graph^1} {\Mmcircuit^1}$. Moreover they do not belong to the same component of $\detach \Graph \Mmcircuit$ according to the claim. Hence we may assume ${\Mmcircuit'}_\Vx$ is a subset of half-edges of $\Comp'$ and ${\Mmcircuit''}_\Vx$ is a subset of half-edges of $\Comp''$. Then, by coloring the half-edges of $X'$ in black and all the other half-edges in white, we obtain a bicoloring compatible with $\Mmcircuit$. \qed \end{proof} \begin{corollary} \label{C.CycSplDetermine} If two Eulerian graphs $\Graph'$ and $\Graph''$ have the same cyclic splitters, then $\mm {\Graph'} = \mm {\Graph''}$. \end{corollary} \endgroup \subsection*{Breaking 2-cuts} Let $\set {\Vset^1, \Vset^2}$ be a bipartition of the vertex-set of $\Graph$. The set $\Cut$ of edges of $\Graph$ that have one end in $\Vset^1$ and one end in $\Vset^2$ is called a \idx {$k$-cut} if $\cardinal \Cut = k$. Since $\Graph$ is Eulerian, $k$ is even. To \idx {break} a 2-cut $\Twocutpair$ is to construct the graph depicted in Figure \ref {F.z1bk2cut}. Formally, denoting by $\Hedge^j_i$ the half-edge incident to $\Edge_i$ and $\Vset^j$, we replace $\Edge_1$ and $\Edge_2$ by two edges $\Edge^1$ and $\Edge^2$, where $\Edge^j$ is incident to $\Hedge^j_1$ and $\Hedge^j_2$, for $j = 1, 2$. So we split the component of $\Graph$ that contains $\Edge_1$ and $\Edge_2$ into a component that contains $\Edge^1$ and a component that contains $\Edge^2$. The reverse operation, which consists in replacing $\set {\Edge^1, \Edge^2}$ by $\set {\Edge_1, \Edge_2}$, is called \idx {glueing} along $\set {\Edge^1, \Edge^2}$. \begin{figure}[hbt] \hbox to \hsize{\hfil\includegraphics{mm2-4.mps}\hfil} \caption{Breaking a 2-cut and glueing along a pair of non-connected edges} \label{F.z1bk2cut} \end{figure} \begin{prop} \label{P.TwoCutBreak} If an Eulerian graph $\Graph'$ is derived from another one $\Graph$ by either breaking a 2-cut or glueing a pair of nonconnected edges, then $\Graph$ and $\Graph'$ have the same cyclic splitters. \end{prop} \begin{proof} Consider a cyclic splitter $\Spl$ of $\Graph$ and a bicoloring of the half-edges compatible with $\Spl$. The same bicoloring, with respect to $\Graph'$, still satisfies the conditions \ref {S.CompCol1} and \ref {S.CompCol2}. If it also satisfies Condition \ref {S.CompCol0}, with respect to $\Graph'$, then $\Spl$ is a cyclic splitter of $\Graph'$, and the property is proved. In the other case we have to modify the bicoloring in order to prove the property. Let $\Cycle$ be the cycle of $\Graph$ incident to the black edges. Case 1: Breaking a 2-cut $\set {\Edge_1, \Edge_2}$. Since the intersection of a cut with a cycle has an even cardinality, $\set {\Edge_1, \Edge_2}$ is either contained in $\Cycle$ or disjoint from $\Cycle$. In both cases the four half-edges incident to $\Edge_1$ and $\Edge_2$ have the same color. These half-edges are also incident to $\Edge^1$ and $\Edge^2$ in $\Graph'$. Therefore Condition \ref {S.CompCol0} is satisfied. Case 2: Glueing along a pair of nonconnected edges $\set {\Edge^1, \Edge^2}$. By Condition \ref {S.CompCol0}, with respect to $\Graph$, the half edges incident to $\Edge^1$ have the same color $\chi_1$, and the half-edges incident to $\Edge^2$ have the same color $\chi_2$. If $\chi_1 = \chi_2$ Condition \ref {S.CompCol0} still holds with respect to $\Graph'$. If $\chi_1 \neq \chi_2$ we exchange the colors black and white on the half-edges of the component of $\Graph$ that contain the edge $\Edge^2$. We have still a bicoloring compatible with $\Spl$, and $\chi_1 = \chi_2$. \qed \end{proof} \begin{corollary} \label{C.Glue} For every Eulerian graph there exists a connected Eulerian graph that admits the same splitter rank function. \end {corollary} \begin{proof} Delete the vertices of null degree, which play no role in the cyclic splitters. Then make successive glueings until obtaining only one component. \qed \end{proof} \begin{figure}[hbt] \hbox to \hsize{\hfil\includegraphics{mm2-5.mps}\hfil} \caption{Switching a 4-cut, $\tau = (1 \, 4) \, (2 \, 3)$.} \label{F.z1switch} \end{figure} \subsection*{Switching a 4-cut} Let $\Cut = \setof {\Edge_{ii}}{i \in I}$, $I = \set {1, 2, 3, 4}$, be a 4-cut of $\Graph$ defined by the bipartition $\set {\Vset^1, \Vset^2}$ of the vertex-set and let $\tau$ be a fixed point free involution on $I$. (Thus $\tau$ is a permutation of $I$ such that $\tau(i) \neq i$ and $\tau^2(i) = i$ hold for all $i$ in $I$. We note that precisely three such involutions exist.) Denote by $\Hedge^j_i$ the half-edge incident to $\Edge_{ii}$ and $\Vset^j$, for all $i$ in $I$ and all $j$ in $\set {1, 2}$. For each $i$ in $I$, remove the edge $\Edge_{ii}$ and replace it by an edge $\Edge_{i \tau(i)}$ incident to $\Hedge^1_i$ and $\Hedge^2_{\tau(i)}$. This transformation, called a \idx {switching}, is illustrated in Figure \ref {F.z1switch}. By performing again the same switching one regains the original graph. \begin{prop} \label{P.SwitchCut} If an Eulerian graph $\Graph'$ is derived from another one $\Graph$ by switching a 4-cut, then $\Graph$ and $\Graph'$ have the same cyclic splitters. \end{prop} \begin{proof} The proof is similar to the preceding one and we use the same notation. The cut $\Cut$ contains an even number of edges of $\Cycle$, say $p$. If $p = 0$ or $p = 4$, the half-edges incident to $\Cut$ have the same color, and so the coloring is still compatible in $\Graph'$. If $p = 2$ and $\Cut \inter \Cycle = \set {\Edge_{ii}, \Edge_{\tau(i)\tau(i)}}$, for some $i$ in $I$, again the coloring is compatible in $\Graph'$. In the remaining case we may assume without loss of generality $\tau = (1 \, 4) \, (2 \, 3)$, the half-edges incident to $\Edge_{11}$ and $\Edge_{22}$ are colored in black, the half-edges incident to $\Edge_{33}$ and $\Edge_{44}$ are colored in white. The coloring of the half-edges, with respect to $\Graph'$, is illustrated in Figure \ref {F.z1exchg}. We obtain a coloring compatible in $\Graph'$ by exchanging the colors black and white on the half-edges incident to $\Vset^2$. \qed \end{proof} \begin{figure}[hbt] \hbox to \hsize{\hfil\includegraphics{mm2-6.mps}\hfil} \caption{Exchanging the colors of the half-edges incident to $\Vset^2$.} \label{F.z1exchg} \end{figure} \topic{Question} Given two connected Eulerian graphs $\Graph$ and $\Graph'$ without 2-cut and such that $\mm \Graph = \mm {\Graph'}$, is it true that $\Graph'$ can be derived from $\Graph$ by a succession of 4-cut switchings? This has been proved when $\Graph$ and $\Graph'$ are 4-regular by \ath {Ghier} \cite {ghier:93}. \endtopic \endgroup %\bibliography{delta,perso} %\bibliographystyle{siam} \begin{thebibliography}{10} \bibitem{Allys:ExtSubmo} {\sc L.~Allys}, {\em Extended submodularity inequality}. \newblock Submitted. \bibitem{Bou:Delmat} {\sc A.~Bouchet}, {\em Greedy algorithm and symmetric matroids}, Math. Programming, 38 (1987), pp.~147--159. \bibitem{Bou:MapsAndDelta} \leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em Maps and ${\Delta}$-matroids}, Discrete Math., 78 (1989), pp.~59--71. \bibitem{Bou:Compat} \leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em Compatible {E}uler tours and supplementary {E}ulerian vectors}, Europ. J. Combin., 514 (1993), pp.~513--520. \bibitem{Bou:Mm1} \leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em Multimatroids {I}. {C}overings by independent sets}, SIAM J. Discrete Math., 10 (1997), pp.~626--646. \bibitem{Bou:Mm3} \leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em Multimatroids {III}. {T}ightness and fundamental graphs}. \newblock Submitted, 1997. \bibitem{Bou:Mm4} \leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em Multimatroids {IV}. {C}hain-group representations}. \newblock To appear in {\it Linear Algebra and its Applications}., 1997. \bibitem{BouCunn:Jump} {\sc A.~Bouchet and W.~H. Cunningham}, {\em Delta--matroids. jump systems, and bisubmodular polyhedra}, SIAM J. Discrete Math., 8 (1995), pp.~17--32. \bibitem{Chandra:Pseudo} {\sc R.~Chandrasekaran and S.~N. Kabadi}, {\em Pseudomatroids}, Discrete Math., 71 (1988), pp.~205--217. \bibitem{CrapoRota} {\sc H.~H. Crapo and G.~C. Rota}, {\em On the {F}oundations of {C}ombinatorial {T}heory: {C}ombinatorial {G}eometries}, The M.I.T. Press, Cambridge, Massachussets, 1970. \bibitem{DressHav:Metro} {\sc A.~Dress and T.~Havel}, {\em Some combinatorial properties of discriminants in metric vector spaces}, Advances in Mathematics, 62 (1986), pp.~285--312. \bibitem{Edmonds:Cov} {\sc J.~Edmonds}, {\em Lehman's switching game and a theorem of {T}utte and {N}ash-{W}illiams}, J. Res. Bur. Standards Sect. B, 69B (1965), pp.~73--77. \bibitem{ghier:93} {\sc L.~Ghier}, {\em Double occurence words with the same alternance graph}, Ars Combinatoria, 36 (1993), pp.~57--64. \bibitem{Jackson2} {\sc B.~Jackson}, {\em A characterization of graphs having three pairwise compatible {E}uler tours}, J. Combin. Theory Ser. B, 53 (1991), pp.~80--92. \bibitem{Jackson1} \leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em Supplementary {E}ulerian vectors in isotropic systems}, J. Combin. Theory Ser. B, 53 (1991), pp.~93--105. \bibitem{KabadiChandra} {\sc S.~N. Kabadi and R.~Chandrasekaran}, {\em On totally dual integral systems}, Discrete Applied Math., 26 (1990), pp.~87--104. \bibitem{Tardos:gmat} {\sc E.~Tardos}, {\em Generalized matroids and supermodular colourings}, Colloquia Societatis Janos Bolyai, 40 (1982), pp.~359--381. \bibitem{Welsh:BookMatro} {\sc D.~Welsh}, {\em Matroid Theory}, Academic Press, 1976. \end{thebibliography} \printindex \end{document}