# Russian SuperGLUE 1.1: Revising the Lessons
not Learned by Russian NLP-models

Alena Fenogenova1
Tatiana Shavrina1,2,3
Alexandr Kukushkin5
&Maria Tikhonova1,2
Anton Emelyanov1,4
Valentin Malykh6,7
1SberDevices, Sberbank, Moscow, Russia
2National Research University Higher School of Economics, Moscow, Russia
3ANO «AI Research Institute», Moscow, Russia
4Moscow Institute of Physics and Technology, Moscow, Russia
5Alex Kukushkin Lab, Moscow, Russia
6Huawei Noah’s Ark lab, Moscow, Russia
7Kazan Federal University, Kazan, Russia
&Vladislav Mikhailov1,2
Denis Shevelev1
Ekaterina Artemova2,6

###### Abstract

In the last year, new neural architectures and multilingual pre-trained models
have been released for Russian, which led to performance evaluation problems
across a range of language understanding tasks.

This paper presents Russian SuperGLUE 1.1, an updated benchmark styled after
GLUE for Russian NLP models. The new version includes a number of technical,
user experience and methodological improvements, including fixes of the
benchmark vulnerabilities unresolved in the previous version: novel and
improved tests for understanding the meaning of a word in context (RUSSE)
along with reading comprehension and common sense reasoning (DaNetQA, RuCoS,
MuSeRC). Together with the release of the updated datasets, we improve the
benchmark toolkit based on jiant framework for consistent training and
evaluation of NLP-models of various architectures which now supports the most
recent models for Russian. Finally, we provide the integration of Russian
SuperGLUE with a framework for industrial evaluation of the open-source
models, MOROCCO (MOdel ResOurCe COmparison), in which the models are evaluated
according to the weighted average metric over all tasks, the inference speed,
and the occupied amount of RAM. Russian SuperGLUE is publicly available at
https://russiansuperglue.com/.
Keywords: model evaluation, natural language understanding, benchmarks, NLP
models, language modelling, general language understanding evaluation

DOI: 10.28995/2075-7182-2021-20-XX-XX

###### ?abstractname?

В прошлом году на русскоязычном материале были обучены новые нейронные
архитектуры, в том числе мультиязычные NLP-модели, что привело к новым вызовам
в оценке качества решений задач понимания естественного языка.

В этой статье представлен Russian SuperGLUE 1.1, бенчмарк на основе GLUE для
оценки языковых моделей для русского языка. Новая версия включает в себя ряд
технических обновлений, улучшение пользовательского опыта и устранение
методологических уязвимостей версии 1.0., в том числе создание новых тестовых
сетов и улучшение датасетов на понимание смысла слова в контексте (RUSSE),
машинное чтение и здравый смысл (DaNetQA, RuCoS, MuSeRC). Кроме того,
представлены технические обновления бенчмарка на основе фреймворка jiant для
консистентного обучения и оценки NLP-моделей различных архитектур, включая
самые последние модели для русского языка. Помимо обновления основного
бенчмарка, мы представляем интеграцию бенчмарка Russian SuperGLUE с
фреймворком для промышленной оценки моделей с открытым исходным кодом –
MOROCCO (MOdel ResOurCe COmparison), в котором модели оцениваются по
средневзвешенной метрике всех заданий, скорости быстродействия и занимаемого
объема оперативной памяти. Материалы Russian SuperGLUE доступны по адресу
https://russiansuperglue.com/.

Ключевые слова: оценка моделей, понимание естественного языка, бенчмарки, NLP-
модели

Russian SuperGLUE 1.1: пересматривая невыученные уроки
русскоязычных NLP-моделей

Алена Феногенова1 |  Мария Тихонова1,2 |  Владислав Михайлов1,2
---|---|---
Татьяна Шаврина1,2,3 |  Антон Емельянов1,4 |  Денис Шевелев1
Александр Кукушкин5 |  Валентин Малых6,7 |  Екатерина Артемова2,6

1SberDevices, Сбербанк, Москва, Россия

2НИУ «Высшая школа экономики», Москва, Россия

3АНО «Институт Искусственного Интеллекта», Москва, Россия

4Московский физико-технический институт, Москва, Россия

5Лаборатория Александра Кукушкина, Москва, Россия

6Huawei Noah’s Ark lab, Москва, Россия

7Казанский (Приволжский) федеральный университет, Казань, Россия

##  1 Introduction

In the last years, new architectures and methods for model pre-training and
transfer learning have driven striking performance improvements across a range
of language understanding tasks. Complex benchmark approaches are being
developed for testing general intellectual “abilities” of NLP models on a wide
range of natural language understanding (NLU) tasks. The tasks range from
identifying causal relations in texts (NLI) to common sense, world knowledge,
and logic. The central benchmarks in the field are GLUE [1] and SuperGLUE [2]
projects for English, they include versatile tasks and allow competitive
evaluation of the models on a public leaderboard. Recently, analogous general
language understanding evaluation benchmarks have been developed for Chinese
[3], French [4], Polish [5] and Russian [6]. RussianSuperGLUE provides nine
novel Russian NLU tasks, a public leaderboard, count-based and transformer-
based baselines, and human solver evaluation.

This work presents Russian SuperGLUE 1.1, a new release of the benchmark that
provides multiple updates and improvements of the previous version. First, we
updated the following datasets: 1) RUSSE: expansion of the dataset and
construction of a novel test set; 2) DaNetQA: increasing the size of the
dataset and creation of a new test set; 3) RuCoS: doubling the size of the
validation and test sets, cleaning typos and inaccuracies; 4) MuSeRC: the
expansion of the dataset, cleaning typos and inaccuracies. Second, we provide
an improved Russian SuperGLUE toolkit based on jiant framework [7] for
consistent training and evaluation of NLP models for Russian, which now
supports the novel transformer-based models such as
RuGPT111https://github.com/sberbank-ai/ru-gpts/tree/master. Furthermore, we
introduce an enhanced web interface of the benchmark that includes bug fixes
and new features: the model evaluation by individual task (one can get the
score for a specific task), a better notification procedure, and a new
leaderboard based upon the model performance evaluation. Finally, Russian
SuperGLUE has been integrated with MOROCCO, a framework for industrial
evaluation of model performance. Models submitted to the leaderboard can be
additionally estimated by inference speed and memory footprint.

The remainder is organized as follows. Section 2 briefly describes the
benchmark tasks. Section 3 outlines the new release, namely the dataset
updates and improvements of the leaderboard interface. Section 4 provides the
description of MOROCCO framework and the performance evaluation metrics. We
compare a number of novel models for Russian with English ones in Section 5
and conclude in Section 6.

##  2 Previous Work

Russian-based NLP-systems have a long history of benchmarking within various
tasks. Starting with ROMIP Seminar in
2003222http://romip.ru/ru/2003/index.html, then Dialog Evaluation tracks
starting from 2008333http://www.dialog-21.ru/evaluation/ have continued the
prolific tradition of yearly system evaluation on the most technically
relevant problems, including morphological and syntactic parsing, text
classification, spell check, named entity recognition, and many more.
RUSSE’2018444https://russe.nlpub.org/2018/wsi/, word sense induction and
disambiguation for the Russian shared task, is definitely worth mentioning as
well. Last but not least, SberSQuAD [8] QA-system leaderboard completes a
series of traditional single-task benchmarks.

Russian SuperGLUE benchmark first introduced a multi-task benchmark for
Russian, providing a stable updated leaderboard with all the systems ranged by
their average performance on 9 complex tasks.

###  2.1 Russian SuperGLUE Tasks

We continue our work on Russian SuperGLUE555 https://russiansuperglue.com/ [6]
which follows the general language understanding evaluation methodology.
Similarly to the English prototype, Russian benchmark includes a set of NLU
tasks and a publicly available leaderboard. Namely, the benchmark comprises 9
tasks divided into 5 groups:

  * •

Textual Entailment & NLI: TERRa, RCB, LiDiRus;

  * •

Common Sense: RUSSE, PARus;

  * •

World Knowledge: DaNetQA [9];

  * •

Machine Reading: MuSeRC, RuCoS [10];

  * •

Reasoning: RWSD.

##### Task Description

We outline the information on the tasks by their type, metrics and partition
sizes in Table 1.

Task | Task Type | Task Metric | Train | Val | Test
---|---|---|---|---|---
TERRa | NLI | Accuracy | 2616 | 307 | 3198
RCB | NLI | Avg. F1 / Accuracy | 438 | 220 | 438
LiDiRus | NLI & diagnostics | MCC | 0 | 0 | 1104
RUSSE | Common Sense | Accuracy | 19845 | 8508 | 18892
PARus | Common Sense | Accuracy | 400 | 100 | 500
DaNetQA | World Knowledge | Accuracy | 1749 | 821 | 805
MuSeRC | Machine Reading | F1 / EM | 500 | 100 | 322
RuCoS | Machine Reading | F1 / EM | 72193 | 7 577 | 7257
RWSD | Reasoning | Accuracy | 606 | 204 | 154
Table 1: Russian SuperGLUE task description. Train/Val/Test include number of
samples for each set; MCC stands for Matthews Correlation Coefficient; EM -
Exact Match.

TERRA Textual Entailment Recognition for Russian is aimed at capturing textual
entailment in a binary classification form. Given two text fragments (premise
and hypothesis), the task is to determine whether the meaning of the
hypothesis is entailed from the premise. The dataset was sampled from the
Taiga corpus [11].

RCB The Russian Commitment Bank is a 3-way classification task aimed at
recognizing textual entailment (NLI). In contrast to TERRa, the premise in RCB
may represent a textual segment rather than a single sentence. The corpus was
filtered from Taiga with a number of pre-defined rules and labeled by crowd
workers.

LiDiRus is a diagnostic set that tests models for a rich set of 33 linguistic
features, commonsense, and world knowledge. The dataset was constructed as a
translation from GLUE diagnostics with the preservation of all features. Thus,
it provides an opportunity for evaluation of linguistic and semantic
properties of language models in the setting of NLI task and for drawing
comparisons between the languages.

RUSSE is a binary classification task that involves word sense disambiguation.
Given a pair of sentences containing the same ambiguous word, the goal of the
model is to recognize if the word is used in the same meaning. The dataset was
constructed from RUSSE [12].

PARus is a binary classification task aimed to identify the most plausible
alternative out of two for a given premise. It is a manually verified
translation of the COPA dataset from SuperGLUE.

DaNetQA is a Russian QA dataset for yes/no questions which follows the BoolQ
design [21]. Each sample consists of a Wikipedia paragraph and a human-
generated question related to the paragraph. The task is to come up with a
binary answer (yes or no) for the given question.

MuSeRC is a machine reading comprehension (MRC) task. Each sample consists of
a text paragraph, multi-hop questions based on the paragraph, and possible
answers for each question. The goal is to choose all correct answers for each
question. The dataset was collected from publicly available sources across
multiple domains (elementary school texts, news, summary of series, fiction
stories, and fairy tales), and further annotated by crowd-workers.

RuCoS is an MRC task that involves commonsense reasoning and world knowledge.
The dataset is a counterpart of ReCoRD [22] for English. Each example consists
of a text paragraph, a query with a missing named entity, and a set of
candidates for the answer. The task is to select one of the candidates that
best fits the gap.

RWSD Russian Winograd Schema task is devoted to coreference resolution in a
binary classification form. The corpus was created as a manually validated
translation of the Winograd Schema
Challenge666https://cs.nyu.edu/faculty/davise/papers/WinogradSchemas/WS.html.

##  3 New Release Features

Version 1.1 includes important methodological updates to the datasets, as well
as the expansion of a number of "out-of-the-box" supported model architectures
in the software, which is attached for the convenience of developers and a
unified testing environment for all systems. Also, in addition to the main
leaderboard, the model evaluation process was significantly supplemented by
industrial metrics, which will be described below.

###  3.1 Improving the Tasks

The first version of the datasets has a number of drawbacks that revealed
themselves after the initial release. We collected the feedback and fixed the
shortcomings of the previous version of the benchmark. Among the main reasons
for weaknesses are: 1) data leakage, 2) class distributions in test sets, 3)
smaller size of the MRC datasets and the number of typos and inconsistencies
in them. The latest problem is inevitable, RuCoS and MuSeRC are the most
resources and time-consuming for collection and verification datasets - still
their sizes were smaller than in their English analogs (ReCoRD and MultiRC
respectively). As a result, four datasets were improved, for two of them
(DaNetQA and RUSSE) completely new test sets were created. The results of the
leaderboard were rescored - all baselines were measured again on the new
datasets. Additionally, we asked the participants to resubmit on the new data.
Thus, now only the latest version of the datasets and leaderboard are
supported. In this section, we describe the procedure of the dataset
improvements.

####  3.1.1 RUSSE

The update of RUSSE was motivated by extremely high scores of the language
models which significantly outperformed the human benchmark.

For example, mBART [28] achieved almost 99% accuracy, while human performance
was at the level of 75%. We believe that the conversion of the publicly
available RUSSE test set to that of Russian SuperGLUE has possibly led to data
leakage.

To this end, we constructed a completely new test set for the task in order to
eliminate the potential leakage. First, we filtered the anchor words,
discarded the most outdated and rare ones, and enriched the dataset with novel
samples. Second, we collected sentences dating from the 2020 year using
publicly available news sources such as Wikinews777https://www.wikinews.org/
and Lenta.ru888https://lenta.ru/. Finally, we manually validated the meanings
of the anchor words in the resulted sentences and annotated the answers. The
total size of the novel test set is 18 892 examples.

For the obtained test set we re-scored the human benchmark using the same
annotation procedure in Yandex.Toloka task as described in [6] but on the new
subset of the data. The human performance achieved 80.5% accuracy, while the
best model performance on the leaderboard 2 at present is 72.9% (RuBERT
conversational).

####  3.1.2 DaNetQA

Originally, DaNetQA had a limited number of examples: 392, 295, 295
(train/val/test). We extended the dataset following the methodology described
in [9], and converted a subset of MuSeRC into the yes/no QA setting, labeled
by crowd-workers afterward. The new task contains 1750, 821, and 805 examples
(train/val/test). In addition, we manually checked validation and test sets
and balanced both sets by target class, as opposed to the previous version
where the class distribution was 80/20% and changed the answer distribution by
balancing the sets. The current class balance is 50/50% in contrary to the
originally imbalanced data with 80% yes answers.

Since the test set has been changed completely we re-scored the performance of
human solvers and models. While human performance gets 91 of accuracy score
for the updated dataset, the language models (see table 2) are not greater
than 65,7% (not 80% as it was before).

####  3.1.3 RuCoS

The new version of RuCoS involves the following updates. We doubled the size
of the validation (7527 examples) and test (7257 examples) sets as described
in [10]. We manually verified the crowd-worker annotations and corrected typos
and annotation inconsistencies. Since the human performance was assessed on a
subset of the test set, the results remain the same. The best-performing model
is now RuGPT3-XL over a few-shot technique.

####  3.1.4 MuSeRC

As opposed to the English analogue MultiRC, MuSeRC was relatively small in
size which we aimed to improve. However, MuSeRC consists only of multi-hop
questions which makes the tasks more difficult in contrast to MultiRC which
also includes one-hop questions. We extended the train set with more than 300
new samples containing novel multi-hop questions. As a result, the size of
MuSeRC became comparable with MultiRC as the number of multi-hop questions is
5,228 and 5,825 respectively. Thus, in the new Russian SuperGLUE release we:
expanded the train set; cleaned typos, grammar mistakes, and text inaccuracies
in all the samples.

###  3.2 Infrastructure Advances

The interaction between the leaderboard participants and the benchmark
interface is crucially important as the entry usage threshold directly affects
the user experience and submission quantity. To this end, the new release
contains bug fixes and presents new features of the leaderboard interface and
infrastructure.

First, we improved the reliability of the model evaluation system on the
website. We made it more strict and fixed some minor bugs. Furthermore, we
enhanced the web interface and added new features: 1) The user can download
their previous submissions and edit them; 2) The user can evaluate their model
and upload submission both on a single task and the full set of tasks; 3) The
user receives two email notifications after they make their submission public.
The first one confirms the submission verification step, and the second one
informs whether the submission was published on the leaderboard or rejected
(and why); 4) The user guide is updated to provide a better leaderboard usage
experience; 5) The user now can evaluate their model by industrial performance
metrics, namely inference speed and memory footprint which we describe in
Section 4. The performance leaderboard is developed as well (see Figure 1).

Besides, Russian SuperGLUE 1.1 involves minor bug fixes along with the support
of the novel models for Russian: RuGPT3 models999 RuGPT3-Small:
https://huggingface.co/sberbank-ai/rugpt3small_based_on_gpt2,
RuGPT3-Medium: https://huggingface.co/sberbank-ai/rugpt3medium_based_on_gpt2,
RuGPT3-Large: https://huggingface.co/sberbank-ai/rugpt3large_based_on_gpt2,
RuGPT3-XL: https://huggingface.co/sberbank-ai/rugpt3xl included in the list of
models by HuggingFace
library101010https://github.com/huggingface/transformers.

Figure 1: Performance evaluation leaderboard in RussianSuperGLUE benchmark.

##  4 Computational Efficiency Evaluation

A number of closely related benchmarks consider only the task-specific
performance of the models, leaving the computational efficiency unattended. To
this end, Russian SuperGLUE is now integrated with MOROCCO [31], a framework
for industrial evaluation of model performance by the following metrics:
memory footprint and inference speed (see Section 4.1). The user can evaluate
their model by submitting a Docker container which is expected to read the
text from the standard input and channel the predictions to standard output.
The container is run in a fixed isolated environment with limited running
time, RAM, and CPU/GPU resources. We use
Yandex.Cloud111111https://cloud.yandex.com/ platform where the following
hardware is provided: 1 $\times$ Intel Broadwell CPU, 1 $\times$ NVIDIA Tesla
V100 GPU. The Docker container OS is Ubuntu 20.04. The solution is run over
several iterations to eliminate the dispersion, with the median values further
computed. Along with the metrics, we also compute the task-specific metric
based upon the Docker output to further aggregate the results into a final
score for the submission.

###  4.1 Industrial Metrics

Memory footprint, or GPU RAM usage $M$ is measured by running a Docker
container with a single record as input and measuring the maximum $M$. We
repeat the procedure 5 times and take the median value.

Inference speed, or _throughput_ $Tp$ is computed by running a Docker
container with $N$ records as input and optional batch size to measure
$T_{N}$. Besides, we estimate the model initialization time $T_{\text{init}}$
by running the container with a single record as input. The resulting
_throughput_ is computed as follows121212During the evaluation process, the
$N=2000$ is used and the batch size is 32. We repeat the procedure 5 times and
compute the median value.:

$Tp=\frac{N}{T_{N}-T_{\text{init}}}.$

We propose to use these three characteristics, namely $Q$, $Tp$, and $M$, in
the following way: we comprise a 2-dimensional plot with the horizontal axis
being a quality for a downstream task $Q$ (this metric is specific to the
task) and vertical axis being a throughput $Tp$ for the model. To visualize
memory footprint $M$, we propose to use circles of different sizes instead of
a mere point on the plot. The scores that involve industrial performance
metrics for the models from Russian SuperGLUE leaderboard are presented in
Figure 2.

Figure 2: Models comparison on Russian SuperGLUE benchmark.

MOROCCO allows computing the performance by running the containers in other
technical environments that best fit the user needs. Figure 2 presents an
unexpected result: the dilemma of choosing between speed and performance for
the Russian language is not at all a dilemma - the highest quality models are
also the fastest (certainly, except for the simplest solutions and baselines
like TF-IDF).

##  5 Results and Discussion

The current level of systems participating in the above-described language
tests and competitions has certainly grown over the past decades: although the
most common text-based tests are less than a dozen years old, we can trace the
development trends and system evaluations based on simpler, unchanged
technical criteria for their growth. The benchmark approach to the assessment
of intelligent systems is currently dominant, allowing to combine the
assessment of various intellectual abilities under the cumulative assessment
of general intelligence. Intellectual tests, expressed through texts,
constitute the main productive method of such an assessment, making it
possible to formulate a variety of types of tasks and compare the level of
systems with human intelligence, including the formation of sets of examples
of tasks, to successfully solve skills or abilities that are not lower than
human, but which do not have clear definitions within the framework of
neuroscience: common sense, goal-setting, cause-and-effect relationships,
knowledge about the world. The current version of the leaderboard version 1.1
is shown in Figure 3.

The existing problems of benchmark approaches, however, are subject to close
research by the community. The discussion is provoked by a significant
difference in the level of metrics observed in Russian SuperGLUE and in the
English-language leaderboard. The best result so far is 67.9% overall for
Russian (while the human level is 81.1%), while for English the best model
performance is 90.4%, beating the human score of 89.8%.

A separate subject of discussion is the issue of limitations of the presented
leaderboard and its methodological analogues in other languages. While the
tasks set in the benchmark themselves are designed to test the human
intellectual abilities or their imitation, we see that in some cases (for
example, the English SuperGLUE), a result higher than human has already been
achieved in a completely mechanical approach, using transformer models
pretrained on large corpora and fine-tuned on accumulated task-specific data.
At the time of this writing, the best result among Russian-based models was
raised by 15% using simplistic ML-hackathon methods - model ensembling,
automatic translation and training a meta-classifier for weighting the models
in various tasks.

The growing popularity of multilingual benchmarks is promising: the extension
of the testing methodology has led to a comprehensive multilingual assessment
- the XTREME [29] and XGLUE [30] projects have combined the available
materials for testing systems to their ability to reproduce human intellectual
abilities on 40 and 19 typologically diverse languages accordingly. The
Russian language is included as a part of the test material in both of these
benchmarks, which is a promising prospect for the further integration of
project data into multilingual X-benchmarks with both testing and training
data provided. We anticipate that the speed of benchmark hacking will become
lower than the speed of creating weighted, complex benchmarks if they strictly
evaluate the modelling of the language and separate the language itself from
all distinct abilities expressed with the language.

Figure 3: Models comparison on RussianSuperGLUE benchmark.

##  6 Conclusion

We present Russian SuperGLUE v1.1, an updated benchmark for evaluating
general-purpose language understanding systems for Russian. As part of the
development of the project, the tasks were updated:

  * •

RUSSE (understanding word meaning in context) - a new test set has been
compiled, the possibility of a dataset leak is excluded;

  * •

DaNetQA (yes / no questions based on commonsense reasoning and machine
reading) - a new test set was compiled, the composition of classes in the dev
and test set was balanced;

  * •

RuCoS (machine-reading and commonsense reasoning) - task dataset expanded and
manually corrected, the composition of the classes in the dev and test set has
been balanced;

  * •

MuSeRC (machine-reading and information retrieval) - task dataset expanded and
manually corrected.

A prominent direction for future work is to expand the existing tasks, provide
the support for upcoming models for Russian, and improve the user experience
of the MOROCCO framework, specifically by supporting models not released as a
part of HuggingFace library such as
ELMo131313http://docs.deeppavlov.ai/en/master/features/pretrained_vectors.html#elmo.
Overall, we believe that Russian SuperGLUE provides the research community
with a challenging frontier and further natural language understanding
progress for Russian.

## References

[1] Wang, Alex, et al. “GLUE: A multi-task benchmark and analysis platform for
natural language understanding.” arXiv preprint arXiv:1804.07461 (2018).

[2] Wang, Alex, et al. “Superglue: A stickier benchmark for general-purpose
language understanding systems.” arXiv preprint arXiv:1905.00537 (2019).

[3] Xu L. et al. Clue: A chinese language understanding evaluation benchmark
//arXiv preprint arXiv:2004.05986. – 2020.

[4] Le H. et al. Flaubert: Unsupervised language model pre-training for french
//arXiv preprint arXiv:1912.05372. – 2019.

[5] Rybak P. et al. KLEJ: comprehensive benchmark for polish language
understanding //arXiv preprint arXiv:2005.00630. – 2020.

[6] Shavrina, Tatiana, et al. “RussianSuperGLUE: A Russian Language
Understanding Evaluation Benchmark.” arXiv preprint arXiv:2010.15925 (2020).

[7] Pruksachatkun, Yada, et al. "jiant: A software toolkit for research on
general-purpose text understanding models." arXiv preprint arXiv:2003.02249
(2020).

[8] Efimov P. et al. SberQuAD–Russian reading comprehension dataset:
Description and analysis //International Conference of the Cross-Language
Evaluation Forum for European Languages. – Springer, Cham, 2020. – pp. 3-15.

[9] Glushkova, Taisia, et al. “DaNetQA: a yes/no Question Answering Dataset
for the Russian Language.” arXiv preprint arXiv:2010.02605 (2020).

[10] Fenogenova, Alena, Vladislav Mikhailov, and Denis Shevelev. “Read and
Reason with MuSeRC and RuCoS: Datasets for Machine Reading Comprehension for
Russian.” Proceedings of the 28th International Conference on Computational
Linguistics. 2020.

[11] Shavrina, Tatiana, and Olga Shapovalova. “To the methodology of corpus
construction for machine learning: “Taiga” syntax tree corpus and parser.”
Proceedings of “CORPORA-2017” International Conference. 2017.

[12] Panchenko, Alexander, et al. “RUSSE’2018: a shared task on word sense
induction for the Russian language.” arXiv preprint arXiv:1803.05795 (2018).

[13] Sharoff, Serge, and Joakim Nivre. “The proper place of men and machines
in language technology." Processing Russian without any Linguistic Knowledge.
Computational Linguistics and Intelligent Technologies 10.17 (2011): 657-670.

[14] Conneau, Alexis, and Douwe Kiela. “Senteval: An evaluation toolkit for
universal sentence representations.” arXiv preprint arXiv:1803.05449 (2018).

[15] McCann, Bryan, et al. “The natural language decathlon: Multitask learning
as question answering.” arXiv preprint arXiv:1806.08730 (2018).

[16] Eichler, Max, Gözde Gül Şahin, and Iryna Gurevych. “LINSPECTOR WEB: A
multilingual probing suite for word representations.” arXiv preprint
arXiv:1907.11438 (2019).

[17] Şahin, Gözde Gül, et al. “Linspector: Multilingual probing tasks for word
representations.” Computational Linguistics 46.2 (2020): 335-385.

[18] Wolf, Thomas, et al. “HuggingFace’s Transformers: State-of-the-art
natural language processing.” arXiv preprint arXiv:1910.03771 (2019).

[19] Gauen, Kent, et al. “Low-power image recognition challenge.” 2017 22nd
Asia and South Pacific Design Automation Conference (ASP-DAC). IEEE, 2017.

[20] Panchenko, Alexander, et al. “Russe: The first workshop on russian
semantic similarity.” arXiv preprint arXiv:1803.05820 (2018).

[21] Clark, Christopher, et al. “BoolQ: Exploring the surprising difficulty of
natural yes/no questions.” arXiv preprint arXiv:1905.10044 (2019).

[22] Zhang, Sheng, et al. “Record: Bridging the gap between human and machine
commonsense reading comprehension.” arXiv preprint arXiv:1810.12885 (2018).

[23] Dagan, Ido, Oren Glickman, and Bernardo Magnini. “The pascal recognising
textual entailment challenge.” Machine Learning Challenges Workshop. Springer,
Berlin, Heidelberg, 2005.

[24] Haim, R. Bar, et al. “The second pascal recognising textual entailment
challenge.” Proceedings of the Second PASCAL Challenges Workshop on
Recognising Textual Entailment. 2006.

[25] Giampiccolo, Danilo, et al. “The third pascal recognizing textual
entailment challenge.” Proceedings of the ACL-PASCAL workshop on textual
entailment and paraphrasing. 2007.

[26] Bentivogli, Luisa, et al. “The Fifth PASCAL Recognizing Textual
Entailment Challenge.” TAC. 2009.

[27] Min, Sewon, et al. “NeurIPS 2020 EfficientQA Competition: Systems,
Analyses and Lessons Learned.” arXiv preprint arXiv:2101.00133 (2021).

[28] Liu, Yinhan, et al. "Multilingual denoising pre-training for neural
machine translation." Transactions of the Association for Computational
Linguistics 8 (2020): 726-742.

[29] Hu J. et al. XTREME: A Massively Multilingual Multi-task Benchmark for
Evaluating Cross-lingual Generalisation //International Conference on Machine
Learning. – PMLR, 2020. – pp. 4411-4421.

[30] Liang Y. et al. Xglue: A new benchmark dataset for cross-lingual pre-
training, understanding and generation //arXiv preprint arXiv:2004.01401. –
2020.

[31] V.Malykh, A.Kukushkin, E.Artemova, V.Mikhailov, M.Tikhonova, T.Shavrina.
MOROCCO: Model Resource Comparison Framework. //arXiv preprint
arXiv:2104.14314. – 2021.

##  7 Appendix

###  7.1 Appendix 1. Russian SuperGLUE Leaderboard

Table 2: Russian SuperGLUE v 1.1 Leaderboard Rank | Name | Score | LiDiRus | RCB | PARus | MuSeRC | TERRa | RUSSE | RWSD | DaNetQA | RuCoS
---|---|---|---|---|---|---|---|---|---|---|---
1 |  | HUMAN
---
BENCHMARK
0.811 | 0.626 | 0.68 / 0.702 | 0.982 | 0.806 / 0.42 | 0.92 | 0.805 | 0.84 | 0.915 | 0.93 / 0.89
2 |  | RuGPT3XL
---
few-shot
0.535 | 0.096 | 0.302 / 0.418 | 0.676 | 0.74 / 0.546 | 0.573 | 0.565 | 0.649 | 0.59 | 0.67 / 0.665
3 |  | MT5
---
Large
0.528 | 0.061 | 0.366 / 0.454 | 0.504 | 0.844 / 0.543 | 0.561 | 0.633 | 0.669 | 0.657 | 0.57 / 0.562
4 |  | RuBERT
---
plain
0.521 | 0.191 | 0.367 / 0.463 | 0.574 | 0.711 / 0.324 | 0.642 | 0.726 | 0.669 | 0.639 | 0.32 / 0.314
5 | RuGPT3Large | 0.505 | 0.231 | 0.417 / 0.484 | 0.584 | 0.729 / 0.333 | 0.654 | 0.647 | 0.636 | 0.604 | 0.21 / 0.202
6 |  | RuBERT
---
conv
0.5 | 0.178 | 0.452 / 0.484 | 0.508 | 0.687 / 0.278 | 0.64 | 0.729 | 0.669 | 0.606 | 0.22 / 0.218
7 | mBert | 0.495 | 0.189 | 0.367 / 0.445 | 0.528 | 0.639 / 0.239 | 0.617 | 0.69 | 0.669 | 0.624 | 0.29 / 0.29
8 |  | heuristic
---
majority
0.468 | 0.147 | 0.4 / 0.438 | 0.478 | 0.671 / 0.237 | 0.549 | 0.595 | 0.669 | 0.642 | 0.26 / 0.257
9 |  | RuGPT3
---
Medium
0.468 | 0.01 | 0.372 / 0.461 | 0.598 | 0.706 / 0.308 | 0.505 | 0.642 | 0.669 | 0.634 | 0.23 / 0.224
10 |  | RuGPT3
---
Small
0.438 | -0.013 | 0.356 / 0.473 | 0.562 | 0.653 / 0.221 | 0.488 | 0.57 | 0.669 | 0.61 | 0.21 / 0.204
11 |  | Baseline
---
TF-IDF1.1
0.434 | 0.06 | 0.301 / 0.441 | 0.486 | 0.587 / 0.242 | 0.471 | 0.57 | 0.662 | 0.621 | 0.26 / 0.252
12 |  | Random
---
weighted
0.385 | 0.0 | 0.319 / 0.374 | 0.48 | 0.45 / 0.071 | 0.483 | 0.528 | 0.597 | 0.52 | 0.25 / 0.247
13 |  | majority
---
class
0.374 | 0.0 | 0.217 / 0.484 | 0.498 | 0.0 / 0.0 | 0.513 | 0.587 | 0.669 | 0.503 | 0.25 / 0.247


# On fractional version of oriented coloring111This work is partially
supported by the IFCAM project “Applications of graph homomorphisms”
(MA/IFCAM/18/39).

Sandip Das$\,{}^{a}$, Soham Das$\,{}^{a}$, Swathy Prabhu$\,{}^{b}$, Sagnik
Sen$\,{}^{c}$

$(a)$ Indian Statistical Institute, Kolkata, India
$(b)$ Ramakrishna Mission Vivekananda Educational and Research Institute,
Kolkata, India
$(c)$ Indian Institute of Technology Dharwad, Dharwad, India

###### Abstract

We introduce the fractional version of oriented coloring and initiate its
study. We prove some basic results and study the parameter for directed cycles
and sparse planar graphs. In particular, we show that for every $\epsilon>0$,
there exists an integer $g_{\epsilon}\geq 12$ such that any oriented planar
graph having girth at least $g_{\epsilon}$ has fractional oriented chromatic
number at most $4+\epsilon$. Whereas, it is known that there exists an
oriented planar graph having girth at least $g_{\epsilon}$ with oriented
chromatic number equal to $5$. We also study the fractional oriented chromatic
number of directed cycles and provide its exact value. Interestingly, the
result depends on the prime divisors of the length of the directed cycle.

Keywords: oriented coloring, fractional coloring, planar graphs, directed
cycles.

##  1 Introduction

“It is possible to go to a graph theory conference and to ask oneself, at the
end of every talk, what is the fractional analogue?” - Scheinermann and Ullman
[5] made this remark in the preface of their book on fractional graph theory.
Considering the popularity of studying fractional versions of well-studied
problems, it is a wonder that the fractional version of oriented coloring is
yet to be studied. We initiate it with this article.

An oriented graph $G$ is a directed graph without any directed cycle of length
1 or 2. In this article, a graph $G$ refers to a simple or an oriented graph
while $V(G)$ denotes the set of vertices of $G$ and $E(G)$ or $A(G)$ refers to
its set of edges or arcs, respectively.

The notion of oriented coloring was introduced by Bruno Courcelle [1] in 1994
inspiring a considerable volume of work on the topic (see recent survey [6]
for details). An oriented $k$-coloring of an oriented graph $G$ is a function
$f$ from $V(G)$ to a set of $k$ colors such that (i) $f(x)\neq f(y)$ for every
arc $xy\in A(G)$, and (ii) $f(y)=f(z)$ implies $f(x)\neq f(w)$ for every
$xy,zw\in A(G)$. The oriented chromatic number $\chi_{o}(G)$ is the minimium
$k$ such that $G$ admits an oriented $k$-coloring. The oriented chromatic
number for a family $\mathcal{F}$ of oriented graphs is given by

$\chi_{o}(\mathcal{F})=\max\\{\chi_{o}(G)|G\in\mathcal{F}\\}.$

Without further ado, let us now define the natural analogue of the fractional
version of the oriented chromatic number. Let $S$ be a set of $k$ colors and
let $P_{b}(S)$ denote the set of all subsets of $S$ having cardinality $b$. A
$b$-fold oriented $k$-coloring is a mapping $f$ from $V(G)$ to $P_{b}(S)$
satisfying $(i)$ $f(x)\cap f(y)=\emptyset$ for every arc $xy\in A(G)$, and
$(ii)$ $f(x)\cap f(w)\neq\emptyset$ implies $f(y)\cap f(z)=\emptyset$ for
every $xy,zw\in A(G)$. The $b$-fold oriented chromatic number
$\chi^{b}_{o}(G)$ of $G$ is the minimum $k$ such that $G$ admits an $b$-fold
oriented $k$-coloring.

The fractional oriented chromatic number of $G$ is given by

$\chi^{*}_{o}(G)=\inf_{b\rightarrow\infty}\frac{\chi^{b}_{o}(G)}{b}.$

Observe that $\chi^{a+b}_{o}(G)\leq\chi^{a}_{o}(G)+\chi^{b}_{o}(G)$ for all
$a,b\in\mathbb{N}$. Thus the above limit exists due to the Subadditivity Lemma
(see Appendix A.4 [5]). Naturally, for a family $\mathcal{F}$ of oriented
graphs

$\chi^{*}_{o}(\mathcal{F})=\max\\{\chi^{*}_{o}(G)|G\in\mathcal{F}\\}.$

Notice that the oriented $k$-coloring and chromatic number $\chi_{o}(\cdot)$
are equivalent to the $1$-fold oriented $k$-coloring and chromatic number
$\chi^{1}_{o}(\cdot)$, respectively.

The close relation between oriented chromatic number and (oriented) graph
homomorphisms is well-known [6]. On the other hand, the fractional version of
the usual chromatic number has a famous equivalent formulation using
homomorphism to Kneser graphs [5]. Thus, naturally we study the relation
between the oriented fractional coloring and oriented graph homomorphisms.
Alongside such a study, we explore some other basic properties of oriented
fractional coloring.

A relevant related concept is the oriented analogues of clique and clique
number. The analogue of clique and clique number for oriented graphs ramified
into two notions: (i) oriented absolute clique and clique number, and (ii)
oriented relative clique and clique number. The later is more relevant here.
An oriented relative clique [3] of an oriented graph $G$ is a vertex subset
$R\subseteq V(G)$ satisfying $f(x)\neq f(y)$ under any homomorphism $f$ of
$G$, and for any distinct vertices $x,y\in R$. The oriented relative clique
number [3] $\omega_{ro}(G)$ of $G$ is the cardinality of a largest oriented
relative clique. The oriented relative clique number
$\omega_{ro}(\mathcal{F})$ for a family $\mathcal{F}$ of oriented graphs is
the maximum $\omega_{ro}(G)$ where $g\in\mathcal{F}$.

We will soon see that the parameter $\chi^{*}_{o}(\cdot)$ is sandwiched
between the parameters oriented relative clique number (lower bound) and
oriented chromatic number (upper bound). Therefore, it is interesting to
examine the oriented fractional chromatic number of oriented graphs or
families of oriented graphs for which the values of $\omega_{ro}$ and
$\chi_{o}$ are different.

The most ordinary such graphs one can think of are probably the directed
cycles $C_{r}$ of length $r$. The study of fractional oriented chromatic
number of these simple looking graphs turn out to be quite challenging.
Moreover, the corresponding results are utterly surprising and have an
interesting relation with prime numbers. To motivate the readers, we present
an interesting example where the fractional oriented chromatic number is
strictly less than the oriented chromatic number.

######  Example 1.1.

Let $C_{7}$ be the directed 7-cycle. We know that $\chi_{o}(C_{7})=4$.
However, Fig. 1 shows a $2$-fold oriented $7$-coloring of $C_{7}$ implying
$\chi^{*}_{o}(C_{7})\leq\frac{7}{2}=3.5<4=\chi_{o}(C_{7})$. Is this upper
bound tight? We will answer that later in this article, and till then we
encourage the readers to think about it.

$x_{0}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$\\{1,2\\}$$\\{3,4\\}$$\\{5,6\\}$$\\{7,1\\}$$\\{2,3\\}$$\\{4,5\\}$$\\{6,7\\}$
Figure 1: Fractional oriented coloring of the directed 7-cycle $C_{7}$.

One of the most important open problems in the domain of oriented coloring is
determining the oriented chromatic number of the family $\mathcal{P}_{3}$ of
oriented planar graphs. In particular, improving the upper bound
$\chi_{o}(\mathcal{P}_{3})\leq 80$ [4] seems to be especially challenging.
Moreover, the related class of questions of determining the oriented chormatic
number $\chi_{o}(\mathcal{P}_{g})$ of the family $\mathcal{P}_{g}$ of oriented
planar graphs with girth (length of a smallest cycle) at least $g$ are also
interesting. However, till date the only known exact bounds are for the cases
$\chi_{o}(\mathcal{P}_{g})=5$ for all $g\geq 12$.

In general, finding the exact value of $\chi_{o}(\mathcal{P}_{g})$ for $g\geq
3$ seems to be tough problem. Therefore, we wondered if the fractional version
will be any easier or if the exact values of the parameter will remain the
same. For this particular article, we focus more on the second question and
find that indeed the fractional oriented chromatic number of $\mathcal{P}_{g}$
can be less than $5$ for large values of $g$, and, in fact, it gets
arbitrarily close to $4$ as $g\to\infty$.

The organization of this article as follows. In Section 2, we present the
preliminary notation, terminology and establish some basic results. In
Sections 3 and 4 we study the fractional oriented chromatic number of directed
graphs and sparse planar graphs, respectively. Finally, in Section 5, we share
our concluding remarks.

##  2 Preliminaries and basic results

Let $G$ and $H$ be two oriented graphs. A function $f:V(G)\to V(H)$ is a
homomorphism of $G$ to $H$ if for each arc $xy$ of $G$, $f(x)f(y)$ is an arc
of $H$. We use the notation $G\to H$ to denote that $G$ admits a homomorphism
to $H$. This definition readily motivates the following result.

######  Proposition 2.1.

If $G\to H$, then $\chi_{o}^{*}(G)\leq\chi_{o}^{*}(H)$.

###### Proof.

Let $\chi_{o}^{*}(H)=\frac{\chi^{b}_{o}(H)}{b}$, and thus there exists a
$b$-fold oriented $\chi^{b}_{o}(H)$-coloring $f$ of $H$. Assume that
$\phi:G\to H$ is a homomorphism. Notice that the composition $f\circ\phi$ is a
$b$-fold oriented $\chi^{b}_{o}(H)$-coloring of $G$. ∎

Now the next natural question is whether there exists any equivalent
definition of oriented fractional coloring and chromatic number using the
notion of homomorphisms. To express such an equivalent formulation we need
some definitions.

The Kneser graph $KG_{a,b}$ is a graph having the subsets of cardinality $b$
of a set of cardinality $a$ as vertices, and two vertices are adjacent if and
only if they are disjoint sets. A consistent sub-orientation of $KG_{a,b}$ is
an oriented graph $\overrightarrow{KG}_{a,b}$, whose underlying graph is a
subgraph of $KG_{a,b}$, and whose arcs are oriented in such a way that given
two arcs $xy$ and $wz$ we have $x\cap z\neq\emptyset\implies y\cap
w=\emptyset$. That brings us to the equivalent formulation of oriented
fractional coloring using the notion of homomorphisms.

######  Theorem 2.2.

An oriented graph $G$ satisfies $\chi_{o}^{*}(G)\leq\frac{a}{b}$ if and only
if $G\to\overrightarrow{KG}_{ac,bc}$ where $\overrightarrow{KG}_{ac,bc}$ is a
consistent sub-orientation of $KG_{ac,bc}$ and $c$ is a constant positive
integer.

To prove the above theorem, we will first prove a supporting result.

######  Theorem 2.3.

If $G\to\overrightarrow{KG}_{a,b}$ for some consistent sub-orientation of
$KG_{a,b}$, then there exists a consistent sub-orientation of $KG_{ac,bc}$
satisfying $G\to\overrightarrow{KG}_{ac,bc}$ for every positive integer $c$.

###### Proof.

It is enough to show that there exists a consistent sub-orientation of
$KG_{ac,bc}$ isomorphic to $\overrightarrow{KG}_{a,b}$. This can be obtained
by replacing each vertex $x=\\{x_{1},x_{2},\cdots,x_{b}\\}$ of
$\overrightarrow{KG}_{a,b}$ with
$\hat{x}=\\{x_{11},x_{12},\cdots,x_{1b},x_{21},x_{22},\cdots,x_{2b},\cdots,x_{c1},x_{c2},\cdots,x_{cb}\\}$.
∎

Now we are ready to prove Theorem 2.2.

Proof of Theorem 2.2. Let $\chi_{o}^{*}(G)\leq\frac{a}{b}$. That means, $G$
admits a $b^{\prime}$-fold oriented $a^{\prime}$-coloring $f$ for some
$a^{\prime},b^{\prime}$ satisfying
$\frac{a^{\prime}}{b^{\prime}}=\frac{a}{b}$. Notice that, as we have not
assumed a reduced form of $\frac{a}{b}$, it is possible to have $a^{\prime}<a$
and $b^{\prime}<b$. However, due to Theorem 2.3 it is enough to prove assuming
a reduced form of $\frac{a}{b}$.

Now let us construct an oriented graph $C$ having the colors used for the
$b^{\prime}$-fold oriented $a^{\prime}$-coloring $f$ of $G$ as vertices.
Moreover, two vertices $x$ and $y$ of $C$ have an arc $xy$ between them if
there exists an arc $uv$ in $G$ satisfying $f(u)=x$ and $f(v)=y$. Notice that,
$C$ is a consistent sub-orientation of $KG_{a^{\prime},b^{\prime}}$ and $f$ is
a homomorphism of $G$ to $C$. This takes care of the “if” part.

On the other hand, if $g:G\to\overrightarrow{KG}_{ac,bc}$ where
$\overrightarrow{KG}_{ac,bc}$ is a consistent sub-orientation of $KG_{ac,bc}$,
then $f$ itself is also a $bc$-fold $ac$-coloring of $G$. This implies
$\chi_{o}^{*}(G)\leq\frac{a}{b}$. This completes the “only if” part. ∎

Next we will move onto the sandwich theorem mentioned in the introduction.
Before stating it, it is useful to recall a handy characterization of an
oriented relative clique.

######  Proposition 2.4.

[3] A vertex subset $R\subseteq V(G)$ of $G$ is an oriented relative clique if
and only if any non-adjacent pair of vertices in $R$ is connected by a
directed 2-path.

Now we are ready to state and prove the sandwich theorem.

######  Theorem 2.5.

For any oriented graph $G$,
$\omega_{ro}(G)\leq\chi^{*}_{o}(G)\leq\chi_{o}(G)$.

###### Proof.

Let $R$ be a relative oriented clique of $G$ with $|R|=\omega_{ro}(G)$.
Suppose $f$ is a $b$-fold oriented $a$-coloring of $G$. Then, as the non-
adjacent vertices of $R$ are connected by a directed $2$-path, we must have
$f(x)\cap f(y)=\emptyset$ for all distinct $x,y\in R$. Thus, a total of $|R|b$
colors have been used on the vertices of $R$. Therefore,
$a\geq|R|b=\omega_{ro}(G)b$ which implies that $\frac{a}{b}\geq\omega_{ro}$.
Hence the first inequality.

The second inequality follows from the trivial observation
$\chi^{*}_{o}(G)\leq\chi^{1}_{o}(G)=\chi_{o}(G)$. ∎

We will sign off the section by establishing a general lower bound for
oriented fractional chromatic number. To do so, we will introduce an oriented
analogue of independent sets. A vertex subset $I\subseteq V(G)$ of an oriented
graph $G$ is an oriented independent set if for each distinct pair of vertices
$x,y\in I$, it is possible to find an oriented coloring $f$ of $G$ satisfying
$f(x)=f(y)$.

######  Proposition 2.6.

Given an oriented graph $G$, a vertex subset $I\subseteq V(G)$ is an oriented
independent set if and only if any two vertices of $I$ are neither adjacent
nor connected by a directed $2$-path.

###### Proof.

The “if” part directly follows from Proposition 2.4.

For the “only if” part, given distinct $x,y\in I$, define the following
function

$f(z)=\begin{cases}z,&\text{ for }z\in V(G)\setminus\\{y\\},\\\ x,&\text{ for
}z=y.\end{cases}$

Notice that $f$ is a homomorphism of $G$ to $G\setminus\\{y\\}$. ∎

We also use this definition to introduce the oriented analogue of the
parameter independence number. The oriented independence number
$\alpha_{o}(G)$ is the maximum $|I|$ where $|I|$ is an oriented independent
set of $G$. Finally, we are ready to state the result that gives us a general
lower bound of oriented fractional chromatic number.

######  Theorem 2.7.

Given any oriented graph $G$ we have
$\chi_{o}^{*}(G)\geq\frac{|V(G)|}{\alpha_{o}(G)}$.

###### Proof.

Let $f$ be a $b$-fold $a$-coloring of $G$ with $\frac{a}{b}=\chi_{o}^{*}(G)$.
This means, there is a set $S$ of $a$ colors whose set of all subsets having
cardinality $b$ is $P_{b}(S)$, and in particular $f$ is a function from $V(G)$
to $P_{b}(S)$.

Note that, if $f(u)=x$ and $f(v)=y$, and $x\cap y\neq emptyset$, then $u,v$
are independent. Thus $S_{z}=\\{u:z\in f(u)\\}$ for any $z\in S$ is an
oriented independent set and $|S_{z}|\leq\alpha_{o}(G)$. Moreover, observe
that every vertex $u\in V(G)$ is part of exactly $b$ such sets. Thus we have

$|V(G)|\cdot b=\sum_{z\in
S}|S_{z}|\leq\alpha_{o}(G)\cdot|S|=\alpha_{o}(G)\cdot a.$

This implies

$\chi_{o}^{*}(G)=\frac{a}{b}\geq\frac{|V(G)|}{\alpha_{o}(G)}$

and completes the proof. ∎

Notice that, we can prove the tightness of the bound $\chi_{o}^{*}(C_{7})=3.5$
easily using the above result. In the next section, we are going to provide
the generalized tight values for $\chi_{o}^{*}(C_{r})$, where $C_{r}$ denotes
the directed cycle of length $r$, for all $r\geq 3$.

##  3 Directed cycles

We use the following classification of prime numbers to present our result. A
prime number $k>3$ is a type-A prime if $k\equiv 3\bmod 4$, and is a type-B
prime if $k\equiv 1\bmod 4$. Let $r>5$ be a positive integer. If $r$ does not
have a type-A prime factor, then $\beta(r)=0$. Otherwise,
$\beta(r)=\frac{4}{p+1}$ where $p$ is the least type-A prime factor of $r$.
For instance $\beta(28)=\beta(35)=\frac{1}{2}$,
$\beta(55)=\beta(88)=\frac{1}{3}$, and $\beta(26)=\beta(2^{n})=0$.

######  Theorem 3.1.

Let $C_{r}$ be a directed cycle of length $r$. Then

  1. (a)

$\chi^{*}_{o}(C_{r})=3$ if $r\equiv 0\bmod 3$,

  2. (b)

$\chi^{*}_{o}(C_{4})=4$,

  3. (c)

$\chi^{*}_{o}(C_{5})=5$,

  4. (d)

$\chi^{*}_{o}(C_{r})=4-\beta(r)$, if $r>5$ and $r\not\equiv 0\bmod 3$.

The first three parts of the above theorem follow directly from known results.
However, the main challenge is to prove the last part of it. That part is
unexpected and gives us another indication of how difficult, counter-intuitive
and yet beautiful the theory of fractional oriented coloring may actually be.

Throughout this section we will assume that the set of vertices of $C_{r}$ is
$V(C_{r})=\\{u_{i}|i\in\mathbb{Z}/r\mathbb{Z}\\}$ and the set of arcs of
$C_{r}$ is

$A(C_{r})=\\{u_{i}u_{i+1}|\text{ the operation `+' is taken modulo }r\\}.$

Proof of Theorem 3.1(a,b,c). We know that
$\omega_{ro}(C_{r})=\chi_{o}(C_{r})=3$ for all $r\equiv 0\bmod 3$ [6]. We also
know that $\omega_{ro}(C_{4})=\chi_{o}(C_{4})=4$ and
$\omega_{ro}(C_{5})=\chi_{o}(C_{5})=5$ [6]. Thus the result follows due to
Proposition 2.5. $\square$

The proof of Theorem 3.1(d) is broken into several lemmas and observations
presented in the following.

For the rest of the section we only deal with $C_{r}$ having $r>5$ and
$r\not\equiv 0\bmod 3$. All the ‘$+$’ and ‘$-$’ operations perfomed in the
subscript of $u$ is computed modulo $r$ unless otherwise stated.

######  Lemma 3.2.

For all $r>5$ and $r\not\equiv 0\bmod 3$ we have,
$3\leq\chi^{*}_{o}(C_{r})\leq 4$.

###### Proof.

We know that $\omega_{ao}(C_{r})=3$ and $\chi_{o}(C_{r})=4$ [6]. Thus the
result follows due to Proposition 2.5. ∎

Any $b$-fold oriented $k$-coloring of $C_{r}$ having $\frac{k}{b}<4$ is a
miser $b$-fold oriented $k$-coloring.

Let $c$ be a miser $b$-fold oriented $k$-coloring of $C_{r}$ using a set $S$
of $k<4b$ colors. Note that as a directed 2-path is an oriented clique, its
vertices must receive disjoint sets of colors. As a consequence:

######  Lemma 3.3.

For all $i,j\in\\{0,1,\cdots,r-1\\}$ satisfying $0\neq|i-j|\leq 2$ we have
$c(u_{i})\cap c(u_{j})=\emptyset$.

Thus assume that $c(u_{0})=A$, $c(u_{1})=B$ and $c(u_{2})=C$. By Lemma 3.3,
$|A\cup B\cup C|=3b$ and $|A|=|B|=|C|=b$. Suppose that $D=S\setminus(A\cup
B\cup C)$. Observe that $|D|=k-3b<b$. Notice that the definitions of $A,B,C$
and $D$ depends on the coloring $c$ and the vertices $u_{0},u_{1},u_{2}$.

Now we introduce some notations to aid our proof. Note that $c(u_{i})\subset
A\cup B\cup C\cup D$ for each $i\in\\{0,1,\cdots,r-1\\}$. We will use the
notation $c(u_{i})=A_{i}B_{i}C_{i}D_{i}$ to denote the set of colors used on
$u_{i}$. However, at some point of time if we are sure that some of the sets
among $A,B,C$ or $D$ has empty intersection with $c(u_{i})$, then we can drop
the corresponding name of the set along with its subscript to denote
$c(u_{i})$. Moreover, if we are sure that $c(u_{i})\cap X\neq\emptyset$ for
some $X\in\\{A,B,C,D\\}$, then we can replace $X_{i}$ with $X^{*}_{i}$ in the
above notation.

One more type of notation that we use is the following: if for some
$X\in\\{A,B,C,D\\}$ we know that $c(u_{i})\cap X\neq\emptyset$, then we may
denote it as $c(u_{i})=X_{\\#}$. For instance if $c(u_{i})=A_{\\#}$, then we
are sure that $c(u_{i})$ has colors from $A$ but it may or may not have colors
from the other sets. Furthermore, if $c(u_{i})\cap X\neq\emptyset$ and
$c(u_{i})\cap Y\neq\emptyset$ for some $X,Y\in\\{A,B,C,D\\}$, then we may
denote it as $c(u_{i})=X_{\\#}Y_{\\#}$. Similarly, we may use three or four
set names among $A,B,C,D$ for this notation.

For instance, if at some point of time we learn that $c(u_{i})\cap
A\neq\emptyset$, $c(u_{i})\cap B=\emptyset$ and $c(u_{i})\cap C=\emptyset$,
then we can write $c(u_{i})=A_{i}B_{i}D_{i}$, $c(u_{i})=A^{*}_{i}D_{i}$,
$c(u_{i})=A^{*}_{i}B^{*}_{i}D_{i}$, $c(u_{i})=A_{\\#}B_{\\#}$ or
$c(u_{i})=A_{\\#}$ to denote the set of colors used on $u_{i}$. We will choose
to use the notation that suits our purpose.

Now we are going to list some observations needed for the proof.

######  Observation 3.4.

There exists no index $i$ with $c(u_{i})=D^{*}_{i}$.

###### Proof.

It is not possible to have $c(u_{i})=D^{*}_{i}$ as $|c(u_{i})|=b$,
$|D^{*}_{i}|\leq|D|<b$. ∎

The next observation directly follows from the second condition from the
definition of $b$-fold oriented $k$-coloring and the fact that $c(u_{0})=A$,
$c(u_{1})=B$, $c(u_{2})=C$.

######  Observation 3.5.

The following implications hold:

  * $(a)$

$c(u_{i})=B_{\\#}\implies c(u_{i+1})\neq A_{\\#}$,

  * $(b)$

$c(u_{i+1})=A_{\\#}\implies c(u_{i})\neq B_{\\#}$,

  * $(c)$

if $c(u_{3})=A$, then $c(u_{i})=A_{\\#}\implies c(u_{i+1})\neq C_{\\#}$,

In the above statement the case if $c(u_{i})=A_{\\#}$ is considered under the
special additional condition $c(u_{3})=A$.

######  Observation 3.6.

If $c(u_{i})=X_{i}D_{i}$ and $c(u_{j})=X_{j}D_{j}$, then $X_{i}D_{i}\cap
X_{j}D_{j}\neq\emptyset$ for any
$(X_{i},X_{j})\in\\{(A_{i},A_{j}),(B_{i},B_{j}),(C_{i},C_{j})\\}$.

###### Proof.

This observation holds by the pigeonhole principle as
$|c(u_{i})|=|c(u_{j})|=b$ and $|X\cup D|<2b$. ∎

The next observation is based on the fact that the color sets assigned to the
three vertices belonging to a directed 2-path must be distinct under any
$b$-fold oriented $k$-coloring as a directed 2-path is an oriented clique.

######  Observation 3.7.

For any index $i\in\\{0,1,\cdots,r-1\\}$ and for any $X\in\\{A,B,C\\}$ we
have,

$X\cap(c(u_{i})\cup c(u_{i+1})\cup c(u_{i+2}))\neq\emptyset.$

###### Proof.

Note that the vertices $u_{i},u_{i+1}$ and $u_{i+2}$ of $C_{r}$ induces a
directed 2-path, and hence $\\{u_{i},u_{i+1},u_{i+2}\\}$ is a an oriented
relative clique. Thus $|c(u_{i})\cup c(u_{i+1})\cup c(u_{i+2})|=3b$. However,
$|S\setminus X|=k-b<3b$. This implies $X\cap(c(u_{i})\cup c(u_{i+1})\cup
c(u_{i+2}))\neq\emptyset$. ∎

The above observation shows that three consecutive vertices of $C_{r}$ cannot
all avoid colors from a particular set $X\in\\{A,B,C\\}$. The following
observation will show the opposite.

######  Observation 3.8.

For any index $i\in\\{0,1,\cdots,r-1\\}$ and for any $X\in\\{A,B,C\\}$ we
cannot have,

$c(u_{i}),c(u_{i+1}),c(u_{i+2})=X_{\\#}.$

###### Proof.

Suppose the contrary.

If $c(u_{i}),c(u_{i+1}),c(u_{i+2})=A_{\\#}$, then Observation 3.5 implies
$c(u_{i-1}),c(u_{i}),c(u_{i+1})\neq B_{\\#}$ contradicting Observation 3.7.
The other two cases, namely, if $c(u_{i}),c(u_{i+1}),c(u_{i+2})=B_{\\#}$ and,
if $c(u_{i}),c(u_{i+1}),c(u_{i+2})=C_{\\#}$ can be proved similarly. ∎

Based on the above observations we are able to show stronger implications.

######  Observation 3.9.

The following implications hold:

  * $(a)$

$c(u_{i})=C_{\\#}$ and $c(u_{i})\neq B_{\\#}\implies c(u_{i+1})=A_{\\#}$ and
$c(u_{i+1})\neq C_{\\#}$,

  * $(b)$

$c(u_{i})=B_{\\#}$ and $c(u_{i})\neq A_{\\#}\implies c(u_{i+1})=C_{\\#}$ and
$c(u_{i+1})\neq B_{\\#}$,

  * $(c)$

$c(u_{3})=A$, $c(u_{i})=A_{\\#}$ and $c(u_{i})\neq C_{\\#}\implies
c(u_{i+1})=B_{\\#}$ and $c(u_{i+1})\neq A_{\\#}$.

###### Proof.

$(a)$ If $c(u_{i})=C_{\\#}$ and $c(u_{i})\neq B_{\\#}$, then $c(u_{i+1})\neq
B_{\\#}$ due to Observation 3.5. Moreover, if $c(u_{i+1})=C_{\\#}$, then
$c(u_{i+2})\neq B_{\\#}$ due to Observation 3.5. This implies
$c(u_{i}),c(u_{i+1}),c(u_{i+2})\neq B_{\\#}$ contradicting Observation 3.7.
Also $c(u_{i+1})=D^{*}_{i+1}$ is not possible due to Observation 3.4. Thus
$c(u_{i+1})=A_{\\#}$ and $c(u_{i+1})\neq C_{\\#}$.

$(b),(c)$ The proofs are similar. ∎

An automorphism of an oriented graph $G$ is a function $f:V(G)\rightarrow
V(G)$ such that $f(u)f(v)\in A(G)$ if and only if $uv\in A(G)$. An oriented
graph $G$ is $3$-dipath transitive if for any two directed $3$-paths $abcd$
and $wxyz$ of $G$ there exists an automorphism $f$ such that $f(a)=w$,
$f(b)=x$, $f(c)=y$ and $f(d)=z$.

Now we are going to prove one of the key lemmas to aid the proof of the
theorem. We need to introduce some notations to state the lemma. The set of
colors $c(u_{i})$ is called the label of $u_{i}$ for any
$i\in\mathbb{Z}/r\mathbb{Z}$. A sequence of $k$ consecutive labels are the
labels used on $u_{i},u_{i+1},\cdots,u_{i+k-1}$ for some
$i\in\mathbb{Z}/r\mathbb{Z}$. A sequence of $3$ consecutive labels of the form
($A^{*}_{i}D_{i},A_{i+1}B^{*}_{i+1}D_{i+1},C^{*}_{i+2}D_{i+2}$) is a triple.
The sequence of $4$ consecutive labels of the form
($A^{*}_{i}D_{i},A^{*}_{i+1}B^{*}_{i+1}D_{i+1},B^{*}_{i+2}C^{*}_{i+2}D_{i+2},C^{*}_{i+3}D_{i+3}$)
is a quad.

######  Lemma 3.10.

Any label is either part of a triple or a quad.

###### Proof.

As $c(u_{0})=A$, $c(u_{1})=B$, $c(u_{2})=C$, the lemma is true for all
$c(u_{i})$ having $i\in\\{0,1,2\\}$.

Now assume that the lemma is true for all $c(u_{i})$ having $i\in\\{0,1,\cdots
k-1\\}$. Observe that $c(u_{k-1})=C^{*}_{k}D_{k}$ due to our assumption. Now
we want to show that $c(u_{k})$ is part of either a triple or a quad.

Note that $c(u_{k})=A^{*}_{k}D_{k}$ due to Observation 3.5 and 3.9.

If $c(u_{k+1})\neq B_{\\#}$, then it contradicts Observation 3.7. Thus
$c(u_{k+1})=A_{i+1}B^{*}_{i+1}C_{i+1}D_{i+1}$. However if
$c(u_{k+1})=C_{\\#}$, then $c(u_{2})\cap c(u_{k+1})\neq\emptyset$. On the
other hand, as $c(u_{3})=A^{*}_{3}D_{3}$, we have $c(u_{3})\cap
c(u_{k})\neq\emptyset$. This contradicts the second condition of the
definition of $b$-fold oriented $k$-coloring. Therefore,
$c(u_{k+1})=A_{i+1}B^{*}_{i+1}D_{i+1}$.

Also $c(u_{k+1})=B_{\\#}$ implies $c(u_{k+2})\neq A_{\\#}$ due to Observation
3.5. Moreover, $c(u_{k+2})=C_{\\#}$ due to Observation 3.7 Therefore, either
$c(u_{k+2})=C^{*}_{i+2}D_{i+2}$ making $c(u_{k})$ part of a triple, or
$c(u_{k+2})=B^{*}_{i+2}C^{*}_{i+2}D_{i+2}$. In the later case, we must have
$c(u_{k+3})=C^{*}_{i+3}D_{i+3}$ due to Observation 3.5. Also this implies that
$c(u_{k+1})=A_{\\#}$ due to Observation 3.7. This makes $c(u_{k})$ part of a
quad. ∎

The labels in the entire cycle can thus be viewed as a circular arrangement of
triples and quads.

Let $(c(u_{t}),c(u_{t+1}),c(u_{t+2}))$ be a triple. If we rename the vertices
as $u_{i}=u_{i+t}$ for all $i\in\mathbb{Z}/r\mathbb{Z}$ and some constant $t$,
then the definitions of the sets $A,B,C$ and $D$ gets changed accordingly.
However, we observe that a triple remains a triple and a quad remains a quad.

######  Lemma 3.11.

If we rename the vertices as $u_{i}=u_{i+t}$ for all
$i\in\mathbb{Z}/r\mathbb{Z}$ and some constant $t$ where
$\Sigma=(c(u_{t}),c(u_{t+1}),c(u_{t+2}))$ is a triple, then a triple remains a
triple and a quad remains a quad.

###### Proof.

For convenience we will refer to every vertex as per their names before
renaming throughout the proof.

After renaming, the definitions of the sets $A,B,C$ and $D$ changes. We will
use the labels
$c(u_{t})=A^{\prime},c(u_{t+1})=B^{\prime},c(u_{t+2})=C^{\prime}$ and
$D^{\prime}=(A\cup B\cup C\cup D)\setminus(A^{\prime}\cup B^{\prime}\cup
C^{\prime})$ for convenience.

Suppose the first triple/quad after $\Sigma$ that does not remain a
triple/quad after renaming is $\Lambda$. We consider the following two cases.

Case 1: Suppose before renaming $\Lambda=(c(u_{j}),c(u_{j+1}),c(u_{j+2}))$ was
a triple.

Considering the situation before renaming, due to pigeonhole principle, we can
say that $c(u_{t})\cap c(u_{j+3})=A^{*}_{t}D_{t}\cap
A^{*}_{j+3}D_{j+3}\neq\emptyset$.

On the other hand, considering the situation after renaming $c(u_{t})\cap
c(u_{j+3})=A^{\prime}\cap C^{\prime*}_{j+3}D^{\prime}_{j+3}=\emptyset$, a
contradiction. Thus $\Lambda$ must be a triple even after renaming.

Case 2: Suppose before renaming
$\Lambda=(c(u_{j}),c(u_{j+1}),c(u_{j+2}),c(u_{j+3}))$ was a quad.

Considering the situation before renaming, due to pigeonhole principle, we can
say that $c(u_{t+2})\cap c(u_{j+3})=C^{*}_{t+2}D_{t+2}\cap
C^{*}_{j+3}D_{j+3}\neq\emptyset$.

On the other hand, considering the situation after renaming $c(u_{t+2})\cap
c(u_{j+3})=C^{\prime}\cap A^{\prime*}_{j+3}D^{\prime}_{j+3}=\emptyset$, a
contradiction. Thus $\Lambda$ must be a quad even after renaming. ∎

If the last element of a triple/quad $\Sigma$ is $c(u_{i})$ and the first
element of a triple/quad $\Lambda$ is $c(u_{i+1})$, then $\Sigma$ and
$\Lambda$ are consecutive where $\Sigma$ is before $\Lambda$ and $\Lambda$ is
after $\Sigma$.

######  Lemma 3.12.

There are no consecutive triples.

###### Proof.

As $r\not\equiv 0\bmod 3$, there must be at least one quad. Thus if there are
consecutive triples, then there exists a quad $\Sigma_{1}$ and two triples
$\Sigma_{2},\Sigma_{3}$ such that $\Sigma_{1},\Sigma_{3}$ are, respectively,
before and after $\Sigma_{2}$.

As the sets $A,B$ and $C$ are defined based on the set of colors assigned to
the vertices $u_{0},u_{1}$ and $u_{2}$, respectively, and as $C_{r}$ is
$3$-dipath transitive, we may assume that
$\Sigma_{2}=(c(u_{0}),c(u_{1}),c(u_{2}))=(A,B,C)$. Therefore,
$\Sigma_{1}=(A^{*}_{-4}D_{-4},A^{*}_{-3}B^{*}_{-3}D_{-3},B^{*}_{-2}C^{*}_{-2}D_{-2},C^{*}_{-1}D_{-1})$
and $\Sigma_{3}=(A^{*}_{3}D_{3},A_{4}B^{*}_{4}D_{4},C^{*}_{5}D_{5})$.

Note that the following constraints follow directly from the definition of
$b$-fold oriented coloring. For any distinct $i,j\in\mathbb{Z}/r\mathbb{Z}$

$c(u_{i})\cap c(u_{j})\neq\emptyset\implies c(u_{i-1})\cap
c(u_{j+1})=\emptyset\text{ and }c(u_{i+1})\cap c(u_{j-1})=\emptyset.$ (1)

Observe that $c(u_{-1})\cap c(u_{5})=C_{-1}D_{-1}\cap C_{5}D_{5}\neq\emptyset$
by pigeonhole principle. This implies $c(u_{0})\cap c(u_{4})=\emptyset$ by
$eq^{n}$ (1).

Furthermore $c(u_{0})\cap c(u_{3})=A\cap A^{*}_{3}D_{3}\neq\emptyset$. This
implies $c(u_{-1})\cap c(u_{4})=\emptyset$ by $eq^{n}$ (1).

By $eq^{n}$ (1) we have

$c(u_{-1})\cap c(u_{2})=C^{*}_{-1}D_{-1}\cap C\neq\emptyset\implies
c(u_{-2})\cap c(u_{3})=\emptyset$

and

$c(u_{-2})\cap c(u_{2})=B^{*}_{-2}C^{*}_{-2}D_{-2}\cap C\neq\emptyset\implies
c(u_{-3})\cap c(u_{3})=\emptyset.$

As $c(u_{-2})\cap c(u_{3})=c(u_{-3})\cap c(u_{3})=\emptyset$, Lemma 3.3
implies $c(u_{-1})\cap c(u_{3})\neq\emptyset$. This implies $c(u_{-2})\cap
c(u_{4})=\emptyset$.

Thus $c(u_{-2})\cup c(u_{-1})\cup c(u_{0})\subseteq(A\cup B\cup C\cup
D)\setminus c(u_{4})$. This is a contradiction to Lemma 3.3 as $|(A\cup B\cup
C\cup D)\setminus c(u_{4})|<3b$. ∎

Therefore, there are some positive number of quads in between any two triples.
In order to analyze the number of quads in between two triples, we construct a
symmetric binary matrix $T$ of dimension $r\times r$ such that

$T[i,j]=1\text{ if and only if }c(u_{i})\cap c(u_{j})\neq\emptyset\text{ for
all }i,j\in\mathbb{Z}/r\mathbb{Z}.$ (2)

Thus $T[i,j]=1$ implies $T[i+1,j-1]=T[i-1,j+1]=0$ by $eq^{n}$ (1). The
$i^{th}$ row of the binary matrix $T$ is denoted by $T_{i}$. Three consecutive
bits along a row or a column cannot be all $0$s or all $1$s due to
Observations 3.7 and 3.8.

A cyclic right-shift is the operation of rearranging the entries in a vector
by moving the final entry to the first position, while shifting all other
entries to the next position.

Now we will present an important property of the binary matrix $T$.

######  Lemma 3.13.

The vector $T_{i+1}$ is obtained by a cyclic right-shift on $T_{i}$.

###### Proof.

We have to show that $T[i,j]=T[i+1,j+1]$ for any
$i,j\in\mathbb{Z}/r\mathbb{Z}$. Suppose the contrary, that is, $T[i,j]\neq
T[i+1,j+1]$ for some $i,j\in\mathbb{Z}/r\mathbb{Z}$.

First assume that $T[i,j]=0$ and $T[i+1,j+1]=1$. This implies
$T[i+2,j]=T[i,j+2]=0$ by $eq^{n}$ (1). Moreover, to avoid three consecutive
$0$s in the $i^{th}$ row we have $T[i,j+1]=1$. This implies $T[i+1,j]=0$ by
$eq^{n}$ (1). Now the $j^{th}$ column has three consecutive $0$s contradicting
Observation 3.7. Thus $T[i,j]=0$ and $T[i+1,j+1]=1$ is not possible.

Similarly it can be shown that it is not possible to have $T[i,j]=1$ and
$T[i+1,j+1]=0$. ∎

Let $\Sigma_{1}$ be a triple and after that there are $q$ quads after which
there is a triple $\Sigma_{2}$. Then we say that $\Sigma_{2}$ is $q$-quads
after $\Sigma_{1}$.

######  Lemma 3.14.

If $\Sigma_{3}$ is $q_{2}$-quads after $\Sigma_{2}$ and $\Sigma_{2}$ is
$q_{1}$-quads after $\Sigma_{1}$, then $q_{2}=q_{1}$.

###### Proof.

Without loss of generality let $\Sigma_{1}=(u_{-i-2},u_{-i-1},u_{-i})$,
$\Sigma_{2}=(u_{0},u_{1},u_{2})$, $\Sigma_{3}=(u_{j},u_{j+1},u_{j+2})$ and
$q_{1}<q_{2}$.

As $c(u_{-i-1})\neq C_{\\#}$, we have $c(u_{-i-1})\cap c(u_{2})=\emptyset$ and
thus due to Lemma 3.13 $c(u_{2})\cap c(u_{i+5})=\emptyset$. However, note that
as $q_{1}<q_{2}$, $c(u_{i+5})$ is the fourth element of a quad. Thus
$c(u_{i+5})=C^{*}_{i+5}D_{i+5}$ implying $c(u_{2})\cap
c(u_{i+5})\neq\emptyset$, a contradiction. ∎

Note that there is at least one triple due to the way the sets $A,B,C$ are
defined. If there are $t$ triples and if a triple is $q$-quads after another,
then $r=(4q+3)t$. Therefore, the next lemma follows directly.

######  Lemma 3.15.

There is no miser $b$-fold oriented $k$-coloring of $C_{r}$ unless $r$ is
divisible by $(4q+3)$ for some $q\in\mathbb{N}$.

Suppose that $r$ is divisible by $(4q+3)$ for some $q\in\mathbb{N}$.
Furthermore, let $q^{\prime}$ is the smallest integer such that
$(4q^{\prime}+3)$ divides $r$. Then observe that $(4q^{\prime}+3)$ is a prime
number. Therefore, if a $C_{r}$ admits a miser $b$-fold oriented $k$-coloring
then $r$ must have a type-$A$ prime factor.

Furthermore we will show that if $r$ is divisible by a type-$A$ prime $p$,
then $\chi^{*}_{o}(C_{r})\leq 4-\frac{4}{p+1}$. In fact we will provide a
particular coloring to prove that.

######  Lemma 3.16.

If a type-$A$ prime $p$ divides $r$, then $\chi^{*}_{o}(C_{r})\leq
4-\beta(r)$.

###### Proof.

Assume that $p$ is the smallest type-$A$ prime that divides $r$. Let $p=4k-1$
and $r=pt$. Now we will provide a $k$-fold oriented $p$-coloring of $C_{r}$.

Let $f(x)=\\{i\cdot k+1,i\cdot k+2,\cdots,i\cdot k+k\\}$ where ‘+’ is taken
modulo $(4k-1)$, $x\equiv i\bmod p$ and $i\leq p-1$ for all $x\in V(C_{r})$.
Observe that $f$ is a $k$-fold oriented $p$-coloring of $C_{r}$. ∎

Also we will show that the above upper bound is the best possible.

######  Lemma 3.17.

If a type-$A$ prime $p$ divides $r$, then $\chi^{*}_{o}(C_{r})\geq
4-\beta(r)$.

###### Proof.

Suppose a miser $b$-fold oriented $k$-coloring $c$ of $C_{r}$ has exactly $t$
triples and $q$ quads in between two successive triples. Therefore,
$r=(4q+3)t$ and $\beta(r)\leq q+1$.

Note that a color from the set $A$ can be used at most once in a triple or a
quad. Thus, a particular color from $A$ is used at most $(q+1)t$ times. As we
can rename the vertices as $u_{i}=u_{i+t}$, any color used can be thought of
as a color from $A$. Hence any color is used at most $(q+1)t$ times.

Thus

$rb\leq k(q+1)t\implies 4-\frac{1}{(q+1)}\leq\frac{k}{b}\implies
4-\beta(r)\leq\frac{k}{b}.$

This ends our proof. ∎

Now we are ready to prove Theorem 3.1(d).

Proof of Theorem 3.1(d). The proof directly follows from Lemma 3.15, 3.16 and
3.17. $\square$

##  4 Sparse planar graphs

Recall that $\mathcal{P}_{g}$ denote the family of oriented planar graphs
having girth at least $g$. Due to Theorem 3.1 proved in the previous section,
we know that $\chi^{*}_{o}(\mathcal{P}_{g})\geq 4$ for all $g\geq 3$. A
natural question to ask is, how close to $4$ can
$\chi^{*}_{o}(\mathcal{P}_{g})$ get as we increase the value of $g$. The next
result is our attempt to answer that question.

######  Theorem 4.1.

For any $\epsilon>0$, there exists an integer $g_{\epsilon}<\infty$ such that
$4\leq\chi^{*}_{o}(\mathcal{P}_{g_{\epsilon}})\leq 4+\epsilon$.

We need to introduce a few notation and terminology for our proof. Given an
arc $xy$ of an oriented graph $G$, $y$ is an out-neighbor of $x$ and $x$ is an
in-neighbor of $y$. The set of all out-neighbors (resp., in-neighbors) of $x$
is denoted by $N^{+}(x)$ (resp., $N^{-}(x)$). Furthermore, given a vertex set
$S\subseteq V(G)$ one can define the following

$N^{+}(S)=\cup_{x\in S}N^{+}(x)\text{ and }N^{-}(S)=\cup_{x\in S}N^{-}(x).$

Let $\alpha=(\alpha_{1},\alpha_{2},\cdots,\alpha_{k})\in\\{+,-\\}^{k}$ be an
$k$-vector. For $k=1$, let us define $N^{\alpha}(x)=N^{\alpha_{1}}(x)$ for any
$x\in V(G)$. After that, for $k\geq 2$, we can inductively define
$N^{\alpha}(x)=N^{\alpha_{1}}(N^{\alpha^{\prime}}(x))$ where
$\alpha^{\prime}=(\alpha_{2},\alpha_{3},\cdots,\alpha_{k})$. An oriented graph
$G$ is $k$-nice if for each $k$-vector $\alpha\in\\{+,-\\}^{k}$ and each
vertex $x\in V(G)$ we have $N^{\alpha}(x)=V(G)$. This is an important property
in our context due to the following result.

######  Proposition 4.2.

[2] If an oriented graph $T$ is $k$-nice, then any $G\in\mathcal{P}_{5k-1}$
admits a homomorphism to $T$.

Next we need to construct a particular class of oriented graph $T_{l}$ for all
$l\geq 0$. Let $m=2^{l}$ and let $n=4m+1=2^{l+2}+1$. Consider the additive
group $\mathbb{Z}/n\mathbb{Z}$ and let $V(T_{l})$ be the set of all $m$-tuples
of $\mathbb{Z}/n\mathbb{Z}$ having consecutive elements, that is,

$V(T_{l})=\\{x_{i}=(i,i+1,\cdots,i+m-1):i\in\mathbb{Z}/n\mathbb{Z}\\}$

where the $+$ operation is taken modulo $n$. Furthermore,

$A(T_{l})=\\{x_{i}x_{j}|i+m\leq j\leq i+m+1\\}.$

Intuitively speaking, the vertex $x_{i}$ is represented by a set of $m$-tuples
$(i,i+1,\cdots,i+m-1)$ and it has arcs to the vertices
$x_{i+m}=(i+m,i+m+1,\cdots,i+2m-1)$ and $x_{i+m+1}=(i+m+1,i+m+2,\cdots,i+2m)$.
Note that the elements of the tuple of $x_{i}$ are distinct from the elements
of the tuple of $x_{i+m}$ and $x_{i+m+1}$. Thus $x_{i}$ has exactly two out-
neighbors $x_{i+m}$ and $x_{i+m+1}$. On the other hand, $x_{i-m}$ and
$x_{i-m-1}$ has $x_{i}$ as their common out-neighbor. That is, $x_{i}$ has
exactly two in-neighbors $x_{i-m}$ and $x_{i-m-1}$. For convenience we have
depicted the oriented graph $T_{l}$ for $l=1$ in Fig. 2.

$x_{0}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$x_{8}$$\\{0,1\\}$$\\{1,2\\}$$\\{2,3\\}$$\\{3,4\\}$$\\{4,5\\}$$\\{5,6\\}$$\\{6,7\\}$$\\{7,8\\}$$\\{8,0\\}$
Figure 2: The oriented graph $T_{l}$ for $l=1$.

Next we will show that $T_{l}$ is $n$-nice.

######  Lemma 4.3.

The oriented graph $T_{l}$ is $n$-nice.

###### Proof.

Observe that each vertex $x_{i}$ of $T_{l}$ has exactly $2$ out-neighbors
$x_{i+m},x_{i+m+1}$ and exactly $2$ in-neighbors $x_{i-m},x_{i-m-1}$.
Therefore, given a set $S=\\{x_{i},x_{i+1},\cdots,x_{i+m-1}\\}$ of $t$
consecutive neighbors of $T_{l}$, we have $|N^{+}(S)|=|N^{-}(S)|=t+1$ for all
$t<n$. Thus, for any vertex $x_{i}$ and any $(n-1)$-vector $\alpha$, we will
have $|N^{\alpha}(x_{i})|=n$. Hence $N^{\alpha}(x_{i})=V(T_{l})$. ∎

Therefore using the above lemma and Proposition 4.2 we can conclude the
following.

######  Lemma 4.4.

Any $G\in\mathcal{P}_{5\cdot n-1}$ admits a homomorphism to $T_{l}$ where
$n=2^{l+2}+1$.

Now we are ready to prove Theorem 4.1.

Proof of Theorem 4.1 Note that a directed cycle $C_{r}$ of length $r=5\cdot
2^{n+1}$ belongs to $\mathcal{P}_{5\cdot n-1}$. Also, $\beta(r)=0$. Thus
according to Theorem 3.1(d), $\chi_{o}^{*}(C_{r})=4$. This implies the lower
bound. We have independently proved Theorem 3.1(d) in the next section.

Next we are going to prove the upper bound. Note that each vertex of $T_{l}$
corresponds to an $m$-tuple. where $m=2^{l}$. That means if we consider the
elements of the tuples to be colors, then the tuple corresponding to $x_{i}$
can be viewed as set of $m$-colors assigned to $x_{i}$. Therefore, the tuples
corresponding to the vertices of $T_{l}$ is a potential $m$-fold oriented
$n$-coloring of $T_{l}$.

We are going to verify if the tuples indeed provide an $m$-fold oriented
$n$-coloring of $T_{l}$. To verify the first condition of $m$-fold oriented
coloring, we observe that any two adjacent vertices of $T_{l}$ corresponds to
tuples that have disjoint elements. To be precise, an arc of $T_{l}$ can be of
the two following types: $x_{i}x_{i+m}$ and $x_{i}x_{i+m+1}$. Clearly, the
elements of $x_{i}=(i,i+1,\cdots,i+m-1)$ is different from the elements of
$x_{i+m}=(i+m,i+m+1,\cdots,i+2m-1)$ and $x_{i+m+1}=(i+m+1,i+m+2,\cdots,i+2m)$.

To verify the second condition, let us assume that the condition is violated
by the set of arcs $x_{i_{1}}x_{i_{2}}$ and $x_{j_{1}}x_{j_{2}}$. In order for
such a violation to happen, we must have at least one common element $s$
between the tuples corrsponding to $x_{i_{1}},x_{j_{2}}$ and at least one
common element $t$ between the tuples corrsponding to $x_{i_{2}},x_{j_{1}}$.

That $s$ is an element of $x_{i_{1}}$ and $t$ is an element of $x_{i_{2}}$
implies $t=s+l$ where $1\leq l\leq 2m$. Similarly, as $t$ is an element of
$x_{j_{1}}$ and $s$ is an element of $x_{j_{2}}$, we have $s=t+l^{\prime}$
where $1\leq l^{\prime}\leq 2m$. Therefore, $s+(l+l^{\prime})=s$ where
$2\leq(l+l^{\prime})\leq 4m$. This is a contradiction as we are working modulo
$(4m+1)$.

Hence, $T_{l}$ admits an $m$-fold oriented $n$-coloring. Therefore, any graph
that admits a homomorphism to $T_{l}$ also admits an $m$-fold oriented
$n$-coloring. Thus if $G$ admits a homomorphism to $T_{l}$, then

$\chi^{*}_{o}(G)\leq\frac{|V(T_{l})|}{m}=\frac{n}{m}=\frac{2^{l+2}+1}{2^{l}}=4+\frac{1}{2^{l}}.$

Thus we are done as $\lim_{l\to\infty}\frac{1}{2^{l}}=0$. $\square$

##  5 Conclusions

This article initiates the study on fractional oriented chromatic number. The
works of this article naturally motivates the following problems.

  1. (1)

Find the linear programming formulation of the notion of fractional oriented
chromatic number.

  2. (2)

Find out the fractional oriented chromatic numbers of all oriented cycles.

  3. (3)

Find out the fractional oriented chromatic numbers of all the families of
oriented planar graphs having girth at least $g$, for all $g\geq 3$.

  4. (4)

Study the complexity dichotomy of finding the parameter.

## References

  * [1] B. Courcelle.  The monadic second order logic of graphs vi: On several representations of graphs by relational structures.  Discrete Applied Mathematics, 54(2):117–149, 1994.
  * [2] P. Hell, A. V. Kostochka, A. Raspaud, and É. Sopena.  On nice graphs.  Discrete Mathematics, 234(1–3):39–51, 2001.
  * [3] A. Nandy, S. Sen, and É. Sopena.  Outerplanar and planar oriented cliques.  Journal of Graph Theory, 82(2):165–193, 2016.
  * [4] A. Raspaud and É. Sopena.  Good and semi-strong colorings of oriented planar graphs.  Information Processing Letters, 51(4):171–174, 1994.
  * [5] E. R. Scheinermann and D. H. Ullman.  Fractional Graph Theory: A Rational Approach to the Theory of Graphs.  2008\.
  * [6] É. Sopena.  Homomorphisms and colourings of oriented graphs: An updated survey.  Discrete Mathematics, 339(7):1993–2005, 2016.