# Online Graph Coloring with Predictions

Antonios Antoniadis , Hajo Broersma, Yang Meng
Faculty of Electrical Engineering, Mathematics and Computer Science
University of Twente

###### Abstract

We introduce learning augmented algorithms to the online graph coloring
problem. Although the simple greedy algorithm FirstFit is known to perform
poorly in the worst case, we are able to establish a relationship between the
structure of any input graph $G$ that is revealed online and the number of
colors that FirstFit uses for $G$. Based on this relationship, we propose an
online coloring algorithm FirstFitPredictions that extends FirstFit while
making use of machine learned predictions. We show that FirstFitPredictions is
both _consistent_ and _smooth_. Moreover, we develop a novel framework for
combining online algorithms at runtime specifically for the online graph
coloring problem. Finally, we show how this framework can be used to robustify
FirstFitPredictions by combining it with any classical online coloring
algorithm (that disregards the predictions).

keywords— learning augmented algorithms, online algorithms, online graph
coloring, first fit

##  1 Introduction

Before we will properly define the concepts we use throughout this paper in
Section 1.1, let us start with a less formal introduction to the subject,
together with some background and motivation.

Graph coloring is a central topic within graph theory that finds its origin in
the notorious Four Color Problem, dating back to 1852. Since then graph
coloring has developed into a mature research field with numerous application
areas, ranging from scheduling [30, 5] and memory allocation [4] to robotics
[14]. In the online version of the problem, the vertices of a (usually
unknown) graph arrive online one by one, together with the adjacencies to the
already present vertices. Upon the arrival of each vertex $v$, a color has to
be irrevocably assigned to $v$. The goal is to obtain a proper coloring, that
is a coloring in which no two adjacent vertices have the same color. The
challenge is to design a coloring strategy which keeps the total number of
assigned colors relatively low.

In this paper, we introduce the online graph coloring problem to learning
augmented algorithms. We assume that alongside the arrival of each vertex, the
algorithm also obtains a prediction $P(v)$ (of unknown quality) on the color
that should be assigned to $v$. These predictions may be used by an algorithm
to obtain a coloring which uses fewer colors, if the predictions turn out to
be relatively accurate. At the same time, the algorithm should maintain a
worst-case guarantee to safeguard against the case in which the predictions
are inaccurate.

Graph coloring is notoriously hard, already in the _offline setting_ , where
the whole input graph is known in advance. Let $\chi(G)$ denote the _chromatic
number_ of a graph $G$, that is the minimum number of distinct colors needed
to obtain a proper coloring of $G$. A straightforward observation is that
$\chi(G)$ is greater than or equal to $\omega(G)$, which is defined as the
cardinality of a maximum clique in $G$. However, there even exist triangle-
free graphs (so with no cliques of cardinality 3) with an arbitrarily large
chromatic number. In case $\chi(H)=\omega(H)$ for every induced subgraph $H$
of a graph $G$, then $G$ is called a _perfect graph_. Perfect graphs are known
to be $\chi(G)$-colorable in polynomial-time via semidefinite programming
[16]. An interesting special case of perfect graphs is the class of bipartite
graphs. These graphs admit a proper coloring using only $2$ colors, and in the
offline setting such a $2$-coloring can be computed in linear time, for
example via breadth first search. However, in general it is an NP-complete
problem to decide whether a given graph admits a proper coloring using $k$
colors, for any fixed $k\geq 3$ [25]. With respect to approximation
algorithms, there is a polynomial-time algorithm using at most $O(n(\log\log
n)^{2}/(\log n)^{3})\cdot\chi(G)$ [21] colors for a graph on $n$ vertices, and
it is NP-hard to approximate the chromatic number within a factor
$n^{1-\epsilon}$ for all $\epsilon>0$ [36].

The problem becomes even more challenging in the _online setting_ where, as
mentioned, vertices arrive online one by one and an algorithm has to
irrevocably assign a color to each vertex upon its arrival – while only having
knowledge of the subgraph revealed so far. Any online algorithm may require at
least $(2n/(\log n)^{2})\chi(G)$ colors in the worst case [22], where $n$ is
the number of vertices of the input graph – and this is true even for
bipartite graphs (so with chromatic number $2$). Restricting the input graphs
even further, for instance to $P_{6}$-free bipartite graphs (containing no
path on six vertices as an induced subgraph), no online algorithm can
guarantee a coloring with constantly many colors [19]. In such cases, bounding
the number of colors used from above by a function of the chromatic number is
not feasible. To this end, a line of research has focused on developing so-
called _online-competitive algorithms_. Applied to any graph $G$, such online
algorithms are guaranteed to produce a proper coloring, the number of colors
of which is bounded from above by a function of the number of colors used by
the _best possible online algorithm_ for $G$. As an example, in the previously
mentioned setting of $P_{6}$-free bipartite graphs, there exists an online
algorithm that uses at most twice as many colors as the best possible online
algorithm [9, 31]. A good source for more information regarding online graph
coloring is the following book chapter due to Kierstead [26]. We will come
back to this in Section 3.3, where we review and utilize several known
results, including more recent work.

Probably the conceptually simplest online algorithm for graph coloring is the
greedy algorithm, which is known as FirstFit. Suppose we have a total order
over the set of available colors. Then upon arrival of each vertex, FirstFit
assigns to it the smallest color according to that order, among the ones that
maintain a proper coloring. This algorithm has been extensively analyzed in
the literature, also for particular graph classes [19, 23]. Although FirstFit
performs well for many practically relevant inputs, it can be very sensitive
to the order in which the vertices of $G$ are revealed. For instance, in a
popular example where $G$ is a complete balanced bipartite graph $K_{n,n}$
minus a perfect matching, there is a specific permutation on the arrival of
the vertices of $G$ for which FirstFit requires $n$ colors (whereas
$\chi(G)=2$) [24].

That FirstFit performs well in some practical scenarios, can be attributed to
the fact that real-world graph coloring instances rarely resemble worst-case
inputs. It is often the case that either the structure of the input graph or
the permutation in which the vertices are revealed can be exploited by a
heuristic or a machine-learning approach in order to yield reasonably good
colorings, despite the inherent worst-case difficulty of the problem. However,
and not too surprisingly, such approaches tend to come without a worst-case
guarantee. In the (hopefully rare) cases where the input diverges
substantially from the expected structure, the resulting coloring could be
arbitrarily poor.

In this paper, we design an algorithm that incorporates predictions of unknown
quality obtained by such a machine-learned approach. It produces a relatively
good coloring in case the predictions turn out to be accurate, while at the
same time providing a worst-case guarantee comparable to the best classical
online algorithm that does not make use of the predictions. Our work falls
within the context of _learning augmented algorithms_.

Learning augmented algorithms is a relatively new and very active field. The
main goal is to develop algorithms combining the respective advantages of
machine-learning approaches and classical worst case algorithm analysis. A
plethora of online problems have already been investigated through the
learning augmented algorithm lens, including for example, caching [29, 2],
facility location [13], ski-rental [34, 35], or various scheduling problems
[34, 27], to name just a few. To the best of our knowledge, learning augmented
algorithms have not been studied for graph coloring problems to date. For a
more extensive discussion on learning augmented algorithms, we refer the
interested reader to a recent survey [33].

A common approach to developing learning augmented algorithms is to design an
algorithm that attempts to follow the predictions, in some sense. At the same
time, this algorithm should be robustified by appropriately combining it with
a classical algorithm that disregards the predictions. At a high level, this
is our approach for graph coloring as well. However, the nature of the problem
poses several novel challenges. First of all, already assigned colors may
significantly restrict the choice of colors for the next and future
assignments of the algorithm. This is in contrast to settings where an
algorithm can, at some cost, move to any arbitrary configuration, for
instance, in problems with an underlying metric. The fact that it is not
possible for an algorithm to move to any possible configuration also rules out
a robustification approach by combining algorithms in an experts-like setting.
See [3] for more information. Secondly, existing online algorithms for online
graph coloring do not possess a particular monotonicity property that tends to
be a crucial ingredient in robustifying algorithms for other problems. In
particular, it is possible that running an algorithm only on the graph induced
by a suffix of the input permutation requires significantly more colors than
running the same algorithm on the graphs of the complete input permutation.
This further complicates the robustification, since one can not directly use a
classical algorithm as a fall back option upon recognizing that the
predictions are of insufficient quality.

###  1.1 Preliminaries

In this section, we formally define the problem setting and its associated
prediction model. We start with the concepts related to (offline) graph
coloring.

######  Definition 1 (Graph coloring [8]).

A _$k$ -vertex coloring_, or simply a _$k$ -coloring_, of a graph $G$ is a
mapping $\phi:V(G)\rightarrow S$, where $S$ is a set of $k$ colors. A
$k$-coloring is proper if no two adjacent vertices are assigned the same
color. A graph is _$k$ -colorable_ if it admits a proper $k$-coloring. The
minimum $k$ for which a graph $G$ is $k$-colorable is called its _chromatic
number_ , denoted by $\chi(G)$. An optimal coloring of $G$ is a proper
$\chi(G)$-coloring.

Online graph coloring describes the setting in which the vertices of $G$
arrive one by one in an online fashion and have to be irrevocably and properly
colored upon arrival.

######  Definition 2 (Online graph coloring [32]).

An _online graph_ $(G,\pi)$ is a graph $G$ together with a permutation
$\pi=v_{1},v_{2},\ldots,v_{n}$ of $V(G)$. An _online coloring algorithm_ takes
an online graph $(G,\pi)$ as input and produces a proper coloring of $V(G)$,
where the color of a vertex $v_{i}$ is chosen from a _universe_ $\mathcal{U}$
of available colors and the choice depends only on the subgraph of $G$ induced
by $\\{v_{1},\ldots,v_{i}\\}$ and the colors assigned to
$v_{1},\ldots,v_{i-1}$, for $1\leq i\leq n$.

Throughout the paper, and unless otherwise specified, algorithm refers to a
_deterministic_ algorithm.

We next define the notions of _competitiveness, online competitiveness_ and
_competitive ratio_ , which are used to evaluate the performance of algorithms
for online graph coloring.

######  Definition 3 (Competitiveness [19], online competitiveness [18] and
competitive ratio [28]).

Let $AOL(G)$ be the set of all online coloring algorithms for a graph $G$ and
let $\Pi(G)$ be the set of all permutations of $V(G)$. For an algorithm
$A\in{AOL(G)}$ and a permutation $\pi\in{\Pi(G)}$, the number of colors used
by $A$ when $V(G)$ gets revealed according to $\pi$ is denoted by
$\chi_{A}(G,\pi)$. The $A$-chromatic number of $G$ is the largest number of
colors used by the online algorithm $A$ for the graph $G$, denoted by
$\chi_{A}(G)$. That is,

$\chi_{A}(G)=\mathop{\max}\limits_{\pi\in{\Pi(G)}}\chi_{A}(G,\pi)$.

For a graph $G$, the online chromatic number $\chi_{OL}(G)$ is the minimum
number of colors used for $G$, over all algorithms of $AOL(G)$. That is,

$\chi_{OL}(G)=\mathop{\min}\limits_{A\in{AOL(G)}}\chi_{A}(G)$.

Let $\mathcal{G}$ be a family of graphs and $AOL(\mathcal{G})$ be the set of
online algorithms for $\mathcal{G}$. For some $A\in{AOL(\mathcal{G})}$, if
there exists a function such that $\chi_{A}(G)\leq{f(\chi(G))}$, (resp.
$\chi_{A}(G)\leq{f(\chi_{OL}(G))}$) holds for every $G\in{\mathcal{G}}$, then
$A$ is _competitive_ (resp. _online competitive_) on $\mathcal{G}$.

Furthermore, the _competitive ratio_ of an algorithm $A\in{AOL(\mathcal{G})}$
over a class of graphs $\mathcal{G}$ is the maximum of
$\frac{\chi_{A}(G)}{\chi(G)}$ for all $G\in{\mathcal{G}}$.

We note that the notion of competitiveness used here follows the literature on
online graph coloring and contrasts the definition commonly used for other
online problems, where an algorithm is said to be competitive if it attains a
constant competitive ratio. We complete this section by presenting the basic
definitions associated with the setting, in which we involve predictions on
the colors.

##### Predictions and prediction error.

Here we assume that alongside the disclosure of each vertex $v$, the algorithm
also obtains a prediction $P:V(G)\rightarrow\mathcal{U}$ on the color of $v$,
where $\mathcal{U}$ is the set of available colors. These predictions are
aimed at obtaining a reasonable coloring. They may stem from a machine-
learning approach based on past inputs or training data, or from a simple
heuristic known to perform well in practice. The quality of the obtained
predictions is measured by means of a _prediction error_. This _prediction
error_ is defined naturally to be the (smallest) number of vertices that
obtained wrong predictions.

######  Definition 4 (Prediction error).

Given an online graph $(G,\pi)$, let $\mathcal{O}(G)$ be the set of all
optimal colorings of $G$, where $O\in\mathcal{O}$ assigns color
$O(v)\in\mathcal{U}$ to vertex $v$. Then the _prediction error_ for online
graph $(G,\pi)$ is given by

$\displaystyle\eta(G)=\min_{O\in\mathcal{O}(G)}\Sigma_{v\in
V(G)}|\\{P(v)\\}\setminus\\{O(v)\\}|.$

In the following, we drop the dependence on $G$ when the underlying online
graph is clear from the context. We use the notation $(G,\pi,P)$ to refer to
an _online graph with predictions_ , where $G$ is the underlying graph, $\pi$
the permutation in which $V$ is revealed, and $P$ the set of associated
predictions.

Following the literature, we say that an algorithm is _$\alpha$ -consistent_
if it attains a competitive ratio of $\alpha$ in the case that the predictions
are perfect ($\eta=0$), and _robust_ if it independently of the prediction
error always obtains a competitive ratio within a constant factor of that of
the best known classical online algorithm. Furthermore, we say that an
algorithm is _smooth_ if its competitive ratio degrades at a rate that is at
most linear in the prediction error. Note that the notion of robustness also
extends to the case where the best known classical online algorithm $A$ is
“only” online competitive. In this scenario, any algorithm that is guaranteed
to use at most a constant number of colors more than what $A$ uses is
_robust_.

We note that one can trivially obtain an optimal coloring when the predictions
are perfect (in other words when $\eta=0$) by just coloring each vertex $v$
with color $P(v)$ upon arrival. This already is a $1$-consistent algorithm.
However, when the obtained predictions are only slightly off, this algorithm
may not even be a valid algorithm for online graph coloring. Indeed, consider
the case where only one vertex $v$ receives a wrong prediction $P(v)$ but is
adjacent to a vertex $u$ with $P(u)=P(v)$.

###  1.2 Our Contribution

Our first contribution lies in establishing a relationship between the
structure of an online graph $(G,\pi)$ and the amount of colors used by
FirstFit for $G$. We emphasize that this result is independent of predictions
and might be of broader interest. More specifically, in Section 2 we show that
if FirstFit uses $x$ colors for $G$, then there exists a set
$V^{\prime}\subseteq V$ of vertices of size $|V^{\prime}|=x+q$, for some
$0\leq q\leq x-2$, such that $V^{\prime}$ can be partitioned into $q+1$ non-
trivial subsets, each of which is a _clique_ in $G$ (that is, each subset
consists of at least two vertices which are all pairwise adjacent in $G$). Our
result is even constructive, i.e., we present an algorithm for finding
$V^{\prime}$ and a partitioning that satisfies these properties.

######  Theorem 1.

Let $(G,\pi)$ be an online graph for which FirstFit uses $x$ colors. Then,
there exists a set $V^{\prime}\subseteq V$ of size $|V^{\prime}|=x+q$ with
$0\leq q\leq x-2$, such that $V^{\prime}$ can be partitioned into $q+1$ non-
trivial subsets of vertices, each of which is a clique.

Our second contribution is to develop a $1$-consistent and smooth algorithm
for online graph coloring with predictions, called FirstFitPredictions in
Subsection 3.1. Consider the setting where the algorithm, upon the reveal of a
vertex $v$ also obtains a prediction on the color that $v$ should be colored
with in an optimal coloring. We give an algorithm that employs FirstFit with a
distinct color palette for each subgraph induced by the set of vertices that
obtained the same prediction. By carefully utilizing the aforementioned
structural result, we are able to associate the number of colors used by the
algorithm with the number of wrong predictions obtained. More specifically, we
are able to show that the number of colors used by the algorithm differs from
that of an optimal coloring by at most the number of wrong predictions
(implying that if the predictions are perfect, the algorithm actually recovers
an optimal coloring, even though the quality of the predictions is not a
priori known to the algorithm).

######  Theorem 2.

Assume that FirstFitPredictions uses $x(G)$ colors for some online graph with
predictions $(G,\pi,P)$ whose chromatic number is unknown to the algorithm,
then $x(G)\leq{\eta(G)+\chi(G)}$.

Our third contribution is a novel framework for combining different online
graph coloring algorithms in Subsection 3.2. Earlier frameworks developed for
other online problems do not seem to carry over to the online graph coloring
problem. Our framework allows us to robustify our algorithm by combining it
with a classical algorithm that disregards the predictions. We show that the
number of colors used by the combination of the two algorithms is within a
factor of $2$ from that of the best performing of the two on this input
instance. This directly implies that this combination is a $2$-consistent,
smooth and robust algorithm.

Although in this paper we only use the framework to combine two algorithms, we
prove the result for combining any number $t$ of online algorithms (at a loss
of $t$ in the competitive ratio). Given an online graph $(G,\pi)$ and an
online coloring algorithm $A$, let $A(G)$ denote the number of colors $A$ uses
for $G$.

######  Theorem 3.

Let $A_{1},A_{2},\dots,A_{t}$ be online graph coloring algorithms that may or
may not make use of the predictions. Then, there exists a meta-algorithm $A$
that combines $A_{1},A_{2},\ldots,A_{t}$, such that for any online graph with
predictions $(G,\pi,P)$

$\displaystyle A(G)\leq t\cdot\min_{1\leq i\leq t}A_{i}(G).$

The generality of our result allows us to obtain learning augmented algorithms
for online graph coloring for several different graph classes in Subsection
3.3.

##  2 A Structural Theorem about FirstFit

This section is devoted to proving Theorem 1, which establishes a relationship
between the number of colors used by FirstFit for an online graph $(G,\pi)$
and a partition of a subset of $V$ into cliques. As mentioned, our proof is
constructive and implies an efficient algorithm for finding such a partition.
In the proof we assume that FirstFit uses $x\geq 2$ colors which are ordered
as $c_{0}<c_{1}<\ldots<c_{x-1}$. We use $N(u)$ to denote the neighbors of a
vertex $u$, i.e., the set of vertices that are adjacent to $u$.

###### Proof of Theorem 1.

Let $t_{x-1}\in V$ be a vertex for which FirstFit uses color $c_{x-1}$. By the
definition of FirstFit vertex $t_{x-1}$ must be adjacent to vertices
$t_{0},t_{1},\ldots,t_{x-2}$, such that $t_{i}$ is colored with color
$c(t_{i})=c_{i}$ for all $i=0,\ldots,x-2$. Let
$S=\bigcup_{i=0}^{x-1}\\{t_{i}\\}$ and let $N^{-}(u)=\\{w\in N(u)\cap S\ |\
c(w)<c(u)\\}$ be its _neighborhood of smaller-colored vertices within $S$_,
$\forall u\in S$.

Note that the set of vertices $V^{\prime}_{0}=\\{t_{i}\in S\ |\
N^{-}(t_{i})=\\{t_{0},t_{1},\dots,t_{i-1}\\}\\}$ is a clique. Also note that
$|V^{\prime}_{0}|\geq 2$, since $\\{t_{0},t_{x-1}\\}\subseteq V^{\prime}_{0}$.
If $V_{0}^{\prime}=S$, then the theorem directly follows for $q=0$. So, assume
for the remainder of this proof that $V_{0}^{\prime}\neq S$. Let
$S^{\prime}=S\setminus V_{0}^{\prime}=\\{u_{1},u_{2},\dots,u_{\ell}\\}$, in
which the vertices of $S^{\prime}$ are ordered by increasing color. We
describe an algorithm for partitioning $S^{\prime}$ into $q$ subsets, with the
property that each of these subsets of $S^{\prime}$ together with one distinct
vertex from $V\setminus S$ is a clique of size at least two. Note that this
implies the theorem since $1\leq|S^{\prime}|\leq x-2$ and thus $1\leq q\leq
x-2$.

At a high level, the algorithm iterates over the vertices of $S^{\prime}$ in
order of increasing color. And for each such vertex $u_{h}$, it either
identifies a vertex $\beta(u_{h})\in V\setminus S$ with
$c(\beta(u_{h}))<c(u_{h})$ such that $(u_{h},\beta(h_{h}))\in E$, and creates
a new vertex set $V_{h}^{\prime}:=\\{u_{h},\beta(u_{h})\\}$ which is a clique
of size 2, or it adds $u_{h}$ to a previously created clique $V^{\prime}_{j}$
for some $1\leq j<h$ to form a larger clique.

More specifically, for every $h\in\\{1,...,\ell\\}$ let $\alpha(u_{h})\in
S^{\prime}$ be a vertex of maximal color with $c(\alpha(u_{h}))<c(u_{h})$ such
that $\alpha(u_{h})$ is not adjacent to $u_{h}$, thus $\alpha(u_{h})\not\in
N^{-}(u_{h})$. And let $\beta(u_{h})\in V\setminus S$ be a vertex with
$c(\beta(u_{h}))=c(\alpha(u_{h}))$ that is adjacent to $u_{h}$. Note that such
vertices must exist: if $\alpha(u_{h})$ did not exist, then $u_{h}$ would be
contained in $V_{0}^{\prime}$; and if $\beta(u_{h})$ did not exist, FirstFit
would have assigned a smaller color, namely $c(\alpha(u_{h}))$, to $u_{h}$.

The algorithm proceeds iteratively over the vertices of $S^{\prime}$ in order
of increasing color. For each vertex $u_{h}\in S^{\prime}$, if
$\beta(u_{h})\not\in V_{j}^{\prime}$ for all $j$ with $1\leq j<h$, then a new
clique $V_{h}^{\prime}=\\{u_{h},\beta(u_{h})\\}$ is created. Else, there
exists a $j$ with $1\leq j<h$ such that $\beta(u_{h})\in V_{j}^{\prime}$. In
this case, set $V_{j}^{\prime}:=V_{j}^{\prime}\cup\\{u_{h}\\}$, in other
words, add $u_{h}$ to $V_{j}^{\prime}$. We will show that this creates a
larger clique. But first note that by the definition of the algorithm each
different $\beta(u_{h})$ is added to exactly one such set $V^{\prime}_{j}$,
and each such set $V_{j}^{\prime}$ contains exactly one specific
$\beta(u_{h})$. Thus, the output is indeed a partition of
$S^{\prime}\bigcup\cup_{h}\\{\beta(u_{h})\\}$.

It remains to argue that upon termination, each set $V^{\prime}_{j}$ is a
clique. We will prove the stronger statement that throughout the execution of
the algorithm each set $V_{j}^{\prime}$ is a clique, and consists of
$\beta(u_{j})$ and a subset of vertices of $S^{\prime}$ with a color strictly
larger than $c(\beta(u_{j}))=c(\alpha(u_{j}))$. This invariant clearly holds
upon creation of such a set $V_{j}^{\prime}$, since it is created as a clique
$\\{u_{j},\beta(u_{j})\\}$ and $c(u_{j})>c(\beta(u_{j}))$. Assume that the
invariant holds up to some iteration $h-1$. Now consider iteration $h$ during
which $u_{h}$ gets added to $V_{j}^{\prime}$. By the definition of the
algorithm $\beta(u_{h})\in V_{j}^{\prime}$, and thus
$\beta(u_{h})=\beta(u_{j})$. And by the definition of $\beta(u_{h})$, it is
adjacent to $u_{h}$. It remains to show that $u_{h}$ is adjacent to all the
vertices in $V_{j}^{\prime}\setminus\\{\beta(u_{j})\\}$, and that
$c(u_{h})>c(\beta(u_{j}))$. The latter directly follows from our ordering and
the fact that $c(u_{h})>c(u_{j})>c(\beta(u_{j}))$. For the former, recall that
$\alpha(u_{h})$ is defined as the vertex of $S^{\prime}$ of maximal color that
is not adjacent to $u_{h}$. In other words, $N^{-}(u_{h})$ contains a vertex
of each color strictly between $c(\alpha(u_{h}))$ and $c(u_{h})$, and
therefore each vertex of $S^{\prime}$ with such a color is adjacent to
$u_{h}$. By the induction hypothesis $V_{j}^{\prime}$ only contains such
vertices (except for the vertex $\beta(u_{j})=\beta(u_{h})$ whose adjacency to
$u_{h}$ has already been argued). ∎

##  3 Algorithmic Results

In this section, we focus on deriving and analysing learning augmented
algorithms for online graph coloring. We introduce a consistent and smooth
algorithm in Subsection 3.1, and show how it can be robustified in Subsection
3.2. Finally, in Subsection 3.3 we argue how it can be used to obtain learning
augmented algorithms for online coloring of specific graph classes.

###  3.1 FirstFitPredictions (FFP)

Throughout this section we assume that the predicted colors are chosen from
the set $\\{c_{0},c_{1},c_{2},\ldots\\}$. Given an online graph with
predictions $(G,\pi,P)$, upon revealing a new vertex $v$ with prediction
$P(v)=c_{i}$, the algorithm FirstFitPredictions (FFP for short) employs
FirstFit with a distinct color palette associated with $c_{i}$. We use
$C(i)=\\{c_{i}^{0}=c_{i},c_{i}^{1},c_{i}^{2},\ldots\\}$ to denote the _color
palette_ associated with color $c_{i}$, implying a natural ordering according
to the superscripts. Keeping the colors of each such palette distinct enables
us to associate the total number of colors used by FFP to the total prediction
error.

FirstFitPredictions: When a new vertex $v$ is revealed with prediction
$P(v)=c_{i}$, assign to $v$ the smallest-superscript eligible color $c\in
C(i)$.

FFP implies a partition of the vertices of $G$ (and the subgraphs of $G$
induced by the vertices that have been revealed so far) based on their color
palettes.

######  Definition 5.

We say that a vertex $v$ belongs to color palette $C(i)$, if it was assigned a
color $c\in C(i)$ by FFP (or equivalently, it received the prediction
$c_{i}$). We use $G_{i}=(V_{i},E_{i})$ to denote the subgraph of $G$ induced
by the set of vertices of color palette $C(i)$.

Note that an alternative, equivalent description of FFP is that it colors each
induced subgraph $G_{i}$ of $G$ using FirstFit with color palette $C(i)$. Also
note that it is without loss of generality to assume that the color palettes
are distinct: every time a specific color is predicted for the first time, one
can “rename” it to a new, unused color (if required) and define the
corresponding color palette accordingly. Finally, note that FFP does not
require any information on the chromatic number $\chi(G)$ of the graph $G$.

We can now relate the number of colors used by FFP in each color palette to
the number of prediction errors within that color palette.

######  Lemma 1.

Fix an optimal coloring $O\in\mathcal{O}(G)$, let $\eta_{i}(G)$ be the number
of vertices $v$ of color palette $C(i)$ for which $O(v)\neq P(v)$, and let
$x_{i}(G)$ be the number of distinct colors used by FFP for vertices of
$C(i)$. Then

$\displaystyle x_{i}(G)\leq\eta_{i}(G)+1.$

###### Proof.

By the definition of FFP, the set of vertices of color palette $C(i)$ is
exactly the set of vertices that received the prediction $c_{i}$, and
therefore exactly the set of vertices of $G_{i}$. Furthermore, the color
assigned to each vertex of $G_{i}$ is the same as it would obtain, if $G_{i}$
was given as input to FirstFit. Therefore, by Theorem 1 a subset of the
vertices of $G_{i}$ can be partitioned into $q+1$ cliques of size at least
two, for some integer $q$ with $0\leq q\leq x_{i}(G)-2$. Since all vertices of
each such clique received the same prediction, at most one of them could have
obtained a correct prediction.

Let $V_{0}^{\prime},V_{1}^{\prime},\dots,V_{q}^{\prime}$ be the partition of
$V^{\prime}\subseteq V_{i}$ implied by applying Theorem 1 on $G_{i}$. Recall
that $|V^{\prime}|=x_{i}(G)+q$. Since each such $V^{\prime}_{j}$ is a clique
in $G_{i}$ and contains vertices that have all obtained the same prediction,
at least $|V_{j}^{\prime}|-1$ vertices of $V_{j}^{\prime}$ must have obtained
a wrong prediction, for all $j\in\\{0,1,\ldots,q\\}$. Summing up over all such
disjoint sets we obtain:

$\displaystyle\eta_{i}(G)\geq\sum_{j=0}^{q}\left(|V_{j}^{\prime}|-1\right)=\sum_{j=0}^{q}|V_{j}^{\prime}|-(q+1)=|V^{\prime}|-q-1=x_{i}(G)-1,$

confirming the statement of the lemma. ∎

Given Lemma 1, we are now ready to prove Theorem 2.

###### Proof of Theorem 2.

Let $\chi(G)=k$ and let $c_{0},c_{1},\dots,c_{\ell}$ be the distinct
predictions assigned by $P$. Note that neither $k$ nor $\ell$ are a priori
known to the algorithm (they are only used for the sake of analysis).

Obviously, $x(G)=\sum_{i=0}^{\ell}x_{i}(G)$, where $x_{i}(G)$ is defined as in
Lemma 1. Note that if $\ell+1>k$, then there exist at least $\ell+1-k$ color
palettes in which no vertex received a correct prediction; in other words,
color palettes for which $x_{i}(G)=\eta_{i}(G)$. Furthermore, by Lemma 1, for
each color palette we have $x_{i}(G)\leq{\eta_{i}(G)+1}$, independently of the
relationship between $\ell$ and $k$. So, overall at most $k$ color palettes
will contribute the additive term “$+1$” to $x(G)$, and thus we have that
$x(G)\leq\eta(G)+k=\eta(G)+\chi(G)$. ∎

Theorem 2 shows that FFP never uses more than $\eta(G)+\chi(G)$ colors for an
online graph $G$ with predictions. The next result shows that there exist
graphs for which this amount of colors may indeed be used.

######  Lemma 2.

For every integer $k\geq 2$, there exists an online graph with predictions
$(G,\pi,P)$ and $\chi(G)=k$ for which FFP uses $x(G)=\eta(G)+k$ colors.

###### Proof.

Considering a fixed integer $k\geq 2$, we will construct a graph $G$ by
appropriately connecting $k$ copies of a complete graph on $k$ vertices. Let
$G_{1},G_{2},\ldots,G_{k}$ be $k$ disjoint copies of a $K_{k}$, and let
$v_{i}$ be an arbitrary vertex of $G_{i}$ for $i=1,\dots,k$. Graph $G$ is
obtained by adding an edge from $v_{1}$ to $v_{i}$ for $i=2,3,\dots,k$. It is
easy to check that $\chi(G)=k$ by using the fact that $\chi(G_{i})=k$, and
observing that a proper $k$-coloring of $G$ can be obtained by applying
suitable permutations of the colors $1,2,\dots,k$ to the copies of the
$K_{k}$.

Fix an arbitrary arrival permutation $\pi$ of the vertices of $G$.
Furthermore, assume that every vertex of $G_{i}$ comes with a prediction of
color $c_{i}$. Since each $G_{i}$ is a complete graph on $k$ vertices, exactly
one prediction in each such subgraph is correct. So, we have

$\displaystyle\eta(G)=k\cdot(k-1).$

On the other hand, FFP will use a different color palette for each $G_{i}$.
Since each vertex set $V(G_{i})$ is a clique of size $k$, FFP will use exactly
$k$ colors in each color palette. So, overall

$\displaystyle x(G)=k^{2}=\eta(G)+k.$

∎

Note that the above construction can easily be extended to having multiple
copies of each graph $G_{i}$, so that $G$ becomes arbitrarily large, while
still yielding the same result.

Theorem 2 and Lemma 2 directly imply the following result.

######  Theorem 4.

The competitive ratio of FFP is $1+\frac{\eta(G)}{\chi(G)}$.

Theorem 4 directly implies the $1$-consistency and smoothness of algorithm
FFP: if $\eta(G)=0$, then FFP produces a $\chi(G)$-coloring and is therefore
optimal; furthermore the number of assigned colors by FFP grows linearly with
the prediction error. Nevertheless, FFP is not a robust algorithm. Indeed, for
example, suppose we are given a bipartite online graph of order $n$ with
predictions $(G,\pi,P)$ such that $\eta(G)=\Theta(n)$. Then FFP would use
$\Theta(n)$ colors. But there exist classical online algorithms (without
predictions) [10, 28, 26] that can color any bipartite graph with $O(\log n)$
colors. In the next section, we present how FFP can be robustified by
elegantly combining it with a classical algorithm.

###  3.2 RobustFirstFitPredictions (RFFP)

A common approach for robustifying a consistent algorithm is to appropriately
combine it with a classical algorithm that disregards the predictions. A first
such attempt for robustifying FFP would be to switch to some classical online
coloring algorithm $A$, once the number of colors used by FFP becomes larger
than some predetermined threshold $T$. Recall that $\chi_{A}(G)$ denotes the
number of colors that algorithm $A$ uses for an online graph with predictions
$(G,\pi,P)$, where $\pi=v_{1},v_{2},v_{3},\ldots,v_{n}$. Furthermore, assume
that FFP would for the first time use $T+1$ colors upon arrival of some vertex
$v_{i}$. Then, by switching to a classical online coloring algorithm $A$
(using the same set of colors) for the restriction of $\pi$ to the _suffix-
subgraph_ $G^{\prime}$ induced by $\\{v_{i},v_{i+1},\ldots,v_{n}\\}$, the
total number of colors used by the combined algorithm would be at most
$T+\chi_{A}(G^{\prime})$. Similarly to the deterministic combination result
for problems with an underlying metric [3], this would already give a robust
algorithm, if we can assume that $A$ is weakly monotone in the following
sense.

######  Definition 6.

Let $A(G,\pi)$ be the number of colors $A$ uses for $(G,\pi)$, where
$\pi=v_{1},v_{2},\dots,v_{n}$. Let $\pi(i)$ be the suffix
$v_{i},v_{i+1},\dots,v_{n}$ of $\pi$, and let $(G(i),\pi(i))$ be the online
subgraph of $(G,\pi)$ induced by the vertices in $\pi(i)$. We say that $A$ is
_weakly monotone_ (resp. _monotone_) if for any $i$, $A(G(i),\pi(i))\leq
c\cdot{A(G,\pi)}$ for some constant $c$ (resp. for $c=1$).

Unfortunately, and perhaps somewhat surprisingly, we are not aware of any
weakly monotone online graph coloring algorithm with a non-trivial guarantee
on the number of used colors. To give some intuition, in Appendix A we present
instances showing that both FirstFit and BiColorMax (See [9] and [10]) are not
weakly monotone, even on specific classes of bipartite graphs which are known
to admit online competitive coloring algorithms.

We are able to circumvent this issue related to the non-monotonicity by
reserving a distinct color palette for each algorithm during the combination.
This, however, has the side-effect that after switching to an algorithm $A$ in
some round $r$, it is possible that upon arrival of a vertex $v$ the algorithm
$A$ itself does not increase its number of used colors (by using a color that
was already employed before round $r$), but the combined algorithm does. This
rules out an expert-setting approach for combining the algorithms (See [3, 6]
for more information), but we are still able to bound the total number of
colors used by the combined algorithm. More specifically, we are able to
combine FFP with $t-1$ classical algorithms and obtain an algorithm
_RobustFirstFitPredictions (RFFP for short)_ which uses a number of colors
bounded from above by the expression in Theorem 3.

###### Proof of Theorem 3.

For $1\leq i\leq n$, let $G(i)$ denote the (online) graph induced by
$\\{v_{1},v_{2},\dots,v_{i}\\}$. For any algorithm $B$, let $c(B,i)$ be the
color that $B$ assigns to vertex $v_{i}$.

In the following, we restrict each of the algorithms
$A_{1},A_{2},\ldots,A_{t}$ to use its own distinct color palette, where we
assume a total ordering of the colors within each palette. Meta-algorithm $A$
is defined as the algorithm that upon arrival of vertex $v_{i}$ (and the
accompanying prediction $P(v_{i})$) colors it with color
$c(\text{ALG}_{i},i)$, where $\text{ALG}_{i}\in\\{A_{1},A_{2},\ldots,A_{t}\\}$
is an algorithm realizing $\min_{1\leq j\leq t}A_{j}(G(i))$.

Note that since each $A_{i}$ produces a proper coloring and uses a distinct
color palette, the resulting coloring after applying $A$ is proper as well. It
remains to argue about the number of colors it would use for $G$.

Let ALG be $\text{ALG}_{n}$, and for any algorithm $A_{i}$, let $d(i)$ be the
maximal index such that $A_{i}(G(d(i)))\leq\text{ALG}(G(d(i)))$. Note that by
the definition of $A$, it will not use any color from $A_{i}$’s color palette
on vertices $v_{i+1},v_{i+2},\dots,v_{n}$. Thus, $A$ uses at most
$A_{i}(G(d(i))$ colors from $A_{i}$’s color palette. Overall, this gives

$\displaystyle A(G)\leq\sum_{i=1}^{t}A_{i}(G(d(i))).$

By the definition of $d(i)$, the above is at most

$\displaystyle\sum_{i=1}^{t}\text{ALG}(G(d(i))).$

Since an online algorithm cannot alter any assigned color,
$\text{ALG}(G(j))\leq\text{ALG}(G(j+1))$ for all $j\in\\{1,2,\ldots,n-1\\}$.
This implies $\text{ALG}(G(d(i)))\leq\text{ALG}(G)$, which concludes the
proof. ∎

Lemma 5 in Appendix B shows that the result is tight for this meta-algorithm
$A$.

In the previous result, we have been combining deterministic algorithms.
However, Theorem 3 easily extends to randomized algorithms as well, assuming
that one can simulate the execution of all algorithms simultaneously. The
following directly follows from Theorem 3, Jensen’s inequality and the
concavity of the minimum function.

######  Corollary 1.

Let $A_{1},A_{2},\ldots,A_{t}$ be randomized algorithms for online graph
coloring that may or may not make use of the predictions, and assume that one
can simulate the execution of these algorithms simultaneously. Then, there
exists a (randomized) meta-algorithm $A$ that combines
$A_{1},A_{2},\ldots,A_{t}$ and for any online graph $(G,\pi)$

$\displaystyle\mathbb{E}(A(G))\leq t\cdot\min_{1\leq i\leq
t}\mathbb{E}(A_{i}(G)).$

Theorem 3 implies that we can combine FFP with a $c$-competitive classical
algorithm (perhaps on a specific class of input graphs) and obtain a
$2\min\\{1+\frac{\eta(G)}{\chi(G)},c\\}$-competitive algorithm. Such an
algorithm attains a consistency of $2$, and is at the same time smooth (the
number of used colors grows linearly with the prediction error) and robust (it
is $2c$-competitive, independently of the prediction quality).

Assume that the (learning augmented) algorithm has knowledge that the input
graph belongs to a specific class of graphs such that (i) all graphs of this
class have chromatic number $k$ and (ii) there exists a classical online
algorithm that is online competitive on this class, with function $f(\cdot)$.
In that specific case, a slight adaptation in the proof of Theorem 3 even
gives us a $1$-consistent algorithm that is at the same time robust.

######  Corollary 2.

For some fixed $k$, assume that the algorithm FFP is aware that the input
graph belongs to a class $\mathcal{C}$ of graphs such that $\chi(G)=k$ for all
$G\in\mathcal{C}$. Moreover, assume that a classical online algorithm $A_{1}$
is known for all graphs of class $\mathcal{C}$. Then, there exists a meta-
algorithm $A^{\prime}$ that combines FFP with $A_{1}$, and for any online
graph $(G,\pi,P)\in\mathcal{C}$,

$\displaystyle{A^{\prime}}(G)$ $\displaystyle\leq
3\min\\{\textsc{FFP}(G),A_{1}(G)\\}\text{ if $\eta(G)>0$},\text{ and}$
$\displaystyle{A^{\prime}}(G)$ $\displaystyle=k\text{ otherwise.}$

###### Proof.

Let $A^{\prime}$ be the meta-algorithm that colors each vertex $v$ with
$P(v)$, until upon the reveal of some $v_{i}$, either $k+1$ distinct colors
are predicted so far, or coloring $v_{i}$ with $P(v_{i})$ would result in an
improper coloring. For the remaining sequence $\pi(i)$, $A^{\prime}$ is
defined precisely as $A$ in the proof of Theorem 3. If $\eta(G)=0$, then
$A^{\prime}$ will follow the predictions on the whole input graph, and thus
produce a proper $k$-coloring. Otherwise, by applying Theorem 3 on FFP and
$A_{1}$, we obtain that $A^{\prime}$ uses at most
$2\min\\{\textsc{FFP}(G),A_{1}(G)\\}$ colors on the sequence $\pi(i)$.
Combining this with the facts that $A^{\prime}$ uses at most $k$ distinct
colors on $v_{1},v_{2},\dots,v_{i-1}$ and that, since FFP and $A_{1}$ produce
proper colorings, both $\textsc{FFP}(G)\geq k$ and $A_{1}(G)\geq k$, we obtain
the required conclusion. ∎

###  3.3 Results for Specific Classes of Graphs

Given that the input graph belongs to a specific graph class (and this is
known to the algorithm a priori), we can obtain more refined results. In this
section, we review some interesting cases for which classical (deterministic)
online algorithms are known.

####  3.3.1 Bipartite Graphs

Although the chromatic number of bipartite graphs is $2$, for any
deterministic online coloring algorithm $A$, there exists an online bipartite
graph on $n$ vertices that forces $A$ to use at least $2\log n-10$ colors
[17]. This result is essentially tight, given that there exists a simple
online coloring algorithm guaranteeing a coloring with at most $2\log n+1$
colors on any bipartite graph on $n$ vertices [28]. This means that there is
no competitive algorithm for bipartite graphs. However, there are (online)
competitive algorithms for specific subclasses of bipartite graphs. Namely,
for $P_{4}$-free bipartite graphs FirstFit is known to be optimal [19] whereas
for $P_{5}$-free bipartite graphs it uses at most three colors [20]. Online
algorithm BiColorMax guarantees a coloring with four colors on any
$P_{5}$-free bipartite graph [10]. The problem becomes significantly more
difficult on $P_{6}$-free bipartite graphs where, as mentioned, no online
algorithm can guarantee a coloring with constantly many colors. However,
BiColorMax is online competitive for such graphs, and
$\chi_{\textsc{BiColorMax}}(G)\leq 2\chi_{OL}(G)-1$ for any $P_{6}$-free
bipartite graph [10, 31, 32]. For $P_{7}$-free, $P_{8}$-free and $P_{9}$-free
bipartite graphs, an algorithm that builds upon BiColorMax is known to be
online competitive and uses at most $4\chi_{OL}(G)-1$, $3(\chi_{OL}+1)^{2}$
and $6(\chi_{OL}(G)+1)^{2}$ colors, respectively [31, 32]. Applying Corollary
2 to FFP and an algorithm of the respective graph class gives the following
theorem.

######  Theorem 5.

There exist (different) algorithms for online coloring bipartite graphs with
predictions obtaining a competitive ratio of $1$ if $\eta(G)=0$, and
$3\min\\{\frac{\eta(G)}{2}+1,X\\}$ otherwise, where $X$ is

  * •

$\Theta(\log n)$ for general bipartite graphs,

  * •

$\chi_{OL}(G)-\frac{1}{2}$ for bipartite $P_{6}$-free graphs,

  * •

$2\chi_{OL}(G)-\frac{1}{2}$ for bipartite $P_{7}$-free graphs,

  * •

$\frac{3(\chi_{OL}(G)+1)^{2}}{2}$ for bipartite $P_{8}$-free graphs, and

  * •

$3(\chi_{OL}(G)+1)^{2}$ for bipartite $P_{9}$-free graphs.

####  3.3.2 Other graph classes

Besides bipartite graphs, the (online) graph coloring problem has been
extensively studied for several other graph classes. Among them, for instance,
are chordal graphs, intersection graphs, $d$-inductive graphs (also known as
$d$-degenerate graphs), graphs with bounded treewith and graphs with forbidden
induced subgraphs. A _chordal graph_ is a simple graph, in which every cycle
of length greater than three has a chord. It is known that FirstFit colors
every chordal graph $G$ with $\chi(G)=d$ using $O(d\cdot\log n)$ colors [23],
which is best possible for any deterministic online algorithm [1]. The
intersection graph of a set of disks in the Euclidean plane is the graph
having a vertex for each disk and an edge between two vertices if and only if
the corresponding disks overlap. A graph $G$ is called a _disk graph_ , if
there exists a set of disks in the Euclidean plane whose intersection graph is
$G$. FirstFit is also $\Theta(\log n)$-competitive on disk graphs, and it is
best possible for any deterministic online algorithm [15].

A graph is _$d$ -inductive_ (or $d$-degenerate), if it can be reduced to
$K_{1}$ by repeatedly deleting vertices of degree at most $d$. Intuitively,
the _treewidth_ of a graph $G$ is an integer denoting how far $G$ is from
being a tree. More formally, a _tree decomposition_ of $G=(V,E)$ is a tree $T$
with vertices $Y_{1},Y_{2},\dots,Y_{n}$ where $Y_{i}\subseteq V$ for all $i$
and $\bigcup_{i}V_{i}=V$, such that all $Y_{i}$’s that contain a vertex $v\in
V$ form a connected subtree in $T$, and furthermore for all $e=(v,w)\in E$
there exists a $Y_{i}$ such that $v\in Y_{i}$ and $w\in Y_{i}$. The _width_ of
a tree decomposition is the size of its largest set $Y_{i}$ minus one, and the
_treewidth_ of graph $G$ is defined as the minimum width among all possible
tree decompositions of $G$. FirstFit colors any $d$-inductive graph and any
graph of treewidth $d$ using $O(d\cdot\log n)$ colors [1]. This is best
possible for both classes, by the aforementioned lower bound on chordal graphs
and the fact that every chordal graph $G$ is $(\chi(G)-1)$-inductive and has
treewidth $\chi(G)-1$ [7].

So altogether applying Theorem 3 on FFP and FirstFit, we get the following
result for chordal graphs, disk graphs and $d$-inductive graphs, as well as
for graphs of treewidth $d$.

######  Theorem 6.

There exist (different) algorithms for online coloring chordal graphs,
$d$-inductive graphs, graphs of treewidth $d$ and disk graphs with predictions
obtaining a competitive ratio of $1$ if $\eta(G)=0$, and
$2\min\\{\frac{\eta(G)}{\chi(G)}+1,X\\}$ otherwise, where $X=O(\log n)$ is the
competitive ratio of the respective classical online algorithm.

The complementary notion of a clique is an _independent set_ , that is a set
$S\subseteq V$ such that no two vertices of $S$ are adjacent. An independent
set of size $s$ is denoted by $I_{s}$. FirstFit is known to achieve a
competitive ratio of $t-1$ on $K_{1,t}$-free graphs where $t\geq 3$ [11], and
there exist classical online algorithms which are $\frac{s}{2}$-competitive on
$I_{s}$-free graphs [12]. Therefore, applying Theorem 3 to FFP and the
respective algorithm for each of these two classes of graphs gives the
following theorem.

######  Theorem 7.

There exist (different) algorithms for online coloring $I_{s}$-free graphs and
$K_{1,t}$-free graphs for $t\geq 3$ with predictions obtaining a competitive
ratio of $1$ if $\eta(G)=0$, and $2\min\\{\frac{\eta(G)}{\chi(G)}+1,X\\}$
otherwise, where $X$ is

  * •

$t-1$ for $K_{1,t}$-free graphs,

  * •

$\frac{s}{2}$ for $I_{s}$-free graphs.

##  4 Discussion

In this paper, we presented a simple learning augmented algorithm for graph
coloring that is $2$-consistent, smooth and robust. When the chromatic number
of the input graph is known, a $1$-consistent, smooth and robust algorithm is
obtained. It would be interesting to investigate whether a learning augmented
algorithm with a consistency better than $2$ is possible, when the chromatic
number of the input graph is not known to the algorithm.

Furthermore, all presented algorithms are smooth and the number of used colors
grows linearly with the prediction error. It is an open question whether there
exist any learning augmented algorithms which achieves the same consistency,
but with a better dependence on the prediction error.

## References

  * [1] Susanne Albers and Sebastian Schubert.  Tight bounds for online matching in bounded-degree graphs with vertex capacities.  In 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPIcs, pages 4:1–4:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022\.
  * [2] Antonios Antoniadis, Joan Boyar, Marek Eliás, Lene M. Favrholdt, Ruben Hoeksma, Kim S. Larsen, Adam Polak, and Bertrand Simon.  Paging with succinct predictions.  CoRR, abs/2210.02775, 2022.
  * [3] Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon.  Online metric algorithms with untrusted predictions.  In ICML, volume 119 of Proceedings of Machine Learning Research, pages 345–355. PMLR, 2020.
  * [4] Leonid Barenboim, Rami Drucker, Oleg Zatulovsky, and Eli Levi.  Memory allocation for neural networks using graph coloring.  In ICDCN ’22: 23rd International Conference on Distributed Computing and Networking, Delhi, AA, India, January 4 - 7, 2022, pages 232–233. ACM, 2022.
  * [5] Nicolas Barnier and Pascal Brisset.  Graph coloring for air traffic flow management.  Ann. Oper. Res., 130(1-4):163–178, 2004.
  * [6] Avrim Blum and Carl Burch.  On-line learning and the metrical task system problem.  Mach. Learn., 39(1):35–58, 2000.
  * [7] Hans L. Bodlaender.  A tourist guide through treewidth.  Acta Cybern., 11(1-2):1–21, 1993.
  * [8] John A. Bondy and Uppaluri S. R. Murty.  Graph Theory with Applications.  Macmillan Education UK, 1976.
  * [9] Hajo Broersma, Agostino Capponi, and Daniël Paulusma.  On-line coloring of h-free bipartite graphs.  In Tiziana Calamoneri, Irene Finocchi, and Giuseppe F. Italiano, editors, Algorithms and Complexity, 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings, volume 3998 of Lecture Notes in Computer Science, pages 284–295. Springer, 2006.
  * [10] Hajo Broersma, Agostino Capponi, and Daniël Paulusma.  A new algorithm for on-line coloring bipartite graphs.  SIAM J. Discret. Math., 22(1):72–91, 2008.
  * [11] Iwona Cieślik.  On-line coloring and cliques covering for $K_{s,t}$-free graphs.  Acta Informatica, 42(1):1–20, 2005.
  * [12] Iwona Cieślik, Marcin Kozik, and Piotr Micek.  On-line coloring of $I_{s}$-free graphs.  Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AF:61–68, 2006.
  * [13] Ilan Reuven Cohen and Debmalya Panigrahi.  A general framework for learning-augmented online allocation.  CoRR, abs/2305.18861, 2023.
  * [14] Marc Demange, Tínaz Ekim, and Dominique de Werra.  A tutorial on the use of graph coloring for some problems in robotics.  Eur. J. Oper. Res., 192(1):41–55, 2009.
  * [15] Thomas Erlebach and Jirí Fiala.  On-line coloring of geometric intersection graphs.  Comput. Geom., 23(2):243–255, 2002.
  * [16] Martin Grötschel, László Lovász, and Alexander Schrijver.  Polynomial algorithms for perfect graphs.  In Topics on Perfect Graphs, volume 88 of North-Holland Mathematics Studies, pages 325–356. North-Holland, 1984.
  * [17] Grzegorz Gutowski, Jakub Kozik, Piotr Micek, and Xuding Zhu.  Lower bounds for on-line graph colorings.  In Hee-Kap Ahn and Chan-Su Shin, editors, Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, volume 8889 of Lecture Notes in Computer Science, pages 507–515. Springer, 2014.
  * [18] András Gyárfás, Zoltán Király, and Jenö Lehel.  Online competitive coloring algorithms.  Technical report, TR-9703-1, 1997.
  * [19] András Gyárfás and Jenö Lehel.  On-line and first fit colorings of graphs.  J. Graph Theory, 12(2):217–227, 1988.
  * [20] András Gyárfás and Jenö Lehel.  Effective online coloring of $P_{5}$-free graphs.  Combinatorica, 11(2):181–184, 1991.
  * [21] Magnús M. Halldórsson.  A still better performance guarantee for approximate graph coloring.  Inf. Process. Lett., 45(1):19–23, 1993.
  * [22] Magnús M. Halldórsson and Mario Szegedy.  Lower bounds for on-line graph coloring.  Theor. Comput. Sci., 130(1):163–174, 1994.
  * [23] Sandy Irani.  Coloring inductive graphs on-line.  Algorithmica, 11(1):53–72, 1994.
  * [24] David S. Johnson.  Worst case behavior of graph coloring algorithms.  In Proceedings of the 5th Southeastern Conference on Combinatorics,, Graph Theory and Computing, pages 513–527. Utilitas Mathematica, 1974.
  * [25] Richard M. Karp.  Reducibility among combinatorial problems.  In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972.
  * [26] Hal A. Kierstead.  Coloring graphs on-line.  In Online Algorithms, volume 1442 of Lecture Notes in Computer Science, pages 281–305. Springer, 1996.
  * [27] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Online scheduling via learned weights.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1859–1877. SIAM, 2020.
  * [28] László Lovász, Michael E. Saks, and William T. Trotter.  An on-line graph coloring algorithm with sublinear performance ratio.  Discret. Math., 75(1-3):319–325, 1989.
  * [29] Thodoris Lykouris and Sergei Vassilvitskii.  Competitive caching with machine learned advice.  In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 3302–3311. PMLR, 2018.
  * [30] Dániel Marx.  Graph coloring problems and their application in scheduling.  Periodica Polytechnica Electrical Engineering, 48:11–16, 2004\.
  * [31] Piotr Micek and Veit Wiechert.  An on-line competitive algorithm for coloring $P_{8}$-free bipartite graphs.  In Hee-Kap Ahn and Chan-Su Shin, editors, Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, volume 8889 of Lecture Notes in Computer Science, pages 516–527. Springer, 2014.
  * [32] Piotr Micek and Veit Wiechert.  An on-line competitive algorithm for coloring bipartite graphs without long induced paths.  Algorithmica, 77(4):1060–1070, 2017.
  * [33] Michael Mitzenmacher and Sergei Vassilvitskii.  Algorithms with predictions.  Commun. ACM, 65(7):33–35, 2022.
  * [34] Manish Purohit, Zoya Svitkina, and Ravi Kumar.  Improving online algorithms via ML predictions.  In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 9684–9693, 2018.
  * [35] Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung-Chan An.  Improved learning-augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis.  CoRR, abs/2302.06832, 2023.
  * [36] David Zuckerman.  Linear degree extractors and the inapproximability of max clique and chromatic number.  Theory Comput., 3(1):103–128, 2007.

##  Appendix A Monotonicity Counterexamples

######  Lemma 3.

FirstFit is not weakly monotone.

###### Proof.

Consider a bipartite graph $G$ (see Figure $1$) with bipartition
$X=\\{v_{1},\ldots,v_{n}\\}$ and $Y=\\{u_{1},\ldots,u_{n}\\}$ and
$E(G)=\\{v_{1}u_{1}\\}\cup\\{v_{i}u_{j}|i\neq{j},i,j=1,2,\ldots,n\\}$ be the
edge set of $G$. The vertices arrive one by one in the following order:

$v_{1},u_{1},v_{2},u_{2},\ldots,v_{n},u_{n}.$

Now we take $v_{1}$ and $u_{1}$ away from $G$ and let $G^{\prime}$ denote the
remaining subgraph. The order of arrival of the vertices in $G^{\prime}$ stays
the same as that in $G$. It is easy to verify that FirstFit would only use two
colors on $G$ whereas $n-1$ colors on $G^{\prime}$. ∎

$v_{1}$$v_{2}$$v_{3}$$\cdots$$v_{n}$$u_{1}$$u_{2}$$u_{3}$$\cdots$$u_{n}$$G$$v_{2}$$v_{3}$$\cdots$$v_{n}$$u_{2}$$u_{3}$$\cdots$$u_{n}$$G^{\prime}$
Figure 1: FirstFit is not weakly monotone.

######  Lemma 4.

BiColorMax is not weakly monotone.

###### Proof.

In [32, 31] the authors present an online bipartite $P_{6}$-free graph
$(G=(V_{1}\cup V_{2},E),\pi)$ for which BiColorMax requires $O(\log n)$
colors. We construct an online $P_{6}$-free bipartite graph
$(G^{\prime},\pi^{\prime})$ as follows. Start with $G$ and add two vertices
$v$ and $v^{\prime}$. Add edges connecting $v$ to $v^{\prime}$ and each of the
vertices of $V_{1}$, and edges connecting $v^{\prime}$ to each of the vertices
in $V_{2}$. The sequence of vertex arrivals is
$\pi^{\prime}=v,v^{\prime},\pi$. By construction $G^{\prime}$ is bipartite. It
is also $P_{6}$-free, suppose on the contrary there is an induced $P_{6}$ in
$G^{\prime}$. Since $G$ is $P_{6}$ free, such an induced $P_{6}$ would have to
contain $v$ or $v^{\prime}$ and at least two vertices from $V_{1}$ as well as
at least two vertices of $V_{2}$. But $v$ is adjacent to all the vertices in
$V_{1}$ and $v^{\prime}$ is adjacent to all the vertices in $V_{2}$, so the
induced subgraph cannot be a path, contradiction.

Note that by the definition of $(G^{\prime},\pi)$ in each step of the (any)
algorithm the currently revealed subgraph will always be connected. By the
definition of BiColorMax (see [10]), it only uses $2$ colors on any bipartite
$P_{6}$-free graph that remains connected throughout the execution of the
algorithm. In other words, BiColorMax uses $2$ colors on
$(G^{\prime},\pi^{\prime})$ but requires $O(\log n)$ colors on $(G,\pi)$
(where $\pi$ is a suffix of $\pi^{\prime}$ and $G$ is the subgraph of
$G^{\prime}$ induced by the vertices in $\pi$). ∎

In [32, 31] extensions of BiColorMax were presented for $P_{8}$-free and
$P_{9}$-free bipartite graphs. The construction in the proof of Lemma 4 can be
used to show that these algorithms are also not weakly monotone. We defer to
the full version for a more extensive discussion.

##  Appendix B Lower Bound for the Meta-Algorithm

######  Lemma 5.

There exist deterministic algorithms $A_{1},A_{2},\dots,A_{t}$ and an online
graph with predictions $(G,\pi,P)$ such that the meta-algorithm $A$ that
combines $A_{1},A_{2}\dots,A_{t}$ in the way described in the proof of Theorem
3 uses exactly $t\cdot\min_{1\leq i\leq t}A_{i}(G)$ colors for $(G,\pi,P)$.

###### Proof.

Let the color palette associated with $A_{i}$ be
$C(i)=\\{c_{i}^{0},c_{i}^{1},\dots,c_{i}^{t-1}\\}$ for $1\leq i\leq t$. Let
$G=tK_{1}$ be given to the algorithm $A$ in an arbitrary order. Let $A_{i}$,
for each $1\leq i\leq t$ be such that it uses $c_{i}^{0}$ to color the first
$i$ vertices of $G$ and assigns a different color to each of the remaining
vertices of $G$. Without loss of generality, we can assume that $A$ follows
$A_{1}$ in the first iteration and switches from $A_{i}$ to $A_{i+1}$ after
the $i$th iteration (the algorithm $A$ satisfies the description from the
proof of Theorem 3). The resulting coloring is trivially a proper coloring,
since $G$ contains no edges. The lemma follows from the fact that $A$ switches
to using a different algorithm after each round, and ends up using $t$ colors
for $(G,\pi,P)$ while algorithm $A_{t}$ only uses $1$ color for $(G,\pi,P)$. ∎


# Optimal transport for some symmetric, multidimensional integer partitions

Daniel Adu, Daniel Keliher  University of Georgia, Athens GA, 30602, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

A result of Hohloch links the theory of integer partitions with the Monge
formulation of the optimal transport problem, giving the optimal transport map
between (Young diagrams of) integer partitions and their corresponding
symmetric partitions. Our aim is to extend Hohloch’s result to the higher
dimensional case. In doing so, we show the Kantorovich formulation of the
optimal transport problem provides the tool to study the matching of higher
dimensional partitions with their corresponding symmetric partitions.

###### Key words and phrases:

Optimal transport, integer partitions

##  1\. Introduction

This paper concerns the intersection of the theory of integer partitions and
of optimal transport. Hohloch has made this connection in [Hohloch] for one-
dimensional integer partitions, where the Monge formulation of optimal
transport problem [Monge] was used as a tool to describe and relate some
bijections coming from the theory of integer partitions (e.g. self-symmetric
partitions and partitions associated via Euler’s identity). While Hohloch, in
[Hohloch] does not provide a specific practical scenario for exploring the
connection between two seemingly unrelated fields, the theory of integer
partitions and of optimal transport, one potential application of the link
between optimal transport and integer partitions could be in data analysis.
Optimal transport can be used to compare probability distributions, and
integer partitions can be used to represent data in a structured way. By
linking these two fields, it may be possible to develop new methods for
analyzing and comparing data sets that are represented as integer partitions.

To state the one-dimensional result in [Hohloch] more precisely, we begin with
the following notations and definitions; given an integer $n\in\mathbb{N}$,
let $\mathcal{P}(n)$ be the set of partitions of $n$ and
$\pi\in\mathcal{P}(n)$ represent a partition of $n$. For any
$\pi\in\mathcal{P}(n)$, one can associate a unique diagram called a Young
diagram, $Y(\pi)$ (see Definition 2.3). Given $\pi$ and the corresponding
Young diagram $Y(\pi)$, by reflecting the Young diagram $Y(\pi)$ across the
line $y=x$ we obtain another Young diagram. We denote the reflected Young
diagram by $Y(\mathrm{sym}(\pi))$, where $\mathrm{sym}(\pi)$ is called the
symmetric partition of $\pi$ and is the corresponding partition for
$Y(\mathrm{sym}(\pi))$ (see Figure 1). Given $Y(\pi)$ and
$Y(\mathrm{sym}(\pi))$, one can construct probability measures $\delta_{\pi}$
and $\delta_{\mathrm{sym}(\pi)}$. Hohloch, in [Hohloch], constructed such
measures using Dirac measures concentrated on the corners of each square of a
Young diagram closest to the origin. This raises two natural questions: what
is the optimal way to match $\pi$ to $\mathrm{sym}(\pi)$, and what properties
of $\mathrm{sym}(\pi)$ can we infer from $\pi$? We summarize one result from
[Hohloch] as follows.

  1. (1)

If the cost function in Monge problem [Monge] is Euclidean distance, then the
function which is the identity map on
$\mathrm{spt}(\delta_{\pi})\cap\mathrm{spt}(\delta_{\mathrm{sym}(\pi)})$ and
is otherwise reflection across $y=x$, is optimal for $\delta_{\pi}$ and
$\delta_{\mathrm{sym}(\pi)}$, where $\mathrm{spt}(-)$ denotes the support of
the measure.

  2. (2)

We have $\pi=\mathrm{sym}(\pi)$ if an only if
$\delta_{\pi}=\delta_{\mathrm{sym}(\pi)}$, i.e. the identity map is optimal.

Figure 1. Left: Young diagram $Y(\pi)$ of the partition
$\pi=(4,2)\in\mathcal{P}(6)$. Right: Young diagram $Y(\mathrm{sym}(\pi))$ of
the partition $\mathrm{sym}(\pi)=(2,2,1,1)\in\mathcal{P}(6)$. The Young
diagram $Y(\mathrm{sym}(\pi))$ is obtained by reflecting $Y(\pi)$ across
$y=x$.

For instance, in Figure 1, the map which is optimal between the left-hand and
right-hand diagrams is the one which leaves the four common squares (i.e. the
intersection of the supports of the two corresponding measures) fixed, and
moves the squares with lower left corners $(2,0)$ and $(3,0)$ in the left-hand
diagram to the ones with lower left corners $(0,2)$ and $(0,3)$, respectively,
in the right-hand diagram.

In [Hohloch]*Conjecture 4.2, Hohloch conjectures that the results in (1) and
(2) above can be extended to higher dimensional integer partitions. The main
contribution of this note is to prove the conjecture: see Theorem 4.1 and
Theorem 4.2.

###  1.1. Outline

In Section 2, we provide formal definitions related to integer partitions and
their higher dimensional analogues, as well as describe how we interpret the
$m$-dimensional partitions as the appropriate probability measures which will
allow us compare different partitions using optimal transport. For this
reason, we review some results from optimal transport in Section 3. We state
and provide a proof of our main result in Section 4. Finally, Section 5
includes concluding remarks and some possible directions of future
investigation.

##  2\. Integer Partitions

In this section we briefly recall some basic definitions related to integer
partitions and their higher dimensional counterparts. The study of integer
partitions has a rich history in number theory and combinatorics; see e.g.
[VanL].

######  Definition 2.1.

Let $n\in\mathbb{N}$. A partition of $n$ is an ordered tuple of integers
$(n_{1},\dots,n_{k})$, where $n_{1}\geq n_{2}\geq\ldots\geq n_{k}\geq 1$,
$n_{i}\in\mathbb{N}$ for all $i\in\\{1,\dots,k\\}$, such that
$\sum_{i=1}^{k}n_{i}=n$.

Given $n\in\mathbb{N}$, we denote by $\mathcal{P}(n)$ the collection of all
the possible partitions on $n$ and set $p(n)=\\#\mathcal{P}(n)$. For example,

$\mathcal{P}(4)=\\{(4),(3,1),(2,2),(2,1,1),(1,1,1,1)\\}$

and $p(4)=5$.

Integer partitions have a natural higher dimensional analogue, which we now
define following [Hohloch]*Definition 3.4.

######  Definition 2.2.

Let $n\in\mathbb{N}$. An $m$-dimensional partition of $n$ is an array of
integers $n_{i_{1},...,i_{m}}\in\mathbb{N}$ where $1\leq i_{j}\leq k_{j}$ for
some integers $1\leq k_{j}\leq n$, $j=1,...,m$, such that for each index
$i_{j}=1,...,k_{j}$ the integers $n_{i_{1},...,i_{m}}$ are monotone a
decreasing sequence with
$n\geq\max_{i_{j}\in\\{1,...,k_{j}\\}}n_{i_{1},...,i_{m}}$ and
$\min_{i_{j}\in\\{1,...,k_{j}\\}}n_{i_{1},...,i_{m}}\geq 1$, and
$\displaystyle\sum_{i_{1}=1}^{k_{1}}\ldots\sum_{i_{m}=1}^{k_{m}}n_{i_{1},\cdots,i_{m}}=n$.

We write $\mathcal{P}_{m}(n)$ for the set of all $m$-dimensional partitions of
$n$, and set $p_{m}(n)=\\#\mathcal{P}_{m}(n)$.

For example,

(2.1) $\left[\begin{tabular}[]{cc}1&{}\hfil\\\ 2&1\end{tabular}\right]\text{
and }\left[\begin{tabular}[]{ccc}1&&\\\ 2&1&\\\ 3&1&1\end{tabular}\right]$

are 2-dimensional partitions of $4$ and $9$, respectively.

To represent a partition, we have the convenient notion of a Young
diagram111NB multiple conventions for Young diagrams appear in the
literature.. In the one dimensional case, the Young diagram of a partition
$\lambda=(\lambda_{1},\lambda_{2},...\lambda_{k})\in\mathcal{P}(n)$ is $n$
squares arranged in left-justified rows where the bottom row has $\lambda_{1}$
squares, the second row has $\lambda_{2}$ squares, and so on. Figure 2 shows
the Young diagram for two partitions of (2.1) from above. We can think of a
Young diagram of a partition $\pi\in\mathcal{P}_{m}(n)$ as a finite collection
of $n$ unit cubes in $\mathbb{R}^{m+1}$ with positions regulated by the choice
of partition, $\pi$.

######  Definition 2.3.

If $\pi=(n_{i_{1},...,i_{m}})_{\begin{subarray}{c}1\leq n_{j}\leq k_{j}\\\
j=1,...,m\end{subarray}}\in\mathcal{P}_{m}(n)$ as in Definition 2.2, the Young
diagram of $\pi$, denoted $Y(\pi)$, is the following union of unit cubes in
$\mathbb{R}^{m+1}$:

(2.2) $Y(\pi):=\bigcup_{1\leq i_{1},...,i_{m}\leq
k_{1},...,k_{m}}\bigcup_{\alpha=1}^{n_{i_{1},...,i_{m}}}\left([\alpha-1,\alpha]\times\prod_{j=1}^{m}[i_{j}-1,i_{j}]\right).$

Figure 2. Young diagrams of a partition in $\mathcal{P}_{2}(4)$ (left) and a
partition in $\mathcal{P}_{2}(9)$ (right) from (2.1)

In a similar fashion, we can ascribe to each partition $\pi$, a probability
measure, $\delta_{\pi}$, which is a sum of point masses as follows:

(2.3) $\delta_{\pi}:=\frac{1}{n}\sum_{1\leq i_{1},...,i_{m}\leq
k_{1},...,k_{m}}\sum_{\alpha=1}^{n_{i_{1},...,i_{m}}}\delta(i_{1},...,i_{m},\alpha)$

where $\delta(x_{1},...,x_{m+1})$ is a Dirac delta at the point
$(x_{1},...,x_{m+1})$. Observe that $\delta_{\pi}(\mathbb{R}^{m+1})=1$ for any
partition $\pi\in\mathcal{P}_{m}(n)$.

The intuition for (2.3) case can be thought of roughly as follows: we can
imagine $\delta_{\pi}$ as assigning a unit point mass to each unit cube in
$Y(\pi)$ taking the value 1 on the corner of each such cube with minimal
Euclidean distance to the origin, and 0 everywhere else.

Given a permutation $\sigma\in S_{m+1}$ letters, one can associate to any
$m$-dimensional partition a new partition as follows.

######  Definition 2.4 ([Hohloch]*Definition 4.5).

Given $\sigma\in S_{m+1}$, an element of the symmetric group on $m+1$
elements, let $T_{\sigma}:\mathbb{R}^{m+1}\rightarrow\mathbb{R}^{m+1}$ be the
linear map defined by $e_{i}\mapsto e_{\sigma(i)}$ where $e_{i}$,
$i=1,...,m+1$, is the standard basis of $\mathbb{R}^{m+1}$. For any
$\pi\in\mathcal{P}_{m}(n)$,

  * •

the $\sigma$-symmetric partition of $\pi$, denoted by
$\text{sym}_{\sigma}(\pi)$, is the partition whose Young diagram satisfies
$Y(\text{sym}_{\sigma}(\pi))=T_{\sigma}(Y(\pi))$;

  * •

if $\pi=\text{sym}_{\sigma}(\pi)$, then we call $\pi$ $\sigma$-self-symmetric.

This definition generalizes the concept of self-symmetric partitions in one-
dimension, which are partitions whose Young diagrams are invariant under
reflection across the $y=x$ line. The $\sigma$-self-symmetric partitions are
invariant under a more general type of reflection, determined by the
permutation $\sigma$. Figure 3 gives an example of a partition
$\pi\in\mathcal{P}_{2}(6)$ alongside $\text{sym}_{(23)}(\pi)$, i.e. partitions
which are $(2~{}3)$-symmetric.

Notice that if $\tau\in S_{2}$ is not the identity permutation, then any
partition $\pi\in\mathcal{P}_{1}(n)$ has a $\tau$-symmetric partition which is
just the partition obtained by reflecting the Young diagram of $\pi$, now in
$\mathbb{R}^{2}$, across the line $y=x$. In this restricted case, $\pi$ is
called _self-symmetric_ if its Young diagram is invariant under reflection
across $y=x$.

Figure 3. Left: $\pi\in\mathcal{P}_{2}(6)$. Right: The $\sigma$-symmetric
partition of $\pi$ with $\sigma=(2~{}3)\in S_{3}$.

##  3\. Optimal Transport

Our goal is to investigate patterns between the $m$-dimensional partition to
its corresponding symmetric partition. The framework that enables us to
establish the pattern is the optimal transport framework. Therefore, we state
the problem and an important preliminary result on the theory of optimal
transport [Villani, Galichon]. Readers who are familiar can skip this section
and refer to it when needed. In order to state the problem more precisely, we
introduce some mathematical notions. Let $x_{1},x_{2}\in\mathbb{R}_{+}^{m+1}$
be an $m+1$-tuples of positive real numbers such that
$\sum_{j=1}^{m+1}x_{1,j}=\sum_{j=1}^{m+1}x_{2,j}=1$ where $x_{i,j}$, with
$i=1,2$ and $j=1,...,m+1$, denotes the $j$th coordinate of $x_{i}$ and
consider two measures

$\delta_{x_{1}}=\sum_{j=1}^{m+1}x_{1,j}\delta_{x_{1,j}}\quad\text{ and
}\quad\delta_{x_{2}}=\sum_{j=1}^{m+1}x_{2,j}\delta_{x_{2,j}}.$

$\delta_{x_{i,j}}$ is the Dirac delta measure on $x_{i,j}$. Let

$X:=\\{(x_{1,i},x_{2,j})\mid 1\leq i,j\leq m+1\\}$

and let $c:X\to\mathbb{R}_{+}\cup\\{\infty\\}$ be a given cost function, we
consider the discrete version of Kantorovich [Kantorovich] problem:

(3.1) $\inf_{\gamma\in\Pi(\delta_{x_{1}},\delta_{x_{2}})}\sum_{1\leq i,j\leq
m+1}c_{i,j}\gamma_{i,j},$

where $c_{ij}=c(x_{1i},x_{2j})$,

(3.2)
$\displaystyle\Pi(\delta_{x_{1}},\delta_{x_{2}}):=\\{\gamma\in\mathbb{R}^{(m+1)\times(m+1)}\mid\gamma\mathbbm{1}_{m+1}=\delta_{\pi}\text{
and
}\gamma^{\mathrm{T}}\mathbbm{1}_{m+1}=\delta_{\mathrm{sym}_{\sigma}(\pi)}\\}$

and $\mathbbm{1}_{m+1}\in\mathbb{R}^{m+1}$ is the vector of ones. The matrices
$\gamma\in\Pi(\delta_{x_{1}},\delta_{x_{2}})$ are called _transport plans_.
Note that the set (3.2) is the set of doubly stochastic matrices which is a
compact set (see [Galichon, Chapter 3]) and hence the existence of optimizers
$\gamma^{*}$ depends on the cost function $c$. In the continuous case, problem
(3.1) is related to the classical Monge problem [Monge]. In particular, for
the case where the cost is $c(x_{1,i},x_{2,j})=|x_{1,i}-x_{2,j}|^{2}$ it is
well-known (see for instance [Ambrosio, Knott, Ruschendorf]) that the solution
of the Monge problem is obtain from the continuous version of problem (3.1).
In general, the Monge problem does not always admit a solution even if the
cost function is very regular. We note that optimal transport theory has
become a useful tool for other fields (see for instance [Adu2022, Daniel2022,
Chen, Peyre, Daniel]).

The characterization of the support of optimal transport plans will be useful
in establishing our results. To state this result more precisely, we begin
with the following definition.

######  Definition 3.1.

We say that a set $\Gamma\subset X$ is $c$-cyclically monotone, if for any
$k\in\mathbb{N}$, any permutation $\sigma\in S_{k}$ and any finite family of
points $((x_{1,1},x_{2,1}),\dots,(x_{1,k},x_{2,k}))\in\Gamma$, we have that

$\sum_{i=1}^{k}c(x_{1,i},x_{2,i})\leq\sum_{i=1}^{k}c(x_{1,\sigma(i)},x_{2,\sigma(i)}).$

The following result will be useful; see [Villani, Galichon].

######  Theorem 3.1.

If $\gamma^{*}$ is optimal for the cost $c$ and $c$ is continuous, then the
support of $\gamma^{*}$ denoted as $\mathrm{spt}(\gamma^{*})\subset X$ is a
$c$-cyclical monotone set.

Note that in this discrete setting, since all mass of $\delta_{x_{i}}$, where
$i=1,2$, are concentrated on isolated points, the $c$-cyclical monotone set
can be used to define a linear map which will describe the optimal pairings
$x_{1,i}$ and $x_{2,j}$. Most importantly, if the cost $c$ is convex, then
this linear map is unique.

##  4\. Main Results and Proofs

This Section is dedicated to providing a proof of the conjuctures stated in
[Hohloch]. We will demonstrate here that, unlike in [Hohloch], the Kantorovich
formulation of optimal transport (3.1)- (3.2) offers an alternative, more
concise approach for handling the higher-dimensional case. We now state are
main results. Recall that for a partition $\pi\in\mathcal{P}_{m}(n)$ and its
$\sigma$-symmetric partition $\mathrm{sym}_{\sigma}(\pi)$, we associate Young
diagrams as in Definition 2.3, and those, we associate measures $\delta_{\pi}$
and $\delta_{\mathrm{sym}_{\sigma}(\pi)}$ as in (2.3), and define the
Wasserstein distance between $\delta_{\pi}$ and
$\delta_{\mathrm{sym}_{\sigma}(\pi)}$ as

(4.1)
$W(\delta_{\pi},\delta_{\mathrm{sym}_{\sigma}(\pi)}):=\min_{\gamma\in\Pi(\delta_{\pi},\delta_{\mathrm{sym}_{\sigma}(\pi)})}\sum_{i,j=1}^{m+1}c_{ij}\gamma_{ij}.$

where $c=(c_{ij})\in\mathbb{R}^{(m+1)\times(m+1)}$, $c_{ij}=|i-j|^{2}$ and
$\Pi(\delta_{\pi},\delta_{\mathrm{sym}_{\sigma}(\pi)})$ is defined in (3.2).

######  Theorem 4.1.

Let $\pi\in\mathcal{P}_{m}(n)$ and $\sigma\in S_{m+1}$. The matrix
$T_{\sigma}=(e_{\sigma(1)},\dots,e_{\sigma(m+1)})$, where
$e_{1},\dots,e_{m+1}$ is the standard basis of $\mathbb{R}^{m+1}$, induces the
optimal matrix in (4.1). In particular, the map which is the identity on
$\mathrm{spt}(\delta_{\pi})\cap\mathrm{spt}(\delta_{\mathrm{sym}_{\sigma}(\pi)})$
and is $T_{\sigma}$ otherwise, is optimal for $\delta_{\pi}$ and
$\delta_{\mathrm{sym}_{\sigma}(\pi)}$.

We state here that the optimal matrix corresponding to
$W(\delta_{\pi},\delta_{\mathrm{sym}_{\sigma}(\pi)})$ exists in
$\Pi(\delta_{\pi},\delta_{\mathrm{sym}_{\sigma}(\pi)})$, since the cost
$c_{ij}$ is Euclidean distance/cost and the constraint set is a compact set.

######  Theorem 4.2.

A partition $\pi\in\mathcal{P}_{m}(n)$ is $\sigma$-self-symmetric if and only
if $W(\delta_{\pi},\delta_{\mathrm{sym}_{\sigma}(\pi)})=0$, where
$W(\delta_{\pi},\delta_{\mathrm{sym}_{\sigma}(\pi)})$ is defined in (4.1).

###### Proof of Theorem 4.1.

Consider measures
$\mu_{\sigma},\nu_{\sigma},\omega_{\sigma}\in\mathcal{P}(\mathbb{R}^{m+1})$
such that

$\displaystyle\mathrm{spt}(\omega_{\sigma})=$
$\displaystyle\mathrm{spt}(\delta_{\pi})\cap\mathrm{spt}(\delta_{\mathrm{sym}_{\sigma}(\pi)}),$
$\displaystyle\mathrm{spt}(\mu_{\sigma})=$
$\displaystyle\mathrm{spt}(\delta_{\pi})\backslash\left(\mathrm{spt}(\delta_{\pi})\cap\mathrm{spt}(\delta_{\mathrm{sym}_{\sigma}(\pi)})\right),$
$\displaystyle\mathrm{spt}(\nu_{\sigma})=$
$\displaystyle\mathrm{spt}(\delta_{\mathrm{sym}_{\sigma}(\pi)})\backslash\left(\mathrm{spt}(\delta_{\pi})\cap\mathrm{spt}(\delta_{\mathrm{sym}_{\sigma}(\pi)})\right).$

Then we decouple $\Pi(\delta_{\pi},\delta_{\mathrm{sym}_{\sigma}(\pi)})$ as
disjoint union

$\Pi(\delta_{\pi},\delta_{\mathrm{sym}_{\sigma}(\pi)})=\Pi(\omega_{\sigma},\omega_{\sigma})\cup\Pi(\mu_{\sigma},\nu_{\sigma}).$

where $\Pi(\omega_{\sigma},\omega_{\sigma})$ is the set of matrices
concentrated on entries corresponding to
$\mathrm{spt}(\omega_{\sigma})\times\mathrm{spt}(\omega_{\sigma})$ and
$\Pi(\mu_{\sigma},\nu_{\sigma})$ is the set of matrices concentrated on
entries corresponding to the compliment of
$\mathrm{spt}(\omega_{\sigma})\times\mathrm{spt}(\omega_{\sigma})$. Therefore,
we have that

$W(\delta_{\pi},\delta_{\mathrm{sym}_{\sigma}(\pi)})=\min_{\hat{\gamma}\in\Pi(\omega_{\sigma},\omega_{\sigma})}\sum_{ij=1}^{m+1}c_{ij}\hat{\gamma}_{ij}+\min_{\tilde{\gamma}\in\Pi(\mu_{\sigma},\nu_{\sigma})}\sum_{ij=1}^{m+1}c_{ij}\tilde{\gamma}_{ij}.$

However, since $c_{ij}=|i-j|^{2}$, we have that

$\min_{\hat{\gamma}\in\Pi(\omega_{\sigma},\omega_{\sigma})}\sum_{ij=1}^{m+1}c_{ij}\hat{\gamma}_{ij}=0,$

where $\hat{\gamma}^{*}\in\Pi(\omega_{\sigma},\omega_{\sigma})$ is the unique
diagonal matrix. Therefore,

(4.2)
$W(\delta_{\pi},\delta_{\mathrm{sym}_{\sigma}(\pi)})=\min_{\tilde{\gamma}\in\Pi(\mu_{\sigma},\nu_{\sigma})}\sum_{ij}^{m+1}c_{ij}\tilde{\gamma}_{ij}.$

Furthermore, from Theorem 3.1, since the support
$\mathrm{spt}(\tilde{\gamma}^{*})\subset\mathrm{spt}(\mu_{\sigma})\times\mathrm{spt}(\nu_{\sigma})$
for the minimizer $\tilde{\gamma}$ for (4.2) is a $c$-cyclical monotone set in
$\mathrm{spt}(\mu_{\sigma})\times\mathrm{spt}(\nu_{\sigma})$ that depends on
$\sigma\in S_{m+1}$, we have that the optimal transport plan is induced by the
matrix $T_{\sigma}=(e_{\sigma(1)},\dots,e_{\sigma(m+1)})$ where
$e_{1},\dots,e_{m+1}$ is the standard basis in $\mathbb{R}^{m+1}$. ∎

We proceed to the proof of the next result.

###### Proof of Theorem 4.2.

Suppose $\pi\in\mathcal{P}_{m}(n)$ is a $\sigma$-self-symmetric partition.
Then, from Definition 2.4, we have that $\pi=\mathrm{sym}_{\sigma}(\pi)$ and
there exists $T_{\sigma}:\mathbb{R}^{m+1}\rightarrow\mathbb{R}^{m+1}$ such
that

$Y(\mathrm{sym}_{\sigma}(\pi))=T_{\sigma}(Y(\pi)).$

Then, since $\pi\in\mathcal{P}_{m}(n)$ is a $\sigma$-self-symmetric partition,
we have that $Y(\pi)=T_{\sigma}(Y(\pi))$. This implies that
$W(\delta_{\pi},\delta_{\mathrm{sym}_{\sigma}(\pi)})=0$. The optimal transport
map and plan are the do-nothing map and plan.

Conversely, suppose $W(\delta_{\pi},\delta_{\mathrm{sym}_{\sigma}(\pi)})=0$.
Then there exists an optimal matrix
$\gamma^{*}\in\Pi(\delta_{\pi},\delta_{\mathrm{sym}_{\sigma}(\pi)})$ such that

$\sum_{ij}^{m+1}c_{ij}\gamma^{*}_{ij}=0.$

Now, since $c_{ij},\gamma^{*}_{ij}\geq 0$ the non-zero entries of $\gamma^{*}$
must be assigned to the entries where $c_{ij}=0$. Therefore, from Theorem 3.1,
the set

$\\{(i,j)\in\mathrm{spt}(\delta_{\pi})\times\mathrm{spt}(\delta_{\mathrm{sym}_{\sigma}(\pi)}):c_{ij}=0\\},$

is the $c$-cyclical monotone set for $\gamma^{*}$. Since $c_{ij}=|i-j|^{2}$,
this implies that $i=j$ and hence the $c$-cyclical monotone set is a diagonal
set and their Young diagram are the same. This implies that
$\mathrm{sym}_{\sigma}(\pi)=\pi$ and hence from Definition 2.4 we conclude
that $\pi\in\mathcal{P}_{m}(n)$ is $\sigma$-self-symmetric partition, which
completes the proof. ∎

######  Example 4.1.

Figure 4 gives an example of the optimal transport map for some
$\pi\in\mathcal{P}_{2}(6)$ and $\mathrm{sym}_{(23)}\pi$.

Figure 4. The Young diagram $Y(\pi)$ for a $\pi\in\mathcal{P}_{2}(6)$ (left)
and $T_{\sigma}\big{(}Y(\pi)\big{)}$ (right) for the $\sigma$-symmetric
partition of $\pi$ with $\sigma=(2~{}3)\in S_{3}$. In purple is their common
support. The orange cube is the image of the black cube under the optimal
transport map induced by $T_{\sigma}$.

##  5\. Conclusion and future work

We have studied a class of $n$-dimensional partitions using tools from optimal
transport. More precisely, we have shown that if the Wasserstein function on
two measures from a partition is zero, their Young diagrams are the same and
hence they must be self-symmetric partitions. We believe the Kantorovich
formulation can also be adapted to study matching between even and odd
partitions as addressed in [Hohloch] in the case of partitions matched by
Euler’s identity.

In the future, one can study matching between different partitions and
potentially a multi-partition version. In particular, given $m$-dimensional
partitions $\pi_{1},\dots,\pi_{k}\in\mathcal{P}_{m}(n)$, what is the closest
partition to these partitions? This problem we believe is related to multi-
marginal optimal transport (see [Brendan] for the survey on this topic).

## References