# Cyclic Orderings of Paving Matroids

Sean McGuinness
Dept. of Mathematics
Thompson Rivers University
McGill Road, Kamloops BC
V2C5N3 Canada
email<EMAIL_ADDRESS>
###### Abstract

A matroid $M$ of rank $r$ is cyclically orderable if there is a cyclic
permutation of the elements of $M$ such that any $r$ consecutive elements form
a basis in $M$. An old conjecture of Kajitani, Miyano, and Ueno states that a
matroid $M$ is cyclically orderable if and only if for all $\mathchar
31\relax\neq X\subseteq E(M),\ \frac{|X|}{r(X)}\leq\frac{|E(M)|}{r(M)}.$ In
this paper, we verify this conjecture for all paving matroids.

AMS Subject Classifications (2012) : 05D99,05B35.

##  1 Introduction

A matroid $M$ of rank $r$ is cyclically orderable if there is a a cyclic
permutation of the elements of $M$ such that any $r$ consecutive elements is a
base.

For a matroid $M$ and a subset $\mathchar 31\relax\neq X\subseteq E(M),$ we
define $\beta(X):=\frac{|X|}{r(X)},$ if $r(X)\neq 0$; otherwise,
$\beta(X):=\infty.$ Let $\gamma(M)=\max_{\mathchar 31\relax\neq X\subseteq
E(M)}\beta(X).$

In [6], Kajitani, Miyano, and Ueno made the following conjecture:

  * 1.1 Conjecture

A matroid $M$ is cyclically orderable if and only if $\gamma(M)=\beta(E(M)).$

Despite having been around for decades, the above conjecture is only known to
be true for a few special classes of matroids. In [2], the conjecture was
shown to be true sparse paving matroids. Perhaps the strongest result thus far
can be found in [8] where it was shown that Conjecture 1 is true when $r(M)$
and $|E(M)|$ are relatively prime.

  * 1.2 Theorem ( Van Den Heuvel and Thomasse )

Let $M$ be a matroid for which $\gamma(M)=\beta(E(M)).$ If $|E(M)|$ and $r(M)$
are relatively prime, then $M$ has a cyclic ordering.

It follows from recent results in [1] on split matroids, a class which
includes paving matroids, that the conjecture is true for paving matroids $M$
where $|E(M)|\leq 2r(M).$ Coupled with Theorem 1, we can replace $2r(M)$ by
$2r(M)+1$ in this bound since $|E(M)|$ and $r(M)$ are relatively prime when
$|E(M)|=2r(M)+1.$ In this paper, we verify Conjecture 1 for all paving
matroids.

  * 1.3 Theorem

Let $M$ be a paving matroid where $\gamma(M)=\beta(E(M)).$ Then $M$ is
cyclically orderable.

For concepts, terminology, and notation pertaining to matroids, we shall
follow Oxley [7] when possible. For a matroid $M$, ${\cal C}(M)$ will denote
the set of all circuits of $M.$

For a finite set $A$ and integer $k\leq|A|$, we let ${\binom{A}{k}}$ denote
the set of all $k$-subsets of $A.$ For a collection of subsets ${\cal A}$ and
integer $k$ we let ${\binom{k}{{\cal A}}}$ denote the set of all sets in
${\cal A}$ having cardinality $k.$

For a set $A$ and elements $x_{1},\dots,x_{k}$ we will often write, for
convenience, $A+x_{1}+x_{2}+\cdots+x_{k}$ (resp. $A-x_{1}-x_{2}-\cdots-x_{k}$)
in place of $A\cup\\{x_{1},\dots,x_{k}\\}$ (resp,
$A\backslash\\{x_{1},\dots,x_{k}\\}$).

For a positive integer $n$, we let $[n]$ denote the set $\\{1,\dots,n\\}.$

###  1.1 Idea behind the proof

To prove the main theorem, we shall use induction on $|E(M)|$. To do this, we
shall first remove a basis $S$ from $M$ so that the resulting matroid
$M^{\prime}$ satisfies $\gamma(M^{\prime})=\beta(E(M)-S).$ While generally
such a basis $S$ may not exist, we will show that such bases exist when
$|E(M)|\geq 2r(M)+2.$ Applying the inductive assumption, $M^{\prime}$ is
cyclically orderable, with a cyclic ordering say $e_{1}e_{2}\cdots e_{m}.$ We
will show that for some $i\in[m]$ and some ordering of $S$, say
$s_{1}s_{2}\cdots s_{r}$ (where $r=r(M)$), the ordering $e_{1}\cdots
e_{i}s_{1}s_{2}\cdots s_{r}e_{i+1}\cdots e_{m}$ is a cyclic ordering of $M$.
To give a rough idea of how to prove this, we will illustrate the proof in the
case where $r(M)=3.$

Suppose $S=\\{s_{1},s_{2},s_{3}\\}$ is a basis of $M$ where
$\gamma(M\backslash S)=\beta(E(M)-S)$ and $r(M\backslash S)=3.$ Assume that
$M^{\prime}=M\backslash S$ has a cyclic ordering $e_{1}e_{2}\cdots e_{m}$.
Suppose we try to insert the elements of $S$, in some order, between $e_{m}$
and $e_{1}$, so as to achieve a cyclic ordering for $M.$ Assume this is not
possible. Then for every permutation $\pi$ of $\\{1,2,3\\}$, $e_{1}e_{2}\cdots
e_{m}s_{\pi(1)}s_{\pi(2)}s_{\pi(3)}$ is not a cyclic ordering of $M.$ Thus for
all permutations $\pi$ of $\\{1,2,3\\}$, at least one of
$\\{e_{m-1},e_{m},s_{\pi(1)}\\},\
\\{e_{m},s_{\pi(1)},s_{\pi(2)}\\},\\{s_{\pi(2)},s_{\pi(3)},e_{1}\\},$ or
$\\{s_{\pi(3)},e_{1},e_{2}\\}$ is a circuit. As an exercise for the reader,
one can now show that there exist distinct $i,j\in\\{1,2,3\\}$ such
$\\{s_{i},e_{m-1},e_{m}\\},\\{s_{j},e_{1},e_{2}\\},S-s_{i}+e_{m},$ and
$S-s_{j}+e_{1}$ are circuits. We may assume that $i=1$ and $j=2$. If instead,
one were to assume that one could not insert the elements of $S$ in some order
between $e_{1}$ and $e_{2}$ so as to achieve a cyclic ordering of $M$, then as
above, there exist distinct $i^{\prime},j^{\prime}\in\\{1,2,3\\},$ such that
$\\{s_{i^{\prime}},e_{m},e_{1}\\},\\{s_{j^{\prime}},e_{2},e_{3}\\},S-s_{i^{\prime}}+e_{1},$
and $S-s_{j^{\prime}}+e_{2}$ are circuits. If $i^{\prime}=1,$ then
$\\{s_{1},e_{m-1},e_{m}\\}$ and $\\{s_{1},e_{m},e_{1}\\}$ are circuits. The
circuit elimination axiom (together with the fact that $M$ is a paving
matroid) would then imply that
$(\\{s_{1},e_{m-1},e_{m}\\}\cup\\{s_{1},e_{m},e_{1}\\})-s_{1}=\\{e_{m-1},e_{m},e_{1}\\}$
is a circuit, contradicting our assumption that $e_{1}e_{2}\cdots e_{m}$ is a
cyclic ordering of $M^{\prime}.$ Also, if $i^{\prime}=2$, then
$\\{s_{2},e_{m},e_{1}\\}$ and $\\{s_{2},e_{1},e_{2}\\}$ are circuits and hence
by the circuit elimination axiom, $\\{e_{m},e_{1},e_{2}\\}$ is a circuit, a
contradiction. Thus $i^{\prime}\not\in\\{1,2\\}$ and hence $i^{\prime}=3$ and
$\\{e_{m},e_{1},s_{3}\\}$ and $\\{s_{1},s_{2},e_{2}\\}$ are circuits. Given
that $\\{s_{2},e_{1},e_{2}\\}$ is also a circuit, it follows that
$\\{e_{1},e_{2}\\}\subset\mathrm{cl}(\\{s_{1},s_{2}\\}).$ Now
$j^{\prime}\in\\{1,2\\},$ and $\\{s_{i^{\prime}},e_{2},e_{3}\\}$ is a circuit,
implying that $e_{3}\in\mathrm{cl}(\\{s_{1},s_{2}\\}).$ However, this is
impossible since (by assumption) $\\{s_{1},s_{2},s_{3}\\}$ is a basis. Thus
there must be some ordering of $S$ so that when the elements of $S$ are
inserted (in this order) between $e_{m}$ and $e_{1}$ or between $e_{1}$ and
$e_{2}$, the resulting ordering is a cyclic ordering for $M.$

##  2 Removing a basis from a matroid

Let $M$ be a paving matroid where $\gamma(M)=\beta(E(M)).$ As a first step in
the proof of Theorem 1, we wish to find a basis $B$ of $M$ where
$\gamma(M\backslash B)=\beta(E(M)-B).$ Unfortunately, there are matroids where
there is no such basis, as for example, the Fano plane. In this section, we
will show that, despite this, such bases exist when $|E(M)|\geq 2r(M)+2.$

The following is an elementary elementary observation which we will refer to
in a number of places.

  * 2.1 Observation

For a basis $B$ in a matroid $M$ and an element $x\in E(M)-B$, the set $B+x$
has a unique circuit which contains $x$.

We will need the following strengthening of Edmonds’ matroid partition theorem
[3] given in [4]:

  * 2.2 Theorem

Let $M$ be a matroid where $\gamma(M)=k+\varepsilon,$ where $k\in\mathbb{N}$
and $0\leq\varepsilon<1,$ then $E(M)$ can be partitioned into $k+1$
independent sets with one set of size at most $\varepsilon r(M).$

We are now in a position to prove the main result of this section.

  * 2.3 Proposition

Let $M$ be a paving matroid where $|E(M)|\geq 2r(M)+2$ and $r(M)\geq 3.$ Then
there is a basis $B\subset E(M)$ where $\gamma(M\backslash B)=\beta(E(M-B))$
and $r(M\backslash B)=r(M).$

###### Proof.

Let $\gamma(M)=k+\frac{\ell}{r(M)}$ where $0\leq\ell<r(M)$ and $k\geq 2.$ Then
$|E(M)|=kr(M)+\ell$ and it follows by Theorem 2 one can partition $E(M)$ into
$k$ bases $F_{1},\dots,F_{k}$ and one independent set $F_{k+1}$ having $\ell$
elements. Let $r=r(M).$ If $\ell=0,$ then $|E(M)|=kr\geq 3r.$ In this case, we
can take $B=F_{k}$ since for $M^{\prime}=M\backslash F_{k},$ it is seen that
$\gamma(M^{\prime})=k-1=\beta(E(M^{\prime})).$ Thus we may assume that
$\ell>0.$

Let $F_{k}=\\{x_{1},x_{2},\dots,x_{r}\\}.$ Suppose there exist distinct
$i,j\in[r]$ for which $r((F_{k}-x_{i})\cup F_{k+1})=r((F_{k}-x_{j})\cup
F_{k+1})=r-1.$ Let $x\in F_{k+1}.$ Then $x+(F_{k}-x_{i})$ and
$x+(F_{k}-x_{j})$ are (distinct) circuits, contradicting Observation 2. Thus
there is at most one $i\in[r]$ for which $r((F_{k}-x_{i})\cup F_{k+1})=r-1.$
As such, we may assume that for $i=1,\dots,r-1$,
$r((F_{k}-x_{i})\cup F_{k+1})=r.$ Thus for $i=1,\dots,r-1$, there is a subset
$A_{i}\subseteq F_{k}-x_{i}$ such that $B_{i}=A_{i}\cup F_{k+1}$ is a basis
for $M.$

We shall show that there exists $i\in[r-1]$ such that $B=B_{i}$ is a basis
satisfying the proposition. Suppose to the contrary that this is false. Then
for all $i\in[r-1],$ there is a subset $X_{i}\subseteq E(M)-B_{i}$ for which
$\beta(X_{i})>\beta(E-B_{i}).$ Since $k>1$, we have that $F_{1}\subseteq
E(M\backslash B_{i})$ and hence $r(M\backslash B_{i})=r.$ Thus we have
$\beta(E-B_{i})=k-1+\frac{\ell}{r}.$ If $r(X_{i})<r-1,$ then $X_{i}$ is
independent and hence $\beta(X_{i})=1\leq\beta(E-B_{i}).$ Thus $r(X_{i})\geq
r-1$ and seeing as $\beta(X_{i})>\beta(E(M)-B_{i}),$ we have $r(X_{i})\leq
r-1.$ Consequently, $r(X_{i})=r-1$ and
$\beta(X_{i})=\frac{|X_{i}|}{r-1}>k-1+\frac{\ell}{r}$ Since $r(X_{i})=r-1,$ it
follows that for $j=1,\dots,k-1$, $|X_{i}\cap F_{j}|\leq r-1.$ Consequently,
$|X_{i}|\leq(k-1)(r-1)+\ell$. If $|X_{i}|<(k-1)(r-1)+\ell,$ then
$\beta(X_{i})\leq k-1+\frac{\ell-1}{r-1}$, implying that $\beta(X_{i})\leq
k-1+\frac{\ell}{r}$ (because $\ell\leq r-1$), contradicting our assumptions.
Thus it follows that $|X_{i}|=(k-1)(r-1)+\ell$ and for all $i\in[r-1]$ and for
all $j\in[k-1],$ $|X_{i}\cap F_{j}|=r-1$, and $F_{k}-A_{i}\subset X_{i}$. Thus
for all $i\in[r-1]$ and for all $j\in[k-1],$ $X_{ij}=X_{i}\cap F_{j}$ spans
$X_{i}.$ Since all circuits in $M$ have size at least $r$, it follows that for
all $j\in[k-1],$ and for all $x\in X_{i}-X_{ij},$ $X_{ij}+x$ is a circuit.

Suppose $k\geq 3.$ Let $i,j\in[r-1]$ where $i$ and $j$ are distinct. Then for
all $x\in X_{i2}\cap X_{j2}$, we have that $x+X_{i1}$ and $x+X_{j1}$ are
circuits. It follows by Observation 2 that $X_{i1}=X_{j1}$ and thus
$\mathrm{cl}(X_{i})=\mathrm{cl}(X_{j}).$ Let $X=\mathrm{cl}(X_{i}).$ Then
$\\{x_{i},x_{j}\\}\subset X$, and since this applies to all $j\in[r-1]-i$, it
follows that $F_{k}-x_{r}\subset X.$ If $r((F_{k}-x_{r})\cup F_{k+1})=r,$ then
it would also follow that $x_{r}\in X,$ implying that $F_{k}\subset X,$ an
impossibility (since $r(X)=r-1$). Thus $r((F_{k}-x_{r})\cup F_{k+1})=r-1,$ and
hence $F_{k+1}\subset X.$ Now it is seen that
$\beta(X)=\frac{|X|}{r(X)}=\frac{k(r-1)+\ell}{r-1}=k+\frac{\ell}{r-1}>\gamma(M),$
a contradiction.

From the above, we have $k=2.$ Since $|E(M)|\geq 2r(M)+2,$ we have $\ell\geq
2.$ Let $i,j\in[r-1]$ be distinct integers. Suppose there exists
$x\in(F_{2}-A_{i})\cap(F_{2}-A_{j}).$ Then $x+X_{i1}$ and $x+X_{j1}$ are
circuits, implying that $X_{i1}=X_{j1}$ and
$\mathrm{cl}(X_{i})=\mathrm{cl}(X_{j}).$ Suppose instead that
$(F_{2}-A_{i})\cap(F_{2}-A_{j})=\mathchar 31\relax.$ That is,
$F_{2}-A_{i}\subseteq A_{j}$ (and $F_{2}-A_{j}\subseteq A_{i}$). Since
$\ell\geq 2,$ there exists $x_{s}\in F_{2}-A_{i}-x_{i}$. Now $x_{s}+B_{i}$
contains a (unique) circuit $C$ where $x_{s}\in C.$ Also, there exists
$x_{t}\in C\cap(F_{2}-A_{j})$ since
$|C\cap(F_{2}-A_{j})|\geq|C|-(r-\ell)-1\geq r-(r-\ell)-1\geq\ell-1\geq 1$.
Noting that $B_{i}-x_{t}+x_{s}$ is also a basis, we can take
$A_{t}=A_{i}-x_{t}+x_{s}$ and $B_{t}=B_{i}-x_{t}+x_{s}.$ Consequently,
$x_{t}\in(F_{2}-A_{t})\cap(F_{2}-A_{j})$ and also,
$x_{i}\in(F_{2}-A_{t})\cap(F_{2}-A_{i}).$ Thus by the above we have
$\mathrm{cl}(X_{i})=\mathrm{cl}(X_{t})=\mathrm{cl}(X_{j}).$ It follows that
for all $j\in[r-1]-1,$ $\mathrm{cl}(X_{1})=\mathrm{cl}(X_{j}).$ Let
$X=\mathrm{cl}(X_{1}).$ We can now adopt the same arguments as in the case
$k\geq 3$ to show that $\beta(X)=k+\frac{\ell}{r-1}>\gamma(M)$, yielding a
contradiction. Thus for at least one integer $i\in[r-1]$, $B=B_{i}$ is a basis
satisfying the proposition. This completes the proof. ∎

##  3 $\mathbf{S}$-Pairs

In the second part of the proof of Theorem 1, we will need to establish the
existence of certain circuits. More specifically, suppose $S$ is a basis as
described in Proposition 2 where we assume that $S=\\{s_{1},\dots,s_{r}\\}.$
Suppose $e_{1}e_{2}\dots e_{m}$ is cyclic ordering for $M^{\prime}=M\backslash
S.$ Suppose that we wish to extend this ordering to a cyclic ordering for $M$
by inserting the elements of $S$, in some order, between $e_{m}$ and $e_{1}.$
Assuming this is not possible, then it turns out (as in the case where
$r(M)=3$) that there must be certain circuits. For example, there are subsets
$\\{B_{1},B_{2}\\}\in{\binom{S}{n-2}}$ such that for all $s_{i}\in B_{1},\
\\{s_{i},e_{m-r+2},\dots,e_{m}\\}\in{\cal C}(M)$ and for all $s_{i}\in
B_{2},\\{s_{1},e_{1},\dots,e_{r-1}\\}\in{\cal C}(M).$ The results in this
section and its successor, lay the ground work to prove the existence of such
circuits.

Let $S$ be a finite, nonempty set. For $i=1,2,$ let ${\cal S}_{i}\subseteq
2^{S}.$ We call the pair $({\cal S}_{1},{\cal S}_{2})$ an $\mathbf{S}$-pair if
it has the following properties.

  * (S1)

For $i=1,2,$ if $A,B\in{\cal S}_{i}$ where $|A|=|B|+1$ and $B\subset A,$ then
${\binom{A}{|B|}}\subseteq{\cal S}_{i}.$

  * (S2)

For $i=1,2$, if $A,B\in{\cal S}_{i}$ where $|A|=|B|$ and $|A\cap B|=|A|-1,$
then $A\cup B\in{\cal S}_{i}.$

  * (S3)

For $i=1,2,$ ${\binom{S}{1}}\not\subseteq{\cal S}_{i}$ and $S\not\in{\cal
S}_{i}.$

  * (S4)

For $k=1,\dots,|S|-1$, if ${\binom{S-x}{k}}\subseteq{\cal S}_{1}$ for some
$x\in S,$ then ${\binom{S-x}{|S|-k}}\not\subseteq{\cal S}_{2}.$

In the next section, we shall need the following observations for an $S$-pair
$({\cal S}_{1},{\cal S}_{2})$ where $|S|=n.$

  * 3.1 Observation

Let $A\subseteq S$ where $\alpha=|A|.$ Suppose that for some some
$i\in\\{1,2\\}$ and some $j\in[\alpha],$ ${\binom{A}{j}}\subseteq{\cal
S}_{i}.$ Then for $k=j,\dots,\alpha,$ ${\binom{A}{k}}\subseteq{\cal S}.$

###### Proof.

We may assume that $j<\alpha.$ Suppose that for some
$k\in\\{j,\dots,\alpha-1\\},$ ${\binom{A}{k}}\subseteq{\cal S}_{i}.$ Let
$B\in{\binom{A}{k+1}}.$ Let $\\{b_{1},b_{2}\\}\subseteq B$ and for $s=1,2,$
let $B_{s}=B-b_{s}$. By assumption, for $s=1,2$, $B_{s}\in{\cal S}_{i}.$ It
now follows by (S2) that $B=B_{1}\cup B_{2}\in{\cal S}_{i}.$ It now follows
that ${\binom{A}{k+1}}\subseteq{\cal S}_{i}.$ Arguing inductively, we see that
for $k=j,\dots,\alpha,$ ${\binom{A}{k}}\subseteq{\cal S}.$ ∎

  * 3.2 Observation

Let $A\in{\cal S}_{i}$ where $\alpha=|A|.$ Suppose that for some
$j\in[\alpha-1]$ and $x\in A,$ we have ${\binom{A-x}{j}}\subseteq{\cal
S}_{i}.$ Then ${\binom{A}{j}}\subseteq{\cal S}_{i}.$

###### Proof.

Suppose first that $j=\alpha-1.$ Then $A^{\prime}=A-x\in{\cal S}_{i}.$ It
follows by (S1) that ${\binom{A}{\alpha-1}}\subseteq{\cal S}_{i}.$ Assume that
$j<\alpha-1$ and the assertion holds for $j+1;$ that is, if
${\binom{A-x}{j+1}}\subseteq{\cal S}_{i}$, then
${\binom{A}{j+1}}\subseteq{\cal S}_{i}.$ Suppose
${\binom{A-x}{j}}\subseteq{\cal S}_{i}.$ Then by Observation 3,
${\binom{A-x}{j+1}}\subseteq{\cal S}_{1}.$ Thus by assumption,
${\binom{A}{j+1}}\subseteq{\cal S}_{i}.$ Let $B\in{\binom{A}{j}}$, where $x\in
B.$ Let $y\in A-B$ and let $B^{\prime}=B-x+y.$ Since
$B^{\prime}\in{\binom{A-x}{j}}$, it follows that $B^{\prime}\in{\cal S}_{1}.$
However, we also have that $B+y\in{\cal S}_{i}.$ Thus it follows by (S1) that
$B\in{\cal S}_{i}.$ We now see that ${\binom{A}{j}}\subseteq{\cal S}_{i}.$ The
assertion now follows by induction. ∎

  * 3.3 Observation

Let $A\subseteq S.$ Suppose for some $x\in A,$ $i\in\\{1,2\\},$ and $j\geq 2,$
we have that $\\{B\in{\binom{A}{j}}\ \big{|}\ x\in B\\}\subseteq{\cal S}_{i}.$
Then ${\binom{A}{j}}\subseteq{\cal S}_{i}$ and $A\in{\cal S}_{i}.$

###### Proof.

We may assume that $|A|\geq j+1.$ Let $B^{\prime}\in{\binom{A-x}{j}}.$ Let
$\\{y_{1},y_{2}\\}\subseteq B^{\prime}$ and for $s=1,2$, let
$B_{s}=B^{\prime}-y_{s}+x.$ By assumption, $\\{B_{1},B_{2}\\}\subset{\cal
S}_{i}.$ It follows by (S2) that $B=B^{\prime}+x=B_{1}\cup B_{2}\in{\cal
S}_{i}.$ Thus by (S1) we have that ${\binom{B}{j}}\subseteq{\cal S}_{i}$ and
hence $B^{\prime}\in{\cal S}_{i}.$ It now follows that
${\binom{A}{j}}\subseteq{\cal S}_{i}$, and moreover, $A\in{\cal S}_{i}$ (by
Observation 3). ∎

##  4 Order consistent pairs

Let $S$ be a set of $n$ elements and let ${\cal S}_{1}\subseteq 2^{S}$ and
${\cal S}_{2}\subseteq 2^{S}.$ We say that the pair $({\cal S}_{1},{\cal
S}_{2})$ is order consistent with respect to $S$ if for any ordering
$s_{1}s_{2}\cdots s_{n}$ of $S$, there exists $i\in[n]$ for which either
$\\{s_{1},\cdots,s_{i}\\}\in{\cal S}_{1}$ or $\\{s_{i},\dots,s_{n}\\}\in{\cal
S}_{2}.$

Let $\Pi$ denote the set of all permutations of $[n].$ Let $\pi\in\Pi.$ We say
that a subset $A\in{\cal S}_{1}$ (resp. $B\in{\cal S}_{2}$) is
$\mathbf{\pi}$-relevant if there exists $i\in[n]$ such that
$A=\\{s_{\pi(1)},\dots,s_{\pi(i)}\\}$ (resp.
$B=\\{s_{\pi(i)},\dots,s_{\pi(n)}\\}$). Let $\Pi^{\prime}\subseteq\Pi$ be a
subset of permutations. We say that a subset ${\cal A}\subseteq{\cal S}_{1}$
(resp. $\mathscr{B}\subseteq{\cal S}_{2}$) is $\mathbf{\Pi}^{\prime}$-relevant
if for all $A\in{\cal A}$ (resp. $B\in\mathscr{B}$), there exists
$\pi\in\Pi^{\prime}$ such that $A$ (resp. $B$) is $\pi$-relevant. We say that
$({\cal A},\mathscr{B})$ is order consistent relative to $\Pi^{\prime}$ if for
all $\pi\in\Pi^{\prime},$ either there exists $A\in{\cal A}$ for which $A$ is
$\pi$-relevant, or there exists $B\in\mathscr{B}$ for which $B$ is
$\pi$-relevant. Furthermore, we say for ${\cal A}\subseteq{\cal H}_{1}$ and
$\mathscr{B}\subseteq{\cal H}_{2}$, the pair $({\cal A},\mathscr{B})$ is
order-consistent relative to $\Pi^{\prime}$ if for all $\pi\in\Pi^{\prime},$
there exists $i\in[r]$ such that either

For $i\in[n],$ we let $\Pi_{i}$ denote the set of permutations $\pi\in\Pi$
where $\pi(1)=i.$ The following theorem will be instrumental in the proof of
main theorem.

  * 4.1 Theorem

Let $S$ be a set where $|S|=n\geq 3$ and let $({\cal S}_{1},{\cal S}_{2})$ be
an $S$-pair. Then $({\cal S}_{1},{\cal S}_{2})$ is order consistent if and
only if there exists $(A_{1},A_{2})\in{\binom{n-1}{{\cal
S}_{1}}}\times{\binom{n-1}{{\cal S}_{2}}}$, $A_{1}\neq A_{2}$, and
$\\{B_{1},B_{2}\\}\subset{\binom{S}{n-2}}$ where for $i=1,2$, $B_{i}\cap
A_{i}=B_{1}\cap B_{2}\in{\binom{A_{1}\cap A_{2}}{n-3}}$ and
${\binom{B_{i}}{1}}\subset{\cal S}_{i}.$

###### Proof.

To prove sufficiency, suppose $A_{i},B_{i},\ i=1,2$ are as described in the
theorem. Note that since $A_{1}\neq A_{2},$ we have that for $i=1,2,$
$B_{i}\subset A_{3-i}$ and $A_{i}-A_{3-i}\subseteq B_{3-i}.$ For $i=1,2,$ let
${\cal T}_{i}=\\{A_{i}\\}\cup{\binom{B_{i}}{1}}.$ We need only show that
$({\cal T}_{1},{\cal T}_{2})$ is order consistent. Suppose it is not. Clearly
it is order consistent relative to the set of permutations $\pi$ for which
$s_{\pi(1)}\in B_{1}$ or $s_{\pi(r)}\in B_{2}.$ Let $\pi\in\Pi$ where
$s_{\pi(1)}\not\in B_{1}$ and $s_{\pi(r)}\not\in B_{2}.$ If $s_{\pi(1)}\not\in
A_{2},$ then $A_{2}=\\{s_{\pi(2)},\dots,s_{\pi(r)}\\}$ and $A_{2}$ is
$\pi$-relevant. Thus $A_{2}-B_{1}=\\{s_{\pi(1)}\\}=(A_{1}\cap A_{2})-B_{1}.$
By similar reasoning, we also have $A_{1}-B_{2}=\\{s_{\pi(r)}\\}=(A_{1}\cap
A_{2})-B_{1}.$ However, our assumptions imply that $(A_{1}\cap
A_{2})-B_{1}=(A_{1}\cap A_{2})-B_{2}$, and consequently,
$s_{\pi(1)}=s_{\pi(r)}.$ This yields a contradiction. It follows that $({\cal
T}_{1},{\cal T}_{2})$ is order consistent.

To prove necessity, we shall use induction on $n$. It is a straightforward
exercise to verify the assertion for $n=3.$ We shall assume that $n\geq 4$ and
the assertion is valid to all values less than $n$. That is, if $|S|<n,$ and
$({\cal S}_{1},{\cal S}_{2})$ is an $S$-pair which is order consistent, then
there exist sets $A_{i},B_{i},\ i=1,2$ as described in the theorem. Assume now
that $|S|=n$ and $({\cal S}_{1},{\cal S}_{2})$ is an $S$-pair which is order
consistent.

For all $k\in[n],$ let $S^{k}=S-s_{k}$ and let ${\cal S}_{1}^{k}=\\{A-s_{k}\
\big{|}\ A\in{\cal S}_{1}\ \mathrm{and}\ s_{k}\in A\\}$ and ${\cal
S}_{2}^{k}=\\{A\in{\cal S}_{2}\ \big{|}\ s_{k}\notin A\\}.$ We observe that
properties (S1) and (S2) still hold for the pair $({\cal S}_{1}^{k},{\cal
S}_{2}^{k})$ whereas (S3) and (S4) may not.

  * (A) For all $k\in[n],$ one of the following holds:

    * (a1)

$\\{s_{k}\\}\in{\cal S}_{1}.$

    * (a2)

$S^{k}\in{\cal S}_{2}.$

    * (a3)

${\binom{S^{k}}{1}}\subseteq{\cal S}_{2}.$

    * (a4)

For some $D\in{\binom{S^{k}}{n-2}},$ and positive integers $i,j$ where
$i+j=n-1,$ ${\binom{D}{i}}\subseteq{\cal S}_{1}^{k}$ and
${\binom{D}{j}}\subseteq{\cal S}_{2}^{k}.$

    * (a5)

There exist $(A_{1}^{k},A_{2}^{k})\in{\binom{n-2}{{\cal
S}_{1}^{k}}}\times{\binom{n-2}{{\cal S}_{2}^{k}}},$ $A_{1}^{k}\neq A_{2}^{k}$,
and $\\{B_{1}^{k},B_{2}^{k}\\}\subseteq{\binom{S^{k}}{n-3}}$ where for
$i=1,2$, $B_{i}^{k}\cap A_{i}^{k}=B_{1}^{k}\cap
B_{2}^{k}\in{\binom{A_{1}^{k}\cap A_{2}^{k}}{n-4}}$ and
${\binom{B_{i}^{k}}{1}}\subseteq{\cal S}_{i}^{k}.$

###### Proof.

Let $k\in[n].$ Assume that none of (a1) - (a4) hold for $k.$ We will show that
(a5) must hold for $k.$ Clearly $S^{k}\not\in{\cal S}_{1}^{k},$ for otherwise
this would mean that $S\in{\cal S}_{1}$ which is not allowed by (S3). We also
have that ${\binom{S^{k}}{1}}\not\subseteq{\cal S}_{1}^{k}$. For if this was
the case, then it would follow that for all $i\in[n]-k,$
$\\{s_{i},s_{k}\\}\in{\cal S}_{1}.$ It would then follow by Observation 3 that
$S\in{\cal S}_{1}$ violating (S3). Given that (a2) -(a4) do not hold, $({\cal
S}_{1}^{k},{\cal S}_{2}^{k})$ is seen to be an $S^{k}$-pair. Let
$\pi\in\Pi_{k}$ and let $\pi^{\prime}=\pi(2)\pi(3)\cdots\pi(n)$. Since $({\cal
S}_{1},{\cal S}_{2})$ is order preserving, there exists $A\in{\cal S}_{1}$ or
$B\in{\cal S}_{2}$ and $i\in[n]$ such that either
$A=\\{s_{\pi(1)},\dots,s_{\pi(i)}\\}$ or
$B=\\{s_{\pi(i)},\dots,s_{\pi(n)}\\}.$ Given that (a1) and (a2) do not hold,
it follows that in the former case, $i\geq 2,$
$A^{\prime}=\\{s_{\pi(2)},\dots,s_{\pi(i)}\\}\in{\cal S}_{1}^{k}$ and hence
$A^{\prime}$ is $\pi^{\prime}$-relevant. In the latter case, $i\geq 3$ and
$B^{\prime}=\\{s_{\pi(i)},\dots,s_{\pi(n)}\\}\in{\cal S}_{2}^{k}$ and
$B^{\prime}$ is $\pi^{\prime}$-relevant. Given that $\pi$ was arbitrarily
chosen from $\Pi_{k}$, we see that $({\cal S}_{1}^{k},{\cal S}_{2}^{k})$ is
order preserving with respect to $S^{k}.$ By the inductive assumption, there
exist $(A_{1}^{k},A_{2}^{k})\in{\binom{n-2}{{\cal
S}_{1}^{k}}}\times{\binom{n-2}{{\cal S}_{2}^{k}}},$ $A_{1}^{k}\neq A_{2}^{k},$
and $\\{B_{1}^{k},B_{2}^{k}\\}\subset{\binom{S^{k}}{n-3}}$ where for $i=1,2$,
$B_{i}^{k}\cap A_{i}^{k}=B_{1}^{k}\cap B_{2}^{k}\in{\binom{A_{1}^{k}\cap
A_{2}^{k}}{n-4}}$ and ${\binom{B_{i}^{k}}{1}}\subset{\cal H}_{i}^{k}.$ Thus
(a5) holds for $k.$ ∎

  * (B) There is at most one integer $k$ for which (a2) or (a3) holds.

###### Proof.

It suffices to prove that (a2) can hold for at most one integer $k$; if (a3)
holds for some integer $k$, then it follows by Observation 3 that
$S^{k}\in{\cal S}_{2}$, and hence (a2) holds for $k.$ Suppose to the contrary
that (a2) holds for distinct integers $k$ and $\ell.$ Then $S^{k}\in{\cal
S}_{2}$ and $S^{\ell}\in{\cal S}_{2}.$ It then follows by (S2) that
$S=S^{k}\cup S^{\ell}\in{\cal S}_{2}.$ However, this violates (S3). Thus no
two such integers can exist. ∎

  * (C) Property (a4) holds for at most one integer $k.$

###### Proof.

Suppose (a4) holds for distinct integers $k$ and $\ell.$ Then for some
$i,j,i^{\prime},j^{\prime}$ where $i+j=n-1$, $i^{\prime}+j^{\prime}=n-1$, and
subsets $D\in{\binom{S^{k}}{n-2}}$ and $D^{\prime}\in{\binom{S^{\ell}}{n-2}},$
we have ${\binom{D}{i}}\subseteq{\cal S}_{1}^{k}$,
${\binom{D}{j}}\subseteq{\cal S}_{2}^{k},$
${\binom{D^{\prime}}{i^{\prime}}}\subseteq{\cal S}_{1}^{\ell},$ and
${\binom{D^{\prime}}{j^{\prime}}}\subseteq{\cal S}_{2}^{\ell}.$ We have that
$F_{1}=D+s_{k}\in{\cal S}_{1}$ and $F_{2}=D^{\prime}+s_{\ell}\in{\cal S}_{1}.$
If $F_{1}\neq F_{2},$ then by property (S2), $F_{1}\cup F_{2}=S\in{\cal
S}_{1},$ violating (S3). Thus $F_{1}=F_{2}=S-s=S^{\prime}$ for some $s\in
S-s_{k}-s_{\ell}$ and $S^{\prime}\in{\cal S}_{1}.$

Let $i^{*}=\max\\{i,i^{\prime}\\}$ and $j^{*}=\min\\{j,j^{\prime}\\}.$ We
claim that ${\binom{S^{\prime}}{i^{*}+1}}\subseteq{\cal S}_{1}$ and
${\binom{S^{\prime}}{j^{*}}}\subseteq{\cal S}_{2}.$ To prove the first
assertion, we first note that it is true when $i^{*}=n-2$ since
$S^{\prime}\in{\cal S}_{1}.$ We may assume that $i^{*}<n-2.$ Then $i^{*}\leq
n-3=|D\cap D^{\prime}|=|S^{\prime}-s_{k}-s_{\ell}|.$ By assumption,
${\binom{D\cap D^{\prime}}{i^{*}}}\subset{\cal S}_{1}^{k}.$ Thus for all
$X\in{\binom{S^{\prime}-s_{k}-s_{\ell}}{i^{*}}},\ X+s_{k}\in{\cal S}_{1}.$ It
now follows by Observation 3 that
${\binom{S^{\prime}-s_{\ell}}{i^{*}+1}}\subseteq{\cal S}_{1}.$ Now Observation
3 implies that ${\binom{S^{\prime}}{i^{*}+1}}\subseteq{\cal S}_{1}.$

To prove that ${\binom{S^{\prime}}{j^{*}}}\subseteq{\cal S}_{2},$ first
suppose that $j^{*}=j=j^{\prime}=n-2$. In this case, $D,D^{\prime}\in{\cal
S}_{2}$ and hence $S^{\prime}=D\cup D^{\prime}\in{\cal S}_{2}$ by (S2). It
would then follow by (S1) that ${\binom{S^{\prime}}{n-2}}\subseteq{\cal
S}_{2}.$ Thus we may assume that $j^{*}<n-2.$ We have that ${\binom{D\cap
D^{\prime}}{j^{*}}}\subseteq{\cal S}_{2}.$ Given that $D\cap
D^{\prime}=S^{\prime}-s_{k}-s_{\ell},$ it follows by Observation 3 that
${\binom{S^{\prime}-s_{\ell}}{j^{*}}}\subseteq{\cal S}_{2}$ and this in turn
implies that ${\binom{S^{\prime}}{j^{*}}}\subseteq{\cal S}_{2}.$

Given that $i+j=i^{\prime}+j^{\prime}=n-1$, it follows that $i^{*}\leq
n-1-j^{*},$ and hence $i^{*}+1+j^{*}\leq n.$ However, this would mean that
(S4) is violated. Thus (a4) can hold for at most one integer $k$. ∎

  * (D) There exists $T\in{\binom{S}{n-3}}$ such that either ${\binom{T}{1}}\subseteq{\cal S}_{1}$ or ${\binom{T}{1}}\subseteq{\cal S}_{2}.$

###### Proof.

Assume that the assertion is false. Then there are at least three integers $k$
for which (a1) does not hold. Furthermore, (a3) does not hold for any integer
$k.$ By (4) and (4), (a2) or (a3) holds for at most one integer $k$ and (a4)
holds for at most one integer $k.$ Thus there exists $k\in[n]$ such that none
of (a1) - (a4) hold. By (4), (a5) holds for $k.$ Thus there exists
$(A_{1}^{k},A_{2}^{k})\in{\binom{n-2}{{\cal
S}_{1}^{k}}}\times{\binom{n-2}{{\cal S}_{2}^{k}}}$, $A_{1}^{k}\neq A_{2}^{k},$
and $\\{B_{1}^{k},B_{2}^{k}\\}\subset{\binom{S^{k}}{n-3}}$ where for $i=1,2$,
$B_{i}^{k}\cap A_{i}^{k}=B_{1}^{k}\cap B_{2}^{k}\in{\binom{A_{1}^{k}\cap
A_{2}^{k}}{n-4}}$ and ${\binom{B_{i}^{k}}{1}}\subset{\cal S}_{i}^{k}.$ Thus we
see that ${\binom{B_{2}^{k}}{1}}\subseteq{\cal S}_{2}^{k}\subseteq{\cal
S}_{2}.$ Given that $|B_{2}^{k}|=n-3,$ this contradicts our assumption. ∎

  * (E) There exists $T\in{\binom{S}{n-2}}$ such that either ${\binom{T}{1}}\subseteq{\cal S}_{1}$ or ${\binom{T}{1}}\subseteq{\cal S}_{2}.$

###### Proof.

By (4), we may assume (by symmetry) that for all $i\in[n-3],\
\\{s_{i}\\}\in{\cal S}_{1}.$ Next, we will show that either
$\\{s_{i}\\}\in{\cal S}_{1}$ for some $i\in\\{n-2,n-1,n\\},$ or
${\binom{S^{\prime}}{1}}\subseteq{\cal S}_{2}$ for some
$S^{\prime}\in{\binom{S}{n-2}}.$ We may assume that (a1) and (a3) do not hold
for all $k\in\\{n-2,n-1,n\\}.$ Furthermore, by (4) and (4), (a2) and (a4) hold
for at most one integer $k\in\\{n-2,n-1,n\\}.$ As such, we may assume that
(a2) and (a4) do not hold for $k=n-2.$ Thus by By (4), (a5) holds for $k=n-2$.
Thus there exist $(A_{1}^{n-2},A_{2}^{n-2})\in{\binom{n-2}{{\cal
S}_{1}^{n-2}}}\times{\binom{n-2}{{\cal S}_{2}^{n-2}}}$, $A_{1}^{n-2}\neq
A_{2}^{n-2},$ and $\\{B_{1}^{n-2},B_{2}^{n-2}\\}\subset{\binom{S^{n-2}}{n-3}}$
where for $i=1,2$, $B_{i}^{n-2}\cap A_{i}^{n-2}=B_{1}^{n-2}\cap
B_{2}^{n-2}\in{\binom{A_{1}^{n-2}\cap A_{2}^{n-2}}{n-4}}$ and
${\binom{B_{i}^{n-2}}{1}}\subset{\cal S}_{i}^{n-2}.$

Suppose $s_{i}\in B_{1}^{n-2}\cap\\{s_{1},\dots,s_{n-3}\\}.$ By assumption,
$\\{s_{i}\\}\in{\cal S}_{1}.$ However, given that $s_{i}\in B_{1}^{n-2}$, we
also have that $\\{s_{i}\\}\in{\cal S}_{1}^{n-2}$ and hence
$\\{s_{i},s_{n-2}\\}\in{\cal S}_{1}.$ By (S1), $\\{s_{n-2}\\}\in{\cal S}_{1},$
a contradiction. Thus $B_{1}^{r-2}\cap\\{s_{1},\dots,s_{n-3}\\}=\mathchar
31\relax.$ Thus $B_{1}^{n-2}\subseteq\\{s_{n-1},s_{n}\\}$ and consequently,
$n-3\leq 2$ and hence $n\leq 5.$ To complete the proof, we need only consider
two cases:

Case 1: $n=5$.

We have $B_{1}^{n-2}=B_{1}^{3}=\\{s_{4},s_{5}\\}.$ We may assume that
$A_{2}^{3}=\\{s_{1},s_{4},s_{5}\\},$ where $B_{1}^{3}\cap
B_{2}^{3}=\\{s_{4}\\}.$ Thus $A_{1}^{3}=\\{s_{1},s_{2},s_{4}\\}$ and
$B_{2}^{3}=\\{s_{2},s_{4}\\}.$ Then
$A_{1}^{3}+s_{3}=\\{s_{1},s_{2},s_{3},s_{4}\\}\in{\cal S}_{1}$ and
$B_{1}^{3}+s_{3}=\\{s_{3},s_{4},s_{5}\\}\in{\cal S}_{1}.$ Also, since
${\binom{B_{1}^{3}}{1}}\subset{\cal S}_{1}^{3},$ it follows that
$\\{s_{3},s_{4}\\},\\{s_{3},s_{5}\\}\in{\cal S}_{1}.$ By (4), for all
$k\in\\{4,5\\},$ one of (a2) - (a5) must hold. Clearly, we may assume that
(a3) does not hold for $k=4$ or $k=5$. Also by (4), (a2) can hold for at most
one value of $k$. Thus we may assume the (a4) or (a5) holds for $k=4.$
However, given that (a5) holds for $k=3,$ it follows by (4) that (a4) holds
for $k=4.$ Then there exists a subset $D^{\prime}\in{\binom{S^{4}}{3}}$ and
integers $i,j$ where $i+j=4$ such that ${\binom{D^{\prime}}{i}}\subseteq{\cal
S}_{1}^{4}$ and ${\binom{D^{\prime}}{j}}\subseteq{\cal S}_{2}^{4}.$ We observe
that $D=D^{\prime}\cup\\{s_{4}\\}\in{\cal S}_{1}$. If
$D\neq\\{s_{1},s_{2},s_{3},s_{4}\\},$ then property (S2) implies that
$D\cup\\{s_{1},s_{2},s_{3},s_{4}\\}=\\{s_{1},\dots,s_{5}\\}=S\in{\cal S}_{1},$
yielding a contradiction. Thus we must have that
$D=\\{s_{1},s_{2},s_{3},s_{4}\\}$, implying that
$D^{\prime}=\\{s_{1},s_{2},s_{3}\\}.$

Suppose $i=1.$ Then ${\binom{D^{\prime}}{1}}\subseteq{\cal S}_{1}^{4}$ and
$\\{s_{1}\\}\in{\cal S}_{1}^{4}.$ This in turn implies that
$\\{s_{1},s_{4}\\}\in{\cal S}_{1}.$ However, given that $\\{s_{1}\\}\in{\cal
S}_{1},$ it would follow that $\\{s_{4}\\}\in{\cal S}_{1},$ a contradiction.
Thus $i\geq 2.$ Also, if $j=1$, then ${\binom{D^{\prime}}{1}}\subseteq{\cal
S}_{2}^{4}\subseteq{\cal S}_{2}.$ In this case, the assertion is proved since
$|D^{\prime}|=3=n-2.$ Thus we may assume that $i=j=2.$ Now we have
${\binom{D^{\prime}}{2}}\subseteq{\cal S}_{2}^{4}\subseteq{\cal S}_{2}$. Given
that $\\{s_{2}\\}\in{\cal S}_{2}$ and for all $i^{\prime}\in\\{1,3\\},$
$\\{s_{2},s_{i^{\prime}}\\}\in{\cal S}_{2},$ it follows that for all
$i^{\prime}\in[3],$ $\\{s_{i^{\prime}}\\}\in{\cal S}_{2}.$ This yields a
contradiction. This completes the case $n=5.$

Case 2: $n=4$.

We may assume that $B_{1}^{n-2}=B_{1}^{2}=\\{s_{4}\\},\
A_{1}^{2}=\\{s_{1},s_{3}\\}.$ There are two possible cases to consider for
$A_{2}^{2}$ and $B_{2}^{2}$: either $A_{2}^{2}=\\{s_{1},s_{4}\\}$ and
$B_{2}^{2}=\\{s_{3}\\}$ or $A_{2}^{2}=\\{s_{3},s_{4}\\}$ and
$B_{2}^{2}=\\{s_{1}\\}.$ We shall assume the former – the latter case can be
handled similarly. We have that
$A_{1}^{2}+s_{2}=\\{s_{1},s_{2},s_{3}\\}\in{\cal S}_{1}$ and
$B_{1}^{2}+s_{2}=\\{s_{2},s_{4}\\}\in{\cal S}_{1}.$ We also have that
$A_{2}^{2}=\\{s_{1},s_{4}\\}\in{\cal S}_{2}$ and $\\{s_{3}\\}\in{\cal S}_{2}.$
We may assume that (a3) does not hold for $k=3$ or $k=4$. Furthermore, (4)
implies that (a2) holds for at most one of $k=3$ or $k=4.$ Thus we may assume
that (a4) or (a5) holds for $k=3.$ Since (a5) already holds for $k=2,$ it
follows by (4) that (a5) can not hold for $k=3.$ Thus (a4) holds for $k=3.$
Then there exists a subset $D^{\prime}\in{\binom{S^{3}}{2}}$ and integers
$i,j$ where $i+j=3$ such that ${\binom{D^{\prime}}{i}}\subseteq{\cal
S}_{1}^{3}$ and ${\binom{D^{\prime}}{j}}\subseteq{\cal S}_{2}^{3}.$ We have
that $D=D^{\prime}\cup\\{s_{3}\\}\in{\cal S}_{1}$. Given that
$\\{s_{1},s_{2},s_{3}\\}\in{\cal S}_{1},$ if $D\neq\\{s_{1},s_{2},s_{3}\\},$
then by (S2), $S=D\cup\\{s_{1},s_{2},s_{3}\\}\in{\cal S}_{1},$ a
contradiction. Thus we must have that $D=\\{s_{1},s_{2},s_{3}\\},$ and thus
$D^{\prime}=\\{s_{1},s_{2}\\}.$ If $j=1,$ then
${\binom{D^{\prime}}{1}}\subseteq{\cal S}_{2}^{3}\subseteq{\cal S}_{2}$. Given
$|D^{\prime}|=2=n-2,$ the assertion holds in this case. Thus we may assume
that $j=2$ and $i=1.$ However, this means that $\\{s_{1}\\}\in{\cal
S}_{1}^{3},$ implying that $\\{s_{1},s_{2}\\}\in{\cal S}_{1}.$ This in turn
implies that $\\{s_{2}\\}\in{\cal S}_{1}$ (since $\\{s_{1}\\}\in{\cal S}_{1}$)
yielding a contradiction. This completes the case for $n=4.$ ∎

By (4), there exists $i\in\\{1,2\\}$ and $T\in{\binom{S}{n-2}}$ for which
${\binom{T}{1}}\subseteq{\cal S}_{i}.$ Without loss of generality, we may
assume that $i=1$ and $T=\\{s_{1},\dots,s_{n-2}\\};$ that is, for all
$j\in[n-2],\ \\{s_{j}\\}\in{\cal S}_{1}.$

Suppose (a1) holds for $k=n-1$; that is, $\\{s_{n-1}\\}\in{\cal S}_{1}.$ Then
(a1) does not hold for $k=n$ (otherwise (S3) is violated). If (a2) or (a3)
holds for $k=n$, then $S^{n}\in{\cal S}_{2}.$ In this case, (S4) is violated.
Thus either (a4) or (a5) holds for $k=n.$ In either case, there exists
$D^{\prime}\in{\binom{S^{n}}{n-2}}$ where $D^{\prime}\in{\cal S}_{1}^{n}.$
Then $D=D^{\prime}+s_{n}\in{\cal S}_{1}.$ Given that
${\binom{D^{\prime}}{1}}\subseteq{\cal S}_{1},$ it follows that
$D^{\prime}\in{\cal S}_{1}.$ Furthermore, Observation 3 implies that
${\binom{D}{1}}\subseteq{\cal S}_{1}.$ However, this yields a contradiction
since $\\{s_{n}\\}\not\in{\cal S}_{1}.$ Thus (a1) does not hold for $k=n-1$
and the same holds for $k=n.$ Generally, the above argument demonstrates that
for all $i\in[2],$ and for all $S^{\prime}\in{\binom{S}{n-1}},$
${\binom{S^{\prime}}{1}}\not\subseteq{\cal S}_{i}.$

Suppose (a2) holds for $k=n-1$. Then
$S^{n-1}=\\{s_{1},\dots,s_{n-2},s_{n}\\}\in{\cal S}_{2}.$ By (4), neither (a2)
nor (a3) holds for $k=n.$ Suppose (a5) holds for $k=n.$ If $n>4,$ then
$|B_{1}^{n}|=n-3>1$ and there exists $s_{i}\in
B_{1}^{n}\cap\\{s_{1},\dots,s_{n-2}\\}$. In this case, $\\{s_{i}\\}\in{\cal
S}_{1}^{n},$ and hence $\\{s_{i},s_{n}\\}\in{\cal S}_{1}.$ However, since
$\\{s_{i}\\}\in{\cal S}_{1},$ it follows that $\\{s_{n}\\}\in{\cal S}_{1},$ a
contradiction. Thus $n=4.$ Furthermore,
$B_{1}^{n}\cap\\{s_{1},\dots,s_{n-2}\\}=B_{1}^{4}\cap\\{s_{1},s_{2}\\}=\mathchar
31\relax.$ It follows that $B_{1}^{4}=\\{s_{3}\\}$ and
$A_{1}^{4}=\\{s_{1},s_{2}\\}.$ Thus $S^{3}=\\{s_{1},s_{2},s_{4}\\}\in{\cal
S}_{1}.$ Since for $i=1,2,$ $\\{s_{i}\\}\in{\cal S}_{1},$ it follows by
Observation 3 that ${\binom{S^{3}}{1}}\subseteq{\cal S}_{1}.$ However, this
implies that $\\{s_{4}\\}\in{\cal S}_{1},$ a contradiction.

It follows from the above that (given (a2) holds for $k=n-1$) (a4) holds for
$k=n.$ Thus there exists $D^{\prime}\in{\binom{S^{n}}{n-2}}$ and integers
$i,j,\ i+j=n-1,$ such that ${\binom{D^{\prime}}{i}}\subseteq{\cal S}_{1}^{n}$
and ${\binom{D^{\prime}}{j}}\subseteq{\cal S}_{2}^{n}.$ Then
$D=D^{\prime}+s_{n}\in{\cal S}_{1}.$ If
$D^{\prime}=\\{s_{1},\dots,s_{n-2}\\},$ then $D^{\prime}\in{\cal S}_{1},$
(since ${\binom{D^{\prime}}{1}}\subseteq{\cal S}_{1}$). It now follows by
Observation 3 that ${\binom{D}{1}}\subseteq{\cal S}_{1}.$ However, this
implies that $\\{s_{n}\\}\in{\cal S}_{1},$ a contradiction. Thus $s_{n-1}\in
D^{\prime}.$ Suppose $i\leq n-3$. Then
${\binom{D^{\prime}-s_{n-1}}{1}}\subseteq{\cal S}_{1}$ and hence
$D^{\prime}-s_{n-1}\in{\cal S}_{1}$. However, since $i\leq n-3,$ we also see
that by Observation 3, ${\binom{D^{\prime}-s_{n-1}}{i}}\subseteq{\cal
S}_{1}^{n}$ and thus $D^{\prime}-s_{n-1}\in{\cal S}_{1}^{n}.$ Consequently, we
have $D^{\prime}-s_{n-1}+s_{n}\in{\cal S}_{1}.$ Again, since
${\binom{D^{\prime}-s_{n-1}}{1}}\subset{\cal S}_{1},$ it follows by
Observation 3 that ${\binom{D^{\prime}-s_{n-1}+s_{n}}{1}}\subseteq{\cal
S}_{1},$ implying that $\\{s_{n}\\}\in{\cal S}_{1},$ a contradiction.

From the above, we have $i=n-2$ and $j=1.$ Then $D^{\prime}\in{\cal
S}_{1}^{n}$ and ${\binom{D^{\prime}}{1}}\subseteq{\cal S}_{2}.$ Let $A_{1}=D,\
A_{2}=S^{n-1},\ B_{1}=S-s_{n-1}-s_{n},$ and $B_{2}=D^{\prime}.$ Then by the
above, $(A_{1},A_{2})\in{\binom{n-1}{{\cal S}_{1}}}\times{\binom{n-1}{{\cal
S}_{2}}}$ and $A_{1}\neq A_{2}.$ Furthermore, we have that for $i=1,2,\
{\binom{B_{i}}{1}}\subseteq{\cal S}_{i}.$ We also see that $B_{1}\cap
B_{2}=D^{\prime}\cap\\{s_{1},\dots,s_{n-2}\\}=A_{1}\cap B_{1}=A_{2}\cap
B_{2}.$ Thus in this case, the theorem is satisfied.

To finish the proof, we will show that no other options are possible. Suppose
now that (a2) does not hold for $k=n-1$, and we may assume the same is true
for $k=n$. Thus (a3) does not hold for $k=n-1$ or $k=n.$

Suppose (a4) holds for $k=n-1.$ Then there exists
$D^{\prime}\in{\binom{S^{n-1}}{n-2}}$ and integers $i,j,\ i+j=n-1,$ such that
${\binom{D^{\prime}}{i}}\subseteq{\cal S}_{1}^{n-1}$ and
${\binom{D^{\prime}}{j}}\subseteq{\cal S}_{2}^{n-2}\subseteq{\cal S}_{2}.$
Then $D=D^{\prime}+s_{n-1}\in{\cal S}_{1}.$ As before,
$D^{\prime}\neq\\{s_{1},\dots,s_{n-2}\\}.$ Thus $s_{n}\in D^{\prime}$ and we
may assume without loss of generality that
$D^{\prime}=\\{s_{1},\dots,s_{n-3},s_{n}\\}.$ By (4), (a4) does not hold for
$k=n.$ Thus (a5) holds for $k=n$ and there exist
$(A_{1}^{n},A_{2}^{n})\in{\binom{n-2}{{\cal
S}_{1}^{n}}}\times{\binom{n-2}{{\cal S}_{2}^{n}}},$ $A_{1}^{n}\neq A_{2}^{n}$,
and $\\{B_{1}^{n},B_{2}^{n}\\}\subseteq{\binom{S^{n}}{n-3}}$ where for
$i=1,2$, $B_{i}^{n}\cap A_{i}^{n}=B_{1}^{n}\cap
B_{2}^{n}\in{\binom{A_{1}^{n}\cap A_{2}^{n}}{n-4}}$ and
${\binom{B_{i}^{n}}{1}}\subseteq{\cal S}_{i}^{n}.$ Arguing as before, we have
$B_{1}^{n}\cap\\{s_{1},\dots,s_{n-2}\\}=\mathchar 31\relax.$ This in turn
implies that $B_{1}^{n}=\\{s_{n-1}\\}$ and hence $n=4.$ Furthermore, we have
that $A_{1}^{n}=A_{1}^{4}=\\{s_{1},s_{2}\\},$ implying that
$\\{s_{1},s_{2},s_{4}\\}\in{\cal S}_{1}.$ However, we also have that
$D=\\{s_{1},s_{3},s_{4}\\}\in{\cal S}_{1}.$ It follows by (S2) that
$S=D\cup\\{s_{1},s_{2},s_{4}\\}\in{\cal S}_{1},$ violating (S3). Thus (a4)
does not hold for $k=n-1$ and the same holds for $k=n.$

From the above, (a5) must hold for both $k=n-1$ and $k=n$, contradicting (4).
This completes the proof of the theorem. ∎

##  5 Proof of Theorem 1

Let $M$ be a paving matroid where $\gamma(M)=\beta(E(M))$ and $|E(M)|=n.$

###  5.1 The case $r(M)=2$

Suppose $r(M)=2.$ We shall prove by induction on $n$ that $M$ is cyclically
orderable. Theorem 1 is seen to be true when $n=2.$ Assume that it is true
when $n=m-1\geq 2.$ We shall prove that it is also true for $n=m.$ Assume that
$M$ is a paving matroid where $r(M)=2$, $|E(M)|=m$ and
$\gamma(M)=\beta(E(M))=\frac{m}{2}.$ For all elements $e\in E(M)$, let $X_{e}$
denote the parallel class containing $e$ and let $m(e)=|X_{e}|.$ Then for all
$e\in E(M),$ $\beta(X_{e})=m(e)\leq\gamma(M)=\frac{m}{2}.$ Thus for all $e\in
E(M),$ $m(e)\leq\frac{m}{2}.$

There exists $f\in E(M)$ for which $r(M\backslash f)=2.$ Let
$M^{\prime}=M\backslash f.$ We claim that
$\gamma(M^{\prime})=\beta(E(M^{\prime}))=\frac{m-1}{2}.$ For if there exists
$X\subseteq E(M^{\prime})$ for which $\beta(X)>\frac{m-1}{2}>1$, then
$r(X)=2,$ and $\beta(X)=\frac{|X|}{2}>\frac{m-1}{2}$. It follows that $|X|=m,$
which is impossible since $|E(M^{\prime})|=m-1.$ Thus
$\gamma(M^{\prime})=\beta(E(M^{\prime})).$ By assumption, there is a cyclic
ordering for $M^{\prime}$, say $e_{1}e_{2}\cdots e_{m-1}.$ Since
$m(f)\leq\frac{m}{2},$ there exists $i\in[m-1]$ such that
$\\{e_{i},e_{i+1}\\}\cap X_{f}=\mathchar 31\relax.$ Consequently, $e_{1}\cdots
e_{i}fe_{i+1}\dots e_{m-1}$ is seen to be a cyclic ordering for $M$. The proof
now follows by induction.

###  5.2 The case where $|E(M)|\leq 2r(M)+1$

Suppose $|E(M)|\leq 2r(M)+1.$ As mentioned earlier, if $|E(M)|=2r(M)+1,$ then
$|E(M)|$ and $r(M)$ are relatively prime and hence it follows by Theorem 1
that $M$ has a cyclic ordering. Thus we may assume that $|E(M)|\leq 2r(M).$ It
now follows by Theorem 2 that there are bases $A$ and $B$ for which $A\cup
B=E(M).$

In [1], the authors verify, among other things, the following conjecture of
Gabow [5] for split matroids, a class which contains paving matroids.

  * 5.1 Conjecture ( Gabow )

Suppose that $A$ and $B$ are bases of a matroid $N$ of rank $r.$ Then there
are orderings $a_{1}a_{2}\cdots a_{r}$ and $b_{1}b_{2}\cdots b_{r}$ of the
elements of $A$ and $B$, respectively, such that for $i=1,\dots,r-1,$
$\\{a_{1},\dots,a_{i},b_{i+1},\dots,b_{r}\\}$ and
$\\{a_{i+1},\dots,a_{r},b_{1}\dots b_{i}\\}$ are bases.

We observe that in the special case of Conjecture 5.2 where $E(N)$ is the
union of two bases, then the conjecture implies that $N$ has a cyclic
ordering. Given that the above conjecture is true for split matroids (and
hence also paving matroids) and $E(M)=A\cup B,$ it follows that $M$ has a
cyclic ordering.

###  5.3 The case where $|E(M)|\geq 2r(M)+2$ and $r(M)\geq 3$.

In this section, we shall assume that $|E(M)|\geq 2r(M)+2$ and $r(M)\geq 3$.
By Proposition 2, there exists a basis $S$ of $M$ for which
$\gamma(M\backslash S)=\beta(E(M)-S)$ and $r(M\backslash S)=r(M).$ Let
$r=r(M)$ and let $S=\\{s_{1},\dots,s_{r}\\}.$ Let $M^{\prime}=M-S$ and let
$m=|E(M^{\prime})|=n-r.$ By assumption, $M^{\prime}$ is cyclically orderable
and we will assume that $e_{1}e_{2}\cdots e_{m}$ is a cyclic ordering. Our
goal is to show that the cyclic ordering for $M^{\prime}$ can be extended to a
cyclic ordering of $M$. To complete the proof of Theorem 1, we need only prove
the following:

  * 5.2 Proposition

There exists $i\in[m]$ and a permutation $\pi$ of $[r]$ such that
$e_{1}e_{2}\cdots e_{i}s_{\pi(1)}s_{\pi(2)}\cdots s_{\pi(r)}e_{i+1}\cdots
e_{m}$ is a cyclic ordering of $M.$

###### Proof.

Assume to the contrary that for all $i\in[m]$ and for all permutations $\pi$
of $[r],$ $e_{1}e_{2}\cdots e_{i}s_{\pi(1)}s_{\pi(2)}\cdots
s_{\pi(r)}e_{i+1}\cdots e_{m}$ is not a cyclic ordering of $M.$ For all
$j\in[m],$ we shall define a pair $({\cal H}_{1}^{j},{\cal H}_{2}^{j})$, where
for $i=1,2,$ ${\cal H}_{i}^{j}\subseteq 2^{S}.$ Let
$x_{1}=e_{j-1},x_{2}=e_{j-2},\dots,x_{r-1}=e_{j-r+1},$ and let
$y_{1}=e_{j},y_{2}=e_{j+1},\dots,y_{r-1}=e_{j+r-2}$ where for all integers
$k$, we define $e_{k}:=e_{\ell}$ where

$\ell:=\left\\{\begin{array}[]{lr}k\ mod\ m&\mathrm{if}\ k\ mod\ m\neq 0\\\
m&\mathrm{otherwise}\end{array}\right.$

Let $X=\\{x_{1},\dots,x_{r-1}\\}$ and $Y=\\{y_{1},\dots,y_{r-1}\\}$.

Let $\pi$ be a permutation of $[r]$. By assumption,
$e_{1}\cdots e_{j-1}s_{\pi(1)}s_{\pi(2)}\cdots s_{\pi(r)}e_{j}\cdots e_{m}$ is
not a cyclic ordering for $M.$ Given that $M$ is a paving matroid, there
exists $i\in[r-1]$ such that either
$\\{x_{1},\dots,x_{i}\\}\cup\\{s_{\pi(1)},\dots,s_{\pi(r-i)}\\}\in{\cal C}(M)$
or $\\{y_{1},\dots,y_{i}\\}\cup\\{s_{\pi(r-i+1)},\dots,s_{\pi(r)}\\}\in{\cal
C}(M).$ Let ${\cal C}_{1}^{j}$ be the set of all $r$-circuits which occur in
the former case, and let ${\cal C}_{2}^{j}$ be the set of all $r$-circuits
occurring in the latter case. That is, ${\cal C}_{1}^{j}$ is the set of all
$r$-circuits $C$ where for some $i\in[r-1],$ $\\{x_{1},\dots,x_{i}\\}\subset
C\subset\\{x_{1},\dots,x_{i}\\}\cup S$, and ${\cal C}_{2}^{j}$ is set of all
$r$-circuits $C$ where for some $i\in[r-1],$ $\\{y_{1},\dots,y_{i}\\}\subset
C\subseteq\\{y_{1},\dots,y_{i}\\}\cup S.$ For $i=1,2,$ let ${\cal
H}_{i}^{j}=\\{C\cap S\ \big{|}\ C\in{\cal C}_{i}^{j}\\}.$

  * (A) For all $j,$ the pair $({\cal H}_{1}^{j},{\cal H}_{2}^{j})$ is an $S$-pair which is order consistent.

###### Proof.

It suffices to prove the assertion for $j=1.$ For convenience, we let ${\cal
H}_{1}={\cal H}_{1}^{1}$, ${\cal H}_{2}={\cal H}_{2}^{1},$ ${\cal C}_{1}={\cal
C}_{1}^{1},$ and ${\cal C}_{2}={\cal C}_{2}^{1}.$ It follows from the
definition of $({\cal H}_{1},{\cal H}_{2})$ that it is order consistent. We
need only show that it is an $S$-pair. Suppose $A,B\in{\cal H}_{1}$ where
$|A|=|B|+1$ and $B\subset A.$ Then for some $i\in[r-1],$
$C_{1}=A\cup\\{x_{1},\dots,x_{i}\\}\in{\cal C}_{1}$ and
$C_{2}=B\cup\\{x_{1},\dots,x_{i+1}\\}\in{\cal C}_{1}.$ Let $x\in B.$ Then
$x\in C_{1}\cap C_{2}$ and hence by the circuit elimination axiom there is a
circuit $C\subseteq(C_{1}\cup C_{2})-x=(A-x)\cup\\{x_{1},\dots,x_{i+1}\\}.$
Thus $C=(A-x)\cup\\{x_{1},\dots,x_{i+1}\\}$ and hence $A-x\in{\cal H}_{1}.$
Since this applies to any element $x\in B$, it follows that
${\binom{A}{|B|}}\subseteq{\cal H}_{1}.$ The same arguments can be applied to
${\cal H}_{2}$. Thus (S1) holds.

To show that (S2) holds, suppose $A,B\in{\cal H}_{1}$ where $|A|=|B|$ and
$|A\cap B|=|A|-1.$ There exists $i\in[r]$ such that
$C_{1}=\\{x_{1},\dots,x_{i}\\}\cup A\in{\cal C}_{1}$ and
$C_{2}=\\{x_{1},\dots,x_{i}\\}\cup B\in{\cal C}_{1}.$ By the circuit
elimination axiom, there exists a circuit $C\subseteq(C_{1}\cup
C_{2})-x_{i}=(A\cup B)\cup\\{x_{1},\dots,x_{i-1}\\}$. Thus $C=(A\cup
B)\cup\\{x_{1},\dots,x_{i-1}\\}$ is a circuit and hence $A\cup B\in{\cal
H}_{1}.$ The same reasoning applies if $A,B\in{\cal H}_{2}.$ Thus (S2) holds.

To show that (S3) holds, suppose ${\binom{S}{1}}\subseteq{\cal H}_{1}.$ Then
for $i=1,\dots,r-1,\ C_{i}=X\cup\\{s_{i}\\}$ is a circuit, and consequently,
$S\subseteq\mathrm{cl}(X).$ However, this is impossible since
$|X|=r-1<r(S)=r.$ Thus ${\binom{S}{1}}\not\subseteq{\cal H}_{1}$ and likewise,
${\binom{S}{1}}\not\subseteq{\cal H}_{2}.$ Also, we clearly have that for
$i=1,2$ $S\not\in{\cal H}_{i}$ since $S$ is a base of $M.$ Thus (S3) holds.

Lastly, to show that (S4) holds, let $S^{\prime}=S-s_{r}$ Suppose first that
${\binom{S^{\prime}}{r-1}}\subseteq{\cal H}_{1}$ and
${\binom{S^{\prime}}{1}}\subseteq{\cal H}_{2}.$ Then $S^{\prime}\in{\cal
H}_{1}$ and hence $S^{\prime}+x_{1}\in{\cal C}_{1}.$ Also, for all
$i\in[r-1],$ $Y+s_{i}\in{\cal C}_{2}$. Thus $x_{1}\in\mathrm{cl}(S^{\prime})$
and $S^{\prime}\subseteq\mathrm{cl}(Y)$. Given that $S^{\prime}$ is
independent and $|S^{\prime}|=|Y|=r-1,$ it follows that
$\mathrm{cl}(S^{\prime})=\mathrm{cl}(Y).$ However, this implies that
$Y+x_{1}=\\{x_{1},y_{1},\dots,y_{r-1}\\}=\\{e_{m},e_{1},\dots,e_{r-1}\\}\subseteq\mathrm{cl}(S^{\prime}),$
which is impossible since by assumption, $\\{e_{m},e_{1},\dots,e_{r-1}\\}$ is
a basis of $M.$

Suppose now that for some $k\in[r-2]$, ${\binom{S^{\prime}}{k}}\subseteq{\cal
H}_{1}$ and ${\binom{S^{\prime}}{r-k}}\subseteq{\cal H}_{2}$. We claim that
$\\{x_{1},\dots,x_{r-k}\\}\cup\\{y_{1},\dots,y_{k}\\}\subseteq\mathrm{cl}(S^{\prime})$.
By (S2) (as in the proof of Observation 3), we have that for $j=k,\dots,r-1$,
${\binom{S^{\prime}}{j}}\subseteq{\cal H}_{1}.$ In particular,
$S^{\prime}\in{\cal H}_{1},$ and hence $C_{1}=S^{\prime}+x_{1}\in{\cal
C}_{1}.$ This implies that $x_{1}\in\mathrm{cl}(S^{\prime}).$ However, seeing
as ${\binom{S^{\prime}}{r-2}}\subseteq{\cal H}_{1},$ we see that
$C_{2}=(S^{\prime}-s_{r-1})\cup\\{x_{1},x_{2}\\}\in{\cal C}_{1}.$ Given that
$x_{1}\in\mathrm{cl}(S^{\prime}),$ it follows that
$x_{2}\in\mathrm{cl}(S^{\prime}).$ Continuing, we see that
$\\{x_{1},\dots,x_{r-k}\\}\subseteq\mathrm{cl}(S^{\prime}).$ By similar
arguments, it can be shown that
$\\{y_{1},\dots,y_{k}\\}\subseteq\mathrm{cl}(S^{\prime}).$ Thus proves our
claim. However, this is impossible since by assumption
$\\{x_{1},\dots,x_{r-k}\\}\cup\\{y_{1},\dots,y_{k}\\}$ is a basis but
$r(S^{\prime})=|S^{\prime}|=r-1.$ Thus no such $k$ exists. More generally, the
same arguments can be applied to any $j\in[r],$ and $S^{\prime}=S-s_{j}.$ Thus
(S4) holds. ∎

By (5.3), $({\cal H}_{1}^{1},{\cal H}_{2}^{1})$ is an $S$-pair which is order
consistent. Thus it follows by Theorem 4, that there exists
$(A_{1},A_{2})\in{\binom{r-1}{{\cal H}_{1}^{1}}}\times{\binom{r-1}{{\cal
H}_{2}^{1}}},$ $A_{1}\neq A_{2},$ and
$\\{B_{1},B_{2}\\}\subseteq{\binom{S}{r-2}}$ where for $i=1,2$, $B_{i}\cap
A_{i}=B_{1}\cap B_{2}\in{\binom{A_{1}\cap A_{2}}{r-3}}$ and
${\binom{B_{i}}{1}}\subseteq{\cal H}_{i}^{1}.$ Also, $({\cal H}_{1}^{2},{\cal
H}_{2}^{2})$ is also an $S$-pair which is order consistent and hence by
Theorem 4, there exists $(A_{1}^{\prime},A_{2}^{\prime})\in{\binom{r-1}{{\cal
H}_{1}^{2}}}\times{\binom{r-1}{{\cal H}_{2}^{2}}},$ $A_{1}^{\prime}\neq
A_{2}^{\prime},$ and
$\\{B_{1}^{\prime},B_{2}^{\prime}\\}\subseteq{\binom{S}{r-2}}$ where for
$i=1,2$, $B_{i}^{\prime}\cap A_{i}^{\prime}=B_{1}^{\prime}\cap
B_{2}^{\prime}\in{\binom{A_{1}^{\prime}\cap A_{2}^{\prime}}{r-3}}$ and
${\binom{B_{i}^{\prime}}{1}}\subseteq{\cal H}_{i}^{2}.$

Suppose $r>4.$ Given that $|B_{2}|=|B_{2}^{\prime}|=r-2,$ it follows that
there exists $s_{i}\in B_{2}\cap B_{2}^{\prime}.$ Then
$C_{1}=\\{s_{i},e_{1},\dots,e_{r-1}\\}$ and
$C_{2}=\\{s_{i},e_{2},e_{3},\dots,e_{r}\\}$ are distinct circuits in $M.$ By
the circuit elimination axiom, there exists a circuit $C\subseteq(C_{1}\cup
C_{2})-s_{i}=\\{e_{1},\dots,e_{r}\\}.$ However, this is impossible since, by
assumption, $\\{e_{1},\dots,e_{r}\\}$ is a basis. Thus $r\leq 4.$

Suppose $r=3$. Without loss of generality, we may assume that
$A_{1}=\\{s_{1},s_{2}\\}$ and $B_{1}=\\{s_{3}\\}$ and
$A_{2}=\\{s_{2},s_{3}\\}$ $B_{2}=\\{s_{1}\\}$. Following similar reasoning as
that given in the case $r>4,$ we have that $\\{s_{3}\\}\not\in{\cal
H}_{1}^{2}$ and $\\{s_{1}\\}\not\in{\cal H}_{2}^{2}.$ Suppose that
$\\{s_{1}\\}\in{\cal H}_{1}^{2}.$ Then given that $\\{s_{1}\\}\in{\cal
H}_{2}^{1},$ we have $C_{1}=\\{s_{1},e_{1},e_{2}\\}$ and
$C_{2}=\\{s_{1},e_{m},e_{1}\\}$ are circuits. This would imply that
$\\{e_{m},e_{1},e_{2}\\}=(C_{1}\cup C_{2})-s_{1}$ is a circuit, which is false
since, by assumption, $\\{e_{m},e_{1},e_{2}\\}$ is a basis. Thus
$\\{s_{1}\\}\not\in{\cal H}_{1}^{2}.$ It follows that
$B_{1}^{\prime}=\\{s_{2}\\}$ and $A_{1}^{\prime}=\\{s_{1},s_{3}\\}.$ Since
$\\{s_{1}\\}\not\in{\cal H}_{2}^{2},$ it follows that
$B_{2}^{\prime}=\\{s_{3}\\}$ and $A_{2}^{\prime}=\\{s_{1},s_{2}\\}.$ Since
$A_{1}=A_{2}^{\prime}=\\{s_{1},s_{2}\\},$ it follows that
$C_{1}=\\{s_{1},s_{2},e_{m}\\}$ and $C_{2}=\\{s_{1},s_{2},e_{2}\\}$ are
circuits. Furthermore, since $B_{1}^{\prime}=\\{s_{2}\\},$ it follows that
$C_{3}=\\{s_{2},e_{1},e_{m}\\}$ is a circuit. It is now seen that
$\\{e_{m},e_{1},e_{2}\\}\subset\mathrm{cl}(\\{s_{1},s_{2}\\}),$ which is
impossible since by assumption, $\\{e_{m},e_{1},e_{2}\\}$ is a basis.

Suppose $r=4$. Again, if $B_{1}\cap B_{1}^{\prime}\neq\mathchar 31\relax$,
then it would follow by the circuit elimination axiom that that
$\\{e_{m-2},e_{m-1},e_{m},e_{1}\\}$ is a circuit, contradicting our
assumptions. Thus $B_{1}\cap B_{1}^{\prime}=\mathchar 31\relax$ and similarly,
$B_{2}\cap B_{2}^{\prime}=\mathchar 31\relax.$ Since for $i=1,2$,
$|B_{i}|=|B_{i}^{\prime}|=2$ it follows that $B_{i}\cup B_{i}^{\prime}=S.$
Without loss of generality, we may assume
$B_{1}=\\{s_{1},s_{2}\\},A_{1}=\\{s_{2},s_{3},s_{4}\\}$ and
$B_{2}=\\{s_{2},s_{3}\\},A_{2}=\\{s_{1},s_{2},s_{4}\\}.$ It now follows that
$B_{1}^{\prime}=\\{s_{3},s_{4}\\}$ and $B_{2}^{\prime}=\\{s_{1},s_{4}\\}.$ We
now see that $A_{1}^{\prime}=\\{s_{1},s_{2},s_{4}\\}$ and
$A_{2}^{\prime}=\\{s_{2},s_{3},s_{4}\\}.$ Then
$\\{\\{s_{1}\\},\\{s_{2}\\},\\{s_{2},s_{3},s_{4}\\}\\}\subseteq{\cal
H}_{1}^{1}$,
$\\{\\{s_{2}\\},\\{s_{3}\\},\\{s_{1},s_{2},s_{4}\\}\\}\subseteq{\cal
H}_{2}^{1},$
$\\{\\{s_{3}\\},\\{s_{4}\\},\\{s_{1},s_{2},s_{4}\\}\\}\subseteq{\cal
H}_{1}^{2}$ and
$\\{\\{s_{1}\\},\\{s_{4}\\},\\{s_{2},s_{3},s_{4}\\}\\}\subseteq{\cal
H}_{2}^{2}.$ By (S2) it follows that $\\{s_{1},s_{2}\\}\in{\cal H}_{1}^{1}$
and $\\{s_{2},s_{3}\\}\in{\cal H}_{2}^{1}.$ Thus
$C_{1}=\\{s_{1},s_{2},e_{m-1},e_{m}\\}$ and
$C_{2}=\\{s_{2},s_{3},e_{1},e_{2}\\}$ are circuits.

Since $({\cal H}_{1}^{3},{\cal H}_{2}^{3})$ is an $S$-pair which is order
consistent, we can argue with $({\cal H}_{1}^{2},{\cal H}_{2}^{2})$ in place
of $({\cal H}_{1}^{1},{\cal H}_{2}^{1})$ and $({\cal H}_{1}^{3},{\cal
H}_{2}^{3})$ in place of $({\cal H}_{1}^{2},{\cal H}_{2}^{2}),$ to show that
$\\{\\{s_{1}\\},\\{s_{2}\\}\\}\subseteq{\cal H}_{1}^{3}$ and
$\\{\\{s_{2}\\},\\{s_{3}\\}\\}\subseteq{\cal H}_{2}^{3}.$ Again, we have that
$\\{s_{1},s_{2}\\}\in{\cal H}_{1}^{3}$ and $\\{s_{2},s_{3}\\}\in{\cal
H}_{2}^{3}$ and thus $C_{3}=\\{s_{1},s_{2},e_{1},e_{2}\\}$ and
$C_{4}=\\{s_{2},s_{3},e_{3},e_{4}\\}$ are circuits. By symmetry, we have that
$C_{5}=\\{s_{2},s_{3},e_{m-1},e_{m}\\}$ is also a circuit. By the circuit
elimination axiom, there exists a circuit $C$ where $C\subseteq(C_{1}\cup
C_{5})-e_{m-1}.$ We must have that $C=\\{s_{1},s_{2},s_{3},e_{m}\\},$ implying
that $e_{m}\in\mathrm{cl}(\\{s_{1},s_{2}.s_{3}\\}.$ We now see that
$e_{m-1}\in\mathrm{cl}(\\{s_{1},s_{2}.s_{3}\\}$. Using the circuits $C_{2}$
and $C_{3}$, one can argue in the same manner to show that
$\\{e_{1},e_{2}\\}\subset\mathrm{cl}(\\{s_{1},s_{2}.s_{3}\\}.$ Thus it follows
that
$\\{e_{m-1},e_{m},e_{1},e_{2}\\}\subset\mathrm{cl}(\\{s_{1},s_{2}.s_{3}\\},$
which is impossible since (by assumption) $\\{e_{m-1},e_{m},e_{1},e_{2}\\}$ is
a basis. This concludes the case for $r=4.$ ∎

## References

  * [1] K. Berczi and T. Schwarcz, Exchange distance of basis pairs in split matroids, arXiv:2203.01779v3, 2022.
  * [2] J. Bonin, Base Exchange Properties of Sparse Paving Matroids, Adv. in Appl. Math., 50 (2013) no. 1, 6-15.
  * [3] J. Edmonds, Minimum partition of a matroid into independent sets, J. Res. Nat. Bur. Standards Sect. B 69 B, (1965), 67-72.
  * [4] G. Fan, H. Jiang, P. Li, D. West, D. Yang, X. Zhi, Extensions of matroid covering and packing, European J. Combinatorics, Vol. 76 (2019), 117-122.
  * [5] H. Gabow, Decomposing symmetric exchanges in matroid bases, Mathematical Programming, 10 (1) (1976), 271-276.
  * [6] Y. Kajitani, S. Ueno, H. Miyano, Ordering of the elements of a matroid such that its consecutive $w$ elements are independent, Discrete Math. 72(1988), 187-194.
  * [7] J. Oxley, Matroid Theory, 2nd. ed., Oxford University Press, Oxford, 2011.
  * [8] J. Van Den Heuvel and S. Thomasse, Cyclic orderings and cyclic arboricity of matroids, Journal of Comb. Theory series B, Vol. 102 , 3, (2012), 638-646.