# Weighted exchange distance of basis pairs

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><EMAIL_ADDRESS><EMAIL_ADDRESS>Bence
Mátravölgyi11footnotemark: 1 Tamás Schwarcz11footnotemark: 1

###### Abstract

Two pairs of disjoint bases $\mathbf{P}_{1}=(R_{1},B_{1})$ and
$\mathbf{P}_{2}=(R_{2},B_{2})$ of a matroid $M$ are called _equivalent_ if
$\mathbf{P}_{1}$ can be transformed into $\mathbf{P}_{2}$ by a series of
symmetric exchanges. In 1980, White conjectured that such a sequence always
exists whenever $R_{1}\cup B_{1}=R_{2}\cup B_{2}$. A strengthening of the
conjecture was proposed by Hamidoune, stating that minimum length of an
exchange is at most the rank of the matroid.

We propose a weighted variant of Hamidoune’s conjecture, where the weight of
an exchange depends on the weights of the exchanged elements. We prove the
conjecture for several matroid classes: strongly base orderable matroids,
split matroids, graphic matroids of wheels, and spikes.

Keywords: Graphic matroid, Sequential symmetric basis exchange, Spike, Split
matroid, Strongly base orderable matroid, Wheel graph

##  1 Introduction

Given a matroid $M$ over a ground set $S$, the exchange axiom implies that for
any pair of bases $R$ and $B$ there exists a sequence of exchanges that
transforms $R$ into $B$, and the shortest length of such a sequence is
$|R-B|$. In the light of this, it is natural to ask whether analogous results
hold for basis pairs instead of single basis. More precisely, let $(R,B)$ be
an ordered pair of disjoint bases of $M$, and let $e\in R\setminus B$ and
$f\in B\setminus R$ be such that both $R^{\prime}\coloneqq R-e+f$ and
$B^{\prime}\coloneqq B+e-f$ are bases. In such a case, we call the exchange
feasible and say that the pair $(R^{\prime},B^{\prime})$ is obtained from
$(R,B)$ by a symmetric exchange. Using this terminology, we define the
exchange distance (or distance for short) of two pairs of disjoint bases
$\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ to be the
minimum number of symmetric exchanges needed to transform the former into the
latter if such a sequence exists and $+\infty$ otherwise. We call two pairs of
disjoint bases equivalent if their exchange distance is finite. A sequence of
symmetric exchanges starting from a pair $\mathbf{P}_{1}$ is called strictly
monotone with respect to another pair $\mathbf{P}_{2}$ (or strictly monotone
for short when $\mathbf{P}_{2}$ is clear from the context) if each step
decreases the difference between the first member of the current pair and that
of $\mathbf{P}_{2}$. In other words, a strictly monotone exchange sequence
uses elements only from $(R_{1}\cap B_{2})\cup(R_{2}\cap B_{1})$ and at most
once.

At this point it is not clear (I) when the distance of two pairs will be
finite, and (II) if their distance is finite, whether we can give an upper
bound on it. Regarding question (I), one can formulate an obvious necessary
condition for the distance of $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$ to be
finite, namely $R_{1}\cup B_{1}=R_{2}\cup B_{2}$ should certainly hold – two
pairs with this property are called compatible. In [19], White conjectured
that _two basis pairs $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$ are equivalent if
and only if they are compatible_. While the conjecture was verified for
various matroid classes, it remains open in general.

Much less is known about question (II), that is, the optimization version of
the problem. Gabow [10] studied sequential symmetric exchanges and posed the
following problem, which was later stated as a conjecture by Wiedemann [20]
and by Cordovil and Moreira [6]: _for any two disjoint bases $R$ and $B$ of a
matroid $M$, there is a sequence of $r$ symmetric exchanges that transforms
the pair $\mathbf{P}_{1}=(R,B)$ into $\mathbf{P}_{2}=(B,R)$_. The rank of the
matroid is a trivial lower bound on the minimum number of exchanges needed to
transform a pair $(R,B)$ into $(B,R)$, and the essence of Gabow’s conjecture
is that that many steps might always suffice. The relation between the
conjectures of White and Gabow is immediate: the latter would imply the former
for sequences of the form $(R,B)$ and $(B,R)$.

In general, if $M$ has rank $r$, then $r-|R_{1}\cap R_{2}|$ is an obvious
lower bound on the exchange distance of $\mathbf{P}_{1}=(R_{1},B_{1})$ and
$\mathbf{P}_{2}=(R_{2},B_{2})$. However, it might happen that more symmetric
exchanges are needed even if $M$ is a graphic matroid; see [8] or Figure 5 for
a counterexample. As a common generalization of the conjectures of White and
Gabow, Hamidoune [6] proposed a rather optimistic variant stating that _the
exchange distance of compatible basis pairs is at most the rank of the
matroid_.

Let $w\colon S\to\mathbb{R}_{+}$ be a weight function on the elements of the
ground set $S$. Given a pair $(R,B)$ of disjoint bases, we define the weight
of a symmetric exchange $R^{\prime}\coloneqq R-e+f$ and $B^{\prime}\coloneqq
B+e-f$ to be $w(e)+w(f)$, that is, the sum of the weights of the exchanged
elements. Analogously to the unweighted setting, we define the weighted
exchange distance (or weighted distance for short) of two pairs of disjoint
bases $\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ to be
the minimum total weight of symmetric exchanges needed to transform the former
into the latter if such a sequence exists and $+\infty$ otherwise. As a
weighted extension of Hamidoune’s conjecture, we propose the following.

######  Conjecture 1.

Let $\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ be
compatible basis pairs of a matroid $M$ over a ground set $S$, and let
$w\colon S\to\mathbb{R}_{+}$ be a weight function. Then the weighted exchange
distance of $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$ is at most $w(R_{1}\cup
B_{1})=w(R_{2}\cup B_{2})$.

By setting the weight function to be identically one, we get back Hamidoune’s
conjecture. It is worth mentioning that a strictly monotone exchange sequence
transforming $\mathbf{P}_{1}$ into $\mathbf{P}_{2}$ is optimal in every sense,
i.e., it has both minimum length and minimum weight.

#### Previous work.

By relying on the constructive characterization of bispanning graphs, Farber,
Richter, and Shank [9] proved White’s conjecture for graphic and cographic
matroids, while Farber [8] settled the statement for transversal matroids.
Bonin [5] verified the conjecture for sparse paving matroids. The case of
strongly base orderable matroids was solved by Lasoń and Michałek [15].
McGuinness [17] extended the graphic case to frame matroids satisfying a
certain linearity condition. Kotlar and Ziv [14] 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 [13] 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$.

Gabow’s conjecture was verified for partition matroids, matching and
transversal matroids, and matroids of rank less than $4$ in [10], and an easy
reasoning shows that it also holds for strongly base orderable matroids as
well. The graphic case was settled by Wiedemann [20], Kajitani, Ueno, and
Miyano [12], and Cordovil and Moreira [6].

Recently, Bérczi and Schwarcz [3] showed that Hamidoune’s conjecture hold for
split matroids, a large class that contains paving matroids as well. While
studying a specific maker-breaker game on bispanning graphs, Andres,
Hochstättler and Merkel [1] showed that there is an exchange sequence between
any two pairs of disjoint spanning trees of a wheel of rank at least four
using only so-called left unique exchanges. They also asked whether the
exchange distance of compatible basis pairs of a matroid can be bounded by a
polynomial of the rank – this latter problem is a weakening of Hamidoune’s
conjecture.

The rank of the graphic matroid of a connected graph on $n$ vertices is $n-1$.
Though it is not stated explicitly, the algorithms of [9] and [4] that prove
White’s conjecture for graphic matroids give a sequence of exchanges of length
at most $O(n^{2})$. It remains an intriguing open problem to improve the bound
to $O(n)$, matching the order of the bound in the conjecture.

#### Our results.

We verify Conjecture 1 for various matroid classes. First we consider strongly
base orderable matroids, a class with distinctive structural properties.

For the remaining matroid classes, we work with a further strengthening of the
conjecture where both the length and the weight of the exchange sequence are
ought to be bounded. We verify this stronger variant for split matroids, a
class that was introduced only recently and generalizes paving matroids.

Our main result is a proof of the conjecture for graphic matroids of wheels.
Though wheels are structurally rather simple, the proof for this graph class
is already non-trivial and requires a thorough understanding of feasible
exchanges. As a byproduct, we show that the minimum number of steps required
to transform $\mathbf{P}_{1}$ into $\mathbf{P}_{2}$ can be arbitrarily large
compared to the lower bound $r-|R_{1}\cap R_{2}|$.

Finally, we prove the conjecture for spikes, an important class of 3-connected
matroids. Spikes are interesting because, as we show, one can define an
arbitrarily large number of basis pairs without a strictly monotone exchange
sequence between any two of them. This is in sharp contrast to the case of
wheels, where for any three pairs of bases, there exist two with a strictly
monotone exchange sequence between them.

The rest of the paper is organized as follows. Basic notions and definitions
are given in Section 2, together with some elementary observations on wheels.
We verify Conjecture 1 for strongly base orderable matroids and for split
matroids in Section 3. Graphic matroids of wheels are considered in Section 4,
while spikes are discussed in Section 5. We close the paper with further
observations in Section 6.

##  2 Preliminaries

#### General notation.

The set of nonnegative real numbers is denoted by $\mathbb{R}_{+}$. For
subsets $X,Y\subseteq S$, their symmetric difference is defined as $X\triangle
Y\coloneqq(X\setminus Y)\cup(Y\setminus X)$. When $Y$ consist of a single
element $y$, then $X\setminus\\{y\\}$ and $X\cup\\{y\\}$ are abbreviated as
$X-y$ and $X+y$, respectively. Given a weight function $w\colon
S\to\mathbb{R}_{+}$ and a subset $X\subseteq S$, we use the notation
$w(X)=\sum_{s\in X}w(s)$.

#### Matroids.

For basic definitions on matroids, we refer the reader to [18]. If $M$ is a
rank-$r$ matroid over a ground set $S$ of size $2r$ such that $S$ decomposes
into two disjoint bases $R$ and $B$ of $M$, then such a decomposition is
called a coloring of $M$111Throughout the paper, we will refer to the elements
of $R$ and $B$ as ‘red’ and ‘blue’, respectively.. A feasible exchange of
elements $r\in R$ and $b\in B$ is denoted by $(r,b)$. We extend this notation
to a sequence of symmetric exchanges as well by writing
$(r_{1},b_{1}),\dots,(r_{k},b_{k})$, meaning that
$(R\setminus\\{r_{1},\dots,r_{i}\\})\cup\\{b_{1},\dots,b_{i}\\}$ and
$(B\cup\\{r_{1},\dots,r_{i}\\})\setminus\\{b_{1},\dots,b_{i}\\}$ are bases for
$i=1,\dots,k$. A matroid $M$ is strongly base orderable if or any two bases
$B_{1},B_{2}$, there exists a bijection $\phi\colon B_{1}\to B_{2}$ such that
$(B_{1}\setminus X)\cup\phi(X)$ is also a basis for any $X\subseteq B_{1}$,
where we denote $\phi(X)\coloneqq\\{\phi(e)\mid e\in X\\}$.

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 nonnegative integers satisfying
$|H_{i}\cap H_{j}|\leq r_{i}+r_{j}-r$ for $1\leq i<j\leq q$, and $|S\setminus
H_{i}|+r_{i}\geq r$ 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$ that we call an
elementary split matroid; see [2] for details. A set $F\subseteq S$ is called
$H_{i}$-tight if $|F\cap H_{i}|=r_{i}$. A split matroid is the direct sum of a
single elementary split matroid and some (maybe zero) uniform matroids.

For a graph $G=(V,E)$ on $n$ vertices, the graphic matroid $M=(E,\mathcal{I})$
of $G$ is defined on the edge set by considering a subset $F\subseteq E$ to be
independent if it is a forest, that is, $\mathcal{I}=\\{F\subseteq E\mid F\
\text{does not contain a cycle}\\}$. If the graph is connected, then the bases
of the graphic matroid are exactly the spanning trees of $G$ and the rank of
the matroid is $n-1$.

Let $S=\\{t,x_{1},y_{1},\dots,x_{r},y_{r}\\}$ be a ground set of size $2r+1$
for some $r\geq 3$, and let $\mathcal{C}_{1}=\\{\\{t,x_{i},y_{i}\\}\mid 1\leq
i\leq r\\}$ and $\mathcal{C}_{2}=\\{\\{x_{i},y_{i},x_{j},y_{j}\\}\mid 1\leq
i<j\leq r\\}$. Furthermore, let $\mathcal{C}_{3}\subseteq\\{Z\subseteq
S\mid|Z|=r,\ |Z\cap\\{x_{i},y_{i}\\}|=1\ \text{for $1\leq i\leq r$}\\}$; note
that $\mathcal{C}_{3}$ might be empty. Finally, define
$\mathcal{C}_{4}=\\{C\subseteq S\mid|C|=r+1,\ C^{\prime}\not\subseteq C\
\text{for
$C^{\prime}\in\mathcal{C}_{1}\cup\mathcal{C}_{2}\cup\mathcal{C}_{3}$}\\}$.
Then the family
$\mathcal{C}=\mathcal{C}_{1}\cup\mathcal{C}_{2}\cup\mathcal{C}_{3}\cup\mathcal{C}_{4}$
satisfies the circuit axioms, hence $M=(S,\mathcal{C})$ is a rank-$r$ matroid
with circuit family $\mathcal{C}$. Matroids arising this way are called
spikes, where $t$ and the pairs $\\{x_{i},y_{i}\\}$ are called the tip and the
legs of the spike, respectively. It is not difficult to check that by
restricting $M$ to any $2r$ of its elements (or in other words, deleting any
of its elements) results in a matroid whose ground set decomposes into two
disjoint bases.

#### Wheels.

A graph $G=(V,E)$ is called a wheel graph (or wheel for short) if it is
obtained by connecting a vertex, called the center of the wheel, to all the
vertices of a cycle of length at least three, called the outer cycle of the
wheel. In particular, wheels have at least four vertices. Edges connecting the
center vertex with the vertices of the outer cycle are called spokes, while
the edges of the outer cycle are called rim edges. Wheels are clearly planar,
and so the order of the vertices on the outer cycle implies a natural cyclic
ordering of the spokes and the rim edges as well.

It is not difficult to check that any wheel is the disjoint union of two
spanning trees. Therefore, a coloring of the graphic matroid of a wheel is
basically a partition of its edge set into two colors $R$ and $B$ such that
both color classes form a spanning tree. A nice property of wheels is that we
have a fairly good understanding of the structure of their colorings. Indeed,
in order to decompose a wheel into two spanning trees, we first need to split
the spokes into two nonempty sets. Then, if a rim edge goes between the
endpoints of two spokes having the same color, then it automatically has to be
colored with the other color to obtain a basis. Hence it only remains to
decide the color of the rim edges going between the endpoints of spokes having
different colors. However, once we fix the color of any of those edges, it
determines the color of all the remaining ones.

We call a maximal set of consecutive spokes of the same color an interval. By
the length and color of the interval we mean the number and color of the
spokes in it, respectively. Rim edges going between two intervals are called
boundary edges. By the above, for $X\in\\{R,B\\}$, either every interval of
color $X$ is followed by a boundary edge of color $X$ in a counterclockwise
direction, or every interval of color $X$ is followed by a boundary edge of
color $X$ in a clockwise direction. This property is referred to as the
orientation of the coloring, and the orientation is called positive in the
former and negative in the latter case; see Figure 1(a) for an example.
Orientations will play a crucial role in whether one can go from one coloring
to another using a small number of exchanges or not.

(a) The red and blue intervals are denoted by $I_{1},I_{3}$ and $I_{2},I_{4}$,
respectively.

(b) The coloring obtained by symmetrically exchanging $e$ and its pair
$\varphi_{\mathbf{P},-}(e)$.

Figure 1: Colorings containing four intervals. Thick rim edges correspond to
boundary edges. Note that both colorings have positive orientation.

Given a coloring $\mathbf{P}=(R,B)$ of the wheel graph, each spoke $e$ is
incident to two rim edges. The rim edge sharing a vertex with $e$ in the
direction opposite of the orientation of the coloring can always be exchanged
with $e$. We denote this rim edge by $\varphi_{\mathbf{P},-}(e)$, while the
other rim edge incident to $e$ is denoted by $\varphi_{\mathbf{P},+}(e)$; see
Figure 1(b) for an example. Both $\varphi_{\mathbf{P},-}$ and
$\varphi_{\mathbf{P},+}$ provide bijections between spokes and rim edges. Note
that these bijections are already determined by the orientation of
$\mathbf{P}$. If there are at least four intervals in the coloring, then the
feasible exchanges are exactly the ones exchanging $e$ and
$\varphi_{\mathbf{P},-}(e)$ for some spoke $e$. When there are only two
intervals in the coloring, then there are other pairs that can be
symmetrically exchanged.

##  3 Strongly base orderable and split matroids

As a warm-up, we first consider two basic cases: strongly base orderable and
split matroids. For strongly base orderable matroids, the proof of Conjecture
1 can be read out directly from the proof of White’s conjecture in [15] for
strongly base orderable matroids. However, it might help the reader to get
familiar with the notion of basis exchanges, and also sheds light to the
difficulties caused by the presence of a weight function. For split matroids,
the proof is more involved and relies heavily on that of Hamidoune’s
conjecture appeared in [3].

###  3.1 Strongly base orderable matroids

######  Theorem 1.

Let $\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ be
compatible pairs of disjoint bases of a rank-$r$ strongly base orderable
matroid $M$ over a ground set $S$, and let $w\colon S\to\mathbb{R}_{+}$ be a
weight function. Then there exists a sequence of exchanges of total weight at
most $w(R_{1}\cup B_{1})=w(R_{2}\cup B_{2})$ that transforms $\mathbf{P}_{1}$
into $\mathbf{P}_{2}$ and uses each element at most twice.

###### Proof.

Let $\phi_{1}\colon R_{1}\to B_{1}$ and $\phi_{2}\colon R_{2}\to B_{2}$ be
bijections such that $(R_{i}\setminus X)\cup\phi_{i}(X)$ is a basis for each
$X\subseteq R_{i}$ and $i=1,2$. Consider the bipartite graph $G$ with vertex
set $R_{1}\cup B_{1}=R_{2}\cup B_{2}$, and edges of the form $e\phi_{1}(e)$
for $e\in R_{1}$ and $f\phi_{2}(f)$ for $f\in R_{2}$. We denote the color
classes of $G$ by $S$ and $T$. Note that

$S=(S\cap R_{1})\cup(S\cap B_{1})=(R_{1}\setminus(R_{1}\setminus
S))\cup\phi_{1}(R_{1}\setminus S)$

and

$T=(T\cap R_{1})\cup(T\cap B_{1})=(R_{1}\setminus(R_{1}\setminus
T))\cup\phi_{1}(R_{1}\setminus T),$

hence both $S$ and $T$ are bases of $M$. Let us define the basis pairs
$\mathbf{P}=(S,T)$ and $\mathbf{P}^{\prime}=(T,S)$.

By exchanging the elements between $R_{1}\setminus S$ and $S\setminus R_{1}$
according to $\phi_{1}$, we get a sequence of weight $w(R_{1}\triangle S)$
that transforms $\mathbf{P}_{1}$ into $\mathbf{P}$. By exchanging the elements
between $S\setminus R_{2}$ and $R_{2}\setminus S$ according to $\phi_{2}$, we
get a sequence of weight $w(R_{2}\triangle S)$ that transforms $\mathbf{P}$
into $\mathbf{P}_{2}$. The concatenation of these two sequences transforms
$\mathbf{P}_{1}$ into $\mathbf{P}_{2}$, has total weight $w(R_{1}\triangle
S)+w(R_{2}\triangle S)$, and uses each element at most twice.

By exchanging the elements between $R_{1}\setminus T$ and $T\setminus R_{1}$
according to $\phi_{1}$, we get a sequence of weight $w(R_{1}\triangle T)$
that transforms $\mathbf{P}_{1}$ into $\mathbf{P}^{\prime}$. By exchanging the
elements between $T\setminus R_{2}$ and $R_{2}\setminus T$ according to
$\phi_{2}$, we get a sequence of weight $w(R_{2}\triangle T)$ that transforms
$\mathbf{P}$ into $\mathbf{P}_{2}$. The concatenation of these two sequences
transforms $\mathbf{P}_{1}$ into $\mathbf{P}_{2}$, has total weight
$w(R_{1}\triangle T)+w(R_{2}\triangle T)$, and uses each element at most
twice.

Since

$\displaystyle w(R_{1}\triangle S)+w(R_{2}\triangle S)+w(R_{1}\triangle
T)+w(R_{2}\triangle T)$ $\displaystyle{}={}$ $\displaystyle(w(R_{1}\triangle
S)+w(R_{1}\triangle T))+(w(R_{2}\triangle S)+w(R_{2}\triangle T))$
$\displaystyle{}={}$ $\displaystyle(w(R_{1})+w(B_{1}))+(w(R_{2})+w(B_{2})),$

at least one of the above defined sequences has total weight at most
$w(R_{1}\cup B_{1})=w(R_{2}\cup B_{2})$ and uses each element at most twice.
This concludes the proof of the theorem. ∎

###  3.2 Split matroids

The introduction of split matroids was motivated by the study of matroid
polytopes from a geometry point of view [11]. Besides their immediate
applications in tropical geometry, split matroids generalize paving matroids,
a class that plays a fundamental role among matroids. Crapo and Rota [7] and
Mayhew, Newman, Welsh and Whittle [16] conjectured that the asymptotic
fraction of matroids on $n$ elements that are paving tends to $1$ as $n$ tends
to infinity, hence the same is expected to hold for split matroids as well.

In [3], Bérczi and Schwarcz showed that Hamidoune’s conjecture holds for split
matroids. In fact, they proved that the exchange distance of compatible basis
pairs $\mathbf{P}_{1}=(A_{1},A_{2})$ and $\mathbf{P}_{2}=(B_{1},B_{2})$ of a
rank-$r$ split matroid is at most $\min\\{r,r-|A_{1}\cap B_{1}|+1\\}$, and
that a shortest sequence transforming $\mathbf{P}_{1}$ into $\mathbf{P}_{2}$
can be found in polynomial time if the matroid in question is given by an
independence oracle. By building on their proof, we show how to deduce a
strengthening of their result.

######  Theorem 2.

Let $\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ be
compatible pairs of disjoint bases of a rank-$r$ split matroid $M$ over a
ground set $S$, and let $w\colon S\to\mathbb{R}_{+}$ be a weight function.
Then there exists a sequence of exchanges of length at most
$\min\\{r,r-|R_{1}\cap R_{2}|+1\\}$ and total weight at most $w(R_{1}\cup
B_{1})=w(R_{2}\cup B_{2})$ that transforms $\mathbf{P}_{1}$ into
$\mathbf{P}_{2}$ and uses each element at most twice.

###### Proof.

Similarly to the proof in [3], we first show that it suffices to verify the
theorem for elementary split matroids. If $M$ is not elementary, then all but
at most one of its components are uniform matroids. Let
$M_{0}=(S_{0},\mathcal{B}_{0})$ denote, if exists, the elementary split
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 $R_{1}^{i}\coloneqq R_{1}\cap
S_{i}$, $B_{1}^{i}\coloneqq B_{1}\cap S_{i}$, $R_{2}^{i}\coloneqq R_{2}\cap
S_{i}$, $B_{2}^{i}\coloneqq B_{2}\cap S_{i}$ for $i=0,\dots,t$. Clearly,
$R_{1}^{i}$, $B_{1}^{i}$, $R_{2}^{i}$ and $B_{2}^{i}$ are bases of the uniform
matroid $M_{i}$. Take a sequence of exchanges of length at most
$\min\\{r_{0},r_{0}-|R_{1}^{0}\cap R_{2}^{0}|+1\\}$ and total weight at most
$w(R_{1}^{0}\cup B_{1}^{0})$ that transforms $(R^{0}_{1},B^{0}_{1})$ into
$(R^{0}_{2},B^{0}_{2})$ and uses each element in $S_{0}$ at most twice, where
$r_{0}$ is the rank of $M_{0}$. For each uniform matroid $M_{i}$, take a
strictly monotone sequence of exchanges that transforms
$(R_{1}^{i},B_{1}^{i})$ into $(R_{2}^{i},B_{2}^{i})$; it is not difficult to
see that such a sequence exists for uniform matroids. The concatenations of
these sequences result in an exchange sequence of length at most
$\min\\{r_{0},r_{0}-|R_{1}^{0}\cap
R_{2}^{0}|+1\\}+\sum_{i=1}^{t}[r_{i}-|R_{1}^{i}\cap
R_{2}^{i}|]\leq\min\\{r,r-|R_{1}\cap R_{2}|+1\\}$ and total weight at most
$w(R_{1}\cup B_{1})=w(R_{2}\cup B_{2})$ that transforms $(R_{1},B_{1})$ into
$(R_{2},B_{2})$ and uses each element at most twice.

By the above, we may assume that $M$ is an elementary split matroid. Let
$\mathcal{H}=\\{H_{1},\dots,H_{q}\\}$ be the hypergraph that defines the
matroid, and let $r_{1},\dots,r_{q}$ denote the upper bounds on the size of
the intersection of an independent set with the hyperedges. The length and the
weight of any strictly monotone sequence of exchanges that transforms
$\mathbf{P}_{1}$ into $\mathbf{P}_{2}$ has length $r-|R_{1}\cap R_{2}|$ and
weight $w(R_{1}\triangle R_{2})\leq w(R_{1}\cup B_{1})=w(R_{2}\cup B_{2})$,
respectively, and uses each element at most once. Hence assume that this is
not the case, that is, there exists no strictly monotone exchange sequence
between $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$. In such a case, [3] showed that
$\min\\{r,r-|R_{1}\cap R_{2}|+1\\}=r-|R_{1}\cap R_{2}|+1$ and after performing
a longest strictly monotone exchange sequence from $\mathbf{P}_{1}$ with
respect to $\mathbf{P}_{2}$, one is left with a basis pair
$\mathbf{P}^{\prime}_{1}=(R^{\prime}_{1},B^{\prime}_{1})$ for which there
exists pairwise distinct hyperedges $H_{1}$, $H_{2}$, $H_{3}$ and $H_{4}$ in
$\mathcal{H}$ with the following properties:222Here a) follows from Claims 8
and 11, b) follows from Claims 9 and 10, and c) follows from Claims 9 and 11
of [3].

  1. a)

$R_{1}$, $R^{\prime}_{1}$ and $R_{2}$ are $H_{1}$\- and $H_{3}$-tight, while
$B_{1}$, $B^{\prime}_{1}$ and $B_{2}$ are $H_{2}$\- and $H_{4}$-tight,

  2. b)

$(R_{1}\cap B_{2})\cup(B_{1}\cap R_{2})\subseteq(H_{1}\triangle
H_{3})\cap(H_{2}\triangle H_{4})$,

  3. c)

$|R^{\prime}_{1}\cap B_{2}\cap H_{1}\cap H_{2}|=|R^{\prime}_{1}\cap B_{2}\cap
H_{3}\cap H_{4}|=|B^{\prime}_{1}\cap R_{2}\cap H_{1}\cap
H_{4}|=|B^{\prime}_{1}\cap R_{2}\cap H_{2}\cap H_{3}|>0$.

Moreover, for each $z\in((R_{1}\cap R_{2})\cup(B_{1}\cap
B_{2}))\setminus((H_{1}\triangle H_{3})\cap(H_{2}\triangle H_{4}))$, [3]
showed the existence of an exchange sequence that transforms
$\mathbf{P}^{\prime}_{1}$ into $\mathbf{P}_{2}$, uses $z$ twice, uses the
elements of $(R^{\prime}_{1}\cap B_{2})\cup(B^{\prime}_{1}\cap R_{2})$ once,
and does not use any other elements. Consider the concatenation of the
strictly monotone exchange sequence from $\mathbf{P}_{1}$ to
$\mathbf{P}^{\prime}_{1}$ and the above exchange sequence from
$\mathbf{P}^{\prime}_{1}$ to $\mathbf{P}_{2}$. The sequence thus obtained uses
each element at most twice, has length $r-|R_{1}\cap R_{2}|+1$ and total
weight

$2w(z)+w((R_{1}\cap B_{2})\cup(R_{2}\cap B_{1}))=w(R_{1}\cup
B_{1})+2w(z)-w((R_{1}\cap R_{2})\cup(B_{1}\cap B_{2})).$

Therefore, it suffices to show that there exists an element $z\in((R_{1}\cap
R_{2})\cup(B_{1}\cap B_{2}))\setminus((H_{1}\triangle H_{3})\cap(H_{2}\cap
H_{4}))$ with weight $w(z)\leq\frac{1}{2}w((R_{1}\cap R_{2})\cup(B_{1}\cap
B_{2}))$. We prove that

($\star$) $|((R_{1}\cap R_{2})\cup(B_{1}\cap B_{2}))\setminus((H_{1}\triangle
H_{3})\cap(H_{2}\triangle H_{4}))|\geq 2$

holds from which the statement follows. Using properties b) and c), we get

$\displaystyle 0{}$ $\displaystyle{}<|B^{\prime}_{1}\cap R_{2}\cap H_{2}\cap
H_{3}|$ $\displaystyle{}\leq|B_{1}\cap R_{2}\cap H_{2}\cap H_{3}|$
$\displaystyle{}=|(B_{1}\cap R_{2})\setminus(H_{1}\cup H_{4})|$
$\displaystyle{}\leq|B_{1}\setminus(H_{1}\cup H_{4})|.$

By [3, Lemma 6], if a set $F$ of size $r$ is both $H$-tight and
$H^{\prime}$-tight for some hyperedges $H,H^{\prime}\in\mathcal{H}$ then
$H\cap H^{\prime}\subseteq F\subseteq H\cup H^{\prime}$. As $B_{1}$ is
$H_{4}$-tight and $B_{1}\not\subseteq H_{1}\cup H_{4}$, it follows that
$B_{1}$ is not $H_{1}$-tight, that is, $|B_{1}\cap H_{1}|\leq r_{1}-1$. Using
that $R_{2}$ is $H_{1}$-tight, we get

$\displaystyle|B_{1}\cap B_{2}\cap H_{1}|{}$ $\displaystyle{}=|B_{1}\cap
H_{1}|-|B_{1}\cap R_{2}\cap H_{1}|$ $\displaystyle{}\leq(r_{1}-1)-|B_{1}\cap
R_{2}\cap H_{1}|$ $\displaystyle{}=|R_{2}\cap H_{1}|-|B_{1}\cap R_{2}\cap
H_{1}|-1$ $\displaystyle{}=|R_{1}\cap R_{2}\cap H_{1}|-1.$

An analogous reasoning shows that the inequality

$|B_{1}\cap B_{2}\cap H_{3}|\leq|R_{1}\cap R_{2}\cap H_{3}|-1$

holds as well. As $R_{1}$ is both $H_{1}$\- and $H_{3}$-tight, $H_{1}\cap
H_{3}\subseteq R_{1}\subseteq H_{1}\cup H_{3}$ holds by [3, Lemma 6]. Then

$\displaystyle|B_{1}\cap B_{2}|-|(B_{1}\cap B_{2})\setminus(H_{1}\cup
H_{3})|{}$ $\displaystyle{}=|B_{1}\cap B_{2}\cap H_{1}|+|B_{1}\cap B_{2}\cap
H_{3}|$ $\displaystyle{}\leq|R_{1}\cap R_{2}\cap H_{1}|+|R_{1}\cap R_{2}\cap
H_{3}|-2$ $\displaystyle{}=|R_{1}\cap R_{2}|+|R_{1}\cap R_{2}\cap H_{1}\cap
H_{3}|-2.$

Using $|B_{1}\cap B_{2}|=|R_{1}\cap R_{2}|$, we get

$\displaystyle 2{}$ $\displaystyle{}\leq|R_{1}\cap R_{2}\cap H_{1}\cap
H_{3}|+|(B_{1}\cap B_{2})\setminus(H_{1}\cup H_{3})|$
$\displaystyle{}\leq|((R_{1}\cap R_{2})\cup(B_{1}\cap
B_{2}))\setminus(H_{1}\triangle H_{3})|,$

implying ($\star$) ‣ 3.2 and thus concluding the proof of the theorem. ∎

##  4 Wheels

Our first main result is a proof of Conjecture 1 for the graphic matroid of
wheels. In fact, we prove a much stronger statement: we verify that for any
pair $\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ of
colorings of a wheel $G=(V,E)$, there exists a sequence of exchanges of length
at most $r$ and total weight at most $w(E)$ that transforms $\mathbf{P}_{1}$
into $\mathbf{P}_{2}$ and uses each edge at most twice.

Throughout the section, we assume that $\mathbf{P}_{1}$ has positive
orientation. For ease of notation, we introduce
$\varphi_{\oplus}\coloneqq\varphi_{\mathbf{P}_{1},+}$ and
$\varphi_{\ominus}\coloneqq\varphi_{\mathbf{P}_{1},-}$. Recall that both
$\varphi_{\ominus}$ and $\varphi_{\oplus}$ provide a bijection between spokes
and rim edges.

First we settle the case when the two colorings have the same orientation.

######  Lemma 3.

Let $\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ be
colorings of a wheel $G=(V,E)$ with the same orientation. Then there exists a
strictly monotone sequence of exchanges that transforms $\mathbf{P}_{1}$ into
$\mathbf{P}_{2}$.

###### Proof.

Exchange each spoke $e$ that has different color in $\mathbf{P}_{1}$ than in
$\mathbf{P}_{2}$ with its pair $\varphi_{\ominus}(e)$ in an arbitrary order,
only paying attention to always have at least one spoke in both color classes.
Once the spokes have the right colors, that is, they are colored as in
$\mathbf{P}_{2}$, the rim edges are also colored as required. Indeed, the
orientation was not changed during the procedure and the coloring of the
spokes together with the orientation of the coloring uniquely determines the
colors of the rim edges. ∎

######  Remark 4.

Exchanging a spoke $e$ with its pair $\varphi_{\ominus}(e)$ does not reverse
the orientation of the coloring. Therefore, if the initial coloring
$\mathbf{P}_{1}=(R_{1},B_{1})$ and the target coloring
$\mathbf{P}_{2}=(R_{2},B_{2})$ have different orientations, then any sequence
of feasible exchanges must go through a coloring of the graph with only two
intervals. This results in reversing the orientation of a coloring to be
costly, as one needs to make exchange steps that, at least seemingly, bring
the colorings further away from each other in the sense that they increase the
symmetric difference of $R_{1}$ and $R_{2}$. The class of wheels is
particularly interesting as they admit colorings
$\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ for which
the minimum number of steps required to transform $\mathbf{P}_{1}$ into
$\mathbf{P}_{2}$ is arbitrarily large compared to the trivial lower bound
$(n-1)-|R_{1}\cap R_{2}|$; see Figure 2 for an example.

(a) A coloring $\mathbf{P}_{1}=(R_{1},B_{1})$ with positive orientation. Thick
edges denote the boundary edges.

(b) A coloring $\mathbf{P}_{2}=(R_{2},B_{2})$ with negative orientation. Thick
edges denote the boundary edges.

Figure 2: A pair of $\mathbf{P}_{1}=(R_{1},B_{1})$ and
$\mathbf{P}_{2}=(R_{2},B_{2})$ with $(n-1)-|R_{1}\cap R_{2}|=2$. The colorings
have opposite orientations, hence any sequence of exchanges that transforms
$\mathbf{P}_{1}$ into $\mathbf{P}_{2}$ goes through a coloring having two
intervals, implying that their exchange distance is at least $\frac{n-1}{4}$.

Next we consider colorings with different orientations and a bounded number of
intervals in one of the color classes.

######  Lemma 5.

Let $\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ be
colorings of a wheel $G=(V,E)$ with different orientations where
$\mathbf{P}_{1}$ has at most four intervals, and let $w\colon
E\to\mathbb{R}_{+}$ be a weight function. Then there exists a sequence of
exchanges of length at most $n-1$ and total weight at most $w(E)$ that
transforms $\mathbf{P}_{1}$ into $\mathbf{P}_{2}$ and uses each edge at most
twice.

###### Proof.

We will distinguish two main cases based on the number of intervals in
$\mathbf{P}_{1}$. Recall that $\mathbf{P}_{1}$ is assumed to have positive
orientation throughout.

Case 1. $\mathbf{P}_{1}$ has two intervals.

Case 1.1. $\mathbf{P}_{1}$ has an interval of length one.

We may assume that there exists a red interval of length one, and let $c$
denote the unique spoke in it. We denote by $a$ the spoke following $c$ in
negative direction, and further define
$b\coloneqq\varphi_{\oplus}(a)=\varphi_{\ominus}(c)$ and
$d\coloneqq\varphi_{\oplus}(c)$. Note that $a$ and $b$ are blue, while $d$ is
a red edge; see Figure 3(a). As $\mathbf{P}_{2}$ has negative orientation, $a$
and $\varphi_{\oplus}(a)=b$ have different colors in $\mathbf{P}_{2}$, and the
same holds for $c$ and $\varphi_{\oplus}(c)=d$. Hence the set of edges among
$a$, $b$, $c$ and $d$ that have different colors in $\mathbf{P}_{1}$ and
$\mathbf{P}_{2}$ is either $\\{a,c\\},\\{a,d\\},\\{b,d\\}$ or $\\{b,c\\}$. In
the first three cases, changing the color of the two edges is a feasible
exchange which reverses the orientation. Once the orientation of the coloring
is reversed, there exists a strictly monotone exchange sequence to
$\mathbf{P}_{2}$ by Lemma 3, altogether resulting in a strictly monotone
exchange sequence from $\mathbf{P}_{1}$ to $\mathbf{P}_{2}$.

The only remaining case is when the set of edges among $a$, $b$, $c$ and $d$
that need to change color is $\\{b,c\\}$. In this case, the difficulty comes
from the fact that these edges do not define a feasible exchange between the
two color classes. In order to overcome this, extra steps are needed to
reverse the orientation. Let $s$ be an arbitrary red spoke of
$\mathbf{P}_{2}$. Note that $s\not\in\\{a,c\\}$ as we are in the case when $a$
and $c$ are blue in $\mathbf{P}_{2}$. As $\mathbf{P}_{1}$ has a unique red
spoke, namely $c$, we get that $s$ is blue in $\mathbf{P}_{1}$, and
$\varphi_{\oplus}(s)$ is red in $\mathbf{P}_{1}$ and blue in $\mathbf{P}_{2}$
since $\mathbf{P}_{2}$ has negative orientation. Consider the two exchange
sequences of length three $(b,d)$, $(s,\varphi_{\oplus}(s))$, $(c,d)$ and
$(a,c)$, $(s,\varphi_{\oplus}(s))$, $(a,b)$. Both of these sequences reverse
the orientation of the coloring and fix the colors of the edges $a$, $b$, $c$
and $d$. Therefore, after applying any of them, there exists a strictly
monotone exchange sequence to $\mathbf{P}_{2}$ by Lemma 3 that uses all the
remaining edges in $E-\\{a,b,c,d\\}$ at most once. Thus in overall, we get an
exchange sequence that uses each edge in $E-\\{a,d\\}$ at most once, does not
use one of $a$ and $d$ and uses the other twice. Hence the length of the
sequence is at most half of the number of edges, that is, $n-1$. If $w(a)\geq
w(d)$, then starting the sequence with $(b,d)$, $(s,\varphi_{\oplus}(s))$,
$(c,d)$, while if $w(a)<w(d)$, then starting the sequence with $(a,c)$,
$(s,\varphi_{\oplus}(s))$, $(a,b)$ ensures that total weight of the exchange
sequence is at most $w(E)$, concluding the proof of the case.

Case 1.2. Both intervals of $\mathbf{P}_{1}$ have length at least two.

Let $c$ denote the last spoke of the red interval in positive direction and
let $d\coloneqq\varphi_{\oplus}(c)$. Furthermore, let $a$ be the last spoke of
the blue interval in positive direction and let
$b\coloneqq\varphi_{\oplus}(a)$, see Figure 3(b). Similarly to Case 1.1, the
set of edges among $a$, $b$, $c$ and $d$ that have different colors in
$\mathbf{P}_{1}$ and $\mathbf{P}_{2}$ is either $\\{a,c\\}$, $\\{a,d\\}$,
$\\{b,d\\}$ or $\\{b,c\\}$. However, now fixing the orientation is even
simpler than before as any of the exchanges $(a,c)$, $(a,d)$, $(b,c)$ and
$(b,d)$ is feasible. After reversing the orientation using one of these
exchanges, there exists a strictly monotone exchange sequence to
$\mathbf{P}_{2}$ by Lemma 3, altogether resulting in a strictly monotone
exchange sequence from $\mathbf{P}_{1}$ to $\mathbf{P}_{2}$.

(a) $\mathbf{P}_{1}$ contains two intervals, one of them having length one.

(b) $\mathbf{P}_{1}$ contains two intervals, both having length at least two.

(c) $\mathbf{P}_{1}$ contains four intervals, one of them having length one.

(d) $\mathbf{P}_{1}$ contains both a red and a blue interval of length one.

Figure 3: Illustration of the cases in the proof of Lemma 5.

We denote the number of spokes in $R_{1}$, $R_{2}$, $B_{1}$ and $B_{2}$ by
$r_{1}$, $r_{2}$, $b_{1}$ and $b_{2}$, respectively. Let $2q$ denote the
number of intervals in $\mathbf{P}_{1}$, and let $I_{1},\dots,I_{2q}$ denote
the intervals in a positive direction, where intervals with odd indices have
color red and intervals with even indices have color blue. Furthermore, for
$1\leq i\leq 2q$, we define

$\displaystyle x_{i}\coloneqq\sum[w(e)\mid e\in
I_{i}\cup\varphi_{\ominus}(I_{i}),\ e\ \text{has the same color in
$\mathbf{P}_{1}$ and $\mathbf{P}_{2}$}],$ $\displaystyle
y_{i}\coloneqq\sum[w(e)\mid e\in I_{i}\cup\varphi_{\ominus}(I_{i}),\ e\
\text{has different colors in $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$}].$

By the above definitions, we have
$w(I_{i}\cup\varphi_{\ominus}(I_{i}))=x_{i}+y_{i}$ for $1\leq i\leq 2q$, and
$\sum_{i=1}^{2q}(x_{i}+y_{i})=w(E)$.

Case 2. $\mathbf{P}_{1}$ has four intervals.

Since $r_{1}+r_{2}+b_{1}+b_{2}=2(n-1)$, we have
$\min\\{r_{1}+r_{2},b_{1}+b_{2}\\}\leq n-1$. We may assume that
$r_{1}+r_{2}\leq n-1$. We distinguish two cases based on the structure of the
red intervals in $\mathbf{P}_{1}$.

Case 2.1. $\mathbf{P}_{1}$ has no red interval of length one.

Take one of the intervals $I_{j}\in\\{I_{1},I_{3}\\}$ and exchange each spoke
$p$ in $I_{j}$ with its pair $\varphi_{\ominus}(p)$. The coloring thus
obtained has only two intervals from which the red has length more than one,
hence there exists a strictly monotone exchange sequence to $\mathbf{P}_{2}$
as in Case 1.2. Note that each edge is used at most twice during this process,
and the edges used twice are exactly the edges of $I_{j}$ having the same
color in $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$. The length of the exchange
sequence thus obtained is

$\displaystyle|I_{j}|+|(I_{j}\cup I_{2}\cup I_{4})\cap R_{2}|+|I_{4-j}\cap
B_{2}|{}$ $\displaystyle{}\leq|I_{j}|+|(I_{1}\cup I_{2}\cup I_{3}\cup
I_{4})\cap R_{2}|+|I_{4-j}|$ $\displaystyle{}=r_{1}+r_{2}$
$\displaystyle{}\leq n-1.$

In order to bound the total weight of the exchanges, note that we used edges
twice only from $I_{j}\cup\varphi_{\ominus}(I_{j})$, and all the other edges
were used only if their color had to change. Thus the total weight of the
exchange sequence is $2x_{j}+y_{1}+y_{2}+y_{3}+y_{4}$. As
$2\min\\{x_{1},x_{3}\\}\leq x_{1}+\dots+x_{4}$, we get
$2\min\\{x_{1},x_{3}\\}+y_{1}+y_{2}+y_{3}+y_{4}\leq w(E)$. Hence choosing
$j\in\\{1,3\\}$ such that $x_{j}=\min\\{x_{1},x_{3}\\}$ leads to an exchange
sequence with the required properties.

Case 2.2. $\mathbf{P}_{1}$ has a red interval of length one.

Our approach is similar to that of Case 2.1 with slight modifications. By
applying the same algorithm, the analysis goes through if the the red interval
whose edges are not used before reversing the orientation has length at least
two. Indeed, the bounds on the length and weight of the exchange sequence
remain valid since we did not use the length of the intervals in the proof.
However, a problem occurs if at the orientation reversal step we have an
interval of length one, that is, when the algorithm starts with a red
interval, say $I_{3}$ due to $x_{3}\leq x_{1}$, and the other red interval
$I_{1}$ has length one.

Let $\mathbf{P}^{\prime}_{1}$ denote the coloring obtained by the exchanges so
far, that is, by exchanging each spoke $p$ in $I_{3}$ with its pair
$\varphi_{\ominus}(p)$. At this point, our goal is to reverse the orientation
and then find a strictly monotone sequence to $\mathbf{P}_{2}$. Note that this
is exactly the same scenario we had in Case 1.1, hence we use an analogous
notation that we had there. That is, let $c$ denote the unique red spoke of
$\mathbf{P}^{\prime}_{1}$ and $a$ be the spoke following $c$ in a negative
direction. Furthermore, define
$b\coloneqq\varphi_{\oplus}(a)=\varphi_{\ominus}(c)$ and
$d\coloneqq\varphi_{\oplus}(c)$, see Figure 3(c). Similarly to Case 1.1, the
set of edges among $a$, $b$, $c$ and $d$ that have different colors in
$\mathbf{P}^{\prime}_{1}$ and $\mathbf{P}_{2}$ is either $\\{a,c\\}$,
$\\{a,d\\}$, $\\{b,d\\}$ or $\\{b,c\\}$. In the first three cases, changing
the color of the two edges is a feasible exchange which reverses the
orientation and fixes the color of all four edges $a$, $b$, $c$ and $d$. Once
the coloring is reversed, there exists a strictly monotone exchange sequence
to $\mathbf{P}_{2}$ by Lemma 3. The length and weight of the exchange sequence
can be bounded analogously to Case 2.1.

The only remaining case is when the set of edges among $a$, $b$, $c$ and $d$
that need to change color is $\\{b,c\\}$. Let $s$ be an arbitrary red spoke of
$\mathbf{P}_{2}$. Note that $s\not\in\\{a,c\\}$ as we are in the case when $a$
and $c$ are blue in $\mathbf{P}_{2}$. As $\mathbf{P}^{\prime}_{1}$ has a
unique red spoke, namely $c$, we get that $s$ is blue in
$\mathbf{P}^{\prime}_{1}$, and $\varphi_{\oplus}(s)$ is red in
$\mathbf{P}^{\prime}_{1}$ and blue in $\mathbf{P}_{2}$ since $\mathbf{P}_{2}$
has negative orientation. Consider the two exchange sequences of length three
$(b,d)$, $(s,\varphi_{\oplus}(s))$, $(c,d)$ and $(a,c)$,
$(s,\varphi_{\oplus}(s))$, $(a,b)$. Both of these sequences change the
orientation of the coloring and fix the colors of the edges $a$, $b$, $c$ and
$d$. Therefore, after applying any of them, there exists a strictly monotone
exchange sequence to $\mathbf{P}_{2}$ by Lemma 3. If $w(a)\geq w(d)$, then use
the sequence $(b,d)$, $(s,\varphi_{\oplus}(s))$, $(c,d)$ for reversing the
orientation, and use $(a,c)$, $(s,\varphi_{\oplus}(s))$, $(a,b)$ otherwise. In
what follows, we bound the length and weight of the sequence obtained.

Suppose first that $r_{1}+r_{2}<n-1$. The length of the exchange sequence is

$|I_{3}|+3+|(I_{2}\cup I_{3}\cup I_{4}-s)\cap
R_{2}|=(r_{1}-1)+3+(r_{2}-1)=r_{1}+r_{2}+1\leq n-1.$

We used edges twice only from $I_{3}\cup\varphi_{\ominus}(I_{3})\cup\\{d\\}$
if $w(a)\geq w(d)$, and only from
$I_{3}\cup\varphi_{\ominus}(I_{3})\cup\\{a\\}$ otherwise. Thus the total
weight of the exchange sequence is at most

$2x_{3}+2\min\\{w(a),w(d)\\}+y_{1}+y_{2}+y_{3}+y_{4}\leq
2x_{3}+x_{2}+x_{4}+y_{1}+y_{2}+y_{3}+y_{4}\leq w(E),$

where we used that $2\min\\{w(a),w(d)\\}\leq 2\min\\{x_{4},x_{2}\\}\leq
x_{2}+x_{4}$ and $x_{3}\leq x_{1}$.

We are left with the case when $r_{1}+r_{2}=n-1$, there exists a red interval
consisting of a single spoke $c$, and the edges $c$ and $\varphi_{\ominus}(c)$
have different colors in $\mathbf{P}^{\prime}_{1}$ and $\mathbf{P}_{2}$. Then,
by $r_{1}+r_{2}+b_{1}+b_{2}=2n-2$, we get that $b_{1}+b_{2}=n-1$ also holds.
Up to this point the two colors played different roles in the proof of Case 2
as we used the fact that $r_{1}+r_{2}\leq n-1$. However, now the same
inequality holds for the number of blue spokes as well, hence we can switch
the roles of the two colors. In particular, if none of the blue intervals have
length one, then we are done. Thus suppose that the red interval $I_{1}$
consisting of the single spoke $c$ is followed in positive direction by a blue
interval $I_{2}$ consisting of the single spoke $e$; the case when a blue
interval of length one is followed in positive direction by a red interval of
length one can be proved analogously. We denote by $a$ the spoke before $c$ in
negative direction, and further define
$b\coloneqq\varphi_{\oplus}(a)=\varphi_{\ominus}(c)$,
$d\coloneqq\varphi_{\oplus}(c)=\varphi_{\ominus}(e)$ and
$f\coloneqq\varphi_{\oplus}(e)$, see Figure 3(d). Recall that we are in the
case when the set of edges among $a$, $b$, $c$ and $d$ that need to change
color is $\\{b,c\\}$. However, this means that among the edges $c$, $d$, $e$
and $f$, the set of edges that need to change color cannot be $\\{d,e\\}$.
That is, if we start by exchanging each spoke $p$ in $I_{4}$ with its pair
$\varphi_{\ominus}(p)$, then the resulting coloring
$\mathbf{P}^{\prime\prime}_{1}$ can be transformed into $\mathbf{P}_{2}$ by a
strictly monotone sequence of exchanges, and the analysis of the second
paragraph of Case 2.2 applies. ∎

Our last technical lemma shows that when one of the colorings has at least six
intervals, then there exists a sequence of exchanges that has low weight with
respect to two arbitrary weight functions simultaneously.

######  Lemma 6.

Let $\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ be
colorings of a wheel $G=(V,E)$ with different orientations such that
$\mathbf{P}_{1}$ has at least six intervals, and let $w_{1},w_{2}\colon
E\to\mathbb{R}_{+}$ be weight functions. Then there exists a sequence of
exchanges of total $w_{i}$-weight at most $w_{i}(E)$ for $i=1,2$ that
transforms $\mathbf{P}_{1}$ into $\mathbf{P}_{2}$ and uses each edge at most
twice.

###### Proof.

We distinguish two cases based on the remainder of the number of intervals
modulo four.

Case 1. $q=2k+1$ for some integer $k\geq 1$.

For an index $1\leq j\leq 4k+2$, exchange each spoke
$e\in\bigcup_{i=1}^{k}I_{j+2i-1}$ with its pair $\varphi_{\ominus}(e)$, and do
the same for each spoke $e\in\bigcup_{i=k+1}^{2k}I_{j+2i}$. After these
exchanges, the resulting coloring $\mathbf{P}^{\prime}_{1}$ has two intervals:
$I_{j}\cup I_{j+1}\cup\dots\cup I_{j+2k}$ has the same color in
$\mathbf{P}^{\prime}_{1}$ as $I_{j}$ in $\mathbf{P}_{1}$, and $I_{j+2k+1}\cup
I_{j+2k+2}\cup\dots\cup I_{j+4k+1}$ has the other color. Note that none of
these two intervals has length one as $k\geq 1$. Therefore, there exists a
strictly monotone exchange sequence from $\mathbf{P}^{\prime}_{1}$ to
$\mathbf{P}_{2}$ by Case 1.2 of Lemma 5. Let $w\in\\{w_{1},w_{2}\\}$, and let
us define $I_{i}$, $x_{i}$ and $y_{i}$ for $1\leq i\leq 2q$ as in the proof of
Lemma 5, where the $x_{i}$ and $y_{i}$ values are computed with respect to
$w$. Our goal is to bound the $w$-weight of the above defined sequence of
exchanges.

Exchanging each spoke $e$ in
$\bigcup_{i=1}^{k}I_{j+2i-1}\cup\bigcup_{i=k+1}^{2k}I_{j+2i}$ with its pair
$\varphi_{\ominus}(e)$ has weight

$\sum_{i=1}^{k}(x_{j+2i-1}+y_{j+2i-1})+\sum_{i=k+1}^{2k}(x_{j+2i}+y_{j+2i}).$

Then the strictly monotone sequence to $\mathbf{P}_{2}$ has weight

$\sum_{i=0}^{k}y_{j+2i}+\sum_{i=1}^{k}x_{j+2i-1}+\sum_{i=k}^{2k}y_{j+2i+1}+\sum_{i=k+1}^{2k}x_{j+2i}.$

The total weight is then

$2\cdot\left(\sum_{i=1}^{k}x_{j+2i-1}+\sum_{i=k+1}^{2k}x_{j+2i}\right)+\sum_{i=1}^{4k+2}y_{i}.$

Therefore the total $w$-weight of the exchange sequence is at most
$w(E)=\sum_{i=1}^{4k+2}(x_{i}+y_{i})$ if and only if

($\operatorname{A}_{w}(j)$)
$\sum_{i=1}^{k}x_{j+2i-1}+\sum_{i=k+1}^{2k}x_{j+2i}\leq\sum_{i=0}^{k}x_{j+2i}+\sum_{i=k}^{2k}x_{j+2i+1}.$

Consider inequalities $\operatorname{A}_{w}(j)$ and
$\operatorname{A}_{w}(j+1)$. The sum of these two inequalities gives

$\left(\sum_{i=1}^{4k+2}x_{i}\right)-(x_{j}+x_{j+2k+1})\leq\left(\sum_{i=1}^{4k+2}x_{i}\right)+(x_{j}+x_{j+2k+1}).$

As this inequality clearly holds, at least one of $\operatorname{A}_{w}(j)$
and $\operatorname{A}_{w}(j+1)$ must hold as well. Furthermore,
$\operatorname{A}_{w}(j)$ is identical to $\operatorname{A}_{w}(j+2k+1)$.
These together imply that $\operatorname{A}_{w}(j)$ holds for at least $k+1$
choices of $j$ from $\\{1,\dots,2k+1\\}$ for $w\in\\{w_{1},w_{2}\\}$.
Therefore, there exists an index $j$ for which both
$\operatorname{A}_{w_{1}}(j)$ and $\operatorname{A}_{w_{2}}(j)$ are satisfied.
As each edge is used at most twice, the statement follows.

Case 2. $q=2k$ for some integer $k\geq 2$.

Our approach is similar to that of Case 1. For an index $1\leq j\leq 4k$,
exchange each spoke $e\in\bigcup_{i=1}^{k-1}I_{j+2i-1}$ with its pair
$\varphi_{\ominus}(e)$, and do the same for each spoke
$e\in\bigcup_{i=k}^{2k-1}I_{j+2i}$. After these exchanges, the resulting
coloring $\mathbf{P}^{\prime}_{1}$ has two intervals: $I_{j}\cup
I_{j+1}\cup\dots\cup I_{j+2k-1}$ has the same color in
$\mathbf{P}^{\prime}_{1}$ as $I_{j}$ in $\mathbf{P}_{1}$, and $I_{j+2k}\cup
I_{j+2k+1}\cup\dots\cup I_{j+4k}$ has the other color. Note that none of these
two intervals has length one as $k\geq 2$. Therefore, there exists a strictly
monotone exchange sequence from $\mathbf{P}^{\prime}_{1}$ to $\mathbf{P}_{2}$
by Case 1.2 of Lemma 5. Let $w\in\\{w_{1},w_{2}\\}$, and let us define
$I_{i}$, $x_{i}$ and $y_{i}$ for $1\leq i\leq 2q$ as in the proof of Lemma 5,
where the $x_{i}$ and $y_{i}$ values are computed with respect to $w$. Our
goal is to bound the $w$-weight of the above defined sequence of exchanges.

Exchanging each spoke $e$ in
$\bigcup_{i=1}^{k-1}I_{j+2i-1}\cup\bigcup_{i=k}^{2k-1}I_{j+2i}$ with its pair
$\varphi_{\ominus}(e)$ has weight

$\sum_{i=1}^{k-1}(x_{j+2i-1}+y_{j+2i-1})+\sum_{i=k}^{2k-1}(x_{j+2i}+y_{j+2i}).$

Then the strictly monotone sequence to $\mathbf{P}_{2}$ has weight

$\sum_{i=0}^{k-1}y_{j+2i}+\sum_{i=1}^{k-1}x_{j+2i-1}+\sum_{i=k}^{2k}y_{j+2i-1}+\sum_{i=k}^{2k-1}x_{j+2i}.$

The total weight is then

$2\cdot\left(\sum_{i=1}^{k-1}x_{j+2i-1}+\sum_{i=k}^{2k-1}x_{j+2i}\right)+\sum_{i=1}^{4k}y_{i}.$

Therefore the total $w$-weight of the exchange sequence is at most
$w(E)=\sum_{i=1}^{4k}(x_{i}+y_{i})$ if and only if

($\operatorname{B}_{w}(j)$)
$\sum_{i=1}^{k-1}x_{j+2i-1}+\sum_{i=k}^{2k-1}x_{j+2i}\leq\sum_{i=0}^{k-1}x_{j+2i}+\sum_{i=k-1}^{2k-1}x_{j+2i+1}.$

Consider inequalities $\operatorname{B}_{w}(j)$ and
$\operatorname{B}_{w}(j+1)$. The sum of these two inequalities gives

$\left(\sum_{i=1}^{4k}x_{i}\right)-(x_{j}+x_{j+2k-1})\leq\left(\sum_{i=1}^{4k}x_{i}\right)+(x_{j}+x_{j+2k-1}).$

As this inequality clearly holds, at least one of $\operatorname{B}_{w}(j)$
and $\operatorname{B}_{w}(j+1)$ must hold as well. This implies that
$\operatorname{B}_{w}(j)$ holds for at least $2k$ choices of $j$ from
$\\{1,\dots,4k\\}$. Note that if the number of such choices is exactly $2k$,
then $\operatorname{B}_{w}(j)$ holds either for all odd or for all even
indices.

Now consider inequalities $\operatorname{B}_{w}(j)$ and
$\operatorname{B}_{w}(j+2k)$. The sum of these two inequalities gives

$\left(\sum_{i=1}^{4k}x_{i}\right)-(x_{j+2k-1}+x_{j+4k-1})\leq\left(\sum_{i=1}^{4k}x_{i}\right)+(x_{j+2k-1}+x_{j+4k-1}).$

As this inequality clearly holds, at least one of $\operatorname{B}_{w}(j)$
and $\operatorname{B}_{w}(j+2k)$ must hold as well. As the parities of $j$ and
$j+2k$ are the same, this, together with the above observation, implies that
$\operatorname{B}_{w}(j)$ holds for at least $2k+1$ choices of $j$ from
$\\{1,\dots,4k\\}$ for $w\in\\{w_{1},w_{2}\\}$. Therefore, there exists an
index $j$ for which both $\operatorname{B}_{w_{1}}(j)$ and
$\operatorname{B}_{w_{2}}(j)$ are satisfied. As each edge is used at most
twice, the statement follows. ∎

With the help of Lemmas 3, 5 and 6, we are ready to prove the main result of
the paper.

######  Theorem 7.

Let $\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ be
colorings of a wheel $G=(V,E)$, and let $w\colon E\to\mathbb{R}_{+}$ be a
weight function. Then there exists a sequence of exchanges of length at most
$n-1$ and total weight at most $w(E)$ that transforms $\mathbf{P}_{1}$ into
$\mathbf{P}_{2}$ and uses each edge at most twice.

###### Proof.

If the colorings have identical orientation, then the theorem follows by Lemma
3. Indeed, the length and the weight of any strictly monotone sequence of
exchanges that transforms $\mathbf{P}_{1}$ into $\mathbf{P}_{2}$ achieves the
natural lower bounds $(n-1)-|R_{1}\cap R_{2}|\leq n-1$ and $w(R_{1}\triangle
R_{2})\leq w(E)$, respectively, and uses each edge at most once.

Hence assume that the colorings have different orientations. If
$\mathbf{P}_{1}$ has at most four intervals, then the theorem immediately
follows by Lemma 5. Otherwise, Lemma 6 with the choice $w_{1}\coloneqq w$ and
$w_{2}\equiv 1$ ensures the existence of a sequence of exchanges of total
weight at most $w_{1}(E)=w(E)$ and length at most $w_{2}(E)/2=|E|/2=n-1$ that
uses each edge at most twice, concluding the proof. ∎

##  5 Spikes

In this section, we prove that a strengthening of Conjecture 1 analogous to
Theorem 7 holds for spikes as well. That is, consider a rank-$r$ spike $M$
over ground set $S$, and let $w\colon S\to\mathbb{R}_{+}$ be a weight
function. We show that for any two compatible basis pairs
$\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$, there
exists a sequence of exchanges of length at most $r$ and total weight at most
$w(S)$ that transforms $\mathbf{P}_{1}$ into $\mathbf{P}_{2}$ and uses each
element at most twice.

Recall that $S=\\{t,x_{1},y_{1},\dots,x_{r},y_{r}\\}$, where $t$ is the tip
and $\\{x_{i},y_{i}\\}$ for $1\leq i\leq r$ are the legs of the spike. Hence
$R_{1}\cup B_{1}=R_{2}\cup B_{2}$ does not contain exactly one element $s$ of
$S$; for short, we say that the pairs $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$
miss the element $s$. We distinguish two cases depending on whether this
element is the tip of $M$ or not.

######  Lemma 8.

Let $\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ be
compatible pairs of disjoint bases of a rank-$r$ spike $M$ over a ground set
$S$ missing the tip $t$, and let $w\colon S\to\mathbb{R}_{+}$ be a weight
function. Then there exists a sequence of exchanges of length at most $r$ and
total weight at most $w(S-t)$ that transforms $\mathbf{P}_{1}$ into
$\mathbf{P}_{2}$ and uses each element at most twice.

###### Proof.

Let $Z\subseteq S-t$ be a subset of size $r$. Then $Z$ is a basis of $M$ if
and only if one of the followings hold.

  1. 1.

There exist indices $k$ and $\ell$ such that $\\{x_{k},y_{k}\\}\subseteq Z$,
$\\{x_{\ell},y_{\ell}\\}\cap Z=\emptyset$ and $|\\{x_{i},y_{i}\\}\cap Z|=1$
for all $1\leq i\leq r$, $i\not\in\\{k,\ell\\}$.

  2. 2.

$|Z\cap\\{x_{i},y_{i}\\}|=1$ for all $1\leq i\leq r$ and $Z$ is not a circuit
of $M$.

Bases of the latter type are called transversal bases as they intersect every
leg of $M$, while bases of the former type are called non-transversal bases.

Case 1. Both $R_{1}$ and $R_{2}$ are non-transversal.

We may assume that both $x_{1}$ and $y_{1}$ are red and both $x_{r}$ and
$y_{r}$ are blue in $\mathbf{P}_{1}$. Note that in this case exchanging the
elements $x_{i}$ and $y_{i}$ is feasible for $2\leq i\leq r-1$. As $R_{2}$ is
non-transversal, there exists indices $1\leq k,\ell\leq r$ such that $x_{k}$
and $y_{k}$ are both red and $x_{\ell}$ and $y_{\ell}$ are both blue in
$\mathbf{P}_{2}$. We distinguish cases based on the values of $k$ and $\ell$.

$x_{1}=x_{k}$
---
$x_{\ell}$
---
$x_{r}$
---
$y_{1}$
---
$y_{\ell}$
---
$y_{r}$
---
$R_{1}$
---
$R_{2}$
---
(a) Case $k=1$.

$x_{1}$
---
$x_{\ell}$
---
$x_{r}$
---
$y_{1}$
---
$y_{\ell}$
---
$y_{r}$
---
$R_{1}$
---
$R_{2}$
---
$x_{k}$
---
(b) Case $2\leq k\leq r-1$.

$x_{1}$
---
$x_{\ell}$
---
$x_{r}=x_{k}$
---
$y_{1}$
---
$y_{\ell}$
---
$y_{r}$
---
$R_{1}$
---
$R_{2}$
---
(c) Case $k=r$ and $2\leq\ell\leq r-1$.

$x_{1}=x_{\ell}$
---
$x_{r}=x_{k}$
---
$y_{1}$
---
$y_{\ell}$
---
$y_{r}$
---
$R_{1}$
---
$R_{2}$
---
(d) Case $k=r$ and $\ell=1$.

Figure 4: Illustration of Case 1 of Lemma 8.

Case 1.1. $k=1$.

Exchange $x_{i}$ and $y_{i}$ for all $2\leq i\leq r-1$ for which $i\neq\ell$
and the color of $x_{i}$ differs in $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$. If
$\ell\neq r$, then exchange the unique element of $\\{x_{\ell},y_{\ell}\\}\cap
R_{1}$ with the unique element of $\\{x_{r},y_{r}\\}\cap R_{2}$.

Case 1.2. $2\leq k\leq r-1$.

We may assume that $x_{1}$ and $x_{r}$ are blue in $\mathbf{P}_{2}$ and
$x_{k}$ is red in $\mathbf{P}_{1}$. Exchange $x_{1}$ with $y_{k}$, then
exchange $x_{i}$ and $y_{i}$ for all $2\leq i\leq r-1$ for which
$i\not\in\\{k,\ell\\}$ and the color of $x_{i}$ differs in $\mathbf{P}_{1}$
and $\mathbf{P}_{2}$. Moreover, if $\ell\neq r$ then exchange the unique
element of $\\{x_{\ell},y_{\ell}\\}\cap R_{1}$ with $y_{r}$.

Case 1.3. $k=r$ and $2\leq\ell\leq r-1$.

Exchange the unique element of $\\{x_{\ell},y_{\ell}\\}\cap R_{1}$ with
$x_{r}$. Then exchange $x_{i}$ and $y_{i}$ for all $2\leq i\leq r-1$ for which
$i\neq\ell$ and the color of $x_{i}$ differs in $\mathbf{P}_{1}$ and
$\mathbf{P}_{2}$. Finally, exchange the unique element of
$\\{x_{1},y_{1}\\}\cap B_{2}$ with $y_{r}$.

Case 1.4. $k=r$ and $\ell=1$.

Suppose first that there exists an index $2\leq j\leq r-1$ such that $x_{j}$
has different colors in $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$. We may assume
that $x_{j}$ is red in $\mathbf{P}_{1}$. Exchange $x_{1}$ with $y_{j}$, then
exchange $x_{i}$ and $y_{i}$ for all $2\leq i\leq r-1$ for which $i\neq j$ and
$x_{i}$ has different colors in $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$.
Finally, exchange $y_{1}$ and $x_{r}$, and exchange $x_{j}$ with $y_{r}$. This
results in a strictly monotone exchange sequence that transforms
$\mathbf{P}_{1}$ into $\mathbf{P}_{2}$.

The only remaining case is when $x_{i}$ has the same color in $\mathbf{P}_{1}$
and $\mathbf{P}_{2}$ for all $2\leq i\leq r-1$, we may assume that they are
all red. If $r=2$ then at least one of the exchanges $(x_{1},x_{2})$,
$(x_{1},y_{2})$ is feasible, exchanging them and exchanging the other two
elements afterwards gives a strictly monotone exchange sequence. If $r\geq 3$
then we may assume that $w(y_{2})\leq w(x_{2})$. Consider the exchange
sequence $(x_{1},y_{2})$, $(y_{1},x_{r})$, $(y_{2},y_{r})$ of length $3\leq
r$. The only element that is used twice is $y_{2}$, while $x_{2}$ was not used
at all, hence the sequence has total weight at most $w(E)$ by $w(y_{2})\leq
w(x_{2})$.

Case 2. Both $R_{1}$ and $R_{2}$ are transversal bases.

If $R_{1}$ and $R_{2}$ differ in only one leg, say
$R_{1}\cap\\{x_{i},y_{i}\\}\neq R_{2}\cap\\{x_{i},y_{i}\\}$, then exchanging
$x_{i}$ and $y_{i}$ is feasible. Otherwise we may assume that $x_{1},x_{2}\in
R_{1}$ and $y_{1},y_{2}\in R_{2}$. Exchange $x_{1}$ and $y_{2}$, then exchange
$x_{i}$ and $y_{i}$ for all $3\leq i\leq r$ for which the color of $x_{i}$
differs in $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$. Finally, exchange $x_{2}$
and $y_{1}$.

Case 3. Exactly one of $R_{1}$ and $R_{2}$ is a transversal basis.

We may assume that $R_{1}$ is non-transversal such that both $x_{1}$ and
$y_{1}$ are red and both $x_{r}$ and $y_{r}$ are blue in $\mathbf{P}_{1}$.
Exchange $x_{i}$ and $y_{i}$ for all $2\leq i\leq r-1$ for which the color of
$x_{i}$ differs in $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$. Then exchange the
unique element of $\\{x_{1},y_{1}\\}\cap B_{2}$ with the unique element of
$\\{x_{r},y_{r}\\}\cap R_{2}$.

Concluding the above, in all cases except Case 1.4, the resulting sequence of
exchanges is strictly monotone and uses each element at most twice, hence the
bounds on the length and the total weight follow. In Case 1.4, we showed that
the bounds hold, concluding the proof of the lemma. ∎

Now we consider the case when $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$ miss a
non-tip element, say, $x_{1}$.

######  Lemma 9.

Let $\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ be
compatible pairs of disjoint bases of a rank-$r$ spike $M$ over a ground set
$S$ missing the non-tip element $x_{1}$, and let $w\colon S\to\mathbb{R}_{+}$
be a weight function. Then there exists a sequence of exchanges of length at
most $r$ and total weight at most $w(S-x_{1})$ that transforms
$\mathbf{P}_{1}$ into $\mathbf{P}_{2}$ and uses each element at most twice.

###### Proof.

Let $Z\subseteq S-x_{1}$ be a subset of size $r$. Then $Z$ is a basis of $M$
if and only if one of the followings hold.

  1. 1.

$t\in Z$, $y_{1}\in Z$, $\\{x_{\ell},y_{\ell}\\}\cap Z=\emptyset$ for an index
$2\leq\ell\leq r$, $|\\{x_{i},y_{i}\\}\cap Z|=1$ for all
$i\in\\{2,\dots,r\\}$, $i\neq\ell$.

  2. 2.

$t\in Z$, $y_{1}\not\in Z$, $|\\{x_{i},y_{i}\\}\cap Z|=1$ for all $2\leq i\leq
r$.

  3. 3.

$t\not\in Z$, $y_{1}\in Z$, $|\\{x_{i},y_{i}\\}\cap Z|=1$ for all $2\leq i\leq
r$, $Z$ is not a circuit.

  4. 4.

$t\not\in Z$, $y_{1}\not\in Z$, $\\{x_{\ell},y_{\ell}\\}\subseteq Z$ for an
index $2\leq\ell\leq r$, $|Z\cap\\{x_{i},y_{i}\\}|=1$ for all
$i\in\\{2,\dots,r\\}$, $i\neq\ell$.

We will distinguish two cases based on the coloring of $t$ and $y_{1}$.

Case 1. $t$ and $y_{1}$ have the same color in at least one of
$\mathbf{P}_{1}$ and $\mathbf{P}_{2}$.

We may assume that $t$ and $y_{1}$ are both red, and $x_{r}$ and $y_{r}$ are
both blue in $\mathbf{P}_{1}$. Exchange $x_{i}$ and $y_{i}$ for all $2\leq
i\leq r-1$ for which
$|R_{2}\cap\\{x_{i},y_{i}\\}|=|B_{2}\cap\\{x_{i},y_{i}\\}|=1$ and $x_{i}$ have
different colors in $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$. Let
$\mathbf{P}^{\prime}_{1}=(R^{\prime}_{1},B^{\prime}_{1})$ denote the coloring
obtained this way. Note that all elements have the same color in
$\mathbf{P}^{\prime}_{1}$ and $\mathbf{P}_{2}$, except possibly
$t,y_{1},x_{r},y_{r}$ and at most one leg $\\{x_{\ell},y_{\ell}\\}$. We
distinguish further cases based on the colors of $t$ and $y_{1}$ in
$\mathbf{P}_{2}$.

Case 1.1. $t$ and $y_{1}$ are both red in $\mathbf{P}_{2}$.

Let $\ell$ denote the unique index for which both $x_{\ell}$ and $y_{\ell}$
are blue in $\mathbf{P}_{2}$. If $\ell=r$, we need no further exchanges. If
$\ell\neq r$, exchange the element of the leg $\\{x_{\ell},y_{\ell}\\}$ which
is red in $\mathbf{P}_{1}$ with the element of leg $\\{x_{r},y_{r}\\}$ which
is red in $\mathbf{P}_{2}$.

Case 1.2. Exactly one of $t$ and $y_{1}$ is red in $\mathbf{P}_{2}$. In this
case exactly one of $t$ and $y_{1}$ and exactly one of $x_{r}$ and $y_{r}$
need to change colors and their exchange is feasible.

Case 1.3 Both $t$ and $y_{1}$ are blue in $\mathbf{P}_{2}$.

Let $\ell$ denote the unique index for which $x_{\ell}$ and $y_{\ell}$ are
both red in $\mathbf{P}_{2}$. If $\ell=r$, then consider the exchange
sequences $(y_{1},x_{r})$, $(t,y_{r})$ and $(y_{1},y_{r})$, $(t,x_{r})$ of
length two. At least one of them is feasible since at most one of
$B^{\prime}_{1}-x_{r}+y_{1}$ and $B^{\prime}_{1}-y_{r}+y_{1}$ forms a circuit
by $|(B^{\prime}_{1}-x_{r}+y_{1})\cap(B^{\prime}_{1}-y_{r}+y_{1})|=r-1$.
Adding this to the exchange sequence that transformed $\mathbf{P}_{1}$ into
$\mathbf{P}^{\prime}_{1}$ we get a strictly monotone exchange sequence from
$\mathbf{P}_{1}$ to $\mathbf{P}_{2}$.

If $2\leq\ell\leq r-1$, then we may assume that $x_{\ell}$ is red and
$y_{\ell}$ is blue in $\mathbf{P}_{1}$, while $x_{r}$ is red and $y_{r}$ is
blue in $\mathbf{P}_{2}$. If the exchange $(y_{1},x_{r})$ is feasible, then
adding $(y_{1},x_{r})$, $(t,y_{\ell})$ to the exchange sequence that
transformed $\mathbf{P}_{1}$ into $\mathbf{P}^{\prime}_{1}$ results in a
strictly monotone exchange sequence. From now on we assume that
$(y_{1},x_{r})$ is not feasible which means that $B^{\prime}_{1}-x_{r}+y_{1}$
forms a circuit. As the intersection of two circuits cannot have size $r-1$,
this implies that both $B^{\prime}_{1}-y_{r}+y_{1}$ and
$B^{\prime}_{1}-\\{x_{r},y_{\ell}\\}+\\{x_{\ell},y_{1}\\}$ are bases.

If $w(x_{\ell})\geq w(y_{r})$, then extend the exchange sequence from
$\mathbf{P}_{1}$ to $\mathbf{P}^{\prime}_{1}$ by the exchanges
$(y_{1},y_{r})$, $(y_{\ell},t)$, $(x_{r},y_{r})$. The feasibility of these
exchanges follows from $B^{\prime}_{1}-y_{r}+y_{1}$ being a basis. The total
length of the exchange sequence is at most $(r-3)+3=r$. The sequence does not
use $x_{\ell}$, it uses $y_{r}$ twice, and all the other elements at most
once, so it has weight at most $w(E)$ by the assumption $w(x_{\ell})\geq
w(y_{r})$.

If $w(x_{\ell})<w(y_{r})$, then extend the exchange sequence from
$\mathbf{P}_{1}$ to $\mathbf{P}^{\prime}_{1}$ by the exchanges
$(x_{\ell},x_{r})$, $(y_{1},y_{\ell})$, $(x_{\ell},t)$. The feasibility of
these exchanges follows from
$B^{\prime}_{1}-\\{x_{r},y_{\ell}\\}+\\{x_{\ell},y_{1}\\}$ being a basis. The
total length of the exchange sequence is at most $(r-3)+3=r$. The sequence
does not use $y_{r}$, it uses $x_{\ell}$ twice, and all the other elements at
most once, so it has weight at most $w(E)$ by the assumption
$w(x_{\ell})<w(y_{r})$.

Case 2. $t$ and $y_{1}$ have different colors in both $\mathbf{P}_{1}$ and
$\mathbf{P}_{2}$.

We may assume that $y_{1}$ is red and $t$ is blue in $\mathbf{P}_{1}$. Observe
that each leg contains one red and one blue element in any of the colorings
$\mathbf{P}_{1}$ and $\mathbf{P}_{2}$. If every leg is colored the same way in
$\mathbf{P}_{1}$ and $\mathbf{P}_{2}$, then the exchange distance of
$\mathbf{P}_{1}$ and $\mathbf{P}_{2}$ is at most one. Hence we may assume that
$x_{2}\in B_{1}\cap R_{2}$ and $y_{2}\in B_{2}\cap R_{1}$.

Case 2.1. $y_{1}$ is blue and $t$ is red in $\mathbf{P}_{2}$.

Exchange $x_{2}$ with $y_{1}$. After this step, both $y_{1}$ and $t$ is blue,
hence we can exchange $x_{i}$ and $y_{i}$ for all $3\leq i\leq r$ for which
$x_{i}$ has different colors in $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$.
Finally, exchange $y_{2}$ with $t$.

Case 2.2. $y_{1}$ is red and $t$ is blue in $\mathbf{P}_{2}$.

If $w(y_{1})\leq w(t)$, exchange $y_{1}$ with $x_{2}$. After this step,
exchange $x_{i}$ and $y_{i}$ for all $3\leq i\leq r$ for which $x_{i}$ has
different colors in $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$. Finally, exchange
$y_{1}$ with $y_{2}$. This exchange sequence does not use $t$, uses $y_{1}$
twice and all the other elements at most once. These imply that its length is
at most $r$ and total weight is at most $w(E)$ by $w(y_{1})\leq w(t)$.

If $w(y_{1})>w(t)$, exchange $t$ with $y_{2}$. After this step, exchange
$x_{i}$ and $y_{i}$ for all $3\leq i\leq r$ for which $x_{i}$ has different
colors in $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$. Finally, exchange $t$ with
$x_{2}$. This exchange sequence does not use $y_{1}$, uses $t$ twice and all
the other elements at most once. These imply that its length is at most $r$
and total weight is at most $w(E)$ by $w(y_{1})>w(t)$.

Concluding the above, in all cases except Cases 1.3 and 2.2, the resulting
sequence of exchanges is strictly monotone and uses each element at most
twice, hence the bounds on the length and the total weight follow. In Cases
1.3 and 2.2, we showed that the bounds hold, concluding the proof of the
lemma. ∎

######  Theorem 10.

Let $\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ be
compatible pairs of disjoint bases of a rank-$r$ spike $M$ over a ground set
$S$, and let $w\colon S\to\mathbb{R}_{+}$ be a weight function. Then there
exists a sequence of exchanges of length at most $r$ and total weight at most
$w(S)$ that transforms $\mathbf{P}_{1}$ into $\mathbf{P}_{2}$ and uses each
element at most twice.

###### Proof.

The theorem follows by combining Lemmas 8 and 9. ∎

######  Remark 11.

The orientation of colorings of wheels played a crucial role in the existence
of strictly monotone exchange sequences. In particular, among any three basis
pairs there exists two having the same orientation, and for those there exists
a strictly monotone sequence of exchanges. Spikes are interesting because one
can define an arbitrarily large number of colorings without a strictly
monotone exchange sequence between any two of them.

To see this, consider the spike333This matroid is interesting on its own as it
is isomorphic to the unique rank-$r$ binary spike, see [18] for details. $M$
defined by

$\mathcal{C}_{3}\coloneqq\\{C\subseteq S:\ |C|=r,\ |C\cap\\{x_{i},y_{i}\\}|=1\
\text{for $1\leq i\leq r$},\ |C\cap\\{x_{1},\dots,x_{r}\\}|\ \text{is
odd}\\}.$

Consider all pairs $(R,B)$ of disjoint sets of size $r$ for which $y_{1}\in
R$, $t\in B$, $|R\cap\\{x_{i},y_{i}\\}|=|B\cap\\{x_{i},y_{i}\\}|=1$ for all
$2\leq i\leq r$, and $|R\cap\\{x_{2},\dots,x_{r}\\}|$ is even. There are
$2^{r-2}$ such pairs. Note that all such pairs $(R,B)$ are colorings of the
matroid obtained from $M$ by deleting $x_{1}$. Further observe that any
feasible exchange uses at least one of $y_{1}$ and $t$. Indeed, exchanging
$x_{i}$ with $y_{j}$ for some $2\leq i,j\leq r$ results in an odd number of
red elements in $\\{x_{2},\dots,x_{r}\\}$, meaning that the red elements form
a circuit, showing that the exchange is non-feasible. Exchanging $x_{i}$ with
$x_{j}$ or $y_{i}$ with $y_{j}$ for some $2\leq i,j\leq r$, $i\neq j$ results
in either $\\{t,x_{i},y_{i}\\}$ or $\\{t,x_{j},y_{j}\\}$ forming a blue
circuit, hence the exchange is non-feasible. This implies that there exists no
strictly monotone exchange sequence between any two distinct colorings of this
form.

##  6 Conclusions

In this paper, we proposed a weighted generalization of Hamidoune’s conjecture
on the exchange distance of compatible basis pairs. We verified the conjecture
for strongly base orderable matroids, and its strengthening in which the
exchange sequence had small length and weight simultaneously for split
matroids, graphic matroids of wheels, and spikes. For the latter three
classes, our proofs also imply polynomial-time444In matroid algorithms, it is
usually assumed that the matroids are given by independence oracles, and the
complexity of the algorithm is measured by the number of oracle calls and
other conventional elementary steps. algorithms that determine the required
exchange sequences. For strongly base orderable matroids, we get a similar
result if, for any pair of bases, a bijection $\phi$ between them ensured by
strongly base orderability can be computed in polynomial time.

Motivated by Lemma 6, it would be tempting to formulate a conjecture stating
that there always exists an exchange sequence that has small weight with
respect to two weight functions $w_{1}$ and $w_{2}$ simultaneously. However,
this is not true in general. Let $G=(V,E)$ be a complete graph on four
vertices with edge set $E=\\{a,b,c,d,e,f\\}$, and let $M$ be the graphic
matroid of $G$, see Figure 5. Interestingly, $G$ is a wheel, but $M$ can be
also obtained by deleting the tip of a spike. Consider two colorings
$\mathbf{P}_{1}=(R_{1},B_{1})$ and $\mathbf{P}_{2}=(R_{2},B_{2})$ of $G$ where
$R_{1}=\\{a,b,c\\}$, $B_{1}=\\{d,e,f\\}$, $R_{2}=\\{b,d,f\\}$ and
$B_{2}=\\{a,c,e\\}$. It is not difficult to check that any sequence of
exchanges that transforms $\mathbf{P}_{1}$ into $\mathbf{P}_{2}$ uses at least
one of the edges $b$ and $e$ twice. This implies that if we set
$w_{1}(b)\coloneqq 1$ and $0$ otherwise, and we set $w_{2}(e)\coloneqq 1$ and
$0$ otherwise, then any exchange sequence has $w_{1}$-weight or $w_{2}$-weight
at least $2=2w_{1}(E)=2w_{2}(E)$.

(a) Coloring $\mathbf{P}_{1}=(R_{1},B_{1})$ of $K_{4}$.

(b) Coloring $\mathbf{P}_{2}=(R_{2},B_{2})$ of $K_{4}$.

Figure 5: Example showing that the statement of Lemma 6 is not true in
general. Any exchange sequence that transforms $(R_{1},B_{1})$ into
$(R_{2},B_{2})$ uses one of $b$ and $e$ twice. If $w_{1}(b)=1$ and $0$
otherwise, and $w_{2}(e)=1$ and $0$ otherwise, then any sequence violates the
weight constraint for at least one the weight functions.

On the other hand, no counterexample is known for the case when $w_{2}\equiv
1$, that is, when one would like to find an exchange sequence that has small
length and weight simultaneously. Even more, both Theorems 7 and 10 ensured
the existence of an exchange sequence that uses each element at most twice. A
rather optimistic conjecture would state the existence of a sequence of
exchanges that, besides having small length and weight, also has this
property.

#### Acknowledgement.

The authors are grateful to Attila Bernáth, Zoltán Király, Yusuke Kobayashi,
and Eszter Szabó for helpful discussions.

Tamás Schwarcz was supported by the ÚNKP-22-3 New National Excellence Program
of the Ministry for Culture and Innovation from the source of the National
Research, Development and Innovation Fund. 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] S. D. Andres, W. Hochstättler, and M. Merkel.  On a base exchange game on bispanning graphs.  Discrete Applied Mathematics, 165:25–36, 2014.
  * [2] K. Bérczi, T. Király, T. Schwarcz, Y. Yamaguchi, and Y. Yokoi.  Hypergraph characterization of split matroids.  Journal of Combinatorial Theory, Series A, 194:105697, 2023.
  * [3] K. Bérczi and T. Schwarcz.  Exchange distance of basis pairs in split matroids.  arXiv preprint arXiv:2203.01779, 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] R. Cordovil and M. L. Moreira.  Bases-cobases graphs and polytopes of matroids.  Combinatorica, 13(2):157–165, 1993.
  * [7] H. H. Crapo and G.-C. Rota.  On the Foundations of Combinatorial Theory: Combinatorial Geometries.  MIT press Cambridge, Mass., 1970.
  * [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] H. Gabow.  Decomposing symmetric exchanges in matroid bases.  Mathematical Programming, 10(1):271–276, 1976.
  * [11] M. Joswig and B. Schröter.  Matroids from hypersimplex splits.  Journal of Combinatorial Theory, Series A, 151:254–284, 2017.
  * [12] 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.
  * [13] D. Kotlar.  On circuits and serial symmetric basis-exchange in matroids.  SIAM Journal on Discrete Mathematics, 27(3):1274–1286, 2013.
  * [14] D. Kotlar and R. Ziv.  On serial symmetric exchanges of matroid bases.  Journal of Graph Theory, 73(3):296–304, 2013.
  * [15] M. Lasoń and M. Michałek.  On the toric ideal of a matroid.  Advances in Mathematics, 259:1–12, 2014.
  * [16] D. Mayhew, M. Newman, D. Welsh, and G. Whittle.  On the asymptotic proportion of connected matroids.  European Journal of Combinatorics, 32(6):882–890, 2011.
  * [17] S. McGuinness.  Frame matroids, toric ideals, and a conjecture of White.  Advances in Applied Mathematics, 118:102042, 2020.
  * [18] J. Oxley.  Matroid Theory, volume 21 of Oxford Graduate Texts in Mathematics.  Oxford University Press, Oxford, second edition, 2011.
  * [19] N. L. White.  A unique exchange property for bases.  Linear Algebra and its Applications, 31:81–91, 1980.
  * [20] D. Wiedemann.  Cyclic base orders of matroids.  Manuscript, 1984.


# Leveraging Emotion-specific Features to Improve Transformer Performance for
Emotion Classification

Atharva Kshirsagar* sidnerlikaraditi6, nikhilkhodake2002} @gmail.com Shaily
Desai* sidnerlikaraditi6, nikhilkhodake2002} @gmail.com Aditi Sidnerlikar
sidnerlikaraditi6, nikhilkhodake2002} @gmail.com Nikhil Khodake
sidnerlikaraditi6, nikhilkhodake2002} @gmail.com Manisha Marathe
<EMAIL_ADDRESS>
###### Abstract

††*Equal Contribution

This paper describes team PVG’s AI Club’s approach to the Emotion
Classification shared task held at WASSA $2022$. This Track $2$ sub-task
focuses on building models which can predict a multi-class emotion label based
on essays from news articles where a person, group or another entity is
affected. Baseline transformer models have been demonstrating good results on
sequence classification tasks, and we aim to improve this performance with the
help of ensembling techniques, and by leveraging two variations of emotion-
specific representations. We observe better results than our baseline models
and achieve an accuracy of $0.619$ and a macro F1 score of $0.520$ on the
emotion classification task.

##  1 Introduction

Rapid growth in the availability of human-annotated text documents has led to
an increase in methodologies for tasks such as classification, clustering and
knowledge extraction. A multitude of sources have enabled public access to
structured and semi-structured data comprising of news stories, written
repositories, blog content, among countless other roots of information.
(Bostan and Klinger, 2018) showed that the task of emotion classification has
emerged from being purely research oriented to being of vital importance in
fields like dialog systems, intelligent agents, and analysis and diagnosis of
mental disorders.

Humans themselves sometimes find it tough to comprehend the various layers of
subtlety in emotions, and hence there has been only a limited amount of prior
research revolving around emotion classification. It has been noted that
larger deep learning models can also find it quite challenging to fully grasp
the nuances and underlying context of human emotion.

With the advent of Transformer (Vaswani et al., 2017) models, there has been
an increase in performance for emotion classification of text-based models.
Most transformer-based language models (Devlin et al., 2018; Raffel et al.,
2019; Radford et al., 2018) are pretrained on various self-supervised
objectives. Combining transformer based sentence representations with domain-
specialised representations for improving performance on the specific task has
been successfully used in across many NLP domains (Peinelt et al., 2020;
Poerner et al., 2020; Zhang et al., 2021). Building on these foundations, we
propose a similar approach to the task of Emotion classification.

In this paper, we posit a solution to the WASSA $2022$ Shared Task on Empathy
Detection, Emotion Classification and Personality Detection, specifically
Track-$2$, emotion classification. We propose a hybrid model where we combine
information from various entities to create a rich final representation of
each datapoint, and the observed results show promise in combining the
Transformer output with the emotion-specific embeddings and NRC features.

The rest of the paper is organized in the following manner: Section 2 offers
an overview into the dataset on Empathetic concern in news stories, Section 3
goes in depth about our proposed methodology with subsections describing the
individual constituent modules. Section 4 explains the experimental and
training setup along with the baselines used; Section 5 elucidates the
observed results, and Section 6 concludes this study.

##  2 Dataset

The dataset provided by the organizers consists of $1860$ essays in the
training set, $270$ in the dev set and $525$ in the test set. Each of these
essays has been annotated for empathy and empathy scores, distress and
distress scores, emotion, personality feature and interpersonal reactivity
features. Since this paper describes an approach only to the Emotion
classification task, we shall only describe the data for said subtask. Each
essay has been assigned an emotion class similar to classes in (Ekman, 1992).
Table 1 provides a description on the training, validation and testing subset,
and Figure 1 shows the distribution of the training data among the various
emotion classes.

Set | Essays
---|---
Training | 1860
Validation | 270
Testing | 525
Total | 2655
Table 1: Total datapoints for every set Figure 1: Distribution of the various
classes among the Training Dataset

##  3 Methodology

###  3.1 RoBERTa

We make use of the pretrained RoBERTa base model (Liu et al., 2019) for this
task. RoBERTa provides contextualized essay-level representations which can
capture context sensitive information better than static representations. For
each essay $\mathnormal{E}$ in our corpus, we obtain a $768$ dimensional
representation $\mathnormal{R}$, encoded using the CLS token in the final
hidden layer of the RoBERTa base model. We further process this representation
$\mathnormal{R}$ with Linear and Dropout layers before concatenating it with
our emotion-specific representations.

$\mathnormal{R}=\mathnormal{RoBERTa}(\mathnormal{E})\in\mathbb{R^{\mathnormal{d_{1}}}}$
(1)

Figure 2: Model Architecture

###  3.2 Emotion-Enriched Word Embeddings(EWE)

(Labutov and Lipson, 2013; Bansal et al., 2014),argue that the effectiveness
of word embeddings is highly task dependent. To obtain word embeddings
specific for emotion classification, we used the emotion-enriched embeddings
from (Agrawal et al., 2018). The weight matrix was made by mapping the
vocabulary from our dataset to the $300$ dimensional corresponding vector in
the pre-trained embedding file. Each essay was mapped to the embedding matrix
into a final representation shape of ($100$,$300$). This representation was
passed through $2$ Conv1d and $2$ Maxpool layers to obtain a $16$ dimensional
feature vector $\mathnormal{C}\in\mathbb{R^{\mathnormal{d_{2}}}}$.

###  3.3 NRC Representation

The NRC emotion intensity lexicon (Mohammad, 2018) is a collection of close to
$\mathnormal{10,000}$ words associated with a distinct real valued intensity
score assigned for eight basic emotions. Incorporating this lexicon in
classification tasks has been proven to boost performance (Kulkarni et al.,
2021). Of the $\mathnormal{8}$ basic emotions in the lexicon, $\mathnormal{6}$
emotions-anger, joy, sadness, disgust, fear and surprise coincide with the
given dataset and hence lexical features for only these features were
considered. For every essay in the dataset, we calculate the value for one
emotion by summing the individual scores for

Model | Accuracy | Macro-F1 Score
---|---|---
| Training | Validation | Training | Validation
Vanilla RoBERTa | 0.601 | 0.540 | 0.513 | 0.452
RoBERTa + EWE | 0.684 | 0.608 | 0.561 | 0.499
RoBERTA + NRC + EWE | 0.693 | 0.619 | 0.618 | 0.520
Table 2: Resulting metrics on baseline models as compared to our methodology

every word $\mathnormal{W}$ in the essay that occurs in the NRC lexicon. We
then create a six dimensional vector $\mathnormal{N}$ corresponding to that
essay which consists of the scores of the emotions in our dataset.

For a datapoint $\mathnormal{E}$, the six values of $\mathnormal{S_{emotion}}$
and the feature vector $\mathnormal{N}$ was constructed in the following
manner:

$\mathnormal{S_{\mathnormal{emotion}}}=\sum\mathnormal{W_{\mathnormal{emotion}}}(\mathnormal{W}\in\mathnormal{E})$
(2)

$N=[S_{\mathnormal{anger}};S_{\mathnormal{joy}};.....;S_{\mathnormal{surprise}}]\in\mathbb{R^{\mathnormal{d_{3}}}}$
(3)

###  3.4 Combined Representation and Classification

The feature vectors obtained from the RoBERTa ($\mathnormal{R}$), Emotion-
Enriched Embeddings ($\mathnormal{C}$) and NRC ($\mathnormal{N}$)were
concatenated to obtain the final representation ($\mathnormal{F}$).

$\mathnormal{F}=[\mathnormal{R};\mathnormal{C};\mathnormal{N}]\in\mathbb{R^{\mathnormal{d_{1}+d_{2}+d_{3}}}}$
(4)

This representation is then passed through a single Linear layer with the
Softmax activation. Figure 2 depicts the model architecture in detail.

##  4 Experimental Setup

###  4.1 Data Preparation

Standard text cleaning steps like removing numbers, special characters,
punctuation, accidental spaces, etc. were applied to each essay in the corpus.
Stopwords were removed using the nltk (Loper and Bird, 2002) library. Every
essay was tokenized to a maximum length of $100$, and essays larger than this
length were truncated. No standardization was done in the case of NRC scores,
as we wanted to feed our model a vector of raw emotion-intensity scores for
each of the six emotions considered in our NRC representation.

###  4.2 Training Setup

We used the pretrained ’roberta-base’ model from the Huggingface Transformers
111https://huggingface.co/transformers/ library. All other modules used in our
methodology were built using PyTorch. As observed by (Kulkarni et al., 2021),
we also found that the Hyperbolic Tangent(Tanh) activation function worked
better than ReLU, and hence we used the Tanh activation for all layers in our
model. The model was trained using an AdamW optimizer (Loshchilov and Hutter,
2019) with a learning rate of $0.001$ and beta values set to $\beta_{1}=0.9$,
$\beta_{2}=0.99$ and the loss used was cross entropy loss. Additionally, early
stopping was used if the validation loss does not decrease after 10 successive
epochs. The batch size was set to $64$ for both Baseline models as well as the
proposed model. A single Nvidia P100-16GB GPU provided by Google Colab was
used to train all models.

###  4.3 Baselines

Our goal in this work is to examine if concatenating emotional-specific
features to pre-existing transformer models leads to an increase in the
emotion classification performance of these models. Hence, we compare our
proposed methodology to the vanilla RoBERTa model, as well as RoBERTa + Ewe
for the emotion classification subtask.

##  5 Results and Discussion

The results for the emotion prediction task on the validation set are given in
Table 2. There was no use of validation data during the training process, and
the provided validation data was used as unseen testing data to benchmark the
models.The official metric for Track $2$ of the shared task was the macro F1
score. To ensure fair comparison, the validation set results have been
averaged over $3$ runs for each model. The proposed model shows a $7$%
increase in macro F1 scores and $8$% increase in accuracy over the vanilla
RoBERTa model. The proposed model also shows the effectiveness of adding the
NRC representations described in section 3.3 as it performs slightly better
than the RoBERTa + Emotion Enriched word embeddings model. We attribute this
increase in performance to the task-specific representations of essays used in
our system. During the training process, it was observed that the performance
of all models was highly susceptible to how they were initialized, and we
received a large range of results across different seeds. As a result, a true
assessment of our method can only be made in comparison to baseline models
with the same seed, as we have done in this study.

##  6 Conclusion

The goal of this study was to examine and enhance the performance of
transformer models using only the Empathetic Concern in News Stories dataset
that was provided to us, with the prospective of testing our method on a
bigger dataset in the future. We proposed a model ensemble which combined the
transformer feature vector with the emotion-intensive word embeddings along
with the word-specific features obtained from the NRC lexicon. We demonstrate
results that outperform the baseline vanilla RoBERTa model, and attest that
combining domain-specific features can indeed improve performance on a task as
involute as emotion classification.

## References

  * Agrawal et al. (2018) Ameeta Agrawal, Aijun An, and Manos Papagelis. 2018.  Learning emotion-enriched word representations.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 950–961, Santa Fe, New Mexico, USA. Association for Computational Linguistics.
  * Bansal et al. (2014) Mohit Bansal, Kevin Gimpel, and Karen Livescu. 2014.  Tailoring continuous word representations for dependency parsing.  In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 809–815, Baltimore, Maryland. Association for Computational Linguistics.
  * Bostan and Klinger (2018) Laura-Ana-Maria Bostan and Roman Klinger. 2018.  An analysis of annotated corpora for emotion classification in text.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 2104–2119, Santa Fe, New Mexico, USA. Association for Computational Linguistics.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Ekman (1992) Paul Ekman. 1992.  An argument for basic emotions.  _Cognition and Emotion_ , 6(3-4):169–200.
  * Kulkarni et al. (2021) Atharva Kulkarni, Sunanda Somwase, Shivam Rajput, and Manisha Marathe. 2021.  PVG at WASSA 2021: A multi-input, multi-task, transformer-based architecture for empathy and distress prediction.  In _Proceedings of the Eleventh Workshop on Computational Approaches to Subjectivity, Sentiment and Social Media Analysis_ , pages 105–111, Online. Association for Computational Linguistics.
  * Labutov and Lipson (2013) Igor Labutov and Hod Lipson. 2013.  Re-embedding words.  In _Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 489–493, Sofia, Bulgaria. Association for Computational Linguistics.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _ArXiv_ , abs/1907.11692.
  * Loper and Bird (2002) Edward Loper and Steven Bird. 2002.  Nltk: The natural language toolkit.  In _Proceedings of the ACL-02 Workshop on Effective Tools and Methodologies for Teaching Natural Language Processing and Computational Linguistics - Volume 1_ , ETMTNLP ’02, page 63–70, USA. Association for Computational Linguistics.
  * Loshchilov and Hutter (2019) Ilya Loshchilov and Frank Hutter. 2019.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_.
  * Mohammad (2018) Saif Mohammad. 2018.  Word affect intensities.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018)_ , Miyazaki, Japan. European Language Resources Association (ELRA).
  * Peinelt et al. (2020) Nicole Peinelt, Dong Nguyen, and Maria Liakata. 2020.  tBERT: Topic models and BERT joining forces for semantic similarity detection.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7047–7055, Online. Association for Computational Linguistics.
  * Poerner et al. (2020) Nina Poerner, Ulli Waltinger, and Hinrich Schütze. 2020.  E-BERT: Efficient-yet-effective entity embeddings for BERT.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 803–818, Online. Association for Computational Linguistics.
  * Radford et al. (2018) Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. 2018.  Improving language understanding by generative pre-training.
  * Raffel et al. (2019) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2019.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _arXiv preprint arXiv:1910.10683_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc.
  * Zhang et al. (2021) Jinpeng Zhang, Baijun Ji, Nini Xiao, Xiangyu Duan, Min Zhang, Yangbin Shi, and Weihua Luo. 2021.  Combining static word embeddings and contextual representations for bilingual lexicon induction.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 2943–2955, Online. Association for Computational Linguistics.