discussed above – e.g. using logical constraints – and to generate and shrink
instances of $\Delta$ with particular properties.

##  8\. Conclusion and related work

We introduced a model for actor-based systems with grey failures and
investigated the definition of behavioural equivalence for it. We used weak
barbed bisimulation to compare systems on the basis of their ability to
recover from faults, and defined properties of resilience, recoverability and
augmentation. We reduced the problem of checking reliability properties of
systems to a problem of checking bisimulation. We introduced scope restriction
for mailboxes based on patterns, which allows us to model relatively complex
real-world scenarios like the Circuit Breaker.

As further work we plan to extend the recovery function $\Sigma$ to model
check-pointing of intermediate node states. Note that $\Sigma$ can already be
set as an arbitrary process, but a more meaningful extension would account for
the way in which checkpoints are saved. Moreover, we plan to add a notion of
intermittent correctness, to model recovery with partial checkpoints rather
than re-starting from the initial state, or intermittent expected/unexpected
behaviour. Another area of future work is to use the characteristic formulae
approach [GS86, Ste89], a method to compute simulation-like relations in
process algebras, to generate formulae for the properties introduced and
reduce them to a model checking problem that can be offloaded to a model
checker.

A related formalism to our model is Timed Rebeca [ACI+11], which is actor-
based and features similar constructs for deadlines and delays. Timed Rebeca
actors can also use a ‘ _now_ ’ function to get their local times. Extending
our calculus with ‘ _now_ ’ and allowing messages to have time as data sort,
would allow us to model scenarios e.g., where a node calculates the return-
trip time to another node and changes its behaviour accordingly. While Timed
Rebeca can encode network delays (adding delays to receive actions – using a
construct called ‘ _after_ ’), it does not model links explicitly. Explicit
links and separation between curses and systems make it easier in our calculus
to compare systems with respect to recoverability. Rebeca was encoded in
McErlang [ACI+11] and Real-Time Maude [SKÖ+15] for verification. We have
ongoing work on encoding our model in UPPAAL. Our main challenge in this
respect is to formalise a meaningful and manageable set of curses to verify
the model against.

In [FH07], Francalanza and Hennessy introduced a behavioural theory for
D$\pi$F, a distributed $\pi$-calculus with with nodes and links failures. For
a subset of D$\pi$F, they also developed a notion of fault-tolerance up to
$n$-faults [FH08], which is preserved by contexts, and which is related to our
notion of resilience. The behavioural theory in [FH07] is based on reduction
barbed congruence. The idea is to use a contextual relation to abstract from
the behaviour of hidden nodes/links, while still observing their effects on
the network, e.g., as to accessibility and reachability of other nodes. The
scoped barbs in Section 6.1 have the similar purpose of hiding augmentations
while observing their effects on recoverability. However, because of
asynchronous communication over mailboxes (while D$\pi$F is based on
synchronous message passing), our notion of hiding is less structural (i.e.,
based on nodes and links) and more application-dependent (i.e., based on
patterns). At present, we have left pattern hiding out of the semantics, but
further investigation towards a contextual relation that works for hidden
patterns is promising future work. D$\pi$F studies partial failures but does
not consider transient failures and time. On the other hand, D$\pi$F features
mobility which we do not support. In fact, we rely on the assumption of fixed
networks: since our observation is based on patterns (and ignores senders) we
opted for relying on a stable structure to simplify our reasoning on what
augmentation vs recoverability means, leaving mobility issues for future
investigation.

Most ingredients of the given model (e.g., timeouts [LZ05, BY07, LP11],
mailboxes [MV11], localities [RH97][BH03][Cas01]) have been studied in
literature, often in isolation. We investigated the inter-play of these
ingredients, focussing on reliability properties. One of the first papers
dealing with asynchronous communication in process algebra is by de Boer et
al. [dBKP92], where different observation criteria are studied (bisimulation,
traces and abstract traces) following the axiomatic approach typical of the
process algebra ACP [BK84]. An alternative approach has been followed by
Amadio et al. [ACS98] who defined asynchronous bisimulation for the
$\pi$-calculus [MPW92]. They started from operational semantics (expressed as
a standard labelled transition system), and then considered the largest
bisimulation defined on internal steps that equates processes only when they
have the same observables, and which is closed under contexts. The equivalence
obtained in this way is called barbed congruence [MS92]. Notably, when
asynchronous communication is considered, barbed congruence is defined
assuming as observables the messages that are ready to be delivered to a
potential external observer. Merro and Sangiorgi [MS98] have subsequently
studied barbed congruence in the context of the Asynchronous Localised
$\pi$-calculus (AL$\pi$), a fragment of the asynchronous $\pi$-calculus in
which only output capabilities can be transmitted, i.e., when a process
receives the name of a channel, it can only send messages along it, but cannot
receive on it. Another line of research deals with applying the testing
approach to asynchronous communication; this has been investigated by
Castellani and Hennessy [CH98] and by Boreale et al. [BNP99, BNP02]. These
papers consider an asynchronous variant of CCS [Mil89]. Testing discriminates
less than our equivalence, concerning choice, and observes divergent
behaviours which we abstract from. Lanese et al. [LSZ19] look at bisimulation
for Erlang, focussing on the management of process ids. Besides the
aforementioned work by Francalanza and Hennessy [FH07, FH08], several works
look at distributed process algebras with unreliable communication due to
faults in the underlying network. Riely and Hennessy [RH97] study behavioural
equivalence over process calculi with locations. Amadio [Ama97] extends the
$\pi$-calculus with located actions, in the context of a higher-order
distributed programming language. Fournet et al. [FGL+96] look at locations,
mobility and the possibility of location failure in the distributed join
calculus. The failure of a location can be detected and recovered from. Berger
and Honda [BH03] augment the asynchronous $\pi$-calculus with a timer,
locations, message-loss, location failure and the ability to save process
state. They define a notion of weak bisimulation over networks. Their model
however does not include timeout, link delays, or a way of injecting faults.
Cano et al. [CCDGP19] develop a calculus and type system for multiparty
reactive systems that models time dependent interactions. Their setting is
synchronous and their focus is on proving properties as types safety or input
timeliness, while ours is comparing asynchronous systems with faults.

In Section 5.4 we discussed two related works: one characterising fault-
tolerance using safety and liveness [Gär99], and one [DCMA17] instantiating
such characterisation using simulation. One of the main differences of our
work with [DCMA17] is the communication model: the work in [DCMA17] uses
coloured Kripke structures, whereas we use an asynchronous process calculus
with explicit actor-based features. Another difference is the model of failure
and the characterization of good versus bad states. Usually, fault-tolerance
is studied against a well define model of failure and set of failure
scenarios. Systems that can recover from arbitrary failures, called _self-
stabilizing_ [Gär99] are difficult to build and verify. Hence models for
foult-tolerant systems normally have a model of failures within. In our case,
this would be a set of $\Delta$ functions. In [DCMA17] there is an explicit
and statical labelling (colouring) of each state as good or bad. In contrast,
we observe deviations from the behaviour of the same system but without
failures, so that a bad state is actually one that breaks the bisimulation
relation with the corresponding uncursed system. Finally, in [Gär99][DCMA17],
there is no clear distinction between the notion of fault – a defect of the
system – and its concrete manifestation as a symptom. Our model of failure,
that separates system from curses yields a more agnostic view of what a bad
state is that supports modular reasoning on the relationship between causes
and symptoms.

## References

  * [ACI+11] Luca Aceto, Matteo Cimini, Anna Ingolfsdottir, Arni Hermann Reynisson, Steinar Hugi Sigurdarson, and Marjan Sirjani.  Modelling and simulation of asynchronous real-time systems using timed rebeca.  EPTCS, 58:1–19, 2011.  doi:10.4204/eptcs.58.1.
  * [ACS98] Roberto M. Amadio, Ilaria Castellani, and Davide Sangiorgi.  On bisimulations for the asynchronous pi-calculus.  Theor. Comput. Sci., 195(2):291–324, 1998.  doi:10.1016/S0304-3975(97)00223-5.
  * [Ama97] Roberto M. Amadio.  An asynchronous model of locality, failure, and process mobility.  In Proc. COORDINATION, volume 1282 of LNCS, pages 374–391. Springer, 1997.  doi:10.1007/3-540-63383-9_92.
  * [APN17] Manuel Adameit, Kirstin Peters, and Uwe Nestmann.  Session types for link failures.  In Proc. FORTE, volume 10321 of LNCS, pages 1–16. Springer International Publishing, 2017.  doi:10.1007/978-3-319-60225-7_1.
  * [Arm13] Joe Armstrong.  Programming Erlang: Software for a Concurrent World.  Pragmatic Bookshelf, Dallas, TX, 2 edition, 2013.
  * [BBO12] Samik Basu, Tevfik Bultan, and Meriem Ouederni.  Deciding choreography realizability.  Proc. ACM Program. Lang. (POPL), 47:191–202, 2012.  doi:10.1145/2103656.2103680.
  * [BGF+21] Benedikt Bollig, Cinzia Di Giusto, Alain Finkel, Laetitia Laversa, Étienne Lozes, and Amrita Suresh.  A unifying framework for deciding synchronizability.  In Proc. CONCUR, volume 203 of LIPIcs, pages 14:1–14:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.CONCUR.2021.14.
  * [BH03] Martin Berger and Kohei Honda.  The two-phase commitment protocol in an extended $\pi$-calculus.  ENTCS, 39(1):21–46, 2003.  doi:10.1016/S1571-0661(05)82502-2.
  * [BK84] Jan A. Bergstra and Jan Willem Klop.  Process algebra for synchronous communication.  Inf. Control., 60(1-3):109–137, 1984.  doi:10.1016/S0019-9958(84)80025-X.
  * [BLTV22] Laura Bocchi, Julien Lange, Simon Thompson, and A. Laura Voinea.  A model of actors and grey failures.  In Proc. COORDINATION, volume 13271 of LNCS, pages 140–158. Springer, 2022.  doi:10.1007/978-3-031-08143-9_9.
  * [BNP99] Michele Boreale, Rocco De Nicola, and Rosario Pugliese.  A theory of “may” testing for asynchronous languages.  In Proc. FoSSaCS, volume 1578 of LNCS, pages 165–179. Springer, 1999.  doi:10.1007/3-540-49019-1_12.
  * [BNP02] Michele Boreale, Rocco De Nicola, and Rosario Pugliese.  Trace and testing equivalence on asynchronous processes.  Inf. Comput., 172(2):139–164, 2002.  doi:10.1006/inco.2001.3080.
  * [BOV23] Laura Bocchi, Dominic Orchard, and A. Laura Voinea.  A Theory of Composing Protocols.  Art Sci. Eng. Program., 7(2), 2023.  doi:10.22152/programming-journal.org/2023/7/6.
  * [BY07] Martin Berger and Nobuko Yoshida.  Timed, distributed, probabilistic, typed processes.  In Proc. APLAS, volume 4807 of LNCS, pages 158–174. Springer, 2007.  doi:10.1007/978-3-540-76637-7_11.
  * [BZ83] Daniel Brand and Pitro Zafiropulo.  On communicating finite-state machines.  J. ACM, 30(2):323–342, 1983.  doi:10.1145/322374.322380.
  * [Cas01] Ilaria Castellani.  Process algebras with localities.  In Handbook of Process Algebra, pages 945–1045. North-Holland / Elsevier, 2001.  doi:10.1016/b978-044482830-9/50033-3.
  * [CCDGP19] Mauricio Cano, Ilaria Castellani, Cinzia Di Giusto, and Jorge A. Pérez.  Multiparty Reactive Sessions.  Research Report 9270, INRIA, April 2019.  URL: https://hal.archives-ouvertes.fr/hal-02106742.
  * [CDYP16] Mario Coppo, Mariangiola Dezani-Ciancaglini, Nobuko Yoshida, and Luca Padovani.  Global progress for dynamically interleaved multiparty sessions.  MSCS, 26(2):238–302, 2016.  doi:10.1017/S0960129514000188.
  * [CGY16] Sara Capecchi, Elena Giachino, and Nobuko Yoshida.  Global escape in multiparty sessions.  MSCS, 26(2):156–205, 2016.  doi:10.1017/S0960129514000164.
  * [CH98] Ilaria Castellani and Matthew Hennessy.  Testing theories for asynchronous languages.  In Proc. FSTTCS, volume 1530 of LNCS, pages 90–101. Springer, 1998.  doi:10.1007/978-3-540-49382-2_9.
  * [CH00] Koen Claessen and John Hughes.  QuickCheck: a lightweight tool for random testing of Haskell programs.  In Proc. ICFP, pages 268–279. ACM, 2000.  doi:10.1145/351240.351266.
  * [CPS+09] Koen Claessen, Michal Palka, Nicholas Smallbone, John Hughes, Hans Svensson, Thomas Arts, and Ulf Wiger.  Finding Race Conditions in Erlang with QuickCheck and PULSE.  SIGPLAN Not., 44(9):149–160, aug 2009.  doi:10.1145/1631687.1596574.
  * [dBKP92] Frank S. de Boer, Jan Willem Klop, and Catuscia Palamidessi.  Asynchronous communication in process algebra.  In Proc. LICS, pages 137–147. IEEE Computer Society, 1992.  doi:10.1109/LICS.1992.185528.
  * [DCMA17] Ramiro Demasi, Pablo F. Castro, Thomas S. E. Maibaum, and Nazareno Aguirre.  Simulation relations for fault-tolerance.  Form. Asp. Comput., 29(6):1013–1050, nov 2017.  doi:10.1007/s00165-017-0426-2.
  * [FGL+96] Cédric Fournet, Georges Gonthier, Jean-Jacques Lévy, Luc Maranget, and Didier Rémy.  A calculus of mobile agents.  In Proc. CONCUR, volume 1119 of LNCS, pages 406–421. Springer, 1996.  doi:10.1007/3-540-61604-7_67.
  * [FH07] Adrian Francalanza and Matthew Hennessy.  A theory for observational fault tolerance.  JLAMP, 73(1-2):22–50, 2007.  doi:10.1007/11690634_2.
  * [FH08] Adrian Francalanza and Matthew Hennessy.  A theory of system behaviour in the presence of node and link failure.  Inf. Comput., 206(6):711–759, 2008.  doi:10.1016/j.ic.2007.12.002.
  * [FLMD19] Simon Fowler, Sam Lindley, J. Garrett Morris, and Sára Decova.  Exceptional asynchronous session types: session types without tiers.  Proc. ACM Program. Lang. (POPL), 3:1–29, 2019.  doi:10.1145/3290341.
  * [Gär99] Felix C. Gärtner.  Fundamentals of fault-tolerant distributed computing in asynchronous environments.  ACM Comput. Surv., 31(1):1–26, 1999.  doi:10.1145/311531.311532.
  * [GS86] Susanne Graf and Joseph Sifakis.  A modal characterization of observational congruence on finite terms of CCS.  Inf. Control., 68(1-3):125–145, 1986.  doi:10.1016/S0019-9958(86)80031-6.
  * [GSS+18] Haryadi S. Gunawi, Riza O. Suminto, Russell Sears, Casey Golliher, Swaminathan Sundararaman, Xing Lin, Tim Emami, Weiguang Sheng, Nematollah Bidokhti, Caitie McCaffrey, Deepthi Srinivasan, Biswaranjan Panda, Andrew Baptist, Gary Grider, Parks M. Fields, Kevin Harms, Robert B. Ross, Andree Jacobson, Robert Ricci, Kirk Webb, Peter Alvaro, H. Birali Runesha, Mingzhe Hao, and Huaicheng Li.  Fail-slow at scale: Evidence of hardware performance faults in large production systems.  ACM Trans. Storage, 14(3):23:1–23:26, 2018.  doi:10.1145/3242086.
  * [HGZ+17] Peng Huang, Chuanxiong Guo, Lidong Zhou, Jacob R. Lorch, Yingnong Dang, Murali Chintalapati, and Randolph Yao.  Gray failure: The achilles’ heel of cloud-scale systems.  In Proc. HotOS, pages 150–155, New York, NY, USA, 2017. Association for Computing Machinery.  doi:10.1145/3102980.3103005.
  * [HNY+13] Raymond Hu, Rumyana Neykova, Nobuko Yoshida, Romain Demangeon, and Kohei Honda.  Practical interruptible conversations.  In Proc. RV, pages 130–148. Springer, 2013.  doi:{10.1007/978-3-642-40787-1_8}.
  * [HR95] Matthew Hennessy and Tim Regan.  A process algebra for timed systems.  Inf. Comput., 117(2):221–239, 1995.  doi:10.1006/inco.1995.1041.
  * [HYC16] Kohei Honda, Nobuko Yoshida, and Marco Carbone.  Multiparty asynchronous session types.  J. ACM, 63(1):9:1–9:67, 2016.  doi:10.1145/2827695.
  * [LHS20] Chang Lou, Peng Huang, and Scott Smith.  Understanding, detecting and localizing partial failures in large system software.  In Proc. NDSI, pages 559–574. USENIX Association, 2020.  URL: https://www.usenix.org/conference/nsdi20/presentation/lou.
  * [LNPV18] Ivan Lanese, Naoki Nishida, Adrián Palacios, and Germán Vidal.  A theory of reversibility for Erlang.  JLAMP, 100:71–97, 2018.  doi:10.1016/j.jlamp.2018.06.004.
  * [LP11] Hugo A. López and Jorge A. Pérez.  Time and exceptional behavior in multiparty structured interactions.  In Proc. WS-FM, volume 7176 of LNCS, pages 48–63. Springer, 2011.  doi:10.1007/978-3-642-29834-9_5.
  * [LSZ19] Ivan Lanese, Davide Sangiorgi, and Gianluigi Zavattaro.  Playing with bisimulation in erlang.  In Models, Languages, and Tools for Concurrent and Distributed Programming: Essays Dedicated to Rocco De Nicola on the Occasion of His 65th Birthday, volume 11665 of LNCS, pages 71–91. Springer International Publishing, 2019.  doi:10.1007/978-3-030-21485-2_6.
  * [LZ05] Cosimo Laneve and Gianluigi Zavattaro.  Foundations of web transactions.  In Proc. FoSSaCS, volume 3441 of LNCS, pages 282–298. Springer, 2005.  doi:10.1007/978-3-540-31982-5_18.
  * [Mil89] Robin Milner.  Communication and concurrency.  PHI Series in computer science. Prentice Hall, 1989.  doi:10.5555/534666.
  * [MPW92] Robin Milner, Joachim Parrow, and David Walker.  A calculus of mobile processes, I.  Inf. Comput., 100(1):1–40, 1992.  doi:10.1016/0890-5401(92)90008-4.
  * [MS92] Robin Milner and Davide Sangiorgi.  Barbed bisimulation.  In Proc. ICALP, volume 623 of LNCS, pages 685–695. Springer, 1992.  doi:10.1007/3-540-55719-9_114.
  * [MS98] Massimo Merro and Davide Sangiorgi.  On asynchrony in name-passing calculi.  In Proc. ICALP, volume 1443 of LNCS, pages 856–867. Springer, 1998.  doi:10.1007/BFb0055108.
  * [Mur19] Maurizio Murgia.  Input urgent semantics for asynchronous timed session types.  JLAMP, 107:38–53, 2019.  doi:doi.org/10.1016/j.jlamp.2019.04.001.
  * [MV11] Dimitris Mostrous and Vasco T. Vasconcelos.  Session typing for a Featherweight Erlang.  In Proc. COORDINATION, volume 6721 of LNCS, pages 95–109. Springer, 2011.  doi:10.1007/978-3-642-21464-6_7.
  * [Nyg18] Michael T Nygard.  Release it!: design and deploy production-ready software.  Pragmatic Bookshelf, 2018.
  * [RH97] James Riely and Matthew Hennessy.  Distributed Processes and Location Failures.  In Proc. ICALP, volume 1256 of LNCS, pages 471–481. Springer, 1997.  doi:10.1007/3-540-63165-8_203.
  * [RH01] James Riely and Matthew Hennessy.  Distributed processes and location failures.  Theor. Comput. Sci., 266(1-2):693–735, 2001.  doi:10.1016/S0304-3975(00)00326-1.
  * [SFE10] Hans Svensson, Lars-Åke Fredlund, and Clara Benac Earle.  A unified semantics for future Erlang.  In Proc. ACM SIGPLAN workshop on Erlang, pages 23–32. ACM, 2010.  doi:10.1145/1863509.1863514.
  * [SKÖ+15] Zeynab Sabahi-Kaviani, Ramtin Khosravi, Peter Csaba Ölveczky, Ehsan Khamespanah, and Marjan Sirjani.  Formal semantics and efficient analysis of timed rebeca in real-time maude.  Sci. Comput. Program., 113:85–118, 2015.  doi:10.1016/j.scico.2015.07.003.
  * [Ste89] Bernhard Steffen.  Characteristic formulae.  In Proc. ICALP, volume 372 of LNCS, pages 723–732. Springer, 1989.  doi:10.1007/BFb0035794.
  * [SW01] Davide Sangiorgi and David Walker.  The $\pi$-calculus: a Theory of Mobile Processes. Cambridge University Press, 2001.
  * [Wya13] Derek Wyatt.  Akka Concurrency.  Artima Incorporation, Sunnyvale, CA, USA, 2013.


# Exchange distance of basis pairs in split matroids

Kristóf Bérczi MTA-ELTE Momentum Matroid Optimization Research Group and MTA-
ELTE Egerváry Research Group, Department of Operations Research, Eötvös Loránd
University, Budapest, Hungary. Email<EMAIL_ADDRESS>Tamás
Schwarcz MTA-ELTE Momentum Matroid Optimization Research Group, Department of
Operations Research, Eötvös Loránd University, Budapest, Hungary. Email:
<EMAIL_ADDRESS>
###### Abstract

The basis exchange axiom has been a driving force in the development of
matroid theory. However, the axiom gives only a local characterization of the
relation of bases, which is a major stumbling block to further progress, and
providing a global understanding of the structure of matroid bases is a
fundamental goal in matroid optimization.

While studying the structure of symmetric exchanges, Gabow proposed the
problem that any pair of bases admits a sequence of symmetric exchanges. A
different extension of the exchange axiom was proposed by White, who
investigated the equivalence of compatible basis sequences. These conjectures
suggest that the family of bases of a matroid possesses much stronger
structural properties than we are aware of.

In the present paper, we study the distance of basis pairs of a matroid in
terms of symmetric exchanges. In particular, we give a polynomial-time
algorithm that determines a shortest possible exchange sequence that
transforms a basis pair into another for split matroids, a class that was
motivated by the study of matroid polytopes from a tropical geometry point of
view. As a corollary, we verify the above mentioned long-standing conjectures
for this large class. Being a subclass of split matroids, our result settles
the conjectures for paving matroids as well.

Keywords: Sequential symmetric basis exchange, Split matroids, Paving matroids

##  1 Introduction

Matroids are distinguished from ordinary hereditary set systems by their
strong structural properties. There are several equivalent ways to define a
matroid axiomatically. In terms of bases, a matroid $M$ is a pair
$(S,\mathcal{B})$ where $S$ is a ground set and $\mathcal{B}\subseteq 2^{S}$
is a family of subsets satisfying the basis axioms: (B1)
$\mathcal{B}\neq\emptyset$, (B2) for any $A,B\in\mathcal{B}$ and $e\in A-B$
there exists $f\in B-A$ such that $A-e+f\in\mathcal{B}$. Property (B2) is
called the exchange axiom and serves as a distinctive feature of matroids. The
exchange axiom has a mirror version, the co-exchange axiom, stating that for
any $A,B\in\mathcal{B}$ and $f\in B-A$ there exists $e\in A-B$ such that
$A-e+f\in\mathcal{B}$. Even more, both versions imply the existence of
mutually exchangeable elements, that is, for any $A,B\in\mathcal{B}$ and $e\in
A-B$ there exists $f\in B-A$ such that $A-e+f\in\mathcal{B}$ and
$B+e-f\in\mathcal{B}$; this property is referred to as symmetric exchange
property.

Given two bases $A$ and $B$ of a matroid $M$, the exchange axiom implies the
existence of a sequence of exchanges that transforms $A$ into $B$, and the
shortest length of such a sequence is $|A-B|$. However, the problem becomes
significantly more difficult when it comes to the distance of basis pairs. Let
$(A_{1},A_{2})$ be an ordered pair of bases of $M$, and assume that there
exist $e\in A_{1}-A_{2}$ and $f\in A_{2}-A_{1}$ such that both
$A^{\prime}_{1}\coloneqq A_{1}-e+f$ and $A^{\prime}_{2}\coloneqq A_{2}+e-f$
are bases. Then we say that the pair $(A^{\prime}_{1},A^{\prime}_{2})$ is
obtained from $(A_{1},A_{2})$ by a symmetric exchange. The exchange distance
of two basis pairs $(A_{1},A_{2})$ and $(B_{1},B_{2})$ is the minimum number
of symmetric exchanges needed to transfer the former into the latter if such a
sequence exists and $+\infty$ otherwise. A sequence of symmetric exchanges is
called strictly monotone for $(A_{1},A_{2})$ and $(B_{1},B_{2})$ if each step
decreases the difference between the first members of the pairs. The basis
pairs are omitted when those are clear from context.

As simple the case of single bases is, so little is known about the exchange
distance of basis pairs. Can we characterize those cases when the exchange
distance is finite? If the distance is finite, can we give an upper bound on
it? Can we find a shortest exchange sequence algorithmically? Given basis
pairs $(A_{1},A_{2})$ and $(B_{1},B_{2})$ of a rank-$r$ matroid, an obvious
lower bound on their exchange distance is $r-|A_{1}\cap B_{1}|$. However, it
might happen that more symmetric exchanges are needed even if $M$ is a graphic
matroid; see [8] for a counterexample in $K_{4}$.

Similar questions were considered before in different contexts. Gabow [12]
studied the structure of symmetric exchanges and showed that for any pair
$A,B\in\mathcal{B}$, there exist partitions $A=X_{1}\cup\dots\cup X_{q}$,
$B=Y_{1}\cup\dots\cup Y_{q}$ and bijections $\varphi^{A}_{i}\colon X_{i}\to
Y_{i}$, $\varphi^{B}_{i}\colon Y_{i}\to X_{i}$ for $i=1,\dots,q$ such that

$\displaystyle\left(\bigcup_{j=1}^{i-1}X_{j}\right)\cup\left((X_{i}-Z)\cup\varphi^{A}_{i}(Z)\right)\cup\left(\bigcup_{j=i+1}^{q}Y_{j}\right)\in\mathcal{B}\quad\text{for
$i=1,\dots,q$ and $Z\subseteq X_{i}$, and}$
$\displaystyle\left(\bigcup_{j=1}^{i-1}Y_{j}\right)\cup\left((Y_{i}-Z)\cup\varphi^{B}_{i}(Z)\right)\cup\left(\bigcup_{j=i+1}^{q}X_{j}\right)\in\mathcal{B}\quad\text{for
$i=1,\dots,q$ and $Z\subseteq Y_{i}$.}$

In other words, the result shows the existence of a sequence of symmetric
exchanges of subsets that can be executed element-by-element. In the light of
this result, it is natural to ask whether $q$ can be made to take the extreme
values, $q=1$ and $q=r$ where $r$ is the rank of the matroid. When $q=1$, then
it is not difficult to see that $\varphi^{A}_{1}$ and $\varphi^{B}_{1}$ can be
assumed to be inverses of each other, and the existence of such a bijection
for any pair of bases is equivalent to the matroid being strongly base
orderable. As strongly base orderable matroids form a proper subclass of
matroids, $q=1$ cannot always be achieved. However, the other extreme case
remained open, and Gabow [12] formulated the following beautiful problem,
later stated as a conjecture by Wiedemann [28] and by Cordovil and Moreira
[7].

######  Conjecture 1 (Gabow).

Let $A$ and $B$ bases of the same matroid. Then there are orderings
$A=(a_{1},\dots,a_{r})$ and $B=(b_{1},\dots,b_{r})$ such that
$\\{a_{1},\dots,a_{i},b_{i+1},\dots,b_{r}\\}$ and
$\\{b_{1},\dots,b_{i},a_{i+1},\dots,a_{r}\\}$ are bases for $i=0,\dots,r$.

We call this property the sequential symmetric exchange property. The
conjecture is sometimes rephrased using cyclic orderings. Indeed, the
statement is equivalent to the following: given two bases $A$ and $B$ of a
rank-$r$ matroid, then the elements of $A$ and $B$ have a cyclic ordering such
that both $A$ and $B$ form an interval, and any $r$ cyclically consecutive
elements form a basis.

A different extension of the exchange axiom was considered by White [27], who
proposed to characterize the equivalence of basis sequences. Let
$\mathcal{X}=(X_{1},\dots,X_{m})$ be a sequence of bases of a matroid $M$, and
assume that there exist $e\in X_{i}-X_{j}$, $f\in X_{j}-X_{i}$ with $1\leq
i<j\leq m$ such that both $X_{i}-e+f$ and $X_{j}+e-f$ are bases. The notion of
symmetric exchanges can be naturally extended to sequences by saying that
$\mathcal{X}^{\prime}=(X_{1},\dots,X_{i-1},X_{i}-e+f,X_{i+1},\dots,X_{j-1},X_{j}+e-f,X_{j+1},\dots,X_{m})$
is obtained from $\mathcal{X}$ by a symmetric exchange. We call two sequences
$\mathcal{X}$ and $\mathcal{Y}$ equivalent if $\mathcal{Y}$ may be obtained
from $\mathcal{X}$ by a composition of symmetric exchanges. Note that for
sequences of length two this is equivalent to the exchange distance of the
pairs being finite. Furthermore, $\mathcal{X}$ and $\mathcal{Y}$ are called
compatible if $|\\{i:\ s\in X_{i},1\leq i\leq m\\}|=|\\{i:\ s\in Y_{i},1\leq
i\leq m\\}|$ for every $s\in S$. Compatibility is obviously a necessary
condition for two sequences being equivalent. White [27] conjectured that
compatibility is also sufficient.

######  Conjecture 2 (White).

Two basis sequences $\mathcal{X}$ and $\mathcal{Y}$ of the same length are
equivalent if and only if they are compatible.

Despite being the center of attention not only in combinatorial optimization
but also in algebra due to its connection to toric ideals and Gröbner bases
[4], White’s conjecture remains open even for sequences of length two. The
close relation between the conjectures of White and Gabow is immediate: the
latter would imply the former for sequences of the form $(A,B)$ and $(B,A)$.
Indeed, a cyclic ordering of the elements defines a series of symmetric
exchanges that transforms the sequence $(A,B)$ into the sequence $(B,A)$.
White’s conjecture is also closely related to the connectivity of basis pair
graphs, and for basis sequences of length two, it is in fact equivalent to a
conjecture of Farber [8, 9].

Equitability of matroids is a notion that is lesser known in the optimization
community. A matroid $M=(S,\mathcal{B})$ is called equitable if for any set
$X\subseteq S$ there exists a basis $B\in\mathcal{B}$ such that $S-B$ is also
a basis and $\lfloor|X|/2\rfloor\leq|B\cap X|\leq\lceil|X|/2\rceil$. Somewhat
surprisingly, the following simple conjecture is open, see [1].

######  Conjecture 3 (Equitability of matroids).

If the ground set of a matroid $M$ can be partitioned into two bases, then $M$
is equitable.

A natural generalization of the problem would be asking for a partition into
$k$ bases $B_{1},\dots,B_{k}$ such that $\lfloor|X|/k\rfloor\leq|B_{i}\cap
X|\leq\lceil|X|/k\rceil$. However, it is not difficult to show that the two
variants are in fact equivalent, thus it suffices to concentrate on the first
one, see [1]. Not only the problem might be of independent combinatorial
interest, but it is implied by both Gabow’s and White’s conjectures, therefore
its validity is a precondition of the validity of the other two.

### Previous work.

It was already observed in [12] that Conjecture 1 holds for special classes of
matroids, such as partition matroids, matching and transversal matroids, and
matroids of rank less than $4$. An easy proof shows that it also holds for
strongly base orderable matroids. The statement was later proved for graphic
matroids by Wiedemann [28], Kajitani, Ueno, and Miyano [16], and Cordovil and
Moreira [7]. Kotlar and Ziv [20] showed that any two elements of a basis have
a sequential symmetric exchange with some two elements of any other basis. At
the same time, Kotlar [18] proved that three consecutive symmetric exchanges
exist for any two bases of a matroid, and that a full sequential symmetric
exchange, of length at most $6$, exists for any two bases of a matroid of rank
$5$. Recently, Kotlar, Roda and Ziv [19] proposed a generalization that would
extend the statement in the same way as the result of Greene and Magnanti [13]
did for symmetric exchanges. Van den Heuvel and Thomassé [25] proposed a
relaxation of the problem where the elements of the initial bases $A$ and $B$
do not have to form intervals. A natural extension would be to consider $k$
bases and to find a suitable cyclic ordering of the elements of these $k$
bases combined. This latter problem is wide open even for matroid classes for
which the original conjecture is known to hold, including graphic matroids.
Kajitani, Ueno and Miyano [16] observed that a necessary condition for the
existence of a required cyclic ordering is the matroid $M$ being uniformly
dense111A matroid is uniformly dense if $r\cdot|X|\leq r_{M}(X)\cdot|S|$ for
every $X\subseteq S$, where $r_{M}$ and $r$ denote the rank function and the
rank of $M$, respectively., and conjectured that this condition is also
sufficient. A matroid admitting a partition of its ground set into bases is
uniformly dense, therefore a proof for the conjecture of Kajitani, Ueno and
Miyano would imply an affirmative answer to that of van den Heuvel and
Thomassé as well. In [25], the conjecture was verified if $|S|$ and $r(S)$ are
coprimes.

A routine argument shows that Conjecture 2 holds for a matroid $M$ if and only
if it holds for its dual $M^{*}$. For basis sequences of length two, Farber,
Richter, and Shank [9] verified the statement for graphic and cographic
matroids, while Farber [8] proved the conjecture for transversal matroids. For
sequences of arbitrary length, the most significant partial result is due to
Blasiak [4], who confirmed the conjecture for graphic matroids by showing that
the toric ideal of a graphic matroid is generated by quadrics. Kashiwabara
[17] settled the case of matroids of rank at most $3$. Schweig [24] proved the
statement for lattice path matroids, a subclass of transversal matroids. The
case of strongly base orderable matroids was solved by Lasoń and Michałek
[21]. Recently, Blasiak’s result was further extended by McGuinness [22] to
frame matroids satisfying a linearity condition. Such classes of matroids
include graphic matroids, bicircular matroids, signed graphic matroids, and
more generally frame matroids obtained from group-labelled graphs.

Apart from the matroid classes for which Conjecture 1 or 2 was settled,
Conjecture 3 was shown to hold for base orderable matroids by Fekete and Szabó
[10]. They also studied an extension of the problem where equitability with
respect to more than one set is required. Király [1] observed that the
equitability of hypergraphic matroids follows from the graphic case. Equitable
partitions are closely related to fair representations, introduced by Aharoni,
Berger, Kotlar, and Ziv [2]. For some positive real $\alpha$, a set $X$
represents another set $A$ $\alpha$-fairly if $|X\cap
A|\geq\lfloor\alpha|A|\rfloor$, and $X$ represents $A$ almost $\alpha$-fairly
if $|X\cap A|\geq\lfloor\alpha|A|\rfloor-1$. The notion of representation is
then extended to partitions: a set is said to represent a partition
$A_{1},\dots,A_{m}$ $\alpha$-fairly (almost $\alpha$-fairly) if it represents
all $A_{i}$’s $\alpha$-fairly (almost $\alpha$-fairly, respectively). The
authors of [2] provided several conjectures and results on fair
representations. In particular, their results imply the following relaxation
of Conjecture 3: If the ground set $S$ of a matroid $M$ can be partitioned
into two bases, then for any $X\subseteq S$ there exists an independent set
$I$ of size at least $r-1$ such that $S-I$ contains a basis, $|I\cap
X|\geq\lfloor|X|/2\rfloor-1$, and $|I\cap(S-X)|\geq\lfloor|S-X|/2\rfloor-1$.

Our investigations were motivated by the results of Bonin [5] who verified
Conjectures 1-3 for sparse paving matroids. On a high level, our proofs
resemble the proofs appearing in [5]. Nevertheless, as one would expect, the
higher complexity of split matroids compared to that of sparse paving matroids
requires significantly more careful and intricate reasonings.

### Split matroids.

While Conjectures 1-3 were verified for various matroid classes, they remained
open for paving matroids, a well-studied class with distinguished structural
properties. Split matroids were introduced by Joswig and Schröter [15] via
polyhedral geometry as a generalization of paving matroids, and quickly found
applications in tropical geometry. Roughly speaking, a rank-$r$ matroid $M$ is
split if the hyperplanes that are used to cut off parts of the matroid base
polytope of the rank-$r$ uniform matroid to obtain that of $M$ satisfy a
certain compatibility condition. The polyhedral point of view proved to be
helpful in understanding the geometry of split matroids, and resulted in
fundamental structural results on this class such as being closed both under
duality and taking minors. Five forbidden minors were identified already in
[15], and Cameron and Mayhew [6] later verified that the list is complete.

Motivated by hypergraph representations of paving matroids, Bérczi, Király,
Schwarcz, Yamaguchi and Yokoi [3] initiated a combinatorial study of split
matroids. They introduced the notion of elementary split matroids, a class
that is a proper subclass of split matroids but includes all connected split
matroids. The definition follows a combinatorial approach by setting the
independent sets of the matroid to be the family of sets having bounded
intersections with certain hyperedges. The proposed class captures all the
nice properties of connected split matroids, and is closed not only under
duality and taking minors but also truncation. More importantly, elementary
split matroids can be characterized by a single forbidden minor.

### Our results.

Our main contribution is a strong upper bound on the exchange distance of
basis pairs in split matroids, together with a polynomial-time algorithm that
determines a shortest exchange sequence222In matroid algorithms, it is usually
assumed that the matroids are given by independence oracles. Then the
complexity of an algorithm is measured by the number of oracle calls and other
conventional elementary steps.. Given compatible basis pairs $(A_{1},A_{2})$
and $(B_{1},B_{2})$ of a rank-$r$ split matroid, we prove that
$\min\\{r,r-|A_{1}\cap B_{1}|+1\\}$ such steps always suffice. This result
immediately implies that, for split matroids, Conjectures 1 and 3 hold in
general, and Conjecture 2 hold for sequences of length two. The graphic
matroid of $K_{4}$ is sparse paving and so it is a split matroid, hence the
example of [8] shows that the bound above is best possible.

As a corollary, we prove that for split matroids there always exists a
strictly monotone sequence of symmetric exchanges of length $r-3|A_{1}\cap
B_{1}|$. For base orderable split matroids and paving matroids, we improve the
bound to $r-2|A_{1}\cap B_{1}|$ and $r-|A_{1}\cap B_{1}|-2$, respectively.
Note that $r-|A_{1}\cap B_{1}|$ is clearly an upper bound on the maximum
length of a strictly monotone sequence.

The rest of the paper is organized as follows. Basic notation and definitions
are given in Section 2. Section 3 provides a polynomial-time algorithm that
determines the exchange distance of basis pairs in split matroids, and
discusses Conjectures 1-3 for this class. Section 4 provides lower bounds on
the maximum length of a strictly monotone sequence of symmetric exchanges in
various settings.

##  2 Preliminaries

Throughout, we denote by $S$ the ground set of a matroid. For subsets
$X,Y\subseteq S$, the difference of $X$ and $Y$ is denoted by $X-Y$. If $Y$
consists of a single element $y$, then $X-\\{y\\}$ and $X\cup\\{y\\}$ are
abbreviated as $X-y$ and $X+y$, respectively. An ordered sequence consisting
of elements of $S$ is denoted by $\underline{\mathbf{x}}=(x_{1},\dots,x_{s})$.

For basic definitions on matroids, we refer the reader to [23]. Let
$M=(S,\mathcal{B})$ be a rank-$r$ matroid on $S$, where $\mathcal{B}$ is the
family of bases of $M$. We denote the rank function of $M$ by $r_{M}$. A
matroid of rank $r$ is called paving if every set of size at most $r-1$ is
independent, or in other words, every circuit of the matroid has size at least
$r$. A matroid is sparse paving if it is both paving and dual to a paving
matroid. For a non-negative integer $r$, a set $S$ of size at least $r$, and a
(possibly empty) family $\mathcal{H}=\\{H_{1},\dots,H_{q}\\}$ of proper
subsets of $S$ such that $|H_{i}\cap H_{j}|\leq r-2$ for $1\leq i<j\leq q$,
the set system $\mathcal{I}=\\{X\subseteq S\mid|X|\leq r,\ |X\cap H_{i}|\leq
r-1\ \text{for }i=1,\dots,q\\}$ forms the family of independent sets of a
rank-$r$ paving matroid, and in fact every paving matroid can be obtained in
this form, see [14, 26].

Joswig and Schröter originally defined split matroids via polyhedral geometry.
They showed that split matroids are closed under taking minors [15,
Proposition 44], and that it suffices to concentrate on the connected case
[15, Proposition 15].

######  Proposition 4 (Joswig and Schröter).

  1. (a)

The class of split matroids is minor-closed.

  2. (b)

A matroid is a split matroid if and only if at most one connected component is
a non-uniform split matroid and all other components are uniform.

In [3], a proper subclass called elementary split matroids was introduced
which includes all connected split matroids. The main advantage of the
proposed subclass is that it admits a hypergraph characterization similar to
that of paving matroids. Namely, let $S$ be a ground set of size at least $r$,
$\mathcal{H}=\\{H_{1},\dots,H_{q}\\}$ be a (possibly empty) collection of
subsets of $S$, and $r,r_{1},\dots,r_{q}$ be non-negative integers satisfying

(H1) $\displaystyle|H_{i}\cap H_{j}|$ $\displaystyle\leq r_{i}+r_{j}-r\
\text{for $1\leq i<j\leq q$,}$ (H2) $\displaystyle|S-H_{i}|+r_{i}$
$\displaystyle\geq r\ \text{for $i=1,\dots,q$.}$

Then $\mathcal{I}=\\{X\subseteq S\mid|X|\leq r,\ |X\cap H_{i}|\leq r_{i}\
\text{for $1\leq i\leq q$}\\}$ forms the family of independent sets of a
rank-$r$ matroid $M$ with rank function
$r_{M}(Z)=\min\big{\\{}r,|Z|,\min_{1\leq i\leq
q}\\{|Z-H_{i}|+r_{i}\\}\big{\\}}$. Matroids that can be obtained in this form
are called elementary split matroids. It was observed already in [3] that the
underlying hypergraph can be chosen in such a way that

(H3) $\displaystyle r_{i}$ $\displaystyle\leq r-1\ \text{for $i=1,\dots,q$,}$
(H4) $\displaystyle|H_{i}|$ $\displaystyle\geq r_{i}+1\ \text{for
$i=1,\dots,q$.}$

Therefore, we call the representation non-redundant if all of (H1)–(H4) hold.
A set $F\subseteq S$ is called $H_{i}$-tight if $|F\cap H_{i}|=r_{i}$.
Finally, we will use the following result from [3, Theorem 11] that
establishes a connection between elementary and connected split matroids.

######  Proposition 5 (Bérczi, Király, Schwarcz, Yamaguchi and Yokoi).

Connected split matroids form a subclass of elementary split matroids.

##  3 Exchange distance of basis pairs

Let $(A_{1},A_{2})$ and $(B_{1},B_{2})$ be compatible basis pairs of a
rank-$r$ split matroid $M$, that is, $A_{1}\cap A_{2}=B_{1}\cap B_{2}$ and
$A_{1}\cup A_{2}=B_{1}\cup B_{2}$. The goal of the current section is to give
an upper bound on the number of symmetric exchanges needed to transform
$(A_{1},A_{2})$ into $(B_{1},B_{2})$. The high-level idea of the proof is as
follows. We recursively try to pair up the elements of $A_{1}\cap B_{2}$ and
$A_{2}\cap B_{1}$ in such a way that each pair $x_{i},y_{i}$ corresponds to a
symmetric exchange between bases
$A_{1}-\\{x_{1},\dots,x_{i-1}\\}\cup\\{y_{1},\dots,y_{i-1}\\}$ and
$A_{2}-\\{y_{1},\dots,y_{i-1}\\}\cup\\{x_{1},\dots,x_{i-1}\\}$. If no such
pair exists, then we identify the obstacle blocking every possible exchange in
terms of hyperedges appearing in a non-redundant representation of $M$. At
this point we show that there exists a symmetric exchange of elements from
$A_{1}\cap B_{1}$ and $A_{2}\cap B_{1}$ that can be followed by a complete
sequence of symmetric exchanges between elements of $A_{1}\cap B_{2}$ and
$A_{2}\cap B_{1}$, leading to the $r-|A_{1}\cap B_{1}|+1$ bound.

In our proof, we will rely on the following simple technical lemma several
times.

######  Lemma 6.

Let $M$ be a rank-$r$ elementary split matroid with a non-redundant
representation $\mathcal{H}=\\{H_{1},\dots,H_{q}\\}$ and
$r,r_{1},\dots,r_{q}$. Let $F$ be a set of size $r$.

  1. (a)

If $F$ is $H_{i}$-tight for some index $i$ then $F$ is a basis of $M$.

  2. (b)

If $F$ is both $H_{i}$-tight and $H_{j}$-tight for distinct indices $i$ and
$j$ then $H_{i}\cap H_{j}\subseteq F\subseteq H_{i}\cup H_{j}$.

###### Proof.

Assume that $F$ is $H_{i}$-tight. Then, by (H1), for any index $j\neq i$ we
get

$\displaystyle|F\cap H_{j}|{}$ $\displaystyle{}=|F\cap(H_{i}\cup
H_{j})|+|F\cap(H_{i}\cap H_{j})|-|F\cap H_{i}|$
$\displaystyle{}\leq|F|+|H_{i}\cap H_{j}|-r_{i}$ $\displaystyle{}\leq
r+(r_{i}+r_{j}-r)-r_{i}$ $\displaystyle{}=r_{j},$

showing the $F$ is indeed a basis. If $F$ is also $H_{j}$-tight, then equality
holds throughout, implying $H_{i}\cap H_{j}\subseteq F\subseteq H_{i}\cup
H_{j}$. ∎

To avoid referring to part (a) of the lemma too often, we implicitly consider
sets of size $r$ that are tight with respect to one of the hyperedges to be
bases. Now we turn to the proof of the main result of the paper.

######  Theorem 7.

Let $(A_{1},A_{2})$ and $(B_{1},B_{2})$ be compatible basis pairs of a
rank-$r$ split matroid $M$. Then the exchange distance of $(A_{1},A_{2})$ and
$(B_{1},B_{2})$ is at most $\min\\{r,r-|A_{1}\cap B_{1}|+1\\}$.

###### Proof.

Recall that $(A_{1},A_{2})$ and $(B_{1},B_{2})$ are compatible if $A_{1}\cap
A_{2}=B_{1}\cap B_{2}$ and $A_{1}\cup A_{2}=B_{1}\cup B_{2}$. We start with
two simplifications. First, we may assume that $A_{1}\cap A_{2}=\emptyset$.
Indeed, if $A_{1}\cap A_{2}\neq\emptyset$, then let $A_{1}^{\prime}\coloneqq
A_{1}-A_{2}$, $A_{2}^{\prime}\coloneqq A_{2}-A_{1}$, $B_{1}^{\prime}\coloneqq
B_{1}-B_{2}$, $B_{2}^{\prime}\coloneqq B_{2}-B_{1}$ and let $M^{\prime}$
denote the matroid obtained from $M$ by contracting $A_{1}\cap A_{2}$. By
Proposition 4(a), $M^{\prime}$ is also a split matroid in which both
$A_{1}^{\prime},A_{2}^{\prime}$ and $B_{1}^{\prime},B_{2}^{\prime}$ are
disjoint bases. Note that the rank of $M^{\prime}$ is $r^{\prime}\coloneqq
r-|A_{1}\cap A_{2}|$. As a sequence of symmetric exchanges that transforms
$(A_{1}^{\prime},A_{2}^{\prime})$ into $(B_{1}^{\prime},B_{2}^{\prime})$ also
transforms $(A_{1},A_{2})$ into $(B_{1},B_{2})$, the claim follows by
$\min\\{r^{\prime},r^{\prime}-|A_{1}^{\prime}\cap
B_{1}^{\prime}|+1\\}\leq\min\\{r,r-|A_{1}\cap B_{1}|+1\\}$.

Second, it suffices to verify the statement for connected split matroids.
Indeed, if $M$ is not connected, then all but at most one of its components
are uniform matroids by Proposition 4(b). Let $M_{0}=(S_{0},\mathcal{B}_{0})$
denote, if exists, the non-uniform component, and let
$M_{1}=(S_{1},\mathcal{B}_{1}),\dots,M_{t}=(S_{t},\mathcal{B}_{t})$ be the
uniform connected components of $M$. Define $A_{1}^{i}\coloneqq A_{1}\cap
S_{i}$, $A_{2}^{i}\coloneqq A_{2}\cap S_{i}$, $B_{1}^{i}\coloneqq B_{1}\cap
S_{i}$, $B_{2}^{i}\coloneqq B_{2}\cap S_{i}$ for $i=0,\dots,t$. Note that
$A_{1}^{i}$, $A_{2}^{i}$, $B_{1}^{i}$ and $B_{2}^{i}$ are bases of $M_{i}$.
Take a sequence of at most $\min\\{r_{0},r_{0}-|A_{1}^{0}\cap B_{1}^{0}|+1\\}$
symmetric exchanges that transforms $(A^{0}_{1},A^{0}_{2})$ into
$(B^{0}_{1},B^{0}_{2})$, where $r_{0}$ is the rank of $M_{0}$. As $M_{i}$ is a
uniform matroid, it is easy to see that the exchange distance of
$(A_{1}^{i},A_{2}^{i})$ and $(B_{1}^{i},B_{2}^{i})$ is exactly
$r_{i}-|A^{i}_{1}\cap B^{i}_{1}|$; take such a sequence for $1\leq i\leq t$.
Then the concatenations of these sequences result in a sequence of at most
$\min\\{r_{0},r_{0}-|A_{1}^{0}\cap
B_{1}^{0}|+1\\}+\sum_{i=1}^{t}[r_{i}-|A_{1}^{i}\cap
B_{1}^{i}|]\leq\min\\{r,r-|A_{1}\cap B_{1}|+1\\}$ symmetric exchanges that
transforms $(A_{1},A_{2})$ into $(B_{1},B_{2})$.

Hence we may assume that $M$ is connected. Let $\mathcal{H}$ be a hypergraph
corresponding to a non-redundant representation of $M$; such a representation
exists by Proposition 5. By convention, we denote the bound on a hyperedge
$H_{i}$ by $r_{i}$. Choose a pair of inclusionwise maximal sequences
$\underline{\mathbf{x}}\coloneqq(x_{1},\dots,x_{s})$ and
$\underline{\mathbf{y}}\coloneqq(y_{1},\dots,y_{s})$ of distinct elements
greedily that correspond to a strictly monotone sequence of exchanges, that
is,

$\displaystyle\begin{array}[]{c}x_{i}\in A_{1}\cap B_{2},\ y_{i}\in A_{2}\cap
B_{1},\\\ (A_{1}-\\{x_{1},\dots,x_{i}\\})\cup\\{y_{1},\dots,y_{i}\\}\ \text{is
a basis for $i=1,\dots,s$,}\\\
(A_{2}-\\{y_{1},\dots,y_{i}\\})\cup\\{x_{1},\dots,x_{i}\\}\ \text{is a basis
for $i=1,\dots,s$.}\end{array}$

Define
$A_{1}^{\prime}\coloneqq(A_{1}-\\{x_{1},\dots,x_{s}\\})\cup\\{y_{1},\dots,y_{s}\\}$
and
$A_{2}^{\prime}\coloneqq(A_{2}-\\{y_{1},\dots,y_{s}\\})\cup\\{x_{1},\dots,x_{s}\\}$.
If $A_{1}^{\prime}=B_{1}$, then these sequences correspond to symmetric
exchanges transforming $(A_{1},A_{2})$ into $(B_{1},B_{2})$, and we are done.
Otherwise $A_{1}^{\prime}\neq B_{1}$ and, by the maximal choice of the
sequences, there is no $x\in A_{1}^{\prime}\cap B_{2}$ and $y\in
A_{2}^{\prime}\cap B_{1}$ such that both $A_{1}^{\prime}-x+y$ and
$A_{2}^{\prime}+x-y$ are bases.

######  Claim 8.

There exist distinct hyperedges $H_{1}$, $H_{2}$, $H_{3}$ and $H_{4}$ such
that $A^{\prime}_{1}$ is $H_{1}$\- and $H_{3}$-tight, while $A^{\prime}_{2}$
is $H_{2}$\- and $H_{4}$-tight.

###### Proof.

Fix an arbitrary $x\in A_{1}^{\prime}\cap B_{2}$ and let $y\in
A_{2}^{\prime}\cap B_{1}$ be an element for which $A_{2}^{\prime}+x-y$ is a
basis. Note that such a $y$ exists by the co-exchange axiom for
$A_{2}^{\prime}$, $B_{2}$ and $x\in B_{2}-A_{2}^{\prime}$. By our assumption,
$A_{1}^{\prime}-x+y$ is not a basis, hence there exists a hyperedge $H_{1}$
with $|(A_{1}^{\prime}-x+y)\cap H_{1}|>r_{1}$. As $A_{1}^{\prime}$ is a basis,
we get $|A_{1}^{\prime}\cap H_{1}|=r_{1}$, $x\notin H_{1}$ and $y\in H_{1}$.

By applying the co-exchange axiom for $A_{1}^{\prime}$, $B_{1}$ and $y\in
B_{1}-A_{1}^{\prime}$, there exists an $x^{\prime}\in A_{1}^{\prime}\cap
B_{2}$ for which $A_{1}^{\prime}-x^{\prime}+y$ is a basis. By our assumption,
$A_{2}^{\prime}+x^{\prime}-y$ is not a basis, hence there exists a hyperedge
$H_{2}$ with $|(A_{2}^{\prime}+x^{\prime}-y)\cap H_{2}|>r_{2}$. As
$A_{2}^{\prime}$ is a basis, we get $|A_{2}^{\prime}\cap H_{2}|=r_{2}$,
$y\notin H_{2}$ and $x^{\prime}\in H_{2}$. Necessarily, $x^{\prime}\in H_{1}$
as otherwise $|(A_{1}^{\prime}-x^{\prime}+y)\cap H_{1}|=r_{1}+1$,
contradicting $A_{1}^{\prime}-x^{\prime}+y$ being a basis. Similarly, $x\notin
H_{2}$ as otherwise $|(A_{2}^{\prime}+x-y)\cap H_{2}|=r_{2}+1$, contradicting
$A_{2}^{\prime}+x-y$ being a basis.

By applying the co-exchange axiom for $A_{2}^{\prime}$, $B_{2}$ and
$x^{\prime}\in B_{2}-A_{2}^{\prime}$, there exists a $y^{\prime}\in
A_{2}^{\prime}\cap B_{1}$ for which $A_{2}^{\prime}+x^{\prime}-y^{\prime}$ is
a basis. By our assumption, $A_{1}^{\prime}-x^{\prime}+y^{\prime}$ is not a
basis, hence there exists a hyperedge $H_{3}$ with
$|(A_{1}^{\prime}-x^{\prime}+y^{\prime})\cap H_{3}|>r_{3}$. As
$A_{1}^{\prime}$ is a basis, we get $|A_{1}^{\prime}\cap H_{3}|=r_{3}$,
$x^{\prime}\notin H_{3}$ and $y^{\prime}\in H_{3}$. The set $A_{1}^{\prime}$
is both $H_{1}$\- and $H_{3}$-tight, hence $H_{1}\cap H_{3}\subseteq
A_{1}^{\prime}\subseteq H_{1}\cup H_{3}$ by Lemma 6(b). As $x\in
A_{1}^{\prime}-H_{1}$, $y\in H_{1}-A_{1}^{\prime}$ and $y^{\prime}\in
H_{3}-A_{1}^{\prime}$, we get $x\in H_{3}$, $y\notin H_{3}$ and
$y^{\prime}\notin H_{1}$, respectively.

Being $H_{1}$-tight, the set $A_{1}^{\prime}-x+y^{\prime}$ is a basis.
Therefore $A_{2}^{\prime}+x-y^{\prime}$ is not a basis, implying the existence
of a hyperedge $H_{4}$ with $|(A_{2}^{\prime}+x-y^{\prime})\cap H_{4}|>r_{4}$.
As $A_{2}^{\prime}$ is a basis, we get $|A_{2}^{\prime}\cap H_{4}|=r_{4}$,
$y^{\prime}\notin H_{4}$ and $x\in H_{4}$. The set $A_{2}^{\prime}$ is both
$H_{2}$\- and $H_{4}$-tight, hence $H_{2}\cap H_{4}\subseteq
A_{2}^{\prime}\subseteq H_{2}\cup H_{4}$ by Lemma 6(b). As $y\in
A_{2}^{\prime}-H_{2}$, $x^{\prime}\in H_{2}-A_{2}^{\prime}$ and $y^{\prime}\in
A_{2}^{\prime}-H_{4}$, we get $y\in H_{4}$, $x^{\prime}\notin H_{4}$ and
$y^{\prime}\in H_{2}$.

Note that the pairs $\\{x^{\prime},y\\}$, $\\{x^{\prime},y^{\prime}\\}$,
$\\{x,y^{\prime}\\}$ and $\\{x,y\\}$ are included only in $H_{1}$, $H_{2}$,
$H_{3}$ and $H_{4}$, respectively, hence these hyperedges are pairwise
distinct. ∎

Our goal is to recover the relations of the four hyperedges identified by
Claim 8. For ease of discussion, we denote by $H_{i,j}\coloneqq(H_{i}\cap
H_{j})-(H_{k}\cup H_{\ell})$ for $\\{i,j,k,\ell\\}=\\{1,2,3,4\\}$. The proof
of the claim also implies that none of the sets $A^{\prime}_{1}\cap B_{2}\cap
H_{3,4}$, $A^{\prime}_{1}\cap B_{2}\cap H_{1,2}$, $A^{\prime}_{2}\cap
B_{1}\cap H_{1,4}$ and $A^{\prime}_{2}\cap B_{1}\cap H_{2,3}$ is empty, see
the elements $x$, $x^{\prime}$, $y$ and $y^{\prime}$.

######  Claim 9.

$A^{\prime}_{1}\cap B_{2}\subseteq H_{1,2}\cup H_{3,4}$ and
$A^{\prime}_{2}\cap B_{1}\subseteq H_{1,4}\cup H_{2,3}$.

###### Proof.

Take an arbitrary $z\in A^{\prime}_{1}\cap B_{2}$. As $z\in
A^{\prime}_{1}-A^{\prime}_{2}$, Claim 8 and Lemma 6(b) together imply $z\in
H_{1}\cup H_{3}$ and $z\notin H_{2}\cap H_{4}$. Furthermore, $z\notin
H_{1}-H_{2}$ as otherwise $A^{\prime}_{1}-z+y$ is $H_{1}$-tight and
$A^{\prime}_{2}+z-y$ is $H_{2}$-tight for any $y\in A^{\prime}_{2}\cap
B_{1}\cap H_{1,4}$, contradicting the assumption that no such symmetric
exchange exists. Similarly, $z\notin H_{3}-H_{4}$ as otherwise
$A^{\prime}_{1}-z+y^{\prime}$ is $H_{3}$-tight and
$A^{\prime}_{2}-y^{\prime}+z$ is $H_{4}$-tight for any $y^{\prime}\in
A^{\prime}_{2}\cap B_{1}\cap H_{2,3}$, contradicting the assumption that no
such symmetric exchange exists. These observations imply $A^{\prime}_{1}\cap
B_{2}\subseteq H_{1,2}\cup H_{3,4}$.

The inclusion $A^{\prime}_{2}\cap B_{1}\subseteq H_{1,4}\cup H_{2,3}$ can be
proved analogously. ∎

Next we show that either the length of the strictly monotone sequence of
exchanges can be increased, or we derive further structural observations on
the hyperedges $H_{1}$, $H_{2}$, $H_{3}$ and $H_{4}$.

######  Claim 10.

Either there exists a pair of sequences
$\underline{\mathbf{x}}^{\prime}=(x^{\prime}_{1},\dots,x^{\prime}_{s+2})$ and
$\underline{\mathbf{y}}^{\prime}=(y^{\prime}_{1},\dots,y^{\prime}_{s+2})$
satisfying 3, or $\\{x_{i},y_{i}\\}\subseteq(H_{1}\triangle
H_{3})\cap(H_{2}\triangle H_{4})$ and $x_{i}$ and $y_{i}$ are contained in the
same hyperedges from $\\{H_{1},H_{2},H_{3},H_{4}\\}$ for each $1\leq i\leq s$.

###### Proof.

We prove the claim by considering the pairs $x_{i},y_{i}$ starting from $i=s$
in a reversed order. In a general phase, consider an index $1\leq i\leq s$ and
assume that $x_{j}$ and $y_{j}$ are contained in the same hyperedges from
$\\{H_{1},H_{2},H_{3},H_{4}\\}$ for each $i+1\leq j\leq s$. This assumption
and Claim 8 imply that

$\displaystyle(A_{1}-\\{x_{1},\dots,x_{j}\\})+\\{y_{1},\dots,y_{j}\\}\
\text{is $H_{1}$- and $H_{3}$-tight for $i+1\leq j\leq s$},$
$\displaystyle(A_{2}-\\{y_{1},\dots,y_{j}\\})+\\{x_{1},\dots,x_{j}\\}\
\text{is $H_{2}$- and $H_{4}$-tight for $i+1\leq j\leq s$}.$

By Claim 8 and Lemma 6(b), we have $x_{i}\not\in H_{1}\cap H_{3}$, $x_{i}\in
H_{2}\cup H_{4}$, $y_{i}\in H_{1}\cup H_{3}$ and $y_{i}\not\in H_{2}\cap
H_{4}$. We prove that either we can construct a pair
$\underline{\mathbf{x}}^{\prime},\underline{\mathbf{y}}^{\prime}$ of sequences
of length $s+2$ satisfying the conditions of 3, or
$\\{x_{i},y_{i}\\}\subseteq(H_{1}\triangle H_{3})\cap(H_{2}\triangle H_{4})$
and $x_{i}$ and $y_{i}$ are contained in the same hyperedges from
$\\{H_{1},H_{2},H_{3},H_{4}\\}$. Fix elements $x\in A^{\prime}_{1}\cap
B_{2}\cap H_{3,4}$, $x^{\prime}\in A^{\prime}_{1}\cap B_{2}\cap H_{1,2}$,
$y\in A^{\prime}_{2}\cap B_{1}\cap H_{1,4}$ and $y^{\prime}\in
A^{\prime}_{2}\cap B_{1}\cap H_{2,3}$. We discuss four cases.

Case 1. $x_{i}\not\in H_{1}\cup H_{3}$.

If $x_{i}\in H_{2}$, define
$\underline{\mathbf{x}}^{\prime}\coloneqq(x_{1},\dots,x_{i-1},x^{\prime},x_{i+1},\dots,x_{s},x,x_{i})$
and
$\underline{\mathbf{y}}^{\prime}\coloneqq(y_{1},\dots,y_{s},y,y^{\prime})$.
Then

$\displaystyle(A_{1}-\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\})+\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\}\
\text{is $H_{3}$-tight for $i\leq j\leq s$ and $H_{1}$-tight for
$j=s+1,s+2$},$
$\displaystyle(A_{2}-\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\})+\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\}\
\text{is $H_{2}$-tight for $i\leq j\leq s+2$}.$

If $x_{i}\notin H_{2}$, then $x_{i}\in H_{4}$. Consider the sequences
$\underline{\mathbf{x}}^{\prime}\coloneqq(x_{1},\dots,x_{i-1},x,x_{i+1},\dots,x_{s},x^{\prime},x_{i})$
and
$\underline{\mathbf{y}}^{\prime}\coloneqq(y_{1},\dots,y_{s},y^{\prime},y)$.
Then

$\displaystyle(A_{1}-\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\})+\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\}\
\text{is $H_{1}$-tight for $i\leq j\leq s$ and $H_{3}$ tight for
$j=s+1,s+2$},$
$\displaystyle(A_{2}-\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\})+\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\}\
\text{is $H_{2}$-tight for $i\leq j\leq s+2$}.$

Case 2. $x_{i}\in H_{2}\cap H_{4}$.

If $x_{i}\notin H_{1}$, define
$\underline{\mathbf{x}}^{\prime}\coloneqq(x_{1},\dots,x_{i-1},x,x_{i+1},\dots,x_{s},x^{\prime},x_{i})$
and
$\underline{\mathbf{y}}^{\prime}\coloneqq(y_{1},\dots,y_{s},y,y^{\prime})$.
Then

$\displaystyle(A_{1}-\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\})+\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\}\
\text{is $H_{1}$-tight for $i\leq j\leq s+2$},$
$\displaystyle(A_{2}-\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\})+\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\}\
\text{is $H_{4}$-tight for $i\leq j\leq s+1$ and $H_{2}$-tight for
$j=s+1,s+2$}.$

If $x_{i}\in H_{1}$, then $x_{i}\notin H_{3}$. Consider the sequences
$\underline{\mathbf{x}}^{\prime}\coloneqq(x_{1},\dots,x_{i-1},x^{\prime},x_{i+1},\dots,x_{s},x,x_{i})$
and
$\underline{\mathbf{y}}^{\prime}\coloneqq(y_{1},\dots,y_{s},y^{\prime},y)$.
Then

$\displaystyle(A_{1}-\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\})+\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\}\
\text{is $H_{1}$-tight for $i\leq j\leq s+2$},$
$\displaystyle(A_{2}-\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\})+\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\}\
\text{is $H_{2}$-tight for $i\leq j\leq s$ and $H_{4}$-tight for
$j=s+1,s+2$}.$

Case 3. $y_{i}\in H_{1}\cap H_{3}$.

If $y_{i}\notin H_{2}$, define
$\underline{\mathbf{x}}^{\prime}\coloneqq(x_{1},\dots,x_{s},x^{\prime},x)$ and
$\underline{\mathbf{y}}^{\prime}\coloneqq(y_{1},\dots,y_{i-1},y,y_{i+1},\dots,y_{s},y^{\prime},y_{i})$.
Then

$\displaystyle(A_{1}-\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\})+\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\}\
\text{is $H_{1}$-tight for $i\leq j\leq s$ and $H_{3}$-tight for
$j=s+1,s+2$},$
$\displaystyle(A_{2}-\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\})+\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\}\
\text{is $H_{2}$-tight for $i\leq j\leq s+2$}.$

If $y_{i}\in H_{2}$, then $y_{i}\notin H_{4}$. Consider the sequences
$\underline{\mathbf{x}}^{\prime}\coloneqq(x_{1},\dots,x_{s},x,x^{\prime})$ and
$\underline{\mathbf{y}}^{\prime}\coloneqq(y_{1},\dots,y_{i-1},\allowbreak
y^{\prime},y_{i+1},\dots,y_{s},y,y_{i})$. Then

$\displaystyle(A_{1}-\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\})+\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\}\
\text{is $H_{3}$-tight for $i\leq j\leq s$ and $H_{1}$-tight for
$j=s+1,s+2$},$
$\displaystyle(A_{2}-\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\})+\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\}\
\text{is $H_{4}$-tight for $i\leq j\leq s$}.$

Case 4. $y_{i}\notin H_{2}\cup H_{4}$.

If $y_{i}\in H_{1}$, define
$\underline{\mathbf{x}}^{\prime}\coloneqq(x_{1},\dots,x_{s},x,x^{\prime})$ and
$\underline{\mathbf{y}}^{\prime}\coloneqq(y_{1},\dots,y_{i-1},y,y_{i+1},\dots,y_{s},y^{\prime},y_{i})$.
Then

$\displaystyle(A_{1}-\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\})+\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\}\
\text{is $H_{1}$-tight for $i\leq j\leq s+2$},$
$\displaystyle(A_{2}-\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\})+\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\}\
\text{is $H_{2}$-tight for $i\leq j\leq s$ and $H_{4}$-tight for
$j=s+1,s+2$}.$

If $y_{i}\notin H_{1}$, then $y_{i}\in H_{3}$. Consider the sequences
$\underline{\mathbf{x}}^{\prime}\coloneqq(x_{1},\dots,x_{s},x^{\prime},x)$ and
$\underline{\mathbf{y}}^{\prime}\coloneqq(y_{1},\dots,y_{i-1},\allowbreak
y^{\prime},y_{i+1},\dots,y_{s},y,y_{i})$. Then

$\displaystyle(A_{1}-\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\})+\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\}\
\text{is $H_{3}$-tight for $i\leq j\leq s+2$},$
$\displaystyle(A_{2}-\\{y^{\prime}_{1},\dots,y^{\prime}_{j}\\})+\\{x^{\prime}_{1},\dots,x^{\prime}_{j}\\}\
\text{is $H_{4}$-tight for $i\leq j\leq s$ and $H_{2}$-tight for
$j=s+1,s+2$}.$

By the above, every basis that is affected by the changes in
$\underline{\mathbf{x}}$ and $\underline{\mathbf{y}}$ remains tight, and hence
a basis. In addition, $x^{\prime}_{s+1},y^{\prime}_{s+1}$ and
$x^{\prime}_{s+2},y^{\prime}_{s+2}$ are also symmetric exchanges for the
corresponding bases, therefore $\underline{\mathbf{x}}^{\prime}$ and
$\underline{\mathbf{y}}^{\prime}$ satisfy the conditions of 3.

If none of Cases 1-4 applies, then $\\{x_{i},y_{i}\\}\subseteq(H_{1}\triangle
H_{3})\cap(H_{2}\triangle H_{4})$. Therefore there exist unique indices
$k,k^{\prime}\in\\{1,3\\}$ and $\ell,\ell^{\prime}\in\\{2,4\\}$ such that
$x_{i}\in H_{k}\cap H_{\ell}$ and $y_{i}\in H_{k^{\prime}}\cap
H_{\ell^{\prime}}$. As
$(A_{1}-\\{x_{1},\dots,x_{i}\\})\cup\\{y_{1},\dots,y_{i}\\}$ is $H_{k}$-tight
and $(A_{1}-\\{x_{1},\dots,x_{i-1}\\})\cup\\{y_{1},\dots,y_{i-1}\\}$ is a
basis, it follows that $y_{i}\in H_{k}$, that is, $k=k^{\prime}$. As
$(A_{2}-\\{y_{1},\dots,y_{i}\\})\cup\\{x_{1},\dots,x_{i}\\}$ is
$H_{\ell^{\prime}}$-tight and
$(A_{2}-\\{y_{1},\dots,y_{i-1}\\})\cup\\{x_{1},\dots,x_{i-1}\\}$ is a basis,
it follows that $x_{i}\in H_{\ell^{\prime}}$, that is, $\ell=\ell^{\prime}$.
This concludes the proof of the claim. ∎

If possible, we increase the length of $\underline{\mathbf{x}}$ and
$\underline{\mathbf{y}}$ using Claim 10, and start again the whole procedure.
Hence assume that this is not the case, that is, $A^{\prime}_{1}\neq B_{1}$
and $\\{x_{i},y_{i}\\}\subseteq(H_{1}\triangle H_{3})\cap(H_{2}\triangle
H_{4})$ for each $1\leq i\leq s$. Let us denote by
$d\coloneqq|A^{\prime}_{1}-B_{1}|=|A^{\prime}_{2}-B_{2}|$.

######  Claim 11.

$|(A^{\prime}_{k}-B_{k})\cap H_{i}|=d/2$ for $k=1,2$ and $1\leq i\leq 4$.
Furthermore, $A_{1}$ and $B_{1}$ are $H_{1}$\- and $H_{3}$-tight, while
$A_{2}$ and $B_{2}$ are $H_{2}$\- and $H_{4}$-tight.

###### Proof.

We know that $A^{\prime}_{1}$ is $H_{1}$\- and $H_{3}$-tight, and
$A^{\prime}_{2}$-is $H_{2}$\- and $H_{4}$-tight. As $x_{i}$ and $y_{i}$ are
contained in the same hyperedges from $\\{H_{1},H_{2},H_{3},H_{4}\\}$ for each
$1\leq i\leq s$ by Claim 10, these immediately imply that $A_{1}$ is $H_{1}$\-
and $H_{3}$-tight, and $A_{2}$ is $H_{2}$\- and $H_{4}$-tight. As
$A^{\prime}_{1}$ is $H_{k}$-tight for $k\in\\{1,3\\}$ and $B_{1}$ is a basis,
we get that

$|A^{\prime}_{1}\cap H_{k}|=r_{k}\geq|B_{1}\cap H_{k}|=|A^{\prime}_{1}\cap
H_{k}|-|A^{\prime}_{1}\cap B_{2}\cap H_{k}|+|A^{\prime}_{2}\cap B_{1}\cap
H_{k}|,$

hence

$|A^{\prime}_{1}\cap B_{2}\cap H_{k}|\geq|A^{\prime}_{2}\cap B_{1}\cap
H_{k}|\text{ for $k\in\\{1,3\\}$}.$

Similarly, as $B_{2}$ is a basis and $A^{\prime}_{2}$ is $H_{k}$-tight for
$k\in\\{2,4\\}$, we have

$|A^{\prime}_{2}\cap B_{1}\cap H_{k}|\geq|A^{\prime}_{1}\cap B_{2}\cap
H_{k}|\text{ for $k\in\\{2,4\\}$}.$

Using these inequalities and Claim 9, it follows that

$\displaystyle|A^{\prime}_{1}\cap B_{2}\cap H_{1}|{}$
$\displaystyle{}\geq|A^{\prime}_{2}\cap B_{1}\cap H_{1}|=|A^{\prime}_{2}\cap
B_{1}\cap H_{4}|$ $\displaystyle{}\geq|A^{\prime}_{1}\cap B_{2}\cap
H_{4}|=|A^{\prime}_{1}\cap B_{2}\cap H_{3}|$
$\displaystyle{}\geq|A^{\prime}_{2}\cap B_{1}\cap H_{3}|=|A^{\prime}_{2}\cap
B_{1}\cap H_{2}|$ $\displaystyle{}\geq|A^{\prime}_{1}\cap B_{2}\cap
H_{2}|=|A^{\prime}_{1}\cap B_{2}\cap H_{1}|.$

Therefore equality holds throughout. This implies that the common size of
these sets is $d/2$, and that $B_{1}$ is $H_{1}$\- and $H_{3}$-tight, while
$B_{2}$ is $H_{2}$\- and $H_{4}$-tight. ∎

Note that $d$ can be interpreted as the number of elements that could not be
included in the strictly monotone sequence of exchanges. The next claim shows
that $d$ is not too large compared to $|A_{1}\cap B_{1}|$.

######  Claim 12.

$d\leq 2|A_{1}\cap B_{1}|$.

###### Proof.

By combining Claims 9 and 11, we get that $|A^{\prime}_{1}\cap B_{2}\cap
H_{1,2}|=|A^{\prime}_{1}\cap B_{2}\cap H_{3,4}|=d/2$, thus $|(A_{1}\cap
B_{2})-(H_{1}\cup H_{2})|\geq|(A^{\prime}_{1}\cap B_{2})-(H_{1}\cup
H_{2})|=d/2$. Using that $A_{1}$ is $H_{1}$-tight and $B_{2}$ is $H_{2}$-tight
by Claim 11, we get

$\displaystyle|H_{1}\cap H_{2}|{}$ $\displaystyle{}\leq r_{1}+r_{2}-r$
$\displaystyle{}=|A_{1}\cap H_{1}|+|B_{2}\cap H_{2}|-r$
$\displaystyle{}=|A_{1}\cap B_{1}\cap H_{1}|+|A_{1}\cap B_{2}\cap
H_{1}|+|A_{1}\cap B_{2}\cap H_{2}|+|A_{2}\cap B_{2}\cap H_{2}|-r$
$\displaystyle{}\leq|A_{1}\cap B_{1}|+|A_{1}\cap B_{2}\cap H_{1}|+|A_{1}\cap
B_{2}\cap H_{2}|+|A_{2}\cap B_{2}|-r$ $\displaystyle{}=|A_{1}\cap
B_{1}|+|A_{1}\cap B_{2}\cap H_{1}|+|A_{1}\cap B_{2}\cap H_{2}|-|A_{1}\cap
B_{2}|$ $\displaystyle{}=|A_{1}\cap B_{1}|+|(A_{1}\cap B_{2})\cap(H_{1}\cap
H_{2})|-|(A_{1}\cap B_{2})-(H_{1}\cup H_{2})|$ $\displaystyle{}\leq|A_{1}\cap
B_{1}|+|H_{1}\cap H_{2}|-d/2$

concluding the proof. ∎

As we assumed that $d>0$ holds, the claim implies $A_{1}\cap
B_{1}\neq\emptyset$, meaning that $\min\\{r,r-|A_{1}\cap
B_{1}|+1\\}=r-|A_{1}\cap B_{1}|+1$. Hence it suffices to show that the
exchange distance of $(A^{\prime}_{1},A^{\prime}_{2})$ and $(B_{1},B_{2})$ is
at most $d+1$. We will directly construct the remaining exchanges by relying
on the existence of an element in $A^{\prime}_{1}\triangle
B_{2}=A^{\prime}_{2}\triangle B_{1}$ that is contained in exactly one or three
of the hyperedges $H_{1}$, $H_{2}$, $H_{3}$ and $H_{4}$.

######  Claim 13.

$(A^{\prime}_{1}\cap B_{1})\cup(A^{\prime}_{2}\cap B_{2})\not\subseteq
H_{1}\triangle H_{3}$ and $(A^{\prime}_{1}\cap B_{1})\cup(A^{\prime}_{2}\cap
B_{2})\not\subseteq H_{2}\triangle H_{4}$.

###### Proof.

We prove $(A^{\prime}_{1}\cap B_{1})\cup(A^{\prime}_{2}\cap
B_{2})\not\subseteq H_{2}\triangle H_{4}$, the inclusion $(A^{\prime}_{1}\cap
B_{1})\cup(A^{\prime}_{2}\cap B_{2})\not\subseteq H_{1}\triangle H_{3}$ can be
proved analogously. Suppose indirectly that $(A^{\prime}_{1}\cap
B_{1})\cup(A^{\prime}_{2}\cap B_{2})\subseteq H_{2}\triangle H_{4}$. Then, by
Claim 9, we get

$\displaystyle r=|A^{\prime}_{1}|=|A^{\prime}_{1}\cap
H_{2}|+|A^{\prime}_{1}\cap H_{4}|\leq r_{2}+r_{4}=|A^{\prime}_{2}\cap
H_{2}|+|A^{\prime}_{2}\cap H_{4}|=|A^{\prime}_{2}|=r.$

That is, $A^{\prime}_{1}$ is $H_{2}$\- and $H_{4}$-tight. However,
$A^{\prime}_{1}$ is also $H_{1}$-tight but, for example, $x\in
A^{\prime}_{1}-(H_{1}\cup H_{2})$, contradicting Lemma 6(b). ∎

Recall that $A^{\prime}_{1}$ and $B_{1}$ are $H_{1}$\- and $H_{3}$-tight,
while $A^{\prime}_{2}$ and $B_{2}$ are $H_{2}$\- and $H_{4}$-tight. Hence, by
Lemma 6(b), $A^{\prime}_{1}\cap B_{1}\subseteq(H_{1}\cup H_{3})-(H_{2}\cap
H_{4})$ and $A^{\prime}_{2}\cap B_{2}\subseteq(H_{2}\cup H_{4})-(H_{1}\cap
H_{3})$. By Claim 13 and by symmetries on the roles of $A^{\prime}_{1}\cap
B_{1}$ and $A^{\prime}_{2}\cap B_{2}$, of $H_{1}$ and $H_{3}$, and of $H_{2}$
and $H_{4}$, we may assume that there exists $z\in A^{\prime}_{1}\cap B_{1}$
for which $z\in H_{1}-(H_{2}\cup H_{3}\cup H_{4})$ or $z\in(H_{1}\cap
H_{3})-H_{2}$. Let

$\displaystyle A^{\prime}_{1}\cap B_{2}\cap
H_{1,2}=\\{e_{1},\dots,e_{d/2}\\},\quad A^{\prime}_{2}\cap B_{1}\cap
H_{1,4}=\\{f_{1},\dots,f_{d/2}\\},$ $\displaystyle A^{\prime}_{1}\cap
B_{2}\cap H_{3,4}=\\{g_{1},\dots,g_{d/2}\\},\quad A^{\prime}_{2}\cap B_{1}\cap
H_{2,3}=\\{h_{1},\dots,h_{d/2}\\}.$

Assume first that $z\in H_{1}-(H_{2}\cup H_{3}\cup H_{4})$. Define

$\displaystyle A^{1}_{1}\coloneqq A^{\prime}_{1}-z+f_{1},$ $\displaystyle
A^{1}_{2}\coloneqq A^{\prime}_{2}+z-f_{1},$ $\displaystyle A^{2i}_{1}\coloneqq
A^{2i-1}_{1}-g_{i}+h_{i},$ $\displaystyle A^{2i}_{2}\coloneqq
A^{2i-1}_{2}+g_{i}-h_{i}$ for $i=1,\dots,d/2$, $\displaystyle
A^{2i+1}_{1}\coloneqq A^{2i}_{1}-e_{i}+f_{i+1},$ $\displaystyle
A^{2i+1}_{2}\coloneqq A^{2i}_{2}+e_{i}-f_{i+1}$ for $i=1,\dots,d/2-1$,
$\displaystyle A^{d+1}_{1}\coloneqq A^{d}_{1}-e_{d/2}+z=B_{1},$ $\displaystyle
A^{d+1}_{2}\coloneqq A^{\prime}_{2}+e_{d/2}-z=B_{2}.$

As $z\in H_{1}-(H_{2}\cup H_{3}\cup H_{4})$, we get that $A^{i}_{1}$ is
$H_{1}$-tight for $i=1,\dots,d+1$, $A^{2i+1}_{2}$ is $H_{2}$-tight for
$i=0,\dots,d/2$, and $A^{2i}_{2}$ is $H_{4}$-tight for $i=1,\dots,d/2$.

Now assume that $z\in(H_{1}\cap H_{3})-H_{2}$. Define

$\displaystyle A^{1}_{1}\coloneqq A^{\prime}_{1}-z+f_{1},$ $\displaystyle
A^{1}_{2}\coloneqq A^{\prime}_{2}+z-f_{1},$ $\displaystyle A^{2i}_{1}\coloneqq
A^{2i-1}_{1}-e_{i}+h_{i},$ $\displaystyle A^{2i}_{2}\coloneqq
A^{2i-1}_{2}+e_{i}-h_{i}$ for $i=1,\dots,d/2$, $\displaystyle
A^{2i+1}_{1}\coloneqq A^{2i}_{1}-g_{i}+f_{i+1},$ $\displaystyle
A^{2i+1}_{2}\coloneqq A^{2i}_{2}+g_{i}-f_{i+1}$ for $i=1,\dots,d/2-1$,
$\displaystyle A^{d+1}_{1}\coloneqq A^{d}_{1}-g_{d/2}+z=B_{1},$ $\displaystyle
A^{d+1}_{2}\coloneqq A^{\prime}_{2}+g_{d/2}-z=B_{2}.$

As $z\in(H_{1}\cap H_{3})-H_{2}$, we get that $A^{2i+1}_{1}$ is $H_{1}$-tight
for $i=0,\dots,d/2$, $A^{2i}_{1}$ is $H_{3}$-tight for $i=1,\dots,d/2$, and
$A^{i}_{2}$ is $H_{2}$-tight for $i=1,\dots,d+1$.

Thus, in both cases, we defined a sequence of $d+1$ symmetric exchanges that
transforms $(A^{\prime}_{1},A^{\prime}_{2})$ into $(B_{1},B_{2})$. This
concludes the proof of the theorem. ∎

Assuming an independence oracle access to the matroid, the proof of Theorem 7
immediately implies a polynomial-time algorithm that determines a sequence of
symmetric exchanges transforming $(A_{1},A_{2})$ into $(B_{1},B_{2})$. Indeed,
the sequences $\underline{\mathbf{x}}$ and $\underline{\mathbf{y}}$ are built
up greedily. In Claim 10, one can check if the sequences can be extended by
considering all possible pairs $x,x^{\prime}\in A^{\prime}_{1}\cap B_{2}$ and
$y,y^{\prime}\in A^{\prime}_{2}\cap B_{1}$, and trying all the modifications
discussed in Cases 1-4 of the proof of the claim. When
$\underline{\mathbf{x}}$ and $\underline{\mathbf{y}}$ cannot be extended, then
one can determine sets $X$, $Y$, $Z$ and $W$ such that
$\\{X,Y\\}=\\{A^{\prime}_{1}\cap B_{2}\cap H_{1,2},A^{\prime}_{1}\cap
B_{2}\cap H_{3,4}\\}$ and $\\{Z,W\\}=\\{A^{\prime}_{2}\cap B_{1}\cap
H_{1,4},A^{\prime}_{2}\cap B_{1}\cap H_{2,3}\\}$ using single exchanges and
the $H_{1}$\- and $H_{3}$-tightness of $A^{\prime}_{1}$ and the $H_{2}$\- and
$H_{4}$-tightness. Finally, checking for all $z\in(A^{\prime}_{1}\cap
B_{1})\cup(A^{\prime}_{2}\cap B_{2})$ if the exchanges described at the end of
the proof are feasible or not results in a desired sequence.

Now we show how to verify Conjectures 1-3 for split matroids using Theorem 7.
The proofs are immediate from the statement of the theorem.

######  Corollary 14.

Conjecture 1 holds for split matroids.

###### Proof.

Consider the ordered basis pairs $(A,B)$ and $(B,A)$; these pairs are clearly
compatible. Note that $|A-B|=|A|=r$ is a lower bound for the minimum length of
a sequence of symmetric exchanges that transforms $(A,B)$ into $(B,A)$. By
Theorem 7, there exists such a sequence with length exactly
$\min\\{r,|A-B|+1\\}=r$. By defining the pairs $a_{i},b_{i}$ to be the
symmetric exchanges of this sequence, the theorem follows. ∎

######  Corollary 15.

Conjecture 2 holds for basis sequences of length two in split matroids.

###### Proof.

Theorem 7 implies that if $(A_{1},A_{2})$ and $(B_{1},B_{2})$ are compatible
basis sequences, then the latter can be obtained from the former by a sequence
of symmetric exchanges, thus the corollary follows. ∎

As both Corollary 14 and Corollary 15 implies the equitability of split
matroids, we also get the following.

######  Corollary 16.

Conjecture 3 holds for split matroids.

##  4 Maximum length strictly monotone exchange sequences

The essence of Theorem 7 is that in split matroids we can transform a basis
pair $(A_{1},A_{2})$ into another $(B_{1},B_{2})$ by using at most one more
symmetric exchanges than the obvious lower bound $r-|A_{1}\cap B_{1}|$.
However, one might be interested in finding a longest strictly monotone
exchange sequence for the basis pairs. It turns out that the sequence
determined in the first half of the algorithm is longest possible.

######  Theorem 17.

Let $(A_{1},A_{2})$ and $(B_{1},B_{2})$ be compatible basis pairs of a
rank-$r$ split matroid $M$. Then a longest strictly monotone sequence of
symmetric exchanges for $(A_{1},A_{2})$ and $(B_{1},B_{2})$ can be determined
using a polynomial number of oracle calls.

###### Proof.

We follow the proof and notations of Theorem 7. Similarly to the proof there,
we may assume that $M$ is connected and $A_{1}\cap A_{2}=\emptyset$. We show
that if the length of $\underline{\mathbf{x}}$ and $\underline{\mathbf{y}}$
cannot be increased as in Claim 10, then they correspond to a longest strictly
monotone sequence of symmetric exchanges. Let
$\underline{\mathbf{x}}^{\prime\prime}=(x^{\prime\prime}_{1},\dots,x^{\prime\prime}_{t})$
and
$\underline{\mathbf{y}}^{\prime\prime}=(y^{\prime\prime}_{1},\dots,y^{\prime\prime}_{t})$
be arbitrary sequences corresponding to a strictly monotone sequence of
symmetric exchanges for $(A_{1},A_{2})$ and $(B_{1},B_{2})$. Our goal is to
show that the length of $\underline{\mathbf{x}}^{\prime\prime}$ is at most the
length of $\underline{\mathbf{x}}$.

We claim that $x^{\prime\prime}_{i}$ and $y^{\prime\prime}_{i}$ are contained
in the same hyperedges from $\\{H_{1},H_{2},H_{3},H_{4}\\}$ for each $1\leq
i\leq t$. Indeed, assume that this holds for each pair
$x^{\prime\prime}_{j},y^{\prime\prime}_{j}$ with $1\leq j\leq i-1$. Then
$(A_{1}-\\{x^{\prime\prime}_{1},\dots,x^{\prime\prime}_{i-1}\\})\cup\\{y^{\prime\prime}_{1},\dots,y^{\prime\prime}_{i-1}\\}$
is $H_{1}$\- and $H_{3}$-tight and
$(A_{2}-\\{y^{\prime\prime}_{1},\dots,y^{\prime\prime}_{i-1}\\})\cup\\{x^{\prime\prime}_{1},\dots,x^{\prime\prime}_{i-1}\\}$
is $H_{2}$\- and $H_{4}$-tight, since $A_{1}$ is $H_{1}$\- and $H_{3}$-tight
and $A_{2}$ is $H_{2}$ and $H_{4}$-tight by Claim 11. As $(A_{1}\cap
B_{2})\cup(A_{2}\cap B_{1})\subseteq(H_{1}\triangle H_{3})\cap(H_{2}\triangle
H_{4})$ by Claims 9 and 10, $x^{\prime\prime}_{i}\in H_{k,\ell}$ and
$y^{\prime\prime}_{i}\in H_{k^{\prime},\ell^{\prime}}$ holds for some
$k,k^{\prime}\in\\{1,3\\}$ and $\ell,\ell^{\prime}\in\\{2,4\\}$. The facts
that
$(A_{1}-\\{x^{\prime\prime}_{1},\dots,x^{\prime\prime}_{i}\\})\cup\\{y^{\prime\prime}_{1},\dots,y^{\prime\prime}_{i}\\}$
is a basis,
$(A_{1}-\\{x^{\prime\prime}_{1},\dots,x^{\prime\prime}_{i-1}\\})\cup\\{y^{\prime\prime}_{1},\dots,y^{\prime\prime}_{i-1}\\}$
is $H_{k^{\prime}}$-tight, and $y^{\prime\prime}_{i}\in H_{k^{\prime}}$,
together imply that $x^{\prime\prime}_{i}\in H_{k^{\prime}}$, that is,
$k=k^{\prime}$. Similarly, it follows from
$(A_{2}-\\{y^{\prime\prime}_{1},\dots,y^{\prime\prime}_{i}\\})\cup\\{x^{\prime\prime}_{1},\dots,x^{\prime\prime}_{i}\\}$
being a basis that $\ell=\ell^{\prime}$. Therefore $x^{\prime\prime}_{i}$ and
$y^{\prime\prime}_{i}$ are indeed contained in the same hyperedges from
$\\{H_{1},H_{2},H_{3},H_{4}\\}$ as claimed.

By the above,
$|\\{x^{\prime\prime}_{1},\dots,x^{\prime\prime}_{t}\\}\cap(H_{1,4}\cup
H_{2,3})|=|\\{y^{\prime\prime}_{1},\dots,y^{\prime\prime}_{t}\\}\cap(H_{1,4}\cup
H_{2,3})|$. Since $|(A_{2}\cap B_{1})\cap(H_{1,4}\cup H_{2,3})|=|(A_{1}\cap
B_{2})\cap(H_{1,4}\cup H_{2,3})|+d$ holds by Claims 9 and 10, it follows that
$|(A_{2}\cap B_{1})-\\{x^{\prime\prime}_{1},\dots,x^{\prime\prime}_{t}\\}|\geq
d$, thus the length of $\underline{\mathbf{x}}^{\prime\prime}$ is at most the
length of $\underline{\mathbf{x}}$, concluding the proof of the theorem. ∎

A matroid $M$ with basis-family $\mathcal{B}$ is base orderable if for any two
bases $A,B\in\mathcal{B}$ there exists a bijection $\varphi\colon A\to B$ such
that $A-e+\varphi(e)\in\mathcal{B}$ and $B-\varphi(e)+e\in\mathcal{B}$ for
every $e\in A$. Base orderable matroids are interesting and important because
we have a fairly good global understanding of their structure, while
frustratingly little is known about the general case.

The proof of Theorem 7 implies that there exists a ‘long’ strictly monotone
sequence of symmetric exchanges in split matroids.

######  Theorem 18.

Let $(A_{1},A_{2})$ and $(B_{1},B_{2})$ be compatible basis pairs of a
rank-$r$ matroid $M$. Then there exists a strictly monotone symmetric exchange
sequence of length

  1. (a)

$r-3|A_{1}\cap B_{1}|$, if $M$ is a split matroid,

  2. (b)

$r-2|A_{1}\cap B_{1}|$, if $M$ is a base orderable split matroid,

  3. (c)

$r-|A_{1}\cap B_{1}|-2$, if $M$ is a paving matroid.

###### Proof.

We follow the proof and notations of Theorem 7. Similarly to the proof there,
we may assume that $M$ is connected and $A_{1}\cap A_{2}=\emptyset$.
Furthermore, assume that there is no (strictly monotone) symmetric exchange
sequence of length $r-|A_{1}\cap B_{1}|$ for $(A_{1},A_{2})$ and
$(B_{1},B_{2})$ as otherwise we are done. Then $\underline{\mathbf{x}}$ and
$\underline{\mathbf{y}}$ define a strictly monotone symmetric exchange
sequence of length $r-|A_{1}\cap B_{1}|-d$, hence (a) follows by the
inequality $d\leq 2|A_{1}\cap B_{1}|$ of Claim 12.

If $M$ is base orderable, then let $\varphi\colon A^{\prime}_{1}\to A_{2}$ be
a bijection such that $A^{\prime}_{1}-e+\varphi(e)$ and $A_{2}+e-\varphi(e)$
are bases for each $e\in A^{\prime}_{1}$. It follows from the definition of
$\varphi$ that it is identical on $A^{\prime}_{1}\cap
A_{2}=\\{y_{1},\dots,y_{s}\\}$. Note that $A^{\prime}_{1}-A_{2}=(A_{1}\cap
B_{1})\cup(A^{\prime}_{1}\cap B_{2})$ and $A_{2}-A^{\prime}_{1}=(A_{2}\cap
B_{2})\cup(A^{\prime}_{2}\cap B_{1})$ where $A^{\prime}_{1}\cap B_{2}\subseteq
H_{1,2}\cup H_{3,4}$ and $A^{\prime}_{2}\cap B_{1}\subseteq H_{1,4}\cup
H_{2,3}$ by Claim 9. For each $e\in A^{\prime}_{1}\cap H_{1,2}$, we have
$f(e)\in H_{2}-H_{3}$ since $A^{\prime}_{1}$ is $H_{3}$-tight and $A_{2}$ is
$H_{2}$-tight by Claim 11. Similarly, for each $e\in A^{\prime}_{1}\cap
H_{3,4}$, we have $f(e)\in H_{4}-H_{1}$. It follows that $f(e)\in A_{2}\cap
B_{2}$ for each $e\in A^{\prime}_{1}\cap B_{2}$, thus $d=|A^{\prime}_{1}\cap
B_{2}|\leq|A_{2}\cap B_{2}|=|A_{1}\cap B_{1}|$, proving (b).

If $M$ is paving, then the $H_{3}$-tightness of $A^{\prime}_{1}$ implies
$|A^{\prime}_{1}\cap H_{3}|=r-1$. By Claims 9 and 11, we get
$d/2=|(A^{\prime}_{1}\cap B_{2})\cap H_{1,2}|\leq|A^{\prime}_{1}-H_{3}|=1$,
proving (c). ∎

##  5 Conclusion

In this paper, we studied the exchange distance of basis pairs in split
matroids. We proved that for any two compatible basis pairs, there exists a
sequence of symmetric exchanges that transforms one into the other, and that
the length of this sequence is at most one more than the trivial lower bound.
The proof was algorithmic, hence the sequence of exchange in question can be
determined in polynomial time. As a corollary, we verified several long-
standing conjectures for the class of split matroids, and also provided lower
bounds on the maximum length of strictly monotone symmetric exchange
sequences.

A lesser known conjecture of Hamidoune states that the exchange distance of
compatible basis pairs is at most the rank of the matroid, see [7]. However,
until now, the conjecture was open even for sparse paving matroids. The
statement might seem rather optimistic at first glance, still, our result
settles it for split matroids. It remains an intriguing open question whether
the conjecture holds in general; such a result would immediately imply
Conjecture 1, Conjecture 2 for sequences of length two and Conjecture 3.

## Acknowledgement

The work was supported by the Lendület Programme of the Hungarian Academy of
Sciences – grant number LP2021-1/2021 and by the Hungarian National Research,
Development and Innovation Office – NKFIH, grant numbers FK128673 and
TKP2020-NKA-06.

## References

  * [1] Equitability of matroids.  http://lemon.cs.elte.hu/egres/open/Equitability_of_matroids.  Accessed: 2021-01-28.
  * [2] R. Aharoni, E. Berger, D. Kotlar, and R. Ziv.  Fair representation in the intersection of two matroids.  The Electronic Journal of Combinatorics, 24(4):P4.10, 2017.
  * [3] K. Bérczi, T. Király, T. Schwarcz, Y. Yamaguchi, and Y. Yokoi.  Hypergraph characterization of split matroids.  arXiv preprint arXiv:2202.04371, 2022.
  * [4] J. Blasiak.  The toric ideal of a graphic matroid is generated by quadrics.  Combinatorica, 28(3):283–297, 2008.
  * [5] J. E. Bonin.  Basis-exchange properties of sparse paving matroids.  Advances in Applied Mathematics, 50(1):6–15, 2013.
  * [6] A. Cameron and D. Mayhew.  Excluded minors for the class of split matroids.  Australasian Journal of Combinatorics, 79(2):195–204, 2021.
  * [7] R. Cordovil and M. L. Moreira.  Bases-cobases graphs and polytopes of matroids.  Combinatorica, 13(2):157–165, 1993.
  * [8] M. Farber.  Basis pair graphs of transversal matroids are connected.  Discrete mathematics, 73(3):245–248, 1989.
  * [9] M. Farber, B. Richter, and H. Shank.  Edge-disjoint spanning trees: A connectedness theorem.  Journal of Graph Theory, 9(3):319–324, 1985.
  * [10] Z. Fekete and J. Szabó.  Equitable partitions to spanning trees in a graph.  The Electronic Journal of Combinatorics, 18(1), 2011.
  * [11] A. Frank.  Connections in Combinatorial Optimization, volume 38 of Oxford Lecture Series in Mathematics and its Applications.  Oxford University Press, Oxford, 2011.
  * [12] H. Gabow.  Decomposing symmetric exchanges in matroid bases.  Mathematical Programming, 10(1):271–276, 1976.
  * [13] C. Greene and T. L. Magnanti.  Some abstract pivot algorithms.  SIAM Journal on Applied Mathematics, 29(3):530–539, 1975.
  * [14] J. Hartmanis.  Lattice theory of generalized partitions.  Canadian Journal of Mathematics, 11:97–106, 1959.
  * [15] M. Joswig and B. Schröter.  Matroids from hypersimplex splits.  Journal of Combinatorial Theory, Series A, 151:254–284, 2017.
  * [16] Y. Kajitani, S. Ueno, and H. Miyano.  Ordering of the elements of a matroid such that its consecutive w elements are independent.  Discrete Mathematics, 72(1-3):187–194, 1988.
  * [17] K. Kashiwabara.  The toric ideal of a matroid of rank 3 is generated by quadrics.  The Electronic Journal of Combinatorics, 17(1):R28, 2010.
  * [18] D. Kotlar.  On circuits and serial symmetric basis-exchange in matroids.  SIAM Journal on Discrete Mathematics, 27(3):1274–1286, 2013.
  * [19] D. Kotlar, E. Roda, and R. Ziv.  On sequential basis exchange in matroids.  SIAM Journal on Discrete Mathematics, 35(4):2517–2519, 2021.
  * [20] D. Kotlar and R. Ziv.  On serial symmetric exchanges of matroid bases.  Journal of Graph Theory, 73(3):296–304, 2013.
  * [21] M. Lasoń and M. Michałek.  On the toric ideal of a matroid.  Advances in Mathematics, 259:1–12, 2014.
  * [22] S. McGuinness.  Frame matroids, toric ideals, and a conjecture of White.  Advances in Applied Mathematics, 118:102042, 2020.
  * [23] J. Oxley.  Matroid Theory, volume 21 of Oxford Graduate Texts in Mathematics.  Oxford University Press, Oxford, second edition, 2011.
  * [24] J. Schweig.  Toric ideals of lattice path matroids and polymatroids.  Journal of Pure and Applied Algebra, 215(11):2660–2665, 2011.
  * [25] J. van den Heuvel and S. Thomassé.  Cyclic orderings and cyclic arboricity of matroids.  Journal of Combinatorial Theory, Series B, 102(3):638–646, 2012\.
  * [26] D. J. A. Welsh.  Matroid Theory.  Academic Press, London, 1976.
  * [27] N. L. White.  A unique exchange property for bases.  Linear Algebra and its Applications, 31:81–91, 1980.
  * [28] D. Wiedemann.  Cyclic base orders of matroids.  Manuscript, 1984.