# Extremal values of degree-based entropies of bipartite graphs

Stijn Cambie Extremal Combinatorics and Probability Group (ECOPRO), Institute
for Basic Science (IBS), Daejeon, South Korea, supported by the Institute for
Basic Science (IBS-R029-C4), E-mail<EMAIL_ADDRESS>or
<EMAIL_ADDRESS>Yanni Dong School of Mathematics and Statistics,
Northwestern Polytechnical University, P.R. China, and Faculty of Electrical
Engineering, Mathematics and Computer Science, University of Twente, The
Netherlands, supported by National Natural Science Foundation of China
(12071370, 12131013 and U1803263) and China Scholarship Council
(202006290070), E-mail<EMAIL_ADDRESS> Matteo Mazzamurro
Department of Computer Science, University of Warwick, UK, supported by: EPSRC
Centre for Doctoral Training in Urban Science and Progress (EP/L016400/1),
EPSRC DTP (EP/N509796/1), E-mail<EMAIL_ADDRESS>
###### Abstract

We characterize the bipartite graphs that minimize the (first-degree based)
entropy, among all bipartite graphs of given size, or given size and (upper
bound on the) order. The extremal graphs turn out to be complete bipartite
graphs, or nearly complete bipartite. Here we make use of an equivalent
representation of bipartite graphs by means of Young tableaux, which make it
easier to compare the entropy of related graphs. We conclude that the general
characterization of the extremal graphs is a difficult problem, due to its
connections with number theory, but they are easy to find for specific values
of the order $n$ and size $m$. We also give a direct argument to characterize
the graphs maximizing the entropy given order and size. We indicate that some
of our ideas extend to other degree-based topological indices as well.

##  1 Introduction

The first-degree based graph entropy of a graph is the Shannon entropy of its
degree sequence normalized by the degree sum. In the remaining of the paper,
it is just referred to as entropy. It has attracted significant attention in
organic chemistry, as measures of uniformity of a graph’s structural aspect of
interest [18, 5, 6]. The interpretation of the entropy of a particular graph
depends on knowing the extremal values. In this paper, we continue our work
[2, 3] on determining the extremal graphs (and thus extremal values) for the
entropy among all graphs satisfying some natural restrictions. Minimizing
(resp. maximizing) the entropy corresponds to maximizing (resp. minimizing)
the function $h(G)=\sum_{i}d_{i}\log(d_{i})$, where $(d_{i})_{1\leq i\leq n}$
is the degree sequence of the graph $G$, where $G$ ranges over all members of
a class of graphs. This is since the entropy $I(G)$ equals
$\log(2m)-\frac{1}{2m}h(G),$ where $m$ is the size (number of edges) of $G$.
Here we determine the graphs with extremal entropy among all bipartite graphs
with given size $m$, or given size $m$ and (upper bound on the) order $n$. The
maximum value for the entropy is obtained by the graphs for which the degree
sequence is as balanced as possible. This is a corollary of Karamata’s
inequality. Note that the random graphs $G_{n,m}$ and $G_{n,p}$ are close to
balanced, i.e. the maximum degree $\deg_{max}$ and the minimum degree
$\deg_{min}$ are nearly the same for $m=\Theta(n^{2})$, and thus have an
entropy which is almost maximal. This is in line with the intuition that
entropy is a measure for randomness.

In graph theory, bipartite graphs are one of the main classes to investigate,
because it finds several applications in pure and applied Mathematics. Hall’s
Matchings Theorem is a famous theorem on bipartite graphs with several
applications in scheduling- and matching problems, e.g. the kidney matching
process. When edges represent bonds between positive and negative charges, the
resulting graph is bipartite. Furthermore, results on bipartite graphs often
lead to results on more general classes of graphs. A famous example is given
by the Kahn-Zhao theorem, where Kahn [13] considered a problem on the maximum
number of independent sets for bipartite graphs and Zhao [21] reduced the
general case to the bipartite case.

We will show that, given the size $m$, the bipartite graphs attaining the
minimum entropy are precisely the complete bipartite graphs of size $m$. So if
$m$ has $\sigma(m)$ divisors, there are
$\left\lceil\frac{\sigma(m)}{2}\right\rceil$ non-isomorphic extremal graphs,
all which are of the form $K_{q,y}$ with $yq=m.$

######  Theorem 1.

If $G=(U\cup V,E)$ is a bipartite graph of size $m$, then $h(G)\leq m\log m$.
Equality occurs if and only if $G$ is a complete bipartite graph.

When there is an upper bound $n$ on the order (one can extend with isolated
vertices since $0\log(0)=0$), such that $m$ cannot be written as a product
$yq$ with $y+q\leq n$, the problem is harder. We will prove that the extremal
bipartite graphs given the size $m$ and order no more than $n$, are of the
form $B(n,m,y)$ for some $1\leq y\leq\sqrt{m}$. Here $B(n,m,y)$ is the graph
formed by connecting an additional vertex with $m-yq$ vertices in $V$ of
$K_{q,y}=(U\cup V,E),$ where $q=\left\lfloor\frac{m}{y}\right\rfloor.$

We will also consider a different representation of bipartite graphs by means
of Young tableaux, as it simplifies the description of the graph operations
needed in the proofs. For a bipartite graph $G=(U\cup V,E)$, let us write
$U=\\{u_{1},u_{2},\ldots,u_{x}\\}$ and $V=\\{v_{1},v_{2},\ldots,v_{y}\\}$ such
that $\deg u_{i}\geq\deg u_{j}$ and $\deg v_{i}\geq\deg v_{j}$ whenever $i\leq
j.$ Let $y_{i}=\deg(u_{i})$ and $x_{j}=\deg(v_{j})$ for every $1\leq i\leq x$
and $1\leq j\leq y.$ We associate the tableau $T$ which contains a cell
$(i,j)$ if and only if $u_{i}v_{j}\in E.$ Note that this gives a one-to-one
correspondence between tableaux and bipartite graphs.

An example of an extremal bipartite graph with $n=10$ and $m=22$ has been
represented in these two ways in Figure 1. Remark that the number of cells in
column $i$ corresponds to the degree of $u_{i}$ and the number of cells in row
$j$ equals the degree of $v_{j}.$

$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$$v_{4}$$v_{3}$$v_{2}$$v_{1}$ (a)
Graph representation

centertableaux [5] &

[5]

[6]

[6]

[4] [4] [4] [4] [4] [2]

(b) Associated Young tableau

Figure 1: Two representations of the extremal bipartite $(10,22)$-graph
$B(10,22,4)$

In Section 2, we prove that the bipartite graphs minimizing the entropy given
the size are exactly the complete bipartite graphs. We give two different
approaches to prove this. One of them is a proof by induction, and the other
one consists in proving that the associated tableau has to be a rectangle. In
Section 3 we study the possible extremal bipartite graphs given order $n$ and
size $m$, by proving that under certain restrictions they are of the form
$B(n,m,y)$ and we estimate the value of $h$ for these graphs. Next, in Section
4, we prove that the extremal graphs are indeed of the form $B(n,m,y).$ For
this, we use the equivalent representation with the Young tableaux and give
local operations that decrease the entropy (equivalently, such that $h$
increases). Furthermore, in Section 5 we remark that some of the ideas can be
applied to other chemical indices, also called degree-based topological
indices, such as e.g. the Second Zagreb index and Reciprocal Randic index.
Just as has been done in [1], we notice that certain results hold more
generally and we give the essence of the proofs of some known results. Here,
we give short proofs for the main results in [12] and [7] about the graphs and
bipartite graphs maximizing the entropy in the more general context of a class
of chemical indices. Finally, in Section 6, we give some conclusions on the
precise extremal graphs $B(n,m,y)$. We do this based on computational results
and the estimates in Section 3, as well as some number theory.

###  1.1 Preliminary definitions and results

In this subsection, we define the notions and help functions we will
frequently use, as well as give some basic results.

######  Definition 2.

We define the function $f(x)=x\cdot\log(x)$ for $x\geq 0$. Here $\log$ denotes
the natural logarithm and $f(0):=0.$ For a graph $G$ with degree sequence
$(d_{i})_{1\leq i\leq n}$, we define $h(G)=\sum_{i}f(d_{i}).$ The entropy
$I(G)$ of a graph of size $m$ equals $\log(2m)-\frac{1}{2m}h(G).$

In the following definition of majorization and the inequality of Karamata, we
only consider non-increasing sequences.

######  Definition 3.

A sequence $(x_{i})_{1\leq i\leq n}$ majorizes the sequence $(y_{i})_{1\leq
i\leq n}$ if and only if $\sum_{1\leq i\leq j}x_{i}\geq\sum_{1\leq i\leq
j}y_{i}$ for every $1\leq j\leq n$ and equality does hold for $j=n$.

######  Theorem 4 (Karamata’s inequality, [14]).

Let $(x_{i})_{1\leq i\leq n}$ be a sequence majorizing the sequence
$(y_{i})_{1\leq i\leq n}$. For every convex function $g$ we have $\sum_{1\leq
i\leq n}g(x_{i})\geq\sum_{1\leq i\leq n}g(y_{i}).$ Furthermore this inequality
is strict if the sequences are not equal and $g$ is a strictly convex
function. For concave functions, the same holds with the opposite sign.

A corollary of Karamata’s inequality is the following

######  Corollary 5.

Let $G$ and $G^{\prime}$ be two graphs such that the degree sequence of
$G^{\prime}$ majorizes the degree sequence of $G$. Then $h(G^{\prime})\geq
h(G).$ Furthermore, equality occurs if and only if the two degree sequences
are equal.

This was also observed by Ghalavand et al. [8].

We will also make use of difference graphs, which were introduced by Hammer et
al. [11]. The following equivalent characterization is due to Mahadev and
Peled [16].

######  Theorem 6 ([16]).

Let $G=(U\cup V,E)$ be a bipartite graph. The graph $G$ is a difference graph
if and only if one of the following equivalent conditions is true.

  * (a)

there are no $u_{1},u_{2}\in U$ and $v_{1},v_{2}\in V$ such that
$u_{1}v_{1},u_{2}v_{2}\in E(G)$ and $u_{1}v_{2},u_{2}v_{1}\notin E(G)$;

  * (b)

every induced subgraph without isolated vertices has on each side of the
bipartition a domination vertex, that is, a vertex which is adjacent to all
the vertices on the other side of the bipartition.

######  Lemma 7.

If $G$ is a graph maximizing $h(G)$ among all bipartite graphs of size $m$,
then $G$ is a difference graph.

###### Proof.

Suppose that $G$ is not a difference graph. By Theorem 6, there are four
vertices $u_{1},u_{2}\in U$ and $v_{1},v_{2}\in V$ such that
$u_{1}v_{1},u_{2}v_{2}\in E(G)$ and $u_{1}v_{2},u_{2}v_{1}\not\in E(G).$
Assume without loss of generality that $\deg(u_{1})\geq\deg(u_{2})$. In that
case the degree sequence of the graph
$G^{\prime}=\left(G\backslash\\{u_{2}v_{2}\\}\right)\cup\\{u_{1}v_{2}\\}$ will
majorize the degree sequence of $G$ (strictly) and so we get the desired
contradiction by Corollary 5. ∎

######  Lemma 8.

Let $t,\ell>0$ be fixed positive integers. Under the condition that
$\sum_{j=1}^{x}z_{i}=t$ and all $z_{i}\geq 0$ are integers,
$\sum_{j=1}^{x}f(z_{j}+\ell)-\sum_{j=1}^{x}f(z_{j})$ is maximized when
$z_{1}=z_{2}=\ldots=z_{x}=\left\lfloor\frac{t}{x}\right\rceil.$

###### Proof.

Note that the function $\Delta^{\ell}(z)=f(z+\ell)-f(z)$ is a strictly concave
function for every $\ell>0$ and every sequence of $x$ integers with sum $t$ do
majorize the sequence with
$z_{1}=z_{2}=\ldots=z_{x}=\left\lfloor\frac{t}{x}\right\rceil.$ Now the result
follows immediately by Karamata’s inequality. ∎

For the function $\Delta^{1}$, we write $\Delta$ for ease of notation. We
define this one separately, as it will be used frequently.

######  Definition 9.

The function $\Delta$ is defined by
$\Delta(x)=f(x)-f(x-1)=1+\int_{x-1}^{x}\log t\,\mathrm{d}t$. This is a
strictly increasing and concave function.

We also use Landau notation, such as $o()$ and $\omega()$. A function $q(x,y)$
or expression is $o_{y}(p(x,y))$ or $\omega_{y}(p(x,y))$ if
$\frac{q(x,y)}{p(x,y)}\to 0$ respectively $\frac{\lvert q(x,y)\rvert}{\lvert
p(x,y)\rvert}\to\infty$ when $y\to\infty$. Sometimes the dependency on $y$ is
removed to keep the notation light.

We also use the notation $[k]=\\{1,2,\ldots,k\\}$ and
$[k..\ell]=\\{k,k+1,\ldots,\ell-1,\ell\\}.$

##  2 Minimum entropy of bipartite graphs of fixed size

In this section, we prove Theorem 1. In both approaches, we assume that our
bipartite graph is $G=(U\cup V,E)$, $U=\\{u_{1},u_{2},\ldots,u_{x}\\}$ and
$V=\\{v_{1},v_{2},\ldots,v_{y}\\}$ are the vertices with degree at least $1.$
Here we assume these are ordered, i.e. $\deg u_{i}\geq\deg u_{j}$ and $\deg
v_{i}\geq\deg v_{j}$ whenever $i\leq j.$ Let $y_{i}=\deg(u_{i})$ and
$x_{j}=\deg(v_{j})$ for every $1\leq i\leq x$ and $1\leq j\leq y.$ So with
this notation, we have $y=y_{1}$ and $x=x_{1}.$

###  2.1 Approach 1

###### Proof of Theorem 1.

We prove the statement by induction on $m.$ The base case $m=1$ is trivial
since we only have one edge. So assume the statement is true when the size is
at most $m-1$ and let $G$ be a graph maximizing $h(G)$ among all graphs of
size $m$. By Lemma 7 we can assume that $G$ is a difference graph. This
implies that $u_{1}$ is a dominating vertex (dominates $V$). Let
$G^{\prime}=G\backslash u_{1}$. By the induction hypothesis applied to
$G^{\prime}$ and Lemma 8 applied with $\ell=1$ and $z_{i}=x_{i}-1$, we know

$\displaystyle h(G)$
$\displaystyle=h(G^{\prime})+f(y)+\sum_{j=1}^{y}f(x_{j})-\sum_{j=1}^{y}f(x_{j}-1)$
$\displaystyle\leq
h(K_{1,m-y})+f(y)+y\left(f\left(\frac{m}{y}\right)-f\left(\frac{m}{y}-1\right)\right).$

Equality here is only attained if $x_{j}=\frac{m}{y}$ for every $1\leq j\leq
y.$ Now the conclusion is direct as

$\displaystyle
h(G)\leq(m-y)\log(m-y)+y\log(y)+m\left(\log(m)-\log(y)\right)-(m-y)\left(\log(m-y)-\log(y)\right)=m\log
m.$

By induction, we see that equality is attained precisely for the complete
bipartite graphs on $m$ edges. ∎

###  2.2 Approach 2

In this subsection, we give an alternative proof for the fact that $K_{1,m}$
minimizes the entropy among all bipartite graphs of size $m$, which does not
use any prerequisites. Note that the proof can be formulated without the
notion of a tableau and that we give a short proof of Lemma 7 as a claim in
this notation.

In every cell $(i,j)$ of the associated tableau $T$ of a bipartite graph $G$,
we put $\log(y_{i}x_{j})=\log(x_{j})+\log(y_{i})$. The sum over all cells,
$h(T)=\sum_{(i,j)\in T}\log(x_{j}y_{i})$ is now exactly equal to
$\sum_{j}f(x_{j})+\sum_{i}f(y_{i})=h(G).$

###### Proof of Theorem 1.

We first prove that the associated tableau $T$ is a Young tableau, i.e. if
$(i,j)\in T$ and $0<i^{\prime}\leq i$ and $0<j^{\prime}\leq j,$ then
$(i^{\prime},j^{\prime})\in T.$

######  Claim 10.

If $G=(U\cup V,E)$ is a bipartite graph maximizing $h(G)$ among all bipartite
graphs of size $m$, then its associated tableau is a Young tableau.

###### Proof.

Assume $(i,j)\in T$ and $(i^{\prime},j^{\prime})\not\in T$. If $i^{\prime}<i$
and $j^{\prime}<j$, then $G^{\prime}=G\backslash u_{i}v_{j}\cup
u_{i^{\prime}}v_{j^{\prime}}$ satisfies
$h(G^{\prime})=h(G)-\Delta(y_{i})-\Delta(x_{j})+\Delta(y_{i^{\prime}}+1)+\Delta(x_{j^{\prime}}+1)>h(G).$
The latter due to $\Delta$ being strictly increasing and $y_{i}\leq
y_{i^{\prime}}$ and $x_{j}\leq x_{j^{\prime}}.$ If $i^{\prime}=i$ or
$j^{\prime}=j$, it is analogous as $h(G^{\prime})-h(G)$ equals
$\Delta(y_{i^{\prime}}+1)-\Delta(y_{i})>0$ or
$\Delta(x_{j^{\prime}}+1)-\Delta(x_{j})>0.$ This implies that $G$ was not
extremal and so we conclude by contradiction. ∎

Next, we note that

$\sum_{(i,j)\in
T}x_{j}y_{i}\leq\sum_{i,j}x_{j}y_{i}=\left(\sum_{j}x_{j}\right)\left(\sum_{i}y_{i}\right)=m^{2}.$

So by Jensen’s inequality, we have

$\sum_{(i,j)\in T}\log(x_{j}y_{i})\leq
m\log\left(\frac{m^{2}}{m}\right)=m\log(m)$

with equality if and only if $x_{j}y_{i}=m$ for every choice of $(i,j)$, i.e.
$G$ is complete, bipartite. ∎

##  3 Minimum entropy among dense Bipartite graphs

We state two propositions in terms of the Young tableaux. Note that by taking
$x=q+1$, we conclude that $B(n,m,y)$ is extremal in both cases.

######  Proposition 11.

Fix integers $x>y>r>0$ and $m=xy-r$. Among all Young tableaux with $m$ cells
in $[x]\times[y],$ $h(T)$ is maximized by

$T^{\prime}=\left([x]\times[y]\right)\backslash\left(x\times[y-r+1..y]\right).$

If $x>y=\omega(r^{2})$, then the latter tableau has $h(T^{\prime})\sim m\log
m-r+o(1).$

###### Proof.

Let $T$ be a Young tableau which equals $[x]\times[y],$ except from the $r$
cells which have coordinates
$(i_{1},j_{1}),(i_{2},j_{2}),\ldots,(i_{r},j_{r})$, where these are ordered in
reverse lexicographic order. In particular $(i_{1},j_{1})=(x,y)$ and for every
$1\leq k\leq r$ the pair $(i_{k},j_{k})$ satisfies $i_{k}+j_{k}\geq x+y+1-k$,
$j_{k}\leq y$ and $i_{k}\leq x.$ Since $\Delta$ is increasing and concave, by
the inequality of Karamata, we have

$\Delta(i_{k})+\Delta(j_{k})\geq\Delta(x)+\Delta(y+1-k).$

Now

$\displaystyle h(T)$
$\displaystyle=xy\log(xy)-\sum_{k=1}^{r}\left(\Delta(i_{k})+\Delta(j_{k})\right)$
$\displaystyle\leq
xy\log(xy)-\sum_{k=1}^{r}\left(\Delta(x)+\Delta(y+1-k)\right)$
$\displaystyle=h(T^{\prime}),$

and furthermore equality occurs if and only if $(i_{k},j_{k})=(x,y+1-k)$ for
every $k$, i.e. $T=T^{\prime}$. Now since
$1+\log(x)-\frac{1}{x-1}\leq\Delta(x)<1+\log(x)$ and
$1+\log(y)-\frac{k}{y-k})\leq\Delta(y+1-k)<1+\log(y)$, we note that when
$y=\omega(r^{2}),$ we have

$\displaystyle h(T^{\prime})$
$\displaystyle=xy\log(xy)-r\Delta(x)-\sum_{k=1}^{r}\Delta(y+1-k)$
$\displaystyle=m\log(m+r)-2r-o(1)$ $\displaystyle=m\log(m)-r-o(1),$

where the $o(1)$ term tends to zero as $x,y\to\infty$ for fixed $r$. ∎

######  Proposition 12.

Fix integers $q\geq y>r>0$ and $m=qy+r$. Among all Young tableaux containing
$[q]\times[y]$ with $m$ cells, $h(T)$ is maximized by

$T^{\prime}=\left([q]\times[y]\right)\cup\left((q+1)\times[r]\right).$

If $q=\omega(r)$, the latter tableau satisfies $h(T^{\prime})\sim
m\log(m)-r\log\left(\frac{y}{r}\right).$

###### Proof.

Let $T$ be a Young tableau which equals $[q]\times[y],$ with $r$ additional
cells which have coordinates
$(i_{1},j_{1}),(i_{2},j_{2}),\ldots,(i_{r},j_{r})$, where these are ordered in
lexicographic order. We note that for every $1\leq k\leq r$ the pair
$(i_{k},j_{k})$ satisfies $i_{k}+j_{k}\leq q+k+1$ and
$\min\\{i_{k},j_{k}\\}\leq k.$ Since $\Delta$ is increasing and concave, by
the inequality of Karamata, we have

$\Delta(i_{k})+\Delta(j_{k})\leq\Delta(\min\\{i_{k},j_{k}\\})+\Delta(q+1+k-\min\\{i_{k},j_{k}\\})\leq\Delta(q+1)+\Delta(k).$

Now

$\displaystyle h(T)$
$\displaystyle=yq\log(yq)+\sum_{k=1}^{r}\left(\Delta(i_{k})+\Delta(j_{k})\right)$
$\displaystyle\leq
yq\log(yq)+\sum_{k=1}^{r}\left(\Delta(q+1)+\Delta(k)\right)$
$\displaystyle=h(T^{\prime}),$

and furthermore equality occurs if and only if $(i_{k},j_{k})=(q+1,k)$ for
every $k$, i.e. $T=T^{\prime}$.

Now since $1+\log(q)\leq\Delta(q+1)<1+\log(q)+\frac{1}{q}$ and
$\sum_{k=1}^{r}\Delta(k)=f(r)=r\log(r)$, we note that when $q=\omega(r),$ we
have

$\displaystyle h(T^{\prime})$ $\displaystyle=yq\log(yq)+r\Delta(q+1)+f(r)$
$\displaystyle=qy\log(q)+qy\log(y)+r\log(q)+r+f(r)+o(1)$
$\displaystyle=m\log(m-r)-r\log(y)+r+r\log(r)+o(1)$
$\displaystyle=m\log(m)-r\log\left(\frac{y}{r}\right)+o(1),$

where the $o(1)$ term tends to zero when $q\to\infty$ for fixed $r.$ ∎

##  4 Minimum is attained by dense Young tableaux

In this subsection, we list and prove a number of lemmas that show that the
extremal Young tableaux are dense, in the sense that they are of the form
presented in Section 3.

We start with proving that the extremal Young tableau cannot have the
following specific form.

$r$$s$$t$$x$$y$ (a) Young tableau $T$

$x$$y$$r^{\prime}$$t^{\prime}$$w$ (b) Young tableau $T^{\prime}$

Figure 2: The Young tableaux from Lemma 13

######  Lemma 13.

Let $m=xy-r-s+1$ with $1\leq r\leq x-y$ and $1\leq s<y$, such that
$r+s-1=wy+r^{\prime}$ for some integers $0<w$ and $0\leq r^{\prime}<y.$ If

$\displaystyle T$
$\displaystyle=\left([x]\times[y]\right)\backslash\left([x-r+1..x]\times
y\right)\backslash\left(x\times[y-s+1..y-1]\right)\mbox{ and}$ $\displaystyle
T^{\prime}$
$\displaystyle=\left([x-w]\times[y]\right)\backslash\left((x-w)\times[y-r^{\prime}+1..y]\right),$

then $h(T)<h(T^{\prime}).$ See Figure 2.

###### Proof.

We prove this in a number of steps. First we prove that it is sufficient to
prove when $s=1.$

######  Claim 14.

If Lemma 13 does hold whenever $s=1$, then so it does for all other cases.

###### Proof.

Assume there are choices of $x,y,r,s$ (and thus Young tableaux $T$ and
$T^{\prime}$) for which Lemma 13 is false. Let $t=y-s$ and
$t^{\prime}=y-r^{\prime}$, and assume $0<t<y-1.$ We now consider two cases.
Case 1: $t^{\prime}\leq t$. In this case, we note that
$\Delta(t+1)+\Delta(x)>\Delta(t^{\prime}+1)+\Delta(x-w)$ and thus we also have
a counterexample with $s-1$ instead of $s$. We can repeat this until $s=1.$
Case 2: $t^{\prime}>t$. Note that $y\cdot(x-w)>m>x\cdot(y-1)$ implying
$\frac{x-w}{x}>\frac{y-1}{y}>\frac{t}{t+1}\geq\frac{t}{t^{\prime}}$ and hence
$(x-w)t^{\prime}>xt.$ Now we have
$\Delta(t)+\Delta(x)<\Delta(t^{\prime})+\Delta(x-w)$. When
$t+x\leq(x-w)+t^{\prime}$, this is by Karamata’s inequality and the fact that
$\Delta$ is increasing and concave. When $t+x>(x-w)+t^{\prime}$, we note that
$(x-u)(t-u)=xt-u(x+t)+u^{2}<(x-w)t^{\prime}-u((x-w)+t^{\prime})+u^{2}=(x-w-u)(t^{\prime}-u)$
for every $u\geq 0$ and thus

$\int_{u=0}^{1}\log\left((x-u)(t-u)\right)\,\mathrm{d}u<\int_{u=0}^{1}\log\left((x-w-u)(t^{\prime}-u)\right)\,\mathrm{d}u.$

The latter being equivalent to
$\Delta(t)+\Delta(x)<\Delta(t^{\prime})+\Delta(x-w)$. This implies that we can
construct a counterexample with $s+1$ instead of $s$ as well and we can repeat
this until $s=y,$ which corresponds to an example with $s=1.$ ∎

Next, we show that we can assume that $x-r=y.$

######  Claim 15.

If Lemma 13 does hold whenever $s=1$ and $r=x-y$, then so it does for all
other cases.

###### Proof.

Assume there are Young tableaux $T$ and $T^{\prime}$ for which Lemma 13 is
false, where $s=1$ and $y+r<x.$ Now deleting the first column of both
tableaux, implies that $h(T)$ decreases by $\Delta(x-r)+(y-1)\Delta(x)+f(y)$
and $h(T^{\prime})$ has been decreased by
$(y-r^{\prime})\Delta(x-w)+r^{\prime}\Delta(x-w-1)+f(y).$ Since
$\\{\underbrace{x,x,\ldots,x}_{y-1},x-r\\}$ majorizes
$\\{\underbrace{x-w,x-w,\ldots,x-w}_{y-r^{\prime}},\underbrace{x-w-1,\ldots
x-w-1}_{r^{\prime}}\\}$, as $\Delta$ is strictly concave, the value
$h(T^{\prime})$ has decreased by a larger amount than $h(T).$ So Lemma 13 is
false for a construction with parameters $(x-1,y,r).$ We can repeat this,
until $x=y+r.$ ∎

Now we finish the proof by proving that Lemma 13 is true when $s=1$ and
$r=x-y.$ In the latter case, we can write $x=ay+b$ where $a>0$ is an integer
and $0\leq b<y$, in which case we know the precise shapes of $T$ and
$T^{\prime}$. These have been represented in Figure 3.

$y$$ay+b$$y$ (a) Young tableau $T$

$a(y-1)+b+1$$y$$b$ (b) Young tableau $T^{\prime}$

Figure 3: The two Young tableaux in the remaining case

When $a=1$, we have $h(T)\leq h(T^{\prime})$ by Proposition 11 and the
inequality is even strict when $b>1.$ We now finish the proof by induction on
$a$. So assume it is proven for the values $a,b,y.$ Going from $a$ to $a+1$,
the value $h(T)$ increases by

$I_{1}=y\cdot f(y-1)+(y-1)\left(f((a+1)y+b)-f(ay+b)\right)$ (1)

while $h(T^{\prime})$ increases by at least

$I_{2}=(y-1)\cdot
f(y)+y\left(f\left(\left(a+1+\frac{b}{y}\right)(y-1)\right)-f\left(\left(a+\frac{b}{y}\right)(y-1)\right)\right).\\\
$ (2)

Now one can note that $I_{1}=I_{2}$ by implementing the following two
equalities in Equation (1) and Equation (2).

$\displaystyle f((a+1)y+b)-f(ay+b)$
$\displaystyle=y+y\int_{u=a+\frac{b}{y}}^{a+1+\frac{b}{y}}\left(\log(u)+\log(y)\right)\,\mathrm{d}u$
$\displaystyle
f\left(\left(a+1+\frac{b}{y}\right)(y-1)\right)-f\left(\left(a+\frac{b}{y}\right)(y-1)\right)$
$\displaystyle=y-1+(y-1)\int_{u=a+\frac{b}{y}}^{a+1+\frac{b}{y}}\left(\log(u)+\log(y-1)\right)\,\mathrm{d}u.$

∎

Having proven this particular case in Lemma 13, we continue with some
observations from which we can conclude that the extremal tableaux will be as
given in Section 3.

######  Lemma 16.

If $G=(U\cup V,E)$ is an extremal bipartite $(n,m)$-graph, then the minimum
degree of the smaller partition class is at least the maximum degree of the
other partition class.

###### Proof.

Consider the associated Young tableau $T$ of $G$. Let $i$ be the value for
which $(i,i)\in T$ and $(i+1,i+1)\not\in T$. Let
$S_{1}=\\{(i^{\prime},j^{\prime})\in T\mid j^{\prime}>i\\}$ and
$S_{2}=\\{(i^{\prime},j^{\prime})\in T\mid i^{\prime}>i\\}.$ Now if both
$S_{1}$ and $S_{2}$ are non-empty, we can construct a tableau $T^{\prime}$ for
which the rows in $S_{1}$ are deleted and are added as columns, in such a way
that another Young tableau $T^{\prime}$ has been formed. It is not hard to see
that the degree sequence of the graph $G^{\prime}$ associated with
$T^{\prime}$ majorizes the degree sequence of $G$. For this, note that is
sufficient to compare the degrees of
$\\{u_{1},\ldots,u_{i},v_{1},\ldots,v_{i}\\}$ (and thus the number of cells in
their rows/columns). Thus, since $f$ is strictly convex, by Karamata’s
inequality we know $h(T^{\prime})>h(T).$ ∎

$S_{1}$$S_{2}$

(a) Young tableau $T$

(b) Young tableau $T^{\prime}$

Figure 4: Sketch of the rearrangement in Lemma 16

######  Theorem 17.

For fixed integers $m$ and $n$, let $T_{*}$ be a tableau with $m$ cells for
which the sum of its length $x$ and width $y$ is at most $n$. If $h(T_{*})$ is
maximal among all such tableaux, then $x,y$ satisfy $xy-\min\\{x,y\\}<m\leq
xy.$

###### Proof.

Assume $m$ cannot be written as a product $xy$ with $x+y\leq n$ and $T_{*}$ is
an extremal tableau with $m\leq(x-1)y,$ where $y<x.$ Let
$x_{1}=x,x_{2},\ldots,x_{y}$ be the number of cells in every row. By Lemma 16,
we know that $[y]\times[y]\subset T_{*}$ and thus $x_{i}\geq y$ for every
$1\leq i\leq y.$ Furthermore, since $m\leq(x-1)y,$ there is a smallest index
$i$ such that $x_{i}<x-1.$ Now, the first $i$ rows of $T_{*}$, i.e.
$T_{i}=T_{*}\cap\left([x]\times[i]\right)$, form a tableau that has the form
of the tableau $T$ in Lemma 13. Replacing $T_{i}$ by the corresponding
$T^{\prime}_{i}$ from Lemma 13 (which does not increase the length of the
tableau) will imply that we also form a $T^{\prime}_{*}$ for which
$h(T^{\prime}_{*})>h(T_{*}),$ since
$h(T^{\prime}_{*})-h(T_{*})=h(T^{\prime}_{i})-h(T_{i})>0.$ For the latter,
note that the only rows and columns that possibly changed, are rows $1$ till
$i$ and columns $x_{i}+1$ till $x,$ all of which do not contain any cell
outside $T_{i}$ or $T^{\prime}_{i}$. This is the desired contradiction. Figure
5 presents this final comparison. ∎

$S$$T_{i}$ (a) Young tableau $T_{*}$

$S$$T^{\prime}_{i}$ (b) Young tableau $T^{\prime}_{*}$

Figure 5: The local move increasing $h(T_{*})$ in Theorem 17

##  5 Maximum entropy and extrema of other chemical indices

The degree-based entropy is one example of a degree-based topological index
(or chemical index), the latter defined as

$\operatorname{TI}_{g}(G)=\sum_{uv\in E(G)}g(\deg(u),\deg(v)),$

for some function $g$, as initially done in e.g. [10]. See e.g. [15, Table 1]
for a clear overview of some more examples. In this case, one can conclude
that the interesting graphical function-indices, defined similarly as
$\sum_{v\in V(G)}g(\deg(u))$, will essentially boil down to
$g(x)=c_{1}x+c_{2}x\log(x)$ and thus be directly related to the entropy case.
So we focus on the chemical indices. The function $h(G)$ can be written as
$\operatorname{TI}_{g}$ where $g(x,y)=\log(xy)$. Our idea of approach $2$ in
Subsection 2.2 works for any $\operatorname{TI}_{g}$ whenever $g$ is an
increasing, concave function in $xy$. E.g. when $g(x,y)=xy$ or
$g(x,y)=\sqrt{xy}$ (i.e. for the Second Zagreb index and Reciprocal Randic
index), the graphs maximizing $\operatorname{TI}_{g}(G)$ among all bipartite
graphs of size $m$ are precisely the complete bipartite graphs $K_{q,y}$ with
$q\cdot y=m$. When we know both the order and size, one can expect that a
similar exposition implies that the extremal graphs are again near complete
bipartite, i.e. $K_{y,x}$ with some small number $r$ of removed (or added)
edges. Xu et al. [19] studied these for the first and second Zagreb indices
for example.

On the other hand, if $g(x,y)=x+y$ or $g(x,y)=(x+y)^{2}$, since
$\deg(u)+\deg(v)\leq m+1$ for every $uv\in E(G)$ the unique extremal graph
(maximizing $\operatorname{TI}_{g}(G)$) is easily seen to be the star
$K_{1,m}.$ In particular, this implies that among bipartite graphs of a given
size, the set of graphs maximizing the First Zagreb index and Second Zagreb
index are not equal. This contrasts some of the intuition in the concluding
section of [19, Sec. 4]. Also among bipartite graphs of a given order and
size, the bipartite graphs with the maximum first Zagreb index might be
different than the one with the maximum second Zagreb index. For the first
Zagreb index these extremal bipartite graphs were determined by Zhang and Zhou
[20]. Here the asymmetry (large degrees) play a major role and so there are
examples for which the bipartite graphs maximizing the first Zagreb index are
not complete bipartite, while there do exist complete bipartite graphs
$K_{y,x}$ with $xy=m$ and $x+y<n$ that maximize the second Zagreb index.

Finally, we prove that the graphs with maximum entropy can be easily
determined and are the graphs for which the degree sequence is as balanced as
possible. We prove these statements by showing that the latter graphs are
those which minimize $\operatorname{TI}_{g}(G)$ for any increasing, strictly
convex function $g$. Thus, we give a short alternative proof for the result in
[7] in this more general setting and for the result of [12].

Among all graphs with fixed size $m$, without constraint on the order,
$mK_{2}$ is the unique extremal graph maximizing the entropy (note that
$h(mK_{2})=0)$ and minimizing $\operatorname{TI}_{g}(G)$ as well (here the
order $n\geq 2m$ and isolated vertices are taken into account as well when
$g(0)\not=0$).

If there is a condition on both the order and size, the extremal graphs and
bipartite graphs are precisely the nearly-regular graphs, as proven in the
following two propositions. Cheng et al. [4] determined these bipartite graphs
with the minimum value of the first Zagreb index for bipartite graphs of a
given order and size. The proof is essentially a corollary of Karamata’s
inequality and noting that there is a degree sequence that is majorized by all
other possible realizations.

######  Proposition 18.

Let $g$ be an increasing, strictly convex function. Among all graphs with
fixed size $m$ and order $n$, every nearly-regular graph (i.e.
$\deg_{max}-\deg_{min}\leq 1$) is extremal and these are the only extremal
graphs.

###### Proof.

Since the degree sequence of any nearly-regular graph is majorized by the
degree sequence of any other $(n,m)$-graph, the result follows by Karamata’s
inequality. The characterization of the extremal graphs is a consequence of
$g$ being strictly convex. The existence of nearly-regular graph (even
connected if $m\geq n-1$ when necessary) is immediate. If $n$ is even, then
$K_{n}$ can be partitioned into $n-1$ perfect matchings and one can add edges
from one perfect matching at a time. If $n$ is odd, then $K_{n}$ can be
partitioned into $\frac{n-1}{2}$ $2$-regular graphs, where at least one of
them is a cycle (when $n=2k+1$ and $V=\\{v_{1},v_{2},\ldots,v_{n}\\}$, for
every $1\leq\ell\leq k$, form the graph with edges $v_{i}v_{j}$ for which
$i-j\equiv\pm\ell\pmod{n}$). Now when $m=an+b,$ one can take the union of $a$
such $2$-regular graphs and a matching or its complement of the cycle. ∎

######  Proposition 19.

Among all bipartite graphs with size $m$ and order $n$, every bipartite graph
$G=(U\cup V,E)$ with $\lvert U\rvert=\left\lceil\frac{n}{2}\right\rceil$ and
$\lvert V\rvert=\left\lfloor\frac{n}{2}\right\rfloor$ for which the degrees in
one partition class differ by at most one attains the maximum entropy in the
graph class. Furthermore, a bipartite graph is extremal if and only if it has
the same degree sequence as this balanced example.

###### Proof.

Let $G^{\prime}=(U^{\prime}\cup V^{\prime},E^{\prime})$ be any other bipartite
graph with size $m$ and order $n$ whose partition classes have size $u\geq v$.
The sum of the $i\leq v$ largest degrees in $V^{\prime}$ are at least equal to
the sum of the $i$ largest degrees of $G$ and the sum of the $i\leq u$
smallest degrees in $U^{\prime}$ are at most the sum of the $i$ smallest
degrees in $G$. Here we use that $u\geq\left\lceil\frac{n}{2}\right\rceil$ and
$v\leq\left\lfloor\frac{n}{2}\right\rfloor$ and the degrees in $G$ are as
balanced as possible. Remark that if $u\geq
i>\left\lceil\frac{n}{2}\right\rceil$, then the sum of the $i$ degrees in
$U^{\prime}$ is at most $m$. So we conclude that the degree sequence of $G$ is
majorized by any degree sequence of any other bipartite graph with order $n$
and size $m$, from which we conclude (also for the uniqueness statement) by
Karamata’s inequality and $g(x)$ being strictly convex.

We remark that one can always construct at least one such a balanced bipartite
graph $G$. If $n$ is even, just partition $K_{n/2,n/2}$ in perfect matchings
and add the edges from one matching at a time up to the point you selected
precisely $m$ edges. When $n$ is odd, for every $1\leq
m\leq\left\lfloor\frac{n^{2}}{4}\right\rfloor,$ one can construct a graph by
adding for every $1\leq k\leq m$ an edge between the vertices $a_{i}$ and
$b_{j}$ for which $k\equiv i\pmod{\left\lceil\frac{n}{2}\right\rceil}$ and
$k\equiv j\pmod{\left\lfloor\frac{n}{2}\right\rfloor}$ respectively. ∎

A few examples have been presented in Figure 6. Since everything boils down to
having a degree sequence that is as balanced as possible, i.e. it is majorized
by any other degree sequence of a graph, the result only depends on the degree
sequence.

We end with a few observations. There do exist both connected and disconnected
extremal bipartite graphs (as presented for $m=n=9$). If $n$ is odd, it is
possible there is no extremal bipartite graph attaining the maximum over all
graphs, since for bipartite $(n,m)$ graphs we might be forced to have
$\deg_{max}-\deg_{min}\geq 2$ (equality can be attained), as is the case with
$m=n=9$. Finally, we observe that the partition itself does not necessarily
has to be balanced (e.g. $m=30,n=22,\lvert U\rvert=10$ and $\lvert
V\rvert=12$) .

(a) $n=8$

(b) $n=9$ (connected)

(c) $n=9$ (disconnected)

Figure 6: Bipartite graphs of size $9$ with maximum entropy

##  6 Conclusion

In this paper, we proved that the bipartite graphs of size $m$ that maximize
the entropy are complete bipartite graphs. If there is a restriction on the
order (at most $n$) and $m$ cannot be written as $x\cdot y$ where $x+y\leq n$,
then the extremal graphs are of the form $B(n,m,y),$ i.e. a complete bipartite
graph minus a star. Nevertheless, it seems impossible to determine $y$ with a
general formula, as we will explain here.

Using a computer program111https://github.com/MatteoMazzamurro/extrema-graph-
entropy/blob/main/bipartite_graphs_entropy.R, we could find all extremal
bipartite graphs for $n\leq 50$ and
$m\leq\left\lfloor\frac{n^{2}}{4}\right\rfloor.$ The output is presented
in222https://github.com/MatteoMazzamurro/extrema-graph-
entropy/blob/main/B_n_m_50.csv. For every pair $(n,m)$ and value $1\leq
y\leq\sqrt{m}$, we computed the values

$q=\left\lfloor\frac{m}{y}\right\rfloor,\;x=\left\lceil\frac{m}{y}\right\rceil,\;m-qy,\;xy-m,\;h=h(B(n,m,y))$

and three boolean values expressing whether $B(n,m,y)$ achieved the maximum
value of $h$ among all choices of $y$ and whether $m-qy$ or $xy-m$ were
minimal among all possible choices for $y$ for that pair $(n,m).$ Among all
extremal graphs which are not complete bipartite, we found $547$ cases for
which both $xy-m$ and $m-qy$ are minimal among all possibilities, $375$ cases
where only $m-qy$ is minimal, $3635$ cases where only $xy-m$ is minimal, and
no cases for which neither $xy-m$ nor $m-qy$ is minimal.

Intuitively, when $xy-m$ or $m-qy$ is small, the graph $B(n,m,y)$ is nearly
complete bipartite (up to the edges of a small star which has been added or
removed) and so it might be extremal. Nevertheless, this was found not to be
the case in general. When $n=17726$ and $m=318728$, the extremal graph is
$B(n,m,18)$, which satisfies $q=17707$, $y=18$ and $r=m-qy=2,$ even though
$y=139$ and $q=2293$ would give $r=1$. Taking into account the estimates in
Proposition 12, one can expect that there are more such examples since the
difference with the upper bound depends on both $r$ and $y$, i.e. one would
like $y$ and $r$ to be both small and the ratio has an influence on this. A
precise statement here would be difficult, as it is related to some hard
number theoretic questions.

Comparing with Proposition 11, whenever $m$ is large, one would wish that
there was a small value of $r$ for which $m+r$ could be written as a product
$xy$ with $x+y\leq n.$ So one may expect from these observations that in most
cases, the extremal graph will be $B(n,m,y)$ with $y$ chosen in such a way
that $y\left\lceil\frac{m}{y}\right\rceil-m$ is minimized under the constraint
that $y+\left\lceil\frac{m}{y}\right\rceil\leq n,$ and so the extremal graph
is a “complete bipartite graph minus a small star”. Furthermore, when there
are multiple choices for $y$, we need to choose the smallest $y$, i.e. for
fixed $r$, the complete bipartite graph will be as asymmetric as possible. To
note the latter, one can compare the computations in Proposition 11 for some
$x^{\prime}>x>y>y^{\prime}$ with $xy=x^{\prime}y^{\prime}$. For a fixed $1\leq
k\leq y-1$, we have
$\Delta(x)+\Delta(y+1-k)\geq\Delta(x^{\prime})+\Delta(y^{\prime}+1-k)$ since
$(x-u)(y+1-k-u)\geq(x^{\prime}-u)(y^{\prime}+1-k-u)$ for $u\in[0,1].$

We can prove that the intuition that $r=xy-m$ is minimal for the extremal
$B(n,m,y)$ is true in many cases, using the notion of $M$-friable numbers. A
positive integer is called $M$-smooth or $M$-friable if its largest prime
divisor is at most $M.$ At this point, the state-of-the-art on smooth/friable
numbers [17, 9] does not address the question if for fixed constants $0<u<1$
and $c>0$, the interval $[m,m+c\log(m)]$ necessarily needs to contain a
$m^{u}$-smooth number whenever $m$ is sufficiently large, but it does so for
almost all $m$ by [17, Cor. 6].

Write $n=(m+\log(m))^{u}+(m+\log(m))^{1-u}$ for some real number
$\frac{2}{3}\leq u<1$. Now for almost all $m$, we know that there does exist a
number $r\leq 0.5(1-u)\log(m)$ such that $m+r$ is $m^{u}$-smooth (by [17, Cor.
6]). Now $m+r$ being $m^{u}$-smooth implies that all its prime divisors are
bounded by $m^{u}$ and thus also $(m+r)^{u}.$ Thus $m+r$ has two divisors
$x,y$ for which $(m+r)^{1-u}\leq y\leq x\leq(m+r)^{u}$. For this, note that if
the largest prime factor $p$ of $m+r$ satisfies $(m+r)^{1-u}\leq
p\leq(m+r)^{u}$, we can take $\\{x,y\\}$ to be equal to
$\left\\{p,\frac{m+r}{p}\right\\}$ and otherwise we can take a product $P$ of
prime divisors of $m+r$ which is between $(m+r)^{1-u}$ and
$(m+r)^{2(1-u)}\leq(m+r)^{u}$ and take $\\{x,y\\}$ to be equal to
$\left\\{P,\frac{m+r}{P}\right\\}$. Since the function $P+\frac{m+r}{P}$ is
increasing for $P\geq\sqrt{m+r}$ and $r<\log m$, we have $x+y<n.$ Comparing
Proposition 12 and Proposition 11 we conclude that the extremal graph is equal
to the graph $B(n,m,y)$ where $y$ has been chosen in such a way that $xy-m$ is
minimized. The latter is because $y+\frac{m}{y}\leq n$ and $y<\sqrt{m}$
implies that $y>>m^{0.5(1-u)}$ and thus $\log(y)-r$ is large.

On the other hand, there will be infinity many examples which are not of this
form. A simple example for this, where $m-qy$ can be arbitrarily large, can be
constructed as follows. Fix $c>0$ and let $n=2a+1$ and $m=a^{2}+c$, where
$a=b^{2}+b$. Now $B(n,m,a)$ is an example for which $m-qy=c$ is minimized
(note that $q+y=2a$ is needed). On the other hand $B(n,m,y)$ will always
satisfy $xy-m\geq 2b-c$ since (note that $x+y=n$ is needed)

$(a-b+1)(a+b)-m=a^{2}+a-b^{2}+b>m>a^{2}+a-b^{2}-b=(a-b)(a+b+1).$

For fixed $c$ and $b$ sufficiently large, we conclude as then
$2b-c>c\log\left(\frac{2b-c}{c}\right).$

## Acknowledgement

Thanks to Bart Michels and Régis de la Bretèche for sharing their expertise on
smooth/friable numbers.

#### Open access statement.

For the purpose of open access, a CC BY public copyright license is applied to
any Author Accepted Manuscript (AAM) arising from this submission.

## References

  * [1] S. Cambie.  Five results on maximizing topological indices in graphs.  Discrete Math. Theor. Comput. Sci., 23(3):Paper No. 10, 13, 2021\.
  * [2] S. Cambie and M. Mazzamurro.  Minimum entropy of graphs with given size.  arXiv e-prints, page arXiv:2204.08251, Apr. 2022.
  * [3] S. Cambie and M. Mazzamurro.  Resolution of Yan’s conjecture on entropy of graphs.  arXiv e-prints, page arXiv:2205.03357, May 2022.
  * [4] T. C. E. Cheng, Y. Guo, S. Zhang, and Y. Du.  Extreme values of the sum of squares of degrees of bipartite graphs.  Discrete Math., 309(6):1557–1564, 2009.
  * [5] B. Danail.  Information Theoretic Indices for Characterization of Chemical Structures.  Research Studies Press, Chichester, 1983.
  * [6] M. Dehmer, K. Varmuza, S. Borgert, and F. Emmert-Streib.  On entropy-based molecular descriptors: Statistical analysis of real and synthetic chemical structures.  Journal of chemical information and modeling, 49(7):1655–1663, 2009\.
  * [7] Y. Dong, S. Qiao, B. Chen, P. Wan, and S. Zhang.  Maximum values of degree-based entropies of bipartite graphs.  Appl. Math. Comput., 401:Paper No. 126094, 7, 2021.
  * [8] A. Ghalavand, M. Eliasi, and A. R. Ashrafi.  First degree-based entropy of graphs.  J. Appl. Math. Comput., 59(1-2):37–46, 2019.
  * [9] E. Goudout.  Lois locales de la fonction $\omega$ dans presque tous les petits intervalles.  Proc. Lond. Math. Soc. (3), 115(3):599–637, 2017.
  * [10] I. Gutman.  Degree-based topological indices.  Croatica chemica acta, 86(4):351–361, 2013.
  * [11] P. L. Hammer, U. N. Peled, and X. Sun.  Difference graphs.  Discrete Appl. Math., 28(1):35–44, 1990.
  * [12] Z. Hu, X. Li, and D. Peng.  Graphs with minimum vertex-degree function-index for convex functions.  MATCH Commun. Math. Comput. Chem., 88(3):521–533, 2022.
  * [13] J. Kahn.  An entropy approach to the hard-core model on bipartite graphs.  Combin. Probab. Comput., 10(3):219–237, 2001.
  * [14] J. Karamata.  Sur une inégalité rélative aux fonctions convexes.  Publ. Math. Univ. Belgrade, 1:145–148, 1932.
  * [15] X. Li and D. Peng.  Extremal problems for graphical function-indices and $f$-weighted adjacency matrix.  Discrete Math. Lett., 9:57–66, 2022.
  * [16] N. V. R. Mahadev and U. N. Peled.  Threshold graphs and related topics, volume 56 of Annals of Discrete Mathematics.  North-Holland Publishing Co., Amsterdam, 1995.
  * [17] K. Matomäki and M. Radziwiłł.  Multiplicative functions in short intervals.  Ann. of Math. (2), 183(3):1015–1056, 2016.
  * [18] A. Mowshowitz.  Entropy and the complexity of graphs: I. an index of the relative complexity of a graph.  The bulletin of mathematical biophysics, 30(1):175–204, 1968.
  * [19] K. Xu, K. Tang, H. Liu, and J. Wang.  The Zagreb indices of bipartite graphs with more edges.  J. Appl. Math. Inform., 33(3-4):365–377, 2015.
  * [20] S. Zhang and C. Zhou.  Bipartite graphs with the maximum sum of squares of degrees.  Acta Math. Appl. Sin. Engl. Ser., 30(3):801–806, 2014.
  * [21] Y. Zhao.  The number of independent sets in a regular graph.  Combin. Probab. Comput., 19(2):315–320, 2010.


# Lucky 52: How Many Languages Are Needed to Instruction Fine-Tune Large
Language Models?

Shaoxiong Ji
University of Helsinki
<EMAIL_ADDRESS>
Pinzhen Chen
University of Edinburgh
<EMAIL_ADDRESS>

###### Abstract

Fine-tuning large language models for multilingual downstream tasks requires a
diverse set of languages to capture the nuances and structures of different
linguistic contexts effectively. While the specific number varies depending on
the desired scope and target languages, we argue that the number of languages,
language exposure, and similarity that incorporate the selection of languages
for fine-tuning are some important aspects to examine. By fine-tuning large
multilingual models on 1 to 52 languages, this paper answers one question: How
many languages are needed in instruction fine-tuning for multilingual tasks?
We investigate how multilingual instruction fine-tuned models behave on
multilingual benchmarks with an increasing number of languages and discuss our
findings from the perspective of language exposure and similarity.

††footnotetext: smiling face with open hands We release all model weights to
Hugging Face at this link.††footnotetext: four leaf clover Fun fact: Lucky 52
was a famous variety show in China in the late 1990s and early 2000s. In this
work, the term is used to denote the 52 languages used in multilingual
instruction tuning.

##  1 Introduction

Multilinguality in the context of language models refers to the ability of a
model to understand and generate texts in multiple languages. Large language
models are often designed to be multilingual, meaning they can handle text in
various languages and even perform translation between them. Large language
models (LLMs), like mGPT (Shliazhko et al., 2022), BLOOM (Scao et al., 2022),
and LLaMA (Touvron et al., 2023), are characterized by their vast size and
extensive pre-training on a collection of diverse multilingual texts from the
Internet. They exhibit impressive capabilities to comprehend and generate
texts across multiple languages to solve downstream tasks. However, mastering
multilingual proficiency requires an understanding of the unique grammatical
structures, idiomatic expressions, and cultural contexts inherent to each
language. Fine-tuning a model for multilingual prowess demands meticulous
consideration of these linguistic nuances to ensure accurate and contextually
appropriate responses.

Recent research has shed light on the efficacy of multilingual instruction
fine-tuning (mIT) in enhancing multilingual performance. Chen et al. (2024)
compared monolingual and multilingual instruction tuning under a resource-fair
scenario. Kew et al. (2023) experimented with English-centric LLMs such as
Llama 2 (Touvron et al., 2023) and Falcon (Almazrouei et al., 2023) and found
that multilingual instruction fine-tuning with as few as three languages
improves models’ cross-lingual transfer abilities. Similarly, Shaham et al.
(2024) studied instruction tuning for multilingual LLMs and observed that
enhancing the diversity of languages in the instruction tuning set, even by
just adding 2, 3, or 4 languages, leads to improved cross-lingual
generalization. Moreover, Chirkova & Nikoulina (2024b) explored zero-shot
cross-lingual transfer, where an LLM is trained on English-only data but
tested on prompts in the other four languages, highlighting the importance of
learning rate in achieving effective cross-lingual transfer.

Nevertheless, it is essential to note the variations in the number and
diversity of languages used in these studies. Kew et al. (2023) considered
five non-English languages (Spanish, Russian, German, Chinese, and French) but
also trained models on the full Guanaco dataset with more than 30 languages.
Shaham et al. (2024) experimented with a machine-translated instruction
dataset in 11 diverse languages. Chirkova & Nikoulina (2024b) studied fine-
tuning with English data and tested on four languages (English, French,
Portuguese, and Russian). These works are not strictly comparable due to
different training configurations, data, model choices, and evaluation tasks
and benchmarks. More importantly, while it has been demonstrated that a small
number of languages can elicit (zero-shot) cross-lingual transfer, it is in no
way associated with achieving the optimal downstream task performance.

We aim to fill in the gap by scaling up the number of languages in the
instruction tuning phase, offering insights into the broader implications of
multilingual instruction fine-tuning. This paper employs instruction fine-
tuning using the multilingual BLOOM model (Scao et al., 2022), and a parallel
instruction dataset named Bactrain-X in 52 languages (Li et al., 2023). We
progressively add a language during instruction fine-tuning at each time, and
train 52 models in total. Then, we evaluate those models using three
multilingual benchmarks. Our experimental results show that:

  * •

Contrary to prior research, adding more languages beyond a handful can further
improve accuracy, although with some outlier cases and diminishing returns.

  * •

Given the considered 52 studied languages, there is no consistent answer
regarding the optimal number of languages for mIT. The optimal number of
instruction languages depends on the language similarity and downstream
evaluation.

  * •

The impact of mIT can vary, potentially aiding or hindering multilingual
performance. Additionally, the cross-lingual transfer ability of mIT exists,
though both phenomena are contingent upon the benchmark and languages
involved.

Our study emphasizes the importance of a closer look at the tasks, benchmarks,
languages, and evaluation metrics. And we advocate for more consistent future
studies focused on mIT. For example, in the prior works that explore open-
ended chat (Shaham et al., 2024; Kew et al., 2023; Chirkova & Nikoulina,
2024b; Chen et al., 2024), there is variation in the evaluation set, number of
samples, and evaluation criteria. Our study highlights the necessity for more
systematic experimental studies on various variables. These variables include
but are not limited to base LLMs, training recipes, instruction data and
languages, evaluation tasks and benchmarks, and evaluation criteria for
different tasks. Such comprehensive and consistent investigations are crucial
for advancing our understanding of mIT and its implications.

##  2 Multilingual Instruction Fine-tuning

We perform multilingual instruction fine-tuning to large language models,
aiming to study their proficiency across multiple languages. By fine-tuning
the model using diverse linguistic datasets, it adapts to various languages,
allowing it to generate more contextually relevant and accurate responses in a
multilingual context. This section describes the methodological settings of
multilingual instruction fine-tuning, multilingual instruction data, and the
base language model, which are necessary for addressing our research
inquiries.

###  2.1 Instruction Fine-tuning with an Increasing Number of Languages

Our setup is supervised fine-tuning, where an instruction and a task input are
fed to an LLM, and the LLM is trained to produce a response. To expand the
multilingual capabilities of the model, we employ a strategy that
progressively incorporates additional languages during instruction fine-
tuning. We start from English and Chinese, which are extensively resourced
languages that are prominently presented in both pretraining corpora and
evaluation benchmarks and also represent distinct written scripts. Then, we
progressively add the other languages in alphabetical order.

It is important to acknowledge a potential limitation stemming from the
increasing data size as the number of languages expands. This can introduce an
additional variable that might impact multilingual performance. To mitigate
this effect, we opt for parallel instruction data in which English
instructions are translated into different languages. This ensures consistency
in the instruction information across languages while minimizing the overall
increase in data size. Moreover, the increase in data size also amplifies the
number of optimization steps when utilizing stochastic gradient descent to
update the model parameters on the same device. The number of updates can be
expressed as: $U=\lceil\frac{N\times L\times E}{B\times W}\rceil$, where $N$
is the number of instruction data, $L$ is the number of languages, $E$ is the
number of training epochs, $B$ is the batch size, and $W$ is the world size
(i.e., the number of GPUs). We increase the number of GPUs proportionally when
increasing the number of languages to maintain a manageable range of updates.

###  2.2 Multilingual Instruction Data

The choice of multilingual instruction data lies in its comprehensive language
coverage and data quality, thus enabling robust and inclusive multilingual
instruction fine-tuning experiments. We use the Bactrian-X dataset (Li et al.,
2023) that addresses the scarcity of high-quality multilingual instruction-
response data. This dataset comprises 3.4 million instruction-response pairs
across 52 languages. Instructions were collected from Alpaca (52K) (Taori et
al., 2023) and Dolly (15K) (Conover et al., 2023) datasets, with Alpaca
instructions generated by a text-davinci-003 model and Dolly instructions
contributed by humans. These 67K instructions in English were then translated
into 51 different languages using the Google Translate API, aligned with the
languages supported by the mBART-50 model (Liu et al., 2020). To ensure
translation accuracy and relevance, instructions containing programming-
related content were identified and excluded. To assess translation quality,
100 randomly selected sentences per language were backtranslated into English
using the same API, with original English sentences as references. Automatic
evaluation with standard metrics indicates reliable and high-quality
translations. For further comprehensive details regarding the dataset creation
process and evaluation, readers are encouraged to refer to the original paper.
In our experimentation, we utilize the Bactrian-X dataset as the foundation
and iteratively augment it by adding one language at a time for multilingual
instruction fine-tuning. The languages selected for instruction tuning follow
the specified order: en (English), zh (Chinese), af (Afrikaans), ar (Arabic),
az (Azerbaijani), bn (Bengali), cs (Czech), de (German), es (Spanish), et
(Estonian), fa (Farsi), fi (Finnish), fr (French), gl (Galician), gu
(Gujarati), he (Hebrew), hi (Hindi), hr (Croatian), id (Indonesian), it
(Italian), ja (Japanese), ka (Georgian), kk (Kazakh), km (Khmer), ko (Korean),
lt (Lithuanian), lv (Latvian), mk (Macedonian), ml (Malayalam), mn
(Mongolian), mr (Marathi), my (Burmese), ne (Nepali), nl (Dutch), pl (Polish),
ps (Pashto), pt (Portuguese), ro (Romanian), ru (Russian), si (Sinhala), sl
(Slovenian), sv (Swedish), sw (Swahili), ta (Tamil), te (Telugu), th (Thai),
tl (Tagalog), tr (Turkish), uk (Ukrainian), ur (Urdu), vi (Vietnamese), xh
(Xhosa). We note that a recent multilingual instruction dataset called Aya
(Singh et al., 2024) was released at the time of writing. We leave it as a
future study.

###  2.3 Base Language Model

Multilingual language models can inherit biases present in the training data,
which may affect their responses when fine-tuned. We adopt a representative
multilingual language model: BLOOM (Scao et al., 2022) that is developed with
careful consideration in multiple natural and coding languages. Its
multilingual capacity makes it well-suited for a wide range of natural
language processing tasks across multiple languages. In our specific
application, we opt for the BLOOM-7B1 variant with 7.1B parameters. This
parameter count ensures necessary capabilities for text understanding and
generation across a multitude of languages and contexts, and it is affordable
considering our computing budget.

##  3 Experimental Setup

###  3.1 Training Details

We use the Hugging Face transformers framework (Wolf et al., 2019) with the
DeepSpeed integration (Rasley et al., 2020) as the training software. The
learning rate is set to 3e-5. The batch size was established at 4 per device.
Gradient accumulation, with a step size of 4, enables the aggregation of
gradients over multiple steps. The number of training epochs is fixed at 3.
The maximum model length is set to 768, the same as the Bactrian-X paper (Li
et al., 2023). Models are trained on the cluster with 4 AMD MI250X GPUs (8 GPU
dies) in each node. We adopt distributed training on multiple nodes from 2 to
10 nodes with the increase in the number of languages, making the global batch
size from 256 to 1280.

###  3.2 Benchmarks and Evaluation

We evaluate the instruction-tuned models on three multilingual benchmarks.
XCOPA (Ponti et al., 2020) is a multilingual dataset for causal commonsense
reasoning in 11 languages XStoryCloze (Lin et al., 2021) is a multilingual
dataset derived from the English StoryCloze dataset (Mostafazadeh et al.,
2017) for commonsense reasoning in the story, translated into 10 non-English
languages. The test involves a system selecting the appropriate ending for a
four-sentence story. XWinograd (Tikhonov & Ryabinin, 2021) is a multilingual
compilation of Winograd Schemas (Levesque et al., 2012) available in six
languages, designed for assessing cross-lingual commonsense reasoning
abilities. We utilize zero-shot evaluation techniques facilitated by the
Language Model Evaluation Harness (lm-evaluation-harness) (Gao et al., 2023).
Different models, trained with progressively added languages, are evaluated on
these benchmarks using accuracy (%) as the evaluation metric.

##  4 Results and Discussion

This section presents the experimental results and our findings.

###  4.1 Overall Performance with the Increasing Number of Languages

We first answer the effect of the number of languages on multilingual
performance - how much multilingualism is needed for instruction-tuning a
large language model, i.e., BLOOM-7B1 in our case study. Figure 1(a)
illustrates the average accuracy on three benchmarks with the increase in the
number of languages. The figure shows fluctuating results. For XCOPA and
XStoryCloze, there is a slightly increasing trend with the increasing number
of instruction languages, except for a notable drop when Korean is added into
the instruction languages. For XWinograd, the trend is not clear, and the
performance also drops when Korean is added. We checked the training curve of
the model trained with Korean added to instruction data and found that the
training and validation loss decreases as training goes on and the model
converges as expected.

Moving to the performance in reference languages, i.e., English and Chinese,
we notice a similar drop in accuracy when Korean is added, as displayed in
Figures 1(b), 1(c) and 1(d), but no obvious trend for cross-lingual transfer
capacity with the increase in the number of languages. For XCOPA, instruction
fine-tuning on Chinese improves the accuracy of the target language, and the
accuracy peaks at the model when Bangla (bn), the 6th language, is added for
instruction fine-tuning. For English and Chinese XStoryCloze, Latvian (lv, the
27th language added) and Malaysian (ml, the 29th language added) are helpful
to boost the performance in these languages respectively. Instruction fine-
tuning turns out to be harmful on the XWinograd dataset, as shown in Figure
1(d) that instruction fine-tuned models are less performant than the base LLM.
Multilingual instruction fine-tuning does not generalize on the three
benchmarks studied; sometimes, multilingual instruction tuning is detrimental.

Overall, the performance of multilingual evaluation does not increase linearly
with the number of languages of instruction data. The effect of the number of
languages on multilingual performance is dependent on the task and the
language added for training. Our results show that instruction fine-tuning
with a few languages is good for cross-lingual transfer but not the most
performant. Further, adding more languages, even in alphabetical order, can
sometimes improve the performance and is occasionally harmful in XCOPA and
XStoryCloze, while in XWinograd, multilingual instruction fine-tuning is
detrimental.

(a) All languages on three benchmarks

(b) Chinese XCOPA

(c) English and Chinese XStoryCloze

(d) English and Chinese XWinograd

Figure 1: Overall accuracy on all languages evaluated (Figure 1(a)) and
accuracy on English and Chinese that act as reference languages (Figures 1(b),
1(c) and 1(d)). ‘instruct’ in the round brackets indicates the scores are
obtained by instruction-tuned models. ‘base’ stands for that obtained by the
base model.

###  4.2 Language Exposure

Assessing the performance of multilingual models after instruction fine-tuning
can be challenging, as it may involve evaluating their proficiency across
multiple languages and tasks. The multilingual benchmarks do not cover the
full list of languages used during pretraining and instruction tuning. We
group the languages into four categories according to base and instruction-
tuned models’ language coverage:

  1. 1.

languages are seen by the base and instruction models, including id, sw, ta,
vi, zh (XCOPA); ar, en, es, hi, id, sw, te, zh (XStoryCloze); en, fr, pt, zh
(Winograd)

  2. 2.

languages are seen by the base model but not the instruction model, including
ht (XCOPA) and eu (XStoryCloze)

  3. 3.

languages are unseen by the base model but seen by the instruction model,
including et, it, th, tr (XCOPA); my, ru (XStoryCloze); ru (XWinograd)

  4. 4.

languages are unseen by the base nor instruction model, including qu (XCOPA)
and jp (XWinograd)

We analyze the performance of multilingual instruction tuning with the
increase in the number of languages in different groups with a focus on unseen
languages by the base or instruction-tuned model. Cross-lingual transfer does
happen in some cases, depending on benchmarks and languages.

Figure 2 displays the accuracy of languages seen by the base model but unseen
during instruction fine-tuning. Multilingual instruction fine-tuning on
languages other than the target languages (i.e., ht and eu) shows good cross-
lingual transfer ability in most cases. And we also see a notable drop in eu
in the XStoryCloze when Korean is added for instruction tuning.

(a) XCOPA

(b) XStoryCloze

Figure 2: Accuracy on languages seen by the base model but unseen by
instruction-tuned model

Then, we look at whether multilingual instruction fine-tuning can adapt the
base LLM to unseen languages during pretraining. Figure 3 shows the accuracy
of languages that have not been used for training the base model but are used
during instruction tuning. We find that adding a language to instruction
tuning can immediately improve the performance on that language as
anticipated, especially for th in Figure 3(c), my in Figure 3(e) and ru in
Figure 3(f), the improvement is remarkable. But for ru in the XWinograd
dataset in Figure 3(g), the improved performance is still worse than the base
model. We also observe that cross-lingual transfer is happening in the
evaluated languages. For example, the performance on et and it in XCOPA shown
in Figures 3(a) and 3(b) can be further improved with the increase of
instruction languages, and instruction fine-tuning on languages other than the
target language tr can contribute to an improved performance than the base
model as in Figure 3(d).

(a) et, the 10th mIT language, in XCOPA

(b) it, the 20th mIT language, in XCOPA

(c) th, the 46th mIT language, in XCOPA

(d) tr, the 48th mIT language, in XCOPA

(e) my, the 32nd mIT language, in XStoryCloze

(f) ru, the 39th mIT language, in XStoryCloze

(g) ru, the 39th mIT language, in XWingrad

Figure 3: Accuracy on languages unseen by the base model but seen by the
instruction-tuned model. The subcaptions indicate the order of evaluated
languages that are added to the instruction languages. The square mark in
black indicates the target language evaluated.

There are two languages that are not covered by the base model and
instruction-tuned models, i.e., qu and jp. Figure 4 shows the results. The
accuracy on qu fluctuates in general, but with a steadily increasing trend
when adding lt, lv, mk, ml, mn, and mr. The accuracy on jp also fluctuates,
but with more than 20 languages for instruction tuning is better than tuning
with fewer than 20 languages in many cases. Moreover, the performance on jp
shows an opposite result to the performance on other languages, and the
average performance - instruction fine-tuning is beneficial to jp in XWinograd
that is completely unseen during pretraining or fine-tuning.

Figure 4: Accuracy on languages unseen by the base model but unseen by
instruction-tuned model. Only XCOPA and XWinograd have languages under this
category.

###  4.3 Language Similarity

We conduct a post-hoc analysis on how language closeness affects cross-lingual
transfer. Instead of studying the relation between the number of fine-tuning
languages and test set performance, we define an aggregated similarity measure
between all languages present in a fine-tuning corpus and a test language
$L_{\mathrm{test}}$:

$\mathrm{similarity}_{\mathrm{train},\mathrm{test}}=\sum_{L\in\mathrm{corpus}}\mathrm{sim}(L,L_{\mathrm{test}})$

where $\mathrm{sim}(,)$ is a similarity metric between two languages. We
measure “aggregated similarity” instead of “average similarity” because we
argue that, given their giant sizes, LLMs have the capacity to model all
language data in the training set simultaneously.

We adopt different similarity measures based on syntactic, geographic,
phonological, genetic, inventory, and featural distances scored by lang2vec
(Littell et al., 2017; Malaviya et al.,
2017).111https://github.com/antonisa/lang2vec In addition, we gathered from
another source a language closeness score derived from sound (consonants)
overlap which is deemed to reflect genetic similarity (Beaufils & Tomin,
2020).222http://www.elinguistics.net/language_evolution.html In total, we test
out seven measures, where the similarity is always normalized to between 0 and
1, indicating the least and most similar. The choice of language closeness
features is similar to a contemporaneous study on language transferability and
similarity (Philippy et al., 2024). For comparison, we provide Pearson
correlation coefficients between the number of languages and performance.
Also, since empirically we observe that the checkpoint with the addition of
Korean has an outlier performance, we also compute coefficients without that
particular checkpoint.

The following observations are made on the benchmarks. Many factors contribute
to the correlation: different languages, different tasks, and different
similarity measures. lang2vec genetic features seem to stand out among all
language features we test for, usually resulting in a higher correlation than
simply the number of languages. We also find that certain languages are
affected by other languages more, e.g. th and sw, whereas certain languages
have weak correlations with these features, e.g. en and zh. Also, across
different test sets, the same language could display distinct behaviours such
as ru in XStoryCloze and XWinograd.

| et | id | it | sw | ta | th | tr | vi | zh
---|---|---|---|---|---|---|---|---|---
num. lang. | 0.44 | 0.44 | 0.63 | 0.54 | -0.80 | 0.53 | 0.45 | -0.46 | -0.20
num. lang. w/o ko | 0.44 | 0.50 | 0.64 | 0.54 | -0.80 | 0.53 | 0.46 | -0.50 | -0.39
sound correspondence | 0.51 | 0.48 | 0.64 | 0.64 | -0.83 | 0.62 | 0.45 | -0.36 | -0.20
lang2vec featural | 0.46 | 0.45 | 0.63 | 0.56 | -0.81 | 0.55 | 0.45 | -0.44 | -0.19
lang2vec genetic | 0.67 | 0.58 | 0.67 | 0.93 | -0.84 | 0.82 | 0.47 | 0.02 | 0.01
lang2vec geographic | 0.43 | 0.46 | 0.64 | 0.93 | -0.80 | 0.55 | 0.45 | -0.45 | 0.01
lang2vec inventory | 0.46 | 0.45 | 0.64 | 0.52 | -0.80 | 0.55 | 0.45 | -0.45 | -0.19
lang2vec phonological | 0.45 | 0.45 | 0.62 | 0.54 | -0.80 | 0.55 | 0.44 | -0.45 | -0.19
lang2vec syntactic | 0.45 | 0.45 | 0.63 | 0.54 | -0.81 | 0.54 | 0.45 | -0.45 | -0.19
Table 1: Pearson correlation between XCOPA performance and training data similarity | ar | en | es | hi | id | my | ru | sw | te | zh
---|---|---|---|---|---|---|---|---|---|---
num. lang. | -0.07 | 0.15 | 0.46 | 0.51 | 0.53 | 0.75 | 0.81 | 0.56 | -0.47 | 0.11
num. lang. w/o ko | 0.08 | 0.41 | 0.73 | 0.66 | 0.63 | 0.75 | 0.86 | 0.56 | -0.53 | 0.31
sound correspondence | -0.06 | 0.15 | 0.48 | 0.52 | 0.57 | 0.82 | 0.83 | 0.67 | -0.43 | 0.12
lang2vec featural | -0.05 | 0.15 | 0.47 | 0.51 | 0.53 | 0.77 | 0.83 | 0.58 | -0.46 | 0.13
lang2vec genetic | 0.17 | 0.16 | 0.50 | 0.54 | 0.66 | 0.96 | 0.87 | 0.96 | -0.26 | 0.37
lang2vec geographic | 0.17 | 0.15 | 0.47 | 0.51 | 0.54 | 0.76 | 0.81 | 0.96 | -0.48 | 0.37
lang2vec inventory | -0.06 | 0.15 | 0.46 | 0.51 | 0.54 | 0.76 | 0.83 | 0.55 | -0.46 | 0.13
lang2vec phonological | -0.05 | 0.15 | 0.47 | 0.51 | 0.53 | 0.76 | 0.83 | 0.57 | -0.45 | 0.13
lang2vec syntactic | -0.05 | 0.15 | 0.47 | 0.51 | 0.53 | 0.78 | 0.82 | 0.57 | -0.45 | 0.13
Table 2: Pearson correlation between XStoryCloze performance and training data similarity | en | fr | jp | pt | ru | zh
---|---|---|---|---|---|---
num. lang. | -0.02 | 0.01 | 0.62 | -0.32 | -0.07 | 0.49
num. lang. w/o ko | -0.03 | 0.00 | 0.66 | -0.35 | -0.07 | 0.50
sound correspondence | -0.01 | -0.01 | 0.66 | -0.33 | -0.06 | 0.45
lang2vec featural | -0.01 | 0.00 | 0.62 | -0.31 | -0.06 | 0.47
lang2vec genetic | -0.02 | -0.08 | 0.72 | -0.35 | -0.05 | -0.31
lang2vec geographic | -0.02 | -0.01 | 0.62 | -0.33 | -0.07 | -0.31
lang2vec inventory | -0.01 | 0.00 | 0.62 | -0.31 | -0.06 | 0.48
lang2vec phonological | -0.01 | 0.01 | 0.63 | -0.32 | -0.06 | 0.48
lang2vec syntactic | -0.02 | 0.00 | 0.62 | -0.32 | -0.06 | 0.47
Table 3: Pearson correlation between XWinograd performance and training data
similarity

##  5 Related Work

#### Multilingual LLMs

Multilingual large language models have been trained to handle multiple
languages, leveraging shared linguistic features across diverse language data.
Many multilingual LLMs have emerged such as BLOOM (Scao et al., 2022), PaLM
(Anil et al., 2023), MADLAD-400 (Kudugunta et al., 2024), and MaLA-500 (Lin et
al., 2024). The following studies have been conducted to explore the capacity
of multilingual LLMs. For example, Ye et al. (2023) examined the multilingual
transfer ability of English-centric models compared to multilingual pretrained
models, and Yuan et al. (2023) assessed the multilingual capacity across 101
languages and revealed that existing LLMs exhibit greater multilingual
capabilities than anticipated.

#### Multilingual Instruction Tuning

Fine-tuning large multilingual language models has attracted much attention in
recent years due to their capability to handle diverse linguistic contexts
effectively. Kew et al. (2023) investigated the impact of multilinguality
during fine-tuning on cross-lingual generalization. Chen et al. (2024)
explored cost-efficient strategies for multilingual instruction tuning of
large language models and compared monolingual and multilingual instruction
tuning using different tuning methods. Shaham et al. (2024) studied the number
of languages for instruction tuning using up to 11 languages and found that
monolingual tuning transfers instruction-following capabilities across
languages. Chirkova & Nikoulina (2024a) explored the effectiveness of zero-
shot cross-lingual generation by fine-tuning multilingual pretrained language
models on generative tasks. Then, Chirkova & Nikoulina (2024b) further
expanded the study to zero-shot cross-lingual transfer of large language
models. Both studies emphasized the importance of model configuration. While
previous works tried to constrain the amount of training data and squeeze the
number of languages, this work attempts to scale up the number of languages,
yielding additional findings to (zero-shot) language transfer. In a small-
scale experiment, the authors of the Bactrian-X dataset discovered that
monolingual models fine-tuned with low-rank adaptation are better than a
single multilingual model (Li et al., 2023), which is different from our
findings albeit with very different experimental setups.

##  6 Conclusion and Future Work

Instruction fine-tuning of large multilingual language models presents both
opportunities and challenges. While it can enable versatile language
processing capabilities, it also demands careful handling to address issues
related to language-specific nuances. Various studies analyzed multilingualism
and cross-lingual transferability in different settings, leading to different
conclusions. This paper conducts an experimental analysis on yet another set
of settings and reveals different findings from prior works, showing that even
with the same base model, instruction data, and training recipe, the
performance is still dependent on the evaluation tasks. Building upon the
findings of prior works and our study, we conclude that the performance of
multilingual instruction fine-tuning is highly dependent on factors such as
base models, instruction data, tasks, and evaluation protocols. Our study
stresses the importance of the theoretical study on the effectiveness and
generalizability of multilingual instruction fine-tuning, as well as the need
for more systematic experimental studies to validate the theory.

## Limitations

Our work studies multilingual instruction fine-tuning in 52 languages, which
might be small compared to thousands of living languages. We did not conduct a
human evaluation due to limited budget constraints. Future work would be to
conduct a more systematic assessment with more rigorously controlled variables
during instruction tuning.

## Ethical Considerations

Multilingual instruction fine-tuning also raises ethical questions about the
responsible use of AI models, especially when dealing with diverse linguistic
and cultural contexts. This paper investigates the challenge in instruction
fine-tuning large multilingual language models and learning lessons to
facilitate future research to harness the full potential of multilingual
models while minimizing potential drawbacks.

## Reproducibility Statement

We make the following efforts to ensure reproducible research. Our base model,
instruction dataset, and evaluation benchmarks are all open-source. We release
the fine-tuned model weights. Our results are reproducible using the provided
model weights and evaluation scripts.

## Acknowledgements

The work has received funding from the European Union’s Horizon Europe
research and innovation programme under grant agreement No 101070350 and from
UK Research and Innovation (UKRI) under the UK government’s Horizon Europe
funding guarantee [grant number 10052546]. Shaoxiong Ji also received funding
from UTTER’s Financial Support for Third Parties. We acknowledge CSC-IT Center
for Science, Finland for awarding this project access to the LUMI
supercomputer, owned by the EuroHPC Joint Undertaking, hosted by CSC (Finland)
and the LUMI consortium through Finnish extreme scale call (project LumiNMT
and MOOMIN) and the call from the Ministry of Education, Youth and Sports of
the Czech Republic through the e-INFRA CZ (ID:90254).

## References

  * Almazrouei et al. (2023) Ebtesam Almazrouei, Hamza Alobeidli, Abdulaziz Alshamsi, Alessandro Cappelli, Ruxandra Cojocaru, Mérouane Debbah, Étienne Goffinet, Daniel Hesslow, Julien Launay, Quentin Malartic, et al.  The Falcon series of open language models.  _arXiv preprint_ , 2023.
  * Anil et al. (2023) Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, et al.  PaLM 2 technical report.  _arXiv preprint_ , 2023.
  * Beaufils & Tomin (2020) Vincent Beaufils and Johannes Tomin.  Stochastic approach to worldwide language classification: the signals and the noise towards long-range exploration.  _SocArXiv_ , 2020.
  * Chen et al. (2024) Pinzhen Chen, Shaoxiong Ji, Nikolay Bogoychev, Andrey Kutuzov, Barry Haddow, and Kenneth Heafield.  Monolingual or multilingual instruction tuning: Which makes a better alpaca.  In _Findings of the Association for Computational Linguistics: EACL 2024_ , 2024.
  * Chirkova & Nikoulina (2024a) Nadezhda Chirkova and Vassilina Nikoulina.  Key ingredients for effective zero-shot cross-lingual knowledge transfer in generative tasks.  _arXiv preprint_ , 2024a.
  * Chirkova & Nikoulina (2024b) Nadezhda Chirkova and Vassilina Nikoulina.  Zero-shot cross-lingual transfer in instruction tuning of large language model.  _arXiv preprint_ , 2024b.
  * Conover et al. (2023) Mike Conover, Matt Hayes, Ankit Mathur, Xiangrui Meng, Jianwei Xie, Jun Wan, Sam Shah, Ali Ghodsi, Patrick Wendell, Matei Zaharia, and Reynold Xin.  Free Dolly: Introducing the world’s first truly open instruction-tuned LLM.  https://www.databricks.com, 2023.
  * Gao et al. (2023) Leo Gao, Jonathan Tow, Stella Biderman, Sid Black, Anthony DiPofi, Charles Foster, Laurence Golding, Jeffrey Hsu, Kyle McDonell, Niklas Muennighoff, et al.  A framework for few-shot language model evaluation.  Zenodo, 2023.
  * Kew et al. (2023) Tannon Kew, Florian Schottmann, and Rico Sennrich.  Turning english-centric llms into polyglots: How much multilinguality is needed?  _arXiv preprint_ , 2023.
  * Kudugunta et al. (2024) Sneha Kudugunta, Isaac Caswell, Biao Zhang, Xavier Garcia, Derrick Xin, Aditya Kusupati, Romi Stella, Ankur Bapna, and Orhan Firat.  Madlad-400: A multilingual and document-level large audited dataset.  _Advances in Neural Information Processing Systems_ , 2024.
  * Levesque et al. (2012) Hector Levesque, Ernest Davis, and Leora Morgenstern.  The Winograd schema challenge.  In _Thirteenth international conference on the principles of knowledge representation and reasoning_ , 2012.
  * Li et al. (2023) Haonan Li, Fajri Koto, Minghao Wu, Alham Fikri Aji, and Timothy Baldwin.  Bactrian-x : A multilingual replicable instruction-following model with low-rank adaptation.  _arXiv preprint_ , 2023.
  * Lin et al. (2024) Peiqin Lin, Shaoxiong Ji, Jörg Tiedemann, André FT Martins, and Hinrich Schütze.  MaLA-500: Massive language adaptation of large language models.  _arXiv preprint arXiv:2401.13303_ , 2024.
  * Lin et al. (2021) Xi Victoria Lin, Todor Mihaylov, Mikel Artetxe, Tianlu Wang, Shuohui Chen, Daniel Simig, Myle Ott, Naman Goyal, Shruti Bhosale, Jingfei Du, et al.  Few-shot learning with multilingual language models.  _arXiv preprint_ , 2021.
  * Littell et al. (2017) Patrick Littell, David R. Mortensen, Ke Lin, Katherine Kairis, Carlisle Turner, and Lori Levin.  URIEL and lang2vec: Representing languages as typological, geographical, and phylogenetic vectors.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers_ , 2017\.
  * Liu et al. (2020) Yinhan Liu, Jiatao Gu, Naman Goyal, Xian Li, Sergey Edunov, Marjan Ghazvininejad, Mike Lewis, and Luke Zettlemoyer.  Multilingual denoising pre-training for neural machine translation.  _Transactions of the Association for Computational Linguistics_ , 2020\.
  * Malaviya et al. (2017) Chaitanya Malaviya, Graham Neubig, and Patrick Littell.  Learning language representations for typology prediction.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , 2017.
  * Mostafazadeh et al. (2017) Nasrin Mostafazadeh, Michael Roth, Annie Louis, Nathanael Chambers, and James Allen.  Lsdsem 2017 shared task: The story cloze test.  In _Proceedings of the 2nd Workshop on Linking Models of Lexical, Sentential and Discourse-level Semantics_ , 2017.
  * Philippy et al. (2024) Fred Philippy, Siwen Guo, Shohreh Haddadan, Cedric Lothritz, Jacques Klein, and Tegawendé F. Bissyandé.  Soft prompt tuning for cross-lingual transfer: When less is more.  In _Proceedings of the 1st Workshop on Modular and Open Multilingual NLP (MOOMIN 2024)_ , 2024.
  * Ponti et al. (2020) Edoardo Maria Ponti, Goran Glavaš, Olga Majewska, Qianchu Liu, Ivan Vulić, and Anna Korhonen.  XCOPA: A multilingual dataset for causal commonsense reasoning.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , 2020.
  * Rasley et al. (2020) Jeff Rasley, Samyam Rajbhandari, Olatunji Ruwase, and Yuxiong He.  Deepspeed: System optimizations enable training deep learning models with over 100 billion parameters.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2020.
  * Scao et al. (2022) Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ilić, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, Matthias Gallé, et al.  BLOOM: A 176B-parameter open-access multilingual language model.  _arXiv preprint_ , 2022.
  * Shaham et al. (2024) Uri Shaham, Jonathan Herzig, Roee Aharoni, Idan Szpektor, Reut Tsarfaty, and Matan Eyal.  Multilingual instruction tuning with just a pinch of multilinguality.  _arXiv preprint_ , 2024.
  * Shliazhko et al. (2022) Oleh Shliazhko, Alena Fenogenova, Maria Tikhonova, Vladislav Mikhailov, Anastasia Kozlova, and Tatiana Shavrina.  mGPT: Few-shot learners go multilingual.  _arXiv preprint_ , 2022.
  * Singh et al. (2024) Shivalika Singh, Freddie Vargus, Daniel Dsouza, Börje F Karlsson, Abinaya Mahendiran, Wei-Yin Ko, Herumb Shandilya, Jay Patel, Deividas Mataciunas, Laura OMahony, et al.  Aya dataset: An open-access collection for multilingual instruction tuning.  _arXiv preprint_ , 2024.
  * Taori et al. (2023) Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto.  Stanford Alpaca: An instruction-following LLaMA model.  https://github.com/tatsu-lab/stanford_alpaca, 2023.
  * Tikhonov & Ryabinin (2021) Alexey Tikhonov and Max Ryabinin.  It’s All in the Heads: Using Attention Heads as a Baseline for Cross-Lingual Transfer in Commonsense Reasoning.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , 2021.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.  LLaMA: Open and efficient foundation language models.  _arXiv preprint_ , 2023.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al.  Huggingface’s transformers: State-of-the-art natural language processing.  _arXiv preprint_ , 2019.
  * Ye et al. (2023) Jiacheng Ye, Xijia Tao, and Lingpeng Kong.  Language versatilists vs. specialists: An empirical revisiting on multilingual transfer ability.  _arXiv preprint_ , 2023.
  * Yuan et al. (2023) Fei Yuan, Shuai Yuan, Zhiyong Wu, and Lei Li.  How multilingual is multilingual llm?  _arXiv preprint_ , 2023.