# Minimum acyclic number and maximum dichromatic number of oriented triangle-
free graphs of a given order

Pierre Aboulker  DIENS, École normale supérieure, CNRS, PSL University, Paris,
France  Frédéric Havet  Université Côte d’Azur, CNRS, Inria, I3S, Sophia
Antipolis, France  François Pirot  Université Paris-Saclay, Gif sur Yvette,
France.  Juliette Schabanel  DIENS, École normale supérieure, CNRS, PSL
University, Paris, France

###### Abstract

Let $D$ be a digraph. Its acyclic number $\vec{\alpha}(D)$ is the maximum
order of an acyclic induced subdigraph and its dichromatic number
$\vec{\chi}(D)$ is the least integer $k$ such that $V(D)$ can be partitioned
into $k$ subsets inducing acyclic subdigraphs. We study ${\vec{a}}(n)$ and
$\vec{t}(n)$ which are the minimum of $\vec{\alpha}(D)$ and the maximum of
$\vec{\chi}(D)$, respectively, over all oriented triangle-free graphs of order
$n$. For every $\varepsilon>0$ and $n$ large enough, we show
$(1/\sqrt{2}-\varepsilon)\sqrt{n\log
n}\leq\vec{a}(n)\leq\frac{107}{8}\sqrt{n}\log n$ and
$\frac{8}{107}\sqrt{n}/\log
n\leq\vec{t}(n)\leq(\sqrt{2}+\varepsilon)\sqrt{n/\log n}$. We also construct
an oriented triangle-free graph on 25 vertices with dichromatic number 3, and
show that every oriented triangle-free graph of order at most 17 has
dichromatic number at most 2.

##  1 Introduction

The _order_ of a graph or digraph is its number of vertices. An _independent
set_ in a graph is a set of pairwise non-adjacent vertices and a _clique_ is a
set of pairwise adjacent vertices. The _independence number_ of a graph $G$,
denoted by $\alpha(G)$, is the size of a maximum independent set in $G$. A
_triangle_ is a clique of size $3$ and a _triangle-free_ graph is a graph with
no triangle. The _Ramsey number_ $R(s,t)$ is the least $n$ such that every
graph of order $n$ contains either a clique of size $s$ or an independent set
of size $t$. The _inverse Ramsey number_ $Q(s,n)$, is the minimum independence
number of a graph of order $n$ with no clique of size $s$. In other words,
$R(s,t)=n$ if and only if $Q(s,n)=t$. In particular, $R(3,t)$ is the minimum
$n$ such that $\alpha(G)\geq t$ for every triangle-free graph of order $n$,
and $Q(3,n)$ the minimum of $\alpha(G)$ over all triangle-free graphs of order
$n$. Ajtai, Komlós, and Szemerédi [1] proved that $R(3,t)=O(t^{2}/\log t)$ and
$Q(3,n)=\Omega(\sqrt{n\log n})$. This was further tighten by Shearer [25], Fiz
Pontiveros, Griffiths, and Morris [13], and Bohman and Keevash [8] :

$\displaystyle\left(\frac{1}{4}-o(1)\right)\frac{t^{2}}{\log t}$
$\displaystyle\leq\leavevmode\nobreak\ R(3,t)\leavevmode\nobreak\ \leq$
$\displaystyle(1+o(1))\frac{t^{2}}{\log t}$
$\displaystyle\left(\frac{1}{\sqrt{2}}-o(1)\right)\sqrt{n\log n}$
$\displaystyle\leq\leavevmode\nobreak\ Q(3,n)\leavevmode\nobreak\ \leq$
$\displaystyle(\sqrt{2}+o(1))\sqrt{n\log n}$

For some positive integer $k$, we use $[k]$ to denote the set
$\\{1,\ldots,k\\}$. A _$k$ -colouring_ of a graph (resp. digraph) $G$ is a
function $\phi:V(G)\rightarrow[k]$. It is proper if $\phi(u)\neq\phi(v)$ for
every edge (resp. arc) $uv\in E(G)$. We say that $G$ is $k$-colourable if it
admits a proper $k$-colouring. The _chromatic number_ $\chi(G)$ of a graph or
digraph $G$ is the least integer $k$ such that $G$ is $k$-colourable.

In 1967, Erdős [10] asks for the greatest chromatic number $t(n)$ of a
triangle-free graph of order $n$. Iteratively pulling out the largest
independent set and using Ajtai-Komlós-Szemerédi bound on $Q(3,\cdot)$, Erdős
and Hajnal [12] proved $t(n)=O(\sqrt{n/\log n})$. Since then, several papers
[12, 25, 16, 13, 8, 9] improved the lower and upper bounds on $t(n)$. The best
upper bound so far has been established by Davies and Illingworth [9]:

$t(n)\leq\left(2\sqrt{2}+o(1)\right)\sqrt{\frac{n}{\log n}}$ (1)

The best lower bound was obtained by Bohman and Keevash [8] by analysing the
triangle-free process.

$t(n)\geq\left(\frac{1}{\sqrt{2}}-o(1)\right)\sqrt{\frac{n}{\log n}}$ (2)

So there is a factor of $4$ between these upper and lower bounds on $t(n)$.

The aim of this paper is to investigate similar questions for _oriented
triangle-free graphs_ , that are oriented graphs with no triangle in their
underlying graph.

A set of vertices is _acyclic_ in a digraph if it induces an acyclic
subdigraph. The _acyclic number_ of a digraph $D$, denoted by
$\vec{\alpha}(D)$, is the maximum size of an acyclic set in $D$, that is the
order of the largest acyclic induced subdigraph of $D$. It can be seen as a
generalization of the independence number of an undirected graph. Indeed,
denoting by $\overset{{}_{\shortleftarrow\\!\\!\\!\shortrightarrow}}{G}$ the
bidirected graph associated to $G$ (which is the digraph obtained from $G$ by
replacing each edge by two arcs in opposite direction between its end-
vertices), we trivially have
$\alpha(G)=\vec{\alpha}(\overset{{}_{\shortleftarrow\\!\\!\\!\shortrightarrow}}{G})$.

In 1964, Erdős and Moser[11] asked for a directed Ramsey-type problem.

######  Problem 1 (Erdős and Moser[11]).

What is the least integer $\operatorname{TT}(k)$ such that every oriented
graph on $\operatorname{TT}(k)$ vertices has acyclic number at least $k$ ?
What is $\vec{\alpha}(n)=\min\\{\vec{\alpha}(D)\mid D\text{ is an oriented
graph of order $n$}\\}$ ?

By definition, $TT(k)=\min\vec{\alpha}^{-1}(k)$. Note that $TT(k)$ is the
least integer $n$ such that every tournament of order $n$ contains a
transitive subtournament on $k$ vertices. Erdős and Moser[11] proved

$\displaystyle 2^{(k-1)/2}$ $\displaystyle<\leavevmode\nobreak\
\operatorname{TT}(k)\leavevmode\nobreak\ \leq$ $\displaystyle 2^{k-1}$ (3)
$\displaystyle\log_{2}n+1$ $\displaystyle\leq\leavevmode\nobreak\
\vec{\alpha}(n)\leavevmode\nobreak\ \leq$ $\displaystyle 2\log_{2}n+2$ (4)

Since this seminal paper, only little progress has been made on the above
problem. Using the Local Lemma, Nagy [19] slightly improved on the lower bound
on $TT(k)$ by showing that, for every $C<1$, $TT(k)>C\cdot 2^{(k+1)/2}$ when
$k$ is large enough. $TT(k)$ has been determined for small values of $k$.
Clearly $\operatorname{TT}(1)=1$, $\operatorname{TT}(2)=2$,
$\operatorname{TT}(3)=4$ (because of the directed $3$-cycle) and
$\operatorname{TT}(4)=8$ (because of the Paley tournament on $7$ vertices).
Reid and Parker [23] showed $\operatorname{TT}(5)=14$ and
$\operatorname{TT}(6)=28$. Sanchez-Flores [24] proved
$\operatorname{TT}(7)=54$. This result implies $\operatorname{TT}(k)\leq
54\times 2^{k-7}$ for all $k\geq 7$.

A _$k$ -dicolouring_ of a digraph $D$ is a function $\phi:V(D)\rightarrow[k]$
such that $D[\phi^{-1}(i)]$ is acyclic for every $i\in[k]$. We say that $D$ is
_$k$ -dicolourable_ if it admits a $k$-dicolouring. The _dichromatic number_
$\vec{\chi}(D)$ of a digraph $D$ is the least integer $k$ such that $D$ is
$k$-dicolourable. A digraph is _$k$ -dichromatic_ if $\vec{\chi}(D)=k$.

Analogously to Erdős’ question, Neumann-Lara [20] asked for the greatest
dichromatic number $\vec{\chi}(n)$ of an oriented graph of order $n$.

######  Problem 2 (Neumann-Lara [20]).

What is $\vec{\chi}(n)=\max\\{\vec{\chi}(D)\mid D\text{ is an oriented graph
of order $n$}\\}$?

Observe first that $\vec{\chi}(n)$ is attained by a tournament. Moreover, for
every oriented graph $D$ of order $n$,
$\vec{\chi}(D)\geq\frac{n}{\vec{\alpha}(D)}$ and a dicolouring of $D$ may be
obtained by iterately pulling out the largest acyclic set. Hence, using the
above bonds on $\vec{\alpha}(n)$, one easily gets

$\frac{1}{2}\frac{n}{\log n+1}\leq\vec{\chi}(n)\leq(1+o(1))\frac{n}{\log n}$
(5)

So there is a factor of $2$ between these upper and lower bounds on
$\vec{\chi}(n)$. However, for small values of $n$, $\vec{\chi}(n)$ is
precisely known. The smallest $2$-dichromatic tournament is the directed
$3$-cycle. For every prime integer $n$ of the form $4k+3$, the Paley
tournament of order $n$ is the tournament $P_{n}$ whose vertex set is
$\\{0,\dots,n-1\\}$ and containing the arc $ij$ if and only if $i-j$ is a
square modulo $n$. Neumann-Lara [20] proved that the smallest $3$-dichromatic
tournament has order 7 and that there exist four such tournaments, including
$P_{7}$. He also proved that the smallest $4$-dichromatic tournament has order
11, is unique and is $P_{11}$. The Paley tournament $P_{19}$ is 4-dicolourable
but Neumann-Lara [21] showed a 5-dichromatic tournament on 19 vertices.
Recently, Bellitto et al. [4] proved that it is actually a smallest one :
there is no 5-dichromatic oriented graph of order less than 19. Hence

$\vec{\chi}(n)\>=\left\\{\begin{array}[]{ll}1,&\text{if $1\leq n\leq 2$,}\\\
2,&\text{if $3\leq n\leq 6$,}\\\ 3,&\text{if $7\leq n\leq 10$,}\\\ 4,&\text{if
$11\leq n\leq 18$,}\\\ 5,&\text{if $n=19$.}\\\ \end{array}\right.$

Similar questions may be asked for subclasses of oriented graphs, and in
particular for $H$-free oriented graphs for a given oriented graph $H$. (A
digraph is _$H$ -free_ if it does not contain $H$ as a (not necessarily
induced) subdigraph. In an unpublished work, Harutyunyan and McDiarmid
proposed the following conjecture.

######  Conjecture 1 (Harutyunyan and McDiarmid [3]).

For every oriented graph $H$, there is $\epsilon>0$ such that every $H$-free
oriented graph $D$ of order $n$ satisfies $\vec{\alpha}(D)\geq n^{\epsilon}$
and $\vec{\chi}(D)\leq n^{1-\epsilon}$.

This conjecture is open even when $H$ is the directed cycle of length $3$. In
fact, it is a strengthening of the following conjecture, which is equivalent
to the celebrated Erdős-Hajnal conjecture.

######  Conjecture 2 (Alon, Pachs, Solymosi [2]).

For every tournament $H$, there exists $\epsilon>0$ such that every $H$-free
tournament $T$ of order $n$ satisfies $\vec{\alpha}(T)\geq n^{\epsilon}$.

This conjecture is known to hold for a few types of tournaments $H$ [5, 6],
but is still wide open in general.

### Our results

In this paper, we study the acyclic and dichromatic numbers of oriented
triangle-free graphs.

More precisely, we give some bounds on

  1. (i)

${\vec{a}}(n)$, the minimum of $\vec{\alpha}(D)$ over all oriented triangle-
free graphs of order $n$, and

  2. (ii)

$\vec{t}(n)$, the maximum dichromatic number of an oriented triangle-free
graph of order $n$.

By definition, ${\vec{a}}(n)\geq Q(3,n)$, and so
${\vec{a}}(n)\geq\left(\frac{1}{\sqrt{2}}-o(1)\right)\sqrt{n\log n}$. In
Subsection 3.1, considering a well-chosen orientation of $G(n,p)$ with
$p=c_{0}/\sqrt{n}$, we prove that $\vec{a}(n)\leq\frac{107}{8}\sqrt{n}\log n$
for $n$ sufficiently large. Hence we have, for every $\varepsilon>0$ and $n$
large enough,

$\left(\frac{1}{\sqrt{2}}-\varepsilon\right)\sqrt{n\log
n}\leq\vec{a}(n)\leq\frac{107}{8}\sqrt{n}\log n.$ (6)

We believe that a similar analysis can be performed on the $n$-vertex
triangle-free process $G_{\triangle}$ (see [7]), to prove that an orientation
of $G_{\triangle}$ has acyclic number $O\left(\sqrt{n\log n}\right)$. We thus
conjecture:

######  Conjecture 3.

$\vec{a}(n)=\Theta(\sqrt{n\log n})$.

The above upper bound on $\vec{a}(n)$ immediately yields
$\vec{t}(n)\geq\frac{8}{107}\frac{\sqrt{n}}{\log n}$. Moreover,
$\vec{t}(n)\leq t(n)$ and so
$\vec{t}(n)\leq\left(2\sqrt{2}+o(1)\right)\sqrt{\frac{n}{\log n}}$. In
Subsection 3.2, we improve this bound by a factor of $2$. We thus have, for
every $\varepsilon>0$ and $n$ large enough,

$\frac{8}{107}\frac{\sqrt{n}}{\log
n}\leq\vec{t}(n)\leq\left(\sqrt{2}+o(1)\right)\sqrt{\frac{n}{\log n}}.$ (7)

Conjecture 3 implies the following.

######  Conjecture 4.

$\vec{t}(n)=\Theta\sqrt{\frac{n}{\log n}}$.

Determining $\vec{t}(n)$ is equivalent to determining $\vec{m}(k)$ the minimum
order of a $k$-dichromatic oriented triangle-free graph, because
$\vec{m}(k)=\min\vec{t}^{-1}(k)$. In Section 4, we present a deterministic way
of building small oriented triangle-free graphs with dichromatic number at
least $k$ from an undirected triangle-free graph with chromatic number at
least $k$. We then use this construction to build a $3$-dichromatic oriented
triangle-free graph on $25$ vertices. Then we prove that all oriented
triangle-free graphs on at most $17$ vertices are $2$-dicolourable. Hence

$18\leq\vec{m}(3)\leq 25$ (8)

Using our construction, we also obtain that $\vec{m}(4)\leq 209$.

In order to prove the upper bound on $\vec{a}(5)$ given in (6), we first show
in Lemma 2.4, that every graph $G$ of order $n$, admits an orientation such
that each of its acyclic sets is $d$-sparse with $d\coloneqq 2\log_{2}n+1$ in
$G$. A set of vertices $X\subseteq V(G)$ is _$d$ -sparse_ in $G$ if the
average degree of $G[X]$ is at most $d$. This lemma also yields interesting
bounds between the (list) chromatic number of graph $G$ and $\vec{\chi}(G)$,
the maximum dichromatic number over all orientations of $G$. In Theorems 2.5
and 2.6, we prove that, for every graph $G$ of order $n$, one has

$\displaystyle\chi(G)$ $\displaystyle\leq
2\vec{\chi}(G)\left(1+\left\lfloor\log_{2}n\right\rfloor\right),\quad\mbox{and}$
(9) $\displaystyle\chi_{\ell}(G)$ $\displaystyle\leq
6\vec{\chi}(G)\left(1+\left\lfloor\log_{2}n\right\rfloor\right).$ (10)

##  2 Preliminary results

###  2.1 Probabilistic tools

######  Lemma 2.1 (c.f. [15]).

Let $X$ be a random variable distributed according to the binomial
distribution $\mathcal{B}(n,p)$, for some integer $n$ and some $p\in(0,1)$.
For every $x\in(0,1)$, we let $\Lambda^{*}(x)\coloneqq
x\ln\frac{x}{p}+(1-x)\ln\frac{1-x}{1-p}$. Then, for every integer $k<n$, one
has

$\mathbb{P}\left[X\leq k\right]\leq e^{-n\,\Lambda^{*}(k/n)}.$

######  Lemma 2.2 (Chernoff’s bound).

Let $X$ be a sum of i.i.d. $(0,1)$-valued variables. Then, for every
$\delta\in(0,1)$,

$\mathbb{P}\left[X<(1-\delta)\mathbb{E}\left[X\right]\right]<\left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^{\mathbb{E}\left[X\right]}$

######  Lemma 2.3 (Lovász Local Lemma).

Let $\\{E_{i}\\}_{i\in[n]}$ be a set of random (bad) events, with dependence
graph $\Gamma$ (i.e. each event $E_{i}$ is mutually independent from every
random event that is not in its neighbourhood in $\Gamma$). If there exist
$y_{1},\ldots,y_{n}>0$ such that $\mathbb{P}\left[E_{i}\right]<1/y_{i}$, and
moreover

$\ln y_{i}>\sum_{E_{j}\in
N_{\Gamma}(E_{i})}y_{j}\mathbb{P}\left[E_{j}\right],$

for every $i\in[n]$, then
$\mathbb{P}\left[\bigwedge_{i\in[n]}\overline{E_{i}}\right]>0$.

###  2.2 A useful orientation

The following lemma is the main tool used to prove the lower bound in (7).

######  Lemma 2.4.

Let $G$ be a graph of order $n$, and fix $d\coloneqq 2\log_{2}n+1$. Then there
exists an orientation $\vec{G}$ of $G$ such that every acyclic set of vertices
in $\vec{G}$ is $d$-sparse in $G$.

###### Proof.

Let $\vec{G}$ be a uniformly random orientation of $G$. Let $X$ be any subset
of vertices of $G$ inducing a subgraph of average degree at least $d\coloneqq
2\log_{2}n+1$. We denote $s\coloneqq|X|$; there are at least $ds/2$ edges in
$G[X]$. For each acyclic orientation of $G[X]$, there is an ordering
$(x_{1},\dots,x_{s})$ of $X$ that $x_{i}x_{j}$ is an arc if and only if
$x_{i}x_{j}\in E(G)$ and $i<j$. Hence the number of acylic orientations of
$G[X]$ is at most the number of orderings of $X$, so at most $s!$. Since there
are exactly $2^{|E(G[X])|}\geq 2^{ds/2}$ orientations of $G[X]$, we have

$\mathbb{P}\left[\mbox{$X$ is acyclic in
$\vec{G}$}\right]\leq\frac{s!}{2^{ds/2}}.$

On the other hand, there are $\binom{n}{s}$ possible choices for a subset $X$
of $s$ vertices, so the probability that there exists an acyclic induced
subdigraph of $\vec{G}$ of density more than $d$ is at most

$\sum_{s\geq 1}\binom{n}{s}\frac{s!}{2^{ds/2}}\leq\sum_{s\geq
1}\left(\frac{n}{2^{d/2}}\right)^{s}\leq\sum_{s\geq
1}\left(\frac{1}{2}\right)^{s}<1.$

We conclude that there exists an orientation $\vec{G}$ of $G$ such that every
acyclic set of $\vec{G}$ is $d$-sparse, as desired. ∎

Lemma 2.4 has interesting consequences when we seek for a lower bound on the
dichromatic number of a graph $G$ in terms of its chromatic parameters.

######  Theorem 2.5.

For every graph $G$ of order $n$, one has

$\chi(G)\leq 2\vec{\chi}(G)\left(1+\left\lfloor\log_{2}n\right\rfloor\right).$

###### Proof.

Let $\vec{G}$ be the orientation of $G$ given by Lemma 2.4. Then every acyclic
subdigraph of $\vec{G}$ is $\left\lfloor d\right\rfloor$-degenerate, and hence
has a proper $(\left\lfloor d\right\rfloor+1)$-colouring, where
$d=2\log_{2}n+1$. Let $c$ be a dicolouring of $\vec{G}$ with
$\vec{\chi}(\vec{G})\leq\vec{\chi}(G)$ colours. We can find a proper colouring
of $G$ by colouring independently each colour class of $c$ using at most
$\left\lfloor d\right\rfloor+1$ (new) colours. Hence

$\chi(G)\leq\vec{\chi}(G)(\left\lfloor
d\right\rfloor+1)=2\vec{\chi}(G)\left(1+\left\lfloor\log_{2}n\right\rfloor\right).$

∎

For a given graph $G$, we let $\chi_{\ell}(G)$ be the _list-chromatic number_
of $G$ (sometimes called the _choosability_ of $G$). We recall that this is
the minimum integer $k$ such that, for every $k$-list-assignment $L\colon
V(G)\to\binom{\mathbb{N}}{k}$, there exists a proper $L$-colouring of $G$,
that is a proper colouring $c\colon V(G)\to\mathbb{N}$ that satisfies $c(v)\in
L(v)$ for every vertex $v\in V(G)$. A greedy algorithm shows that, for every
integer $d\geq 0$, every $d$-degenerate graph $G$ is $(d+1)$-list-colourable,
i.e. $\chi_{\ell}(G)\leq d+1$.

######  Theorem 2.6.

For every graph $G$ of order $n$, one has

$\chi_{\ell}(G)\leq
6\vec{\chi}(G)\left(1+\left\lfloor\log_{2}n\right\rfloor\right).$

###### Proof.

As in the proof of Theorem 2.5, there exists an orientation $\vec{G}$ of $G$
such that each acyclic subdigraph of $\vec{G}$ is $\left\lfloor
d\right\rfloor$-degenerate, and hence $(\left\lfloor d\right\rfloor+1)$-list-
colourable, where $d=2\log_{2}n+1$. We write $k_{0}\coloneqq\left\lfloor
d\right\rfloor+1\geq d$. Let $q=\vec{\chi}(\vec{G})\leq\vec{\chi}(G)$, and let
$\phi$ be a $q$-dicolouring of $\vec{G}$.

Let $k=3qk_{0}\leq 6\vec{\chi}(G)(1+\left\lfloor\log_{2}n\right\rfloor)$, and
let $L\colon V(G)\to\binom{\mathbb{N}}{k}$ be any $k$-list-assignment of $G$.
We let $X\coloneqq\bigcup_{v\in V(G)}L(v)$ be the set of colours covered by
$L$. For every colour $x\in X$, we assign a label $\sigma(x)$ chosen uniformly
at random from $[q]$. For every vertex $v\in V(G)$, we let
$L_{\sigma}(v)\coloneqq\left\\{x\in L(v):\sigma(x)=\phi(v)\right\\}$ be the
list of colours in $L(v)$ that have been assigned $\phi(v)$ as their label.
Then the size of $L_{\sigma}(v)$ is the sum of $k$ independent Bernoulli
variables of parameter $1/q$. By Lemma 2.2, we have

$\displaystyle\mathbb{P}\left[|L_{\sigma}(v)|<k_{0}\right]$
$\displaystyle<\left(\frac{e^{-2/3}}{(1/3)^{1/3}}\right)^{k/q}<e^{-0.9k_{0}}\leq
e^{-0.9d}<1/n.$

We conclude with a union-bound that with non-zero probability we have
$|L_{\sigma}(v)|\geq k_{0}$ for every vertex $v\in V(G)$. Each colour class of
$\phi$ is therefore $L_{\sigma}$-colourable, and since by construction the
colours in $L_{\sigma}$ are disjoint between different colour classes of
$\phi$, we conclude that $G$ is $L_{\sigma}$-colourable. We finish the proof
by noting that any proper $L_{\sigma}$-colouring is also in particular a
proper $L$-colouring. ∎

##  3 Bounds on $\vec{a}(n)$ and $\vec{t}(n)$

In this section, we establish the bounds in (6) and (7).

###  3.1 Upper bound on $\vec{a}(n)$

######  Theorem 3.1.

If $n$ is sufficiently large, then there exists an oriented triangle-free
graph $G$ of order $n$ such that $\vec{\alpha}(G)\leq\frac{107}{8}\sqrt{n}\log
n$. So $\vec{a}(n)\leq\frac{107}{8}\sqrt{n}\log n$.

###### Proof.

Let $c_{0}>0$ be a fixed constant, whose specific value will be determined
later in the proof. Let $G$ be a graph drawn from $G(n,p)$, with
$p=c_{0}/\sqrt{n}$.

By Lemma 2.4, there exists an orientation $\vec{G}$ of $G$ such that every set
that induces an acyclic subdigraph of $\vec{G}$ is $d$-sparse, for $d\coloneqq
2\log_{2}n+1$. To finish the proof, we show that, with non-zero probability,
$G$ has no triangle and there is no $d$-sparse set of size $k\coloneqq
c_{1}\,\frac{d}{p}+1$ in $G$, for suitable values of $c_{0},c_{1}$ (given at
the end of the proof).

Let $X\subseteq V(G)$ be a subset of $k$ vertices of $G$. The number of edges
in $G[X]$ follows the binomial distribution $\mathcal{B}(\binom{k}{2},p)$, and
we note that $X$ is $d$-sparse if and only if $G[X]$ has at most $dk/2$ edges.
For $x\in(0,1)$, we recall that
$\Lambda^{*}(x)=x\ln\frac{x}{p}+(1-x)\ln\frac{1-x}{1-p}$. By Lemma 2.1, we
have

$\displaystyle\mathbb{P}\left[\mbox{$X$ is $d$-sparse}\right]$
$\displaystyle\leq e^{-\binom{k}{2}\Lambda^{*}\left(\frac{d}{k-1}\right)}$
$\displaystyle\leq
e^{-\frac{(k-1)^{2}}{2}\left(\frac{p}{c_{1}}\ln\frac{1}{c_{1}}+\left(1-\frac{p}{c_{1}}\right)\left(\ln(1-p/c_{1})-\ln(1-p)\right)\right)}$
$\displaystyle\leq
e^{-\frac{c_{1}^{2}d^{2}}{2p^{2}}\left(\frac{p}{c_{1}}\ln\frac{1}{c_{1}}+\left(1-\frac{p}{c_{1}}\right)\left(-\frac{p}{c_{1}}+p+O(p^{2})\right)\right)}$
$\displaystyle\leq e^{-\frac{c_{1}^{2}d^{2}}{2p^{2}}\left(\frac{c_{1}-1-\ln
c_{1}}{c_{1}}\,p+O(p^{2})\right)}=e^{-c_{1}(c_{1}-1-\ln
c_{1})\frac{d^{2}}{2p}+O(d^{2})}.$

For every set $T\in\binom{V(G)}{3}$, we let $A_{T}$ be the random event that
$G[T]$ is a triangle. We have $\mathbb{P}\left[A_{T}\right]=p^{3}$. For every
set $X\in\binom{V(G)}{k}$, we let $B_{X}$ be the random event that $X$ is
$d$-sparse. By the above, we have $\mathbb{P}\left[B_{X}\right]\leq
e^{-c_{1}(c_{1}-1-\ln c_{1})d^{2}/2p+O(d^{2})}$. Let $\mathcal{A}=\\{A_{T}\mid
T\in\binom{V(G)}{3}\\}$, $\mathcal{B}=\\{B_{X}\mid X\in\binom{V(G)}{k}\\}$ and
$\mathcal{E}\coloneqq\mathcal{A}\cup\mathcal{B}$. We wish to apply Lemma 2.3
in order to show that, with non-zero probability, no random event in
$\mathcal{E}$ occurs. The rest of the proof is similar to that in [26]. Let
$\Gamma$ be the dependence graph of $\mathcal{E}$. Two events in $\mathcal{E}$
are adjacent in $\Gamma$ if and only if they concern sets that intersect on at
least $2$ vertices (since otherwise they depend on disjoint sets of edges).
For every $\mathcal{X},\mathcal{Y}\in\\{\mathcal{A},\mathcal{B}\\}$, we let
$N_{\mathcal{X}\mathcal{Y}}$ be the maximum number of nodes of $\mathcal{Y}$
adjacent to a given node of $\mathcal{X}$ in $\Gamma$ . We have

$\displaystyle N_{\mathcal{A}\mathcal{B}},N_{\mathcal{B}\mathcal{B}}$
$\displaystyle\leq|\mathcal{B}|=\binom{n}{k}<\left(\frac{ne}{k}\right)^{k};$
$\displaystyle N_{\mathcal{A}\mathcal{A}}$ $\displaystyle=3(n-3)<3n\;;$
$\displaystyle N_{\mathcal{B}\mathcal{A}}$
$\displaystyle=\binom{k}{2}(n-k)+\binom{k}{3}<\frac{(k-1)^{2}n}{2}=\frac{1}{2}\left(\frac{c_{1}dn}{c_{0}}\right)^{2}\quad\mbox{for
$n$ large enough.}$

For Lemma 2.3 to apply, there remains to find $y,z>0$ such that, for every
$T\in\binom{V(G)}{3}$ and $X\in\binom{V(G)}{k}$,

$\begin{split}\mathbb{P}\left[A_{T}\right]&<1/y,\quad\mathbb{P}\left[B_{X}\right]<1/z\;;\\\
\ln
y&>y\mathbb{P}\left[A_{T}\right]N_{\mathcal{A}\mathcal{A}}+z\mathbb{P}\left[B_{X}\right]N_{\mathcal{A}\mathcal{B}}\;;\\\
\ln
z&>y\mathbb{P}\left[A_{T}\right]N_{\mathcal{B}\mathcal{A}}+z\mathbb{P}\left[B_{X}\right]N_{\mathcal{B}\mathcal{B}}.\end{split}$
(11)

Let $y=1+\varepsilon$ for some $\varepsilon>0$ small enough, and let
$z=e^{c_{2}d^{2}/2p}$ for some $0<c_{2}<c_{1}(c_{1}-1-\ln c_{1})$. With these
values, we have

$\displaystyle z\mathbb{P}\left[B_{S}\right]\binom{k}{n}$
$\displaystyle<\exp\left(\frac{d^{2}}{2p}(c_{2}-c_{1}(c_{1}-1-\ln
c_{1}))+k\ln\frac{ne}{k}+O(d^{2})\right)$
$\displaystyle<\exp\left(\frac{d^{2}}{2p}(c_{2}-c_{1}(c_{1}-1-\ln
c_{1}))+\frac{d^{2}}{2p}(1+o(1))\right)$
$\displaystyle\underset{n\to\infty}{\to}0$ if $c_{1}(c_{1}-1-\ln
c_{1})>1+c_{2}$; $\displaystyle
y\mathbb{P}\left[A_{T}\right]N_{\mathcal{B}\mathcal{A}}$
$\displaystyle<(1+\varepsilon)\frac{p^{3}}{2}\left(\frac{c_{1}dn}{c_{0}}\right)^{2}=(1+\varepsilon)\frac{c_{0}c_{1}^{2}}{2}d^{2}\sqrt{n}$
$\displaystyle<(1+\varepsilon)(c_{0}c_{1})^{2}\frac{d^{2}}{2p}<\ln
z-\varepsilon$ if $c_{2}>(1+\varepsilon)(c_{0}c_{1})^{2}$ and $n$ is large
enough.

It is straightforward that (11) holds whenever the two conditions on
$c_{0},c_{1},c_{2}$ above hold, and $n$ is large enough. In order to minimise
the value of $k$, we may fix $c_{0}=0.513$, $c_{1}=3.43$, and $c_{2}=3.1$. ∎

###  3.2 Upper bound on $\vec{t}(n)$

The goal of this section is to prove the upper bound of (7), see Theorem 3.6.

Given a digraph $D$, and a total order $\prec$ on $V(D)$, we denote $D[\prec]$
the subdigraph induced by the arcs $(v,u)\in A(D)$ such that $u\prec v$. We
may disregard the orientation of the edges in $D[\prec]$, in which case this
is usually called the _backedge graph_ associated with $D$ and $\prec$. It is
straightforward that every independent set $I$ of $D[\prec]$ induces an
acyclic digraph $D[I]$. A well-known consequence is that
$\vec{\chi}(D)\leq\chi(D[\prec])$. To the best of our knowledge, the possible
tightness of that bound has never been discussed in the literature. We prove
that there always exists $\prec$ such that $\vec{\chi}(D)=\chi(D[\prec])$.

######  Theorem 3.2.

For every digraph $D$, one has

$\vec{\chi}(D)=\min\,\Big{\\{}\chi(D[\prec]):\mbox{$\prec$ is a total order on
$V(D)$}\Big{\\}}.$

###### Proof.

We have already shown that $\vec{\chi}(D)\leq\chi(D[\prec])$ for every total
order $\prec$ on $V(D)$. Let us prove the other direction. Let
$k\coloneqq\vec{\chi}(D)$, and let $\phi$ be a $k$-dicolouring of $D$. Let
$C_{1},\ldots,C_{k}$ be the colour classes of $\phi$. For every $i\in[k]$,
$D[C_{i}]$ is acyclic, and so induces a partial order on $C_{i}$. Let
$\prec_{i}$ be a total order of $C_{i}$ that extends this partial order. For
every $u,v\in V(D)$, we let $u\prec
v\equiv(\phi(u)<\phi(v))\vee(v\prec_{\phi(v)}u)$. It is straightforward that
each $C_{i}$ is an independent set in $D[\prec]$, and so $\phi$ is a proper
$k$-colouring of $D[\prec]$. This proves that
$\chi(D[\prec])\leq\vec{\chi}(D)$, as desired. ∎

Theorem 3.2 reduces the problem of finding a minimum dicolouring of a digraph
$D$ to finding a total order $\prec$ on $V(D)$ that minimises
$\chi(D[\prec])$. Hence, any order $\prec$ that makes $D[\prec]$ sparse in a
sense that lets us bound its chromatic number efficiently is of interest. In
the following, we prove that we can halve the maximum degree of a digraph with
a well-chosen order.

######  Lemma 3.3.

Let $D$ be a digraph of maximum total degree $\Delta$. Then there exists a
total order $\prec$ on $V(D)$ such that
$\deg_{D[\prec]}(v)\leq\left\lfloor\deg_{D}(v)/2\right\rfloor$ for every
vertex $v\in V(D)$.

###### Proof.

Let $\prec$ be an order that minimises the number of edges in $D[\prec]$. Let
us prove that $\prec$ has the desired property. For the sake of contradiction,
assume that there is a vertex $v$ such that
$\deg_{D[\prec]}(v)>\left\lfloor\deg_{D}(v)/2\right\rfloor$. Let
$\operatorname{pred}(v)$ be the set of neighbours $u$ of $v$ in $D$ such that
$u\prec v$, and let
$\operatorname{succ}(v)=N_{D}(v)\setminus\operatorname{pred}(v)$. Then $v$ is
adjacent in $D[\prec]$ with more than half the vertices in either
$\operatorname{succ}(v)$ or $\operatorname{pred}(v)$, say in
$\operatorname{succ}(v)$ without loss of generality. Then, letting
$\prec^{\prime}$ be the order obtained from $\prec$ after making $v$ the
largest element, we infer that $D[\prec^{\prime}]$ has strictly fewer edges
than $D[\prec]$, a contradiction. ∎

Given a class of graphs $\mathscr{G}$, let
$\chi(\mathscr{G})\coloneqq\max\,\\{\chi(G):G\in\mathscr{G}\\}$ and
$\vec{\chi}(\mathscr{G})\coloneqq\max\,\\{\vec{\chi}(G):G\in\mathscr{G}\\}$.
For every integer $d$, we let $\mathscr{G}_{\Delta\leq
d}\coloneqq\\{G\in\mathscr{G}:\Delta(G)\leq d\\}$ be the class of graphs of
maximum degree at most $d$ in $\mathscr{G}$. Theorem 3.2 applied together with
Lemma 3.3 yields the following result as a corollary.

######  Corollary 3.4.

For every hereditary class of graphs $\mathscr{G}$, and every integer $d$, one
has

$\vec{\chi}(\mathscr{G}_{\Delta\leq
d})\leq\chi(\mathscr{G}_{\Delta\leq\left\lfloor d/2\right\rfloor}).$

If we apply Corollary 3.4 to the class of triangle-free graphs, and use the
bound given by the Johansson-Molloy theorem [18], we obtain the following.

######  Theorem 3.5.

For every triangle-free graph $G$ of maximum degree $\Delta$, one has

$\vec{\chi}(G)\leq(1+o(1))\frac{\Delta}{2\ln\Delta}\quad\mbox{as
$\Delta\to\infty$.}$

We are now ready to prove the main result of this section.

######  Theorem 3.6.

For every triangle-free graph $G$ of order $n$, one has

$\vec{\chi}(G)\leq(1+o(1))\sqrt{\frac{2n}{\ln n}}\text{\quad as
$n\to\infty$.}$

###### Proof.

The following proof is similar in many aspects to that of [9, Theorem 1]. Let
$0<\varepsilon\leq 1/2$, and let $d(n)\coloneqq\sqrt{2n\ln n}$ for all $n\geq
2$. By Theorem 3.5, there exists $n_{1}$ such that, for every triangle-free
digraph $D$ of maximum degree at most $d(n)$, one has
$\vec{\chi}(D)\leq(1+\varepsilon)\sqrt{2n/\ln n}$ if $n\geq n_{1}$.

Let $n_{0}\coloneqq\max\,\\{e^{\frac{1+\varepsilon}{\varepsilon}},n_{1}\\}\geq
e^{3}$, and let $f(x)\coloneqq n_{0}+(1+\varepsilon)\sqrt{2x/\ln x}$ for all
$x>1$. Let us prove by induction on $n$ that, for every triangle-free graph
$G$ of order $n$, one has $\vec{\chi}(G)\leq f(n)$.

If $n\leq n_{0}$, then $n\leq f(n)$ and the result holds trivially by
assigning a distinct colour to every vertex. We may now assume that $n\geq
n_{0}$, which implies that $\frac{1}{\ln
n}\leq\frac{\varepsilon}{1+\varepsilon}$. If $\Delta(G)\leq d(n)$, this is a
direct consequence of Theorem 3.5 as explained above. So may assume that
$\Delta(G)\geq d(n)$. The neighbourhood of a vertex of maximum degree yields
an independent set $I$ of size at least $d(n)$. Given a fixed orientation $D$
of $G$, any dicolouring of $D\setminus I$ may be extended to $D$ with an extra
colour that we assign to the vertices in $I$. By the induction hypothesis,
this shows that

$\vec{\chi}(G)\leq f(n-d(n))+1.$

So the result holds if we can show that $f(n)-f(n-d(n))\geq 1$. The second
derivative of $f$ is negative on the interval $[6,+\infty)$, so $f$ is concave
on that interval. Since $n-d(n)\geq n_{0}-d(n_{0})>6$, this implies that

$\displaystyle f(n)-f(n-d(n))$ $\displaystyle\geq
d(n)f^{\prime}(n)=\sqrt{2n\ln n}\cdot(1+\varepsilon)\frac{\ln n-1}{(\ln
n)^{2}}\sqrt{\frac{\ln n}{2n}}=(1+\varepsilon)\left(1-\frac{1}{\ln n}\right)$
$\displaystyle\geq(1+\varepsilon)\left(1-\frac{\varepsilon}{1+\varepsilon}\right)=1,$

as desired. ∎

##  4 A deterministic approach

###  4.1 Linear forests

A _directed linear forest_ is a forest formed by a disjoint union of directed
paths. Given a directed graph $D$, we denote by $\vec{\ell}(D)$ the maximum
number of arcs of a directed linear forest of $D$. For every (undirected)
graph $G$, we define
$\vec{\ell}(G)\coloneqq\min\;\\{\vec{\ell}(\vec{G}):\vec{G}\mbox{ is an
orientation of $G$}\\}$.

######  Lemma 4.1.

For every graph $G$ of order $n$, $\vec{\ell}(G)=n-\alpha(G)$.

###### Proof.

Let $\vec{G}$ be an orientation of $G$. Every directed linear forest of
$\vec{G}$ may trivially be extended into a spanning directed linear forest
with the same number of arcs, by adding all uncovered vertices as isolated
trees of order $1$. Hence $\vec{\ell}(\vec{G})$ is also the maximum number of
arcs of a spanning directed linear forest of $\vec{G}$. Now, for a spanning
directed linear forest $F$, the number of arcs of $F$ plus the number of paths
of $F$ equals $n$. By the Gallai-Milgram Theorem [14], $\vec{G}$ can be
covered with at most $\alpha(G)$ directed paths, which together form a
directed linear forest of size at least $n-\alpha(G)$. Hence
$\vec{\ell}(G)\geq n-\alpha(G)$.

To show the other direction, let $I$ be a maximum independent set of $G$, and
let $D$ be an orientation of $G$ where each vertex $x\in I$ has in-degree $0$.
Let $F$ be any directed linear forest of $D$; each vertex $x\in I$ belongs to
a distinct directed path in $F$. So $F$ contains at least $\alpha(G)$ distinct
paths, hence it has size at most $n-\alpha(G)$. ∎

###  4.2 The construction

Let $D$ be a digraph. The _$n$ -backward-blowup_ $D^{\leftarrow n}$ of $D$ is
the digraph defined by

$\displaystyle V(D^{\leftarrow n})$ $\displaystyle=$
$\displaystyle\\{(v,i)\mid v\in V(D),i\in[n]\\};$ $\displaystyle
A(D^{\leftarrow n})$ $\displaystyle=$ $\displaystyle F(D^{\leftarrow n})\cup
B(D^{\leftarrow n}),\mbox{\leavevmode\nobreak\ \leavevmode\nobreak\ with}$
$\displaystyle F(D^{\leftarrow n})$ $\displaystyle=$
$\displaystyle\\{(u,i)\to(v,i)\mid u\to v\in
A(D),i\in[n]\\},\mbox{\leavevmode\nobreak\ and}$ $\displaystyle
B(D^{\leftarrow n})$ $\displaystyle=$ $\displaystyle\\{(v,i)\to(u,j)\mid u\to
v\in A(D),i\in[n],j\in[n],\mbox{\leavevmode\nobreak\ and\leavevmode\nobreak\
}i\neq j\\}$

$F(D^{\leftarrow n})$ is the set of _forward arcs_ of $D^{\leftarrow n}$ and
$B(D^{\leftarrow n})$ is the set of _backward arcs_ of $D^{\leftarrow n}$. For
$v\in V(D)$, $\\{(v,i)\mid i\in[n]\\}$ is the _pack_ of $v$. Two vertices in a
same pack are called _twins_.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$u_{4}$$u_{3}$$u_{2}$$u_{1}$$v_{4}$$v_{3}$$v_{2}$$v_{1}$

######  Lemma 4.2.

Let $k$ be a positive integer, and let $G$ be a graph such that $\chi(G)>k$.
Then, for every orientation $\vec{G}$ of $G$, the
$(k\vec{\ell}(\vec{G})+1)$-backward-blowup of $\vec{G}$ is not
$k$-dicolourable.

###### Proof.

Let $\vec{G}$ be an orientation of $G$ and $D$ be the
$(k\vec{\ell}(\vec{G})+1)$-backward-blowup of $\vec{G}$, and let $\phi$ be any
$k$-colouring of the vertices of $D$. Let us assume for the sake of
contradiction that $\phi$ induces no monochromatic directed cycle.

The forward arcs of $D$ form $k\vec{\ell}(\vec{G})+1$ pairwise disjoint copies
of $\vec{G}$. Since $\chi(G)>k$, there is at least one monochromatic arc in
each of these copies; let us pick one for each copy arbitrarily and obtain a
matching $M$ of $k\vec{\ell}(\vec{G})+1$ monochromatic forward arcs. By the
Pigeonhole Principle, we can find a set $N$ of $\vec{\ell}(\vec{G})+1$ arcs of
$M$ with the same colour.

If two arcs of $N$ lie between the same pair of packs (say $u\to v$ and
$u^{\prime}\to v^{\prime}$ where $(u,u^{\prime})$ and $(v,v^{\prime})$ are
pairs of twins), they induce a monochromatic directed $4$-cycle (namely $u\to
v\to u^{\prime}\to v^{\prime}\to u$), a contradiction.

If $N$ contains two arcs $u\to v$ and $w\to v^{\prime}$ where $v$ and
$v^{\prime}$ are twins, then $u\to v\to w\to v^{\prime}\to u$ is a
monochromatic directed $4$-cycle in $D$, a contradiction. Similarly, if $N$
contains two arcs $v\to u$ and $v^{\prime}\to w$ where $v$ and $v^{\prime}$
are twins, then $v\to u\to v^{\prime}\to w\to v$ is a monochromatic directed
$4$-cycle in $D$, a contradiction.

Henceforth, the graph $F$ induced by $N$ after contracting each pack into a
single vertex has maximum in- and out-degree $1$. If $F$ contains a directed
cycle, then there are $p$ arcs of $N$ that may be labelled $u_{1}\to
u^{\prime}_{2},u_{2}\to u^{\prime}_{3},\ldots,u_{p-1}\to
u^{\prime}_{p},u_{p}\to u^{\prime}_{1}$ so that $u_{i},u^{\prime}_{i}$ are
twins for every $i\in[p]$. We infer that $u_{1}\to u_{p}\to\ldots\to u_{2}\to
u_{1}$ is a monochromatic directed cycle in $D$, a contradiction. We conclude
that $F$ is a directed linear forest. Since $F$ is composed only of forward
arcs, we infer that $F$ is a subdigraph of $\vec{G}$. So $F$ can contain at
most $\vec{\ell}(\vec{G})$ edges, a contradiction.

This finishes the proof that $\phi$ induces a monochromatic cycle in $D$. ∎

In the above proof, we note that if $\vec{G}$ is an acyclic orientation of
$G$, then the monochromatic cycle constructed is always of length $4$, and
alternates between forward and backward arcs.

By combining Lemma 4.1 and Lemma 4.2, we have the following result as a
corollary.

######  Corollary 4.3.

Let $k$ be a positive integer, and let $G$ be an $n$-vertex graph such that
$\chi(G)>k$. Then there exists an orientation $\vec{G}$ of $G$ such that the
$\big{(}k\big{(}n-\alpha(G)\big{)}+1\big{)}$-backward-blowup of $\vec{G}$ is
not $k$-dicolourable.

As a consequence, the $19$-backward-blowup of some orientation of the Grötzsch
graph $M_{4}$ is not $3$-dicolourable. This yields a $4$-dichromatic triangle-
free graph on $209$ vertices. We note that $\min\;\\{\vec{\ell}(G):\mbox{$G$
is a triangle-free graph and $\chi(G)>3$}\\}=6$, so the Grötzch graph is best
possible when we apply Corollary 4.3 with $k=3$. This holds because, given a
triangle-free graph $G$ such that $\chi(G)>3$, and any independent set $I$ of
$G$, one has $\chi(G\setminus I)>2$. If we assume for the sake of
contradiction that $|V(G\setminus I)|\leq 5$, then $G\setminus I$ is
isomorphic to $C_{5}$. Therefore, for every vertex $x\in I$, the neighbourhood
of $x$ is an independent set of $C_{5}$, so it has size at most $2$. We
conclude that $G$ is $2$-degenerate, which contradicts the fact that
$\chi(G)>3$.

######  Proposition 4.4.

There exists a $4$-dichromatic $209$-vertex triangle-free graph.

We note that because of a result by Mohar and Wu [17, Lemma 3.2], Corollary
4.3 does not provide smallest-known $k$-dichromatic triangle-free graphs when
$k\geq 5$.

######  Lemma 4.5 (Mohar, Wu, 2016).

Let $k$ be a positive interger, and let $G$ be a graph such that $\chi(G)>k$.
Let $m$ be an integer that satisfies $2+2\ln m\leq\left\lceil
m/k\right\rceil$. Then there is an orientation of the $m$-blowup of $G$ that
is not $k$-dicolourable.

Namely, if we want to apply Corollary 4.3 to the $r$-backward-blowup of an
orientation of $M_{5}$ (the Mycielskian of the Grötzsch graph), we need
$r=49$. In contrast, Lemma 4.5 implies that there exists an orientation of the
$37$-blowup of $M_{5}$ that is not $4$-dicolourable.

###  4.3 Getting a better bound in the case $k=2$

We note that Lemma 4.2 is tight when applied to any acyclic orientation of
$C_{5}$ with $k=2$. In particular, for the two of them that contain no
directed path of length $4$, the $7$-backward-blowup is not $2$-dicolourable,
and this is best possible as illustrated in Figure 1. However, it turns out
that Lemma 4.2 is no longer tight if we apply it to the directed $5$-cycle,
and this is the orientation of $C_{5}$ that yields the minimum size of the
backward-blowup that makes it not $2$-dicolourable.

Figure 1: A 2-dicoloration of the 6-backward-blowup of the two orientations of
$C_{5}$ that contain no directed path of length 4.

In Proposition 4.6, we show that the $5$-backward-blowup of
$\overrightarrow{C_{5}}$ is not $2$-dicolourable, while Lemma 4.2 only tells
us that this holds for the $9$-backward-blowup of $\overrightarrow{C_{5}}$.
More generally, it is possible to repeat the arguments used in the proof of
Proposition 4.6 in order to show that the $\ell$-backward-blowup of
$\overrightarrow{C_{\ell}}$ is not $2$-dicolourable, for every odd $\ell$.

######  Proposition 4.6.

$D_{25}=\vec{C}_{5}^{\leftarrow 5}$ is a $3$-dicritical oriented triangle-free
graph on $25$ vertices

###### Proof.

Set $V(D_{25})=\\{u_{i,j}|i\in[5],j\in[5]\\}$ and
$A(D_{25})=\\{u_{i,j}u_{i+1,j^{\prime}}\mid
i\in[5],j\in[5],j^{\prime}\in[5],j\neq
j^{\prime}\\}\cup\\{u_{i+1,j}u_{i,j}\mid i\in[5],j\in[5]\\}$ reading the
indices modulo 5. The packs are $U_{i}=\\{u_{i,j}|j\in[5]\\}$ for $i\in[5]$.
Two vertices are called _matched_ if the arc between them is forward.

Figure 2: The digraph $D_{25}$. Left (only the forward arcs are represented):
in green a pair of matched vertices, and in orange a pack. Right: the three
main types of directed cycles.

Let us emphasize two types of directed cycles in $D_{25}$.

  * •

_matched cycle_ : directed $4$-cycle induced by two pairs of matched vertices
(for example the red arcs on Figure 2 left), formally, $u_{i,j}\to
u_{i+1,j}\to u_{i,j^{\prime}}\to u_{i+1,j^{\prime}}\to u_{i,j}$ for some
$i\in[5]$ and two different indices $j,j^{\prime}\in[5]$.

  * •

_backward cycle_ : directed $5$-cycle with five backward arcs (for example the
yellow arcs on Figure 2 left), formally, $u_{1,j_{1}}\to u_{5,j_{5}}\to
u_{4,j_{4}}\to u_{3,j_{3}}\to u_{2,j_{2}}\to u_{1,j_{1}}$ for some
$j_{1},\dots,j_{5}\in[5]$ such that $j_{i}\neq j_{i+1}$ for all $i\in[5]$.

Assume that there is a 2-dicolouring $\phi$ of $D_{25}$.

First assume that there is a monochromatic pack. Without loss of generality,
all vertices of $U_{1}$ are red. Since there is no monochromatic matched
cycle, both $U_{2}$ and $U_{5}$ have at most one red vertex and so at least
$4$ blue vertices, and thus $U_{3}$ and $U_{4}$ have each at least least three
red vertices.
If both $U_{2}$ and $U_{5}$ have one red vertex, $u_{2,j_{2}}$ and
$u_{5,j_{5}}$, then one can choose $j_{1}\in[5]\setminus\\{j_{1},j_{5}\\}$,
$j_{3}\in[5]\setminus\\{j_{2}\\}$ and $j_{4}\in[5]\setminus\\{j_{3},j_{5}\\}$
so that $u_{1,j_{1}}$, $u_{3,j_{3}}$, and $u_{4,j_{4}}$ are red. Then
$u_{1,j_{1}}\to u_{5,j_{5}}\to u_{4,j_{4}}\to u_{3,j_{3}}\to u_{2,j_{2}}\to
u_{1,j_{1}}$ is a monochromatic backward cycle, a contradiction. (See Figure 3
left.)
Henceforth, one of $U_{2},U_{5}$, say $U_{2}$, has no red vertex and so five
blue vertices. Since there is no blue matched cycle between $U_{2}$ and
$U_{3}$, at least four vertices of $U_{3}$ are red. But then, since there are
at least three red vertices in $U_{4}$, there is a red matched cycle between
$U_{3}$ ans $U_{4}$, a contradiction. Henceforth, we may assume that there is
no monochromatic pack.

Figure 3: Left: a red backward cycle, when $U_{1}$ has five red vertices and
$U_{2}$ and $U_{5}$ at least one.
Right: The case with a pack with a $4$-$1$ colour partition.

Assume that there is a pack, say $U_{1}$, with four vertices of the same
colour, say red. Since there is no red matched cycles, each of $U_{2},U_{5}$
has at least three blue vertices. Since there is no blue matched cycles, each
of $U_{3},U_{4}$ has at least two red vertices. Since no pack is
monochromatic, there is a red vertex $u_{2,j_{2}}$ in $U_{2}$ and a red vertex
$u_{5,j_{5}}$ in $U_{5}$. There exists $j_{1}\in[5]\setminus\\{j_{2},j_{5}\\}$
such that $u_{1,j_{1}}$ is red. There are no two distinct indices
$j_{3}\in[5]\setminus\\{j_{2}\\}$ and $j_{4}\in[5]\setminus\\{j_{5}\\}$ such
that $u_{3,j_{3}}$ and $u_{4,j_{4}}$ are red for otherwise there would be a
red backward cycle. Then, necessarily, the two red vertices in $U_{3}$ are
$u_{3,j_{2}},u_{3,j_{5}}$ and the two red vertices in $U_{4}$ are
$u_{4,j_{2}},u_{4,j_{5}}$. But then those vertices induce a monochromatic
matched cycle, a contradiction.

Henceforth, each pack has two or three vertices in each colour. Without loss
of generality, $U_{1}$ has three red vertices. Let $u_{2,j_{2}}$ be is a red
vertex in $U_{2}$. Since there are at least two red vertices in each $U_{i}$,
for $i=3$ to $5$, we can find $j_{i}\neq j_{i-1}$ such that $u_{i,j_{i}}$ is
red. Since $U_{1}$ has three red vertices, there is
$j_{1}\notin\\{j_{2},j_{5}\\}$ such that $u_{1,j_{1}}$ is red. Then
$u_{1,j_{1}}\to u_{5,j_{5}}\to u_{4,j_{4}}\to u_{3,j_{3}}\to u_{2,j_{2}}\to
u_{1,j_{1}}$ is a backward cycle, a contradiction.

This proves that $D_{25}$ is not $2$-dicolourable.

Figure 4 depicts a 2-dicolouring of $D_{25}$ minus any vertex, $D_{25}$ minus
a forward arc, and $D_{25}$ minus a backward arc. Since all forward (resp.
backward) arcs are equivalent, that is there is an automorphism of the graph
mapping any forward (resp. backward) arc to any other forward (resp. backward)
arc, this shows that $D_{25}$ is 3-dicritical.

Figure 4: 2-dicolouring of $D_{25}$ minus a vertex (left), $D_{25}$ minus a
forward arc (dotted blue) (center), $D_{25}$ minus a backward arc (dotted red)
(right).

∎

###  4.4 Lower bound on the number of vertices of oriented triangle-free
graphs with dichromatic number 3

######  Lemma 4.7.

Let $D$ be a oriented triangle-free graph. If $V(D)$ can be partitioned into
three sets, $X$, $Y$ and $Z$ such that :

  1. (i)

$D[X]$ has no directed cycle,

  2. (ii)

$Y$ is an independent set

  3. (iii)

there is no edge between $X$ and $Z$

  4. (iv)

there is a $2$-dicolouring of $Z$ such that $c^{-1}(1)$ is either empty, a
single vertex or two adjacent vertices,

then $D$ is $2$-dicolourable.

###### Proof.

Consider the $2$-dicolouring $c$ of $Z$ given by $(iv)$ and extend it by
colouring the vertices of $Y$ with colour 1 and the vertices of $X$ with
colour 2. There is no monochromatic cycle in $Z$ nor in $X$, and none can
intersect $X$ as its neighbourhood is included in $Y$, and therefore has a
different colour. So if there were a monochromatic cycle, it would intersect
both $Y$ and $Z$, thus have colour 1. $Y$ is pendent so the cycle contains two
vertices of $Z$, but as $D$ is triangle-free, no vertex can be adjacent to
both colour 1 vertices in $Z$, so there cannot be any monochromatic cycle. ∎

######  Lemma 4.8.

For every triangle-free digraph $D$ on at most $7$ vertices, there exists a
subset $X\subseteq V(D)$ which consists of one vertex or two adjacent vertices
such that $D\setminus X$ is acyclic.

###### Proof.

Let $D$ be a triangle-free digraph on at most 7 vertices of underlying graph
$G$. We may assume that $\delta^{-}(D)\geq 1$ and $\delta^{+}(D)\geq 1$ (and
so $\delta(G)\geq 2$), since a vertex of in- or out-degree $0$ is contained in
no directed cycle.

  * •

If $G$ is bipartite, by the minimum degree condition on $G$, either $G$ is
isomorphic to $K_{2,5}$, or $G$ is a subgraph of $K_{3,4}$.

In the first case, removing any of the two vertices of degree $5$ in $G$
yields an acyclic graph.

In the second case, let $(X,Y)$ be the bipartition of $G$, with $|X|\leq 3$
and $|Y|\leq 4$. If there is a vertex $x\in X$ with $d^{-}(x)=1$ or
$d^{+}(x)=1$, let $u_{x}$ be the neighbour of $x$ through that unique ingoing
or outgoing arc. Let $x^{\prime}\in X$ be an other neighbour of $u_{x}$ in
$G$. Then $D\setminus\\{u_{x},x^{\prime}\\}$ is acyclic, since there remains
at most one vertex in $X$ of in- and out-degree at least $1$. We can now
assume that $d_{G}(x)=4$ for every $x\in X$, i.e. $G$ is isomorphic to
$K_{3,4}$. For every vertex $y\in Y$, $d_{G}(y)=3$, so either $d^{+}_{D}(y)=1$
or $d^{-}_{D}(y)=1$. Let $u_{y}$ be the neighbour of $y$ through that unique
ingoing or outgoing arc. By the Pigeonhole Principle, there exists $x\in X$
such that $x=u_{y}=u_{y^{\prime}}$ for two distinct vertices $y,y^{\prime}\in
Y$. Let $y^{\prime\prime}\in Y\setminus\\{y,y^{\prime}\\}$. Then
$D\setminus\\{x,y^{\prime\prime}\\}$ is acyclic, since there remains at most
one vertex in $Y$ of in- and out-degree at least $1$.

  * •

If $G$ is not bipartite, then it contains an odd cycle, which is either a
$C_{5}$ or a $C_{7}$.

First, assume that $G$ contains a $C_{5}$ and no $C_{7}$. Let $X$ be a set of
vertices of $G$ that induces a $C_{5}$, and $Y\coloneqq V(G)\setminus X$. We
have $|Y|\leq 2$. The $C_{5}$ does not have any chord as it would form a
triangle, so every other cycle of $G$ intersects $Y$. If $Y$ induces an
independent set, then every vertex $y\in Y$ has exactly two neighbours in $X$
by the minimum degree condition on $G$. If there is a vertex $x$ of $X$
adjacent to all vertices of $Y$, then $D\setminus\\{x\\}$ is acyclic.
Otherwise, $Y=\\{y_{1},y_{2}\\}$, and there exist two consecutive vertices
$x_{1}$ and $x_{2}$ on the $C_{5}$ such that $x_{1}\in N_{G}(y_{1})$ and
$x_{2}\in N_{G}(y_{2})$. Then $D\setminus\\{x_{1},x_{2}\\}$ is acyclic. If
$Y=\\{y_{1},y_{2}\\}$ induces an arc, then we cannot have two consecutive
vertices $x_{1},x_{2}$ on the $C_{5}$ such that $x_{1}\in N_{G}(y_{1})$ and
$x_{2}\in N_{G}(y_{2})$, since this would yield a $C_{7}$. This implies that
$y_{1}$ and $y_{2}$ have each exactly one neighbour in $X$, respectively
$x_{1}$ and $x_{2}$. Then $D\setminus\\{x_{1},y_{1}\\}$ is acyclic.

Assume now that $G$ contains a $C_{7}$. Since $G$ is triangle-free, it is a
subgraph of the graph depicted in Figure 5 (when forgetting about the
orientation). If the removal of $\\{u_{5},u_{6}\\}$, of $\\{u_{6},u_{0}\\}$,
and of $\\{u_{0},u_{1}\\}$ leaves a directed cycle, then this forces the
partial orientation depicted in Figure 5, or the reverse orientation. So
removing $\\{u_{3}\\}$ leaves an acyclic digraph.

∎

$u_{0}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$ Figure 5: The case where $G$
contains a $C_{7}$

This lemma can be improved as follows.

######  Lemma 4.9.

Let $D$ be a oriented triangle-free graph on 8 vertices, then one of the
following statements holds :

  1. (i)

There is an arc $uv\in E(D)$ such that $D-\\{u,v\\}$ is acyclic.

  2. (ii)

$D$ is an orientation of either two disjoint $4$-cycles, or the cube, or the
cube with two diagonals, or $K_{4,4}$, or $K_{4,4}$ minus an edge, or the
subgraph of $K_{4,4}$ with degree sequence $(2,2,4,4),(3,3,3,3)$.

This result has been obtained by enumerating all oriented triangle-free graphs
on $8$ vertices and filtering out those that do not satisfy Property (i) in
Lemma 4.9. More precisely, there are $83$ triangle-free graphs on $8$ vertices
with minimal degree at least $2$ (one can generate them using nauty). Removing
those that can be made acyclic by removing a pair of adjacent vertices, only
$30$ remain. Finally, by generating all possible orientations of these $30$
graphs, one can check that those that do not satisfy (i) satisfy (ii) (there
are $998$ such digraphs).

We note here that we were able to prove Lemma 4.9 by hand in the case where
$D$ is not a subgraph of $K_{4,4}$. The method is similar to the proof of
Lemma 4.8 but the proof is long and not particularly enlightening, so we
choose not to include it here.

######  Proposition 4.10 (Picasarri-Arrieta [22]).

If $\Delta(D)<6$, then $D$ is $2$-dicolourable.

######  Corollary 4.11.

Every digraph on at most $14$ vertices is $2$-dicolourable.

###### Proof.

Take $u\in V$ with $d(u)\geq 6$. Then $X=\\{u\\}$ and $Y=N(u)$ satisfy the
hypothesis of Lemma 4.7 since $|V\setminus(X\cup Y)|\leq 7$. ∎

This bound can be improved. Using Lemma 4.9, we checked by computer calculus
that every graph on at most $17$ vertices has a decomposition $(X,Y,Z)$ as
described in Lemma 4.7, and is therefore $2$-dicolourable, without having to
consider their possible orientations. Using the fact that a $3$-dicritic graph
must have minimum degree at least $4$ and arboricity at least $3$, we have
proceeded as follows : We have enumerated all biconnected triangle-free graphs
on $n\leq 17$ vertices with minimum degree at least $4$ and maximum degree at
most $n-9$ (if $v$ has degree at least $n-8$, then $X=\\{v\\}$, $Y=N(v)$ and
$Z=V\setminus(X\cup Y)$ satisfy the hypothesis since $|Z|\leq 7$) using nauty.
Then we filtered out all those of arboricity at most $2$. For each graph $G$
obtained during this enumeration, we have computed several candidates for
$(X,Y)$ by first fixing $X=\\{u\\}$ and $Y=N(u)$ for some vertex $v\in V(G)$,
and adding to $X$ all vertices $u^{\prime}\in V(G)$ whose neighbourhood is
contained in $N(u)$ (since $G$ is triangle-free, $X$ and $Y$ are independent
sets). We have kept the couple $(X,Y)$ for with $|X|+|Y|$ is maximised, and
there remained to check whether $Z\coloneqq V(G)\setminus(X\cup Y)$ satisfied
condition $(iv)$ of Lemma 4.7. It turns out that, when $n\leq 17$, condition
$(iv)$ is systematically satisfied for the set $Z\subset V(G)$ constructed as
above because we have $\\#\\{z\in Z:\deg(z)\geq 2\\}\leq 8$, and when equality
holds $G[Z]$ is not one of the exceptions listed in Lemma 4.9. More precisely
for $n=17$, we found $375$ graphs with arboricity at least $3$, among which
$362$ led to a $Z$ with at most $7$ vertices, $12$ on with $8$ vertices and
one with $10$ vertices. For all $Z$ with $8$ vertices, $G[Z]$ was not one of
the exceptions listed in Lemma 4.9. And the one on $10$ vertices has $2$
vertices with degree $1$, and the graph obtained by deleting them was not an
exception.

######  Lemma 4.12.

Any $3$-dicritical oriented triangle-free graph has at least 18 vertices.

We stopped at $n=17$ only because of the time needed for the enumeration of
triangle-free graphs — using a laptop, the enumeration for $n=17$ took a week.
Since we could find a decomposition with $X$ independent and $Z$ small for
each graph, we believe that our lower bound is far from optimal. It might be
possible to improve it with more computational power.

## Acknowledgements

This work was partially supported by the french Agence Nationale de la
Recherche under contract Digraphs ANR-19-CE48-0013-01 and DAGDigDec (JCJC)
ANR-21-CE48-0012 and by the group Casino/ENS Chair on Algorithmics and Machine
Learning.

## References

  * [1] Miklós Ajtai, János Komlós, and Endre Szemerédi.  A note on ramsey numbers.  Journal of Combinatorial Theory, Series A, 29(3):354–360, 1980\.
  * [2] Noga Alon, János Pach, and Jozsef Solymosi.  Ramsey-type theorems with forbidden subgraphs.  Combinatorica, 21, 04 2001.
  * [3] Colin McDiarmid Ararat Harutyunyan.  Large acyclic sets in oriented graphs.  unpublished.
  * [4] Thomas Bellitto, Nicolas Bousquet, Adam Kabela, and Théo Pierron.  The smallest 5-chromatic tournament, 2023.
  * [5] Eli Berger, Krzysztof Choromanski, and Maria Chudnovsky.  Forcing large transitive subtournaments.  J. Comb. Theory Ser. B, 112(C):1–17, may 2015.
  * [6] Eli Berger, Krzysztof Choromanski, and Maria Chudnovsky.  On the Erdős–Hajnal conjecture for six-vertex tournaments.  European Journal of Combinatorics, 75:113–122, 2019.
  * [7] Tom Bohman.  The triangle-free process.  Advances in Mathematics, 221(5):1653–1677, 2009.
  * [8] Tom Bohman and Peter Keevash.  Dynamic concentration of the triangle-free process.  Random Structures & Algorithms, 58(2):221–293, 2021.
  * [9] Ewan Davies and Freddie Illingworth.  The $\chi$-ramsey problem for triangle-free graphs.  SIAM Journal on Discrete Mathematics, 36(2):1124–1134, 2022.
  * [10] Paul Erdős.  Some remarks on chromatic graphs.  Colloquium Mathematicum, 16:253–256, 1967.
  * [11] P. Erdős and L. Moser.  On the representation of directed graphs as unions of orderings.  Magyar Tud. Akad. Mat. Kutató Int. Közl., 9:125–132, 1964.
  * [12] Paul Erdös and Andras Hajnal.  Chromatic number of finite and infinite graphs and hypergraphs.  Discrete Mathematics, 53:281–285, 1985.  Ordered Sets And Their Applications.
  * [13] Gonzalo Fiz Pontiveros, Simon Griffiths, and Robert Morris.  The triangle-free process and the ramsey number $r(3,t)$.  Memoirs of the American Mathematical Society, 263, 01 2020.
  * [14] Tilbor Gallai and Arthur Norton Milgram.  Verallgemeinerung eines graphentheoretischen satzes von rédei.  Acta Sc. Math, 21:181–186, 1960.
  * [15] Ross J. Kang and Colin McDiarmid.  The t-improper chromatic number of random graphs.  Combinatorics, Probability and Computing, 19(1):87–98, 2010.
  * [16] Jeong Han Kim.  The ramsey number r(3, t) has order of magnitude t2/log t.  Random Structures & Algorithms, 7(3):173–207, 1995.
  * [17] Bojan Mohar and Hehui Wu.  Dichromatic number and fractional chromatic number.  In Forum of Mathematics, Sigma, volume 4, page e32. Cambridge University Press, 2016.
  * [18] Michael Molloy.  The list chromatic number of graphs with small clique number.  Journal of Combinatorial Theory, Series B, 134:264–284, 2019.
  * [19] Zoltán Nagy.  Density version of the Ramsey problem and the directed Ramsey problem.  Australasian Journal of Combinatorics, 66:240–155, 01 2014.
  * [20] Victor Neumann-Lara.  The 3 and 4-dichromatic tournaments of minimum order.  Discret. Math., 135(1-3):233–243, 1994.
  * [21] Victor Neumann-Lara.  Dichromatic number, circulant tournaments and zykov sums of digraphs.  Discuss. Math. Graph Theory, 20(2):197–207, 2000.
  * [22] Lucas Picasarri-Arrieta.  Strengthening the directed Brooks’ theorem for oriented graphs and consequences on digraph redicolouring.  Journal of Graph Theory, n/a(n/a).
  * [23] Kenneth B. Reid and Ernest T. Parker.  Disproof of a conjecture of Erdös and Moser on tournaments.  Journal of Combinatorial Theory, 9(3):225 – 238, 1970.
  * [24] Adolfo Sanchez-Flores.  On tournaments free of large transitive subtournaments.  Graphs and Combinatorics, 14(2):181–200, Jun 1998.
  * [25] James B. Shearer.  A note on the independence number of triangle-free graphs.  Discrete Mathematics, 46(1):83–87, 1983.
  * [26] Joel Spencer.  Asymptotic lower bounds for ramsey functions.  Discrete Mathematics, 20:69–76, 1977.


# Analysis of size distributions of fictional characters: from Pokémon to
Godzilla

Ken Yamamoto  Department of Physics and Earth Sciences, Faculty of Science,
University of Ryukyus, Nishihara, Okinawa 903–0213, Japan

###### Abstract

In this letter, the size (height and weight) of fictional characters in
animations, superhero series, movies, and other media is studied. We find that
the distributions of character height and weight approximately follow
lognormal distributions in common to five selected works. We propose a
mechanism governing this lognormal behavior based on the principle of maximum
entropy and the Weber-Fechner law. Moreover, we provide a comparison to the
size distributions of real animals. Although the size distributions of
fictional characters and real animals are both lognormal, the distributions
are essentially different, particularly in the scaling between height and
weight.

Size distribution is an important tool in analyzing complex systems. We can
compute size distributions simply by collecting and organizing data. In
general, obtaining precise microscopic dynamics in complex systems is
difficult, and an effective approach for it is a phenomenological description
[1, 2]. The properties of size distributions is useful in constructing
phenomenological models. In many cases, size distributions follow heavy-tailed
probability distributions whose decay in the tail is slower than the
exponential functions; thus, the mean, variance, or higher moments diverge
[3]. The emergence of heavy-tailed distributions indicates the existence of
elements much larger than the ones of typical size. Further, numerous
theoretical mechanisms have been proposed to obtain heavy-tailed
distributions, such as power-law and lognormal distributions [4, 5].

Generally, the size of the biological organisms typically follows lognormal
distribution [6, 7, 8, 9]. This is a heavy-tailed distribution where the
logarithm of the size is distributed normally [10]. Theoretically, the
lognormal behavior of organisms is simply explained by the multiplicative
stochastic process

$X_{t+1}=R_{t}X_{t},$ (1)

where $R_{t}$ is a random growth rate. In the simplest case, when
$R_{1},R_{2},\ldots$ are independently and identically distributed, $\ln
X_{t}$ approximately follows a normal distribution for sufficiently large $t$
(because of the central limit theorem), and $X_{t}$ follows a lognormal
distribution. This model for the lognormal distribution dates back to
Kolmogorov [11].

In this study, we analyzed the sizes (height and weight) of fictional
creatures, instead of real organisms. They are characters in creations such as
animations, movies, and comics whose sizes are arbitrarily determined by their
designers. Nevertheless, we find that size distributions for different works
exhibit a common lognormal behavior. (A preliminary result was already
reported [12].) We propose a simple mechanism that produces this lognormal
distribution based on the principle of maximum entropy and the Weber-Fechner
law regarding the perception of numbers. Moreover, we investigate the
similarities and differences between fictional characters and real animals
from the perspective of size distribution.

To analyze the size distribution, it is desirable to select works in which the
sizes of a large number of characters are officially determined. We analyze
the following five groups of characters:

  1. 1.

Pokémon (creatures) from the Pokémon series (video games, animations, and
other media)

  2. 2.

Zords (robots and vehicles) from the Power Rangers series (American superhero
television series)

  3. 3.

Giant monsters from the Godzilla series (Japanese movie series),

  4. 4.

Villains (giant monsters and alien invaders) from the Ultraman series
(Japanese superhero television series)

  5. 5.

Characters from the Dragon Ball series (Japanese comics and animations of
martial arts experts and alien warriors).

We obtained the sizes of Pokémon creatures from the online official database
Pokédex [13] (up to Generation VII), the sizes of Zords from the online
database RangerWiki [14] (up to the 25th season, entitled Super Ninja Steel),
and the sizes of characters in Dragon Ball from the online database Dragon
Ball Wiki [15] in March 2019. We referred to Japanese books [16, 17] to obtain
the character sizes in Godzilla (including 29 movie titles from 1954 to 2016)
and Ultraman (Showa Ultraman series aired in Japan from 1966 to 1981). We only
analyzed characters whose height and weight were both provided.

a b

Figure 1:  (Color online) Cumulative height (a) and weight (b) distributions
of Pokémon (circles), Zords in Power Rangers (squares), Godzilla monsters
(upper triangles), Ultraman villains (lower triangles), and Dragon Ball
characters (diamonds). The curves present a lognormal fit for each group of
characters.

Figure 1 shows the height (a) and weight (b) distributions in cumulative form.
Each curve is a lognormal distribution:

$F(x)=\frac{N}{2}\left(1-\operatorname{erf}\left(\frac{\ln
x-\mu}{\sqrt{2}\sigma}\right)\right),$

where $N$ is the number of characters, $\operatorname{erf}$ is the Gauss error
function, and $\mu$ and $\sigma$ are parameters. The values of $N$, $\mu$ and
$\sigma$ are listed in Table Analysis of size distributions of fictional
characters: from Pokémon to Godzilla. The height and weight distributions are
both consistent with a lognormal distribution. As shown in Fig. 1 a,
approximately ten of the tallest characters in Pokémon (circles), Power
Rangers (squares), and Ultraman (lower triangles) deviate from the lognormal
distribution. In Fig. 1 b, only the heaviest character in Godzilla (the
rightmost upper triangle), SpaceGodzilla Flying Form with a weight of
$720\,000\text{\,}\mathrm{t}\mathrm{o}\mathrm{n}\mathrm{s}$ [16], deviates
greatly from the lognormal curve.

Table 1: The number $N$ of characters and the lognormal parameters $\mu$ and
$\sigma$ for the height and weight distributions in each work.

|  | Height | Weight
---|---|---|---
Title | $N$ | $\mu_{\mathrm{H}}$ | $\sigma_{\mathrm{H}}$ | $\mu_{\mathrm{W}}$ | $\sigma_{\mathrm{W}}$
Pokémon | $927$ | $-0.05$ | $0.74$ | $3.34$ | $1.40$
Power Rangers | $502$ | $3.80$ | $0.52$ | $14.48$ | $1.15$
Godzilla | $122$ | $3.89$ | $0.69$ | $16.97$ | $0.95$
Ultraman | $369$ | $3.97$ | $0.22$ | $17.20$ | $0.54$
Dragon Ball | $58$ | $0.55$ | $0.17$ | $4.21$ | $0.52$

To investigate the lognormal distribution of character size in more detail, we
applied quantile-quantile (Q-Q) plots [18]. The $q$-quantile $Q_{q}$ (for
$0\leq q\leq 1$) of a random variable $X$ is defined by $P(X\leq Q_{q})\geq q$
and $P(X\geq Q_{q})\geq 1-q$. The Q-Q plot is a scatter plot of the data and
the corresponding theoretical quantiles of a certain reference probability
distribution (usually a normal distribution). If the points in the Q-Q plot
are linearly aligned, the data are determined to follow the reference
distribution well.

Figure 2 shows Q-Q plots for the height and weight of the characters, where
log-transformed sizes are compared with the quantiles of a normal
distribution. (Note that a normal distribution for the log-transformed size
indicates that the size is distributed lognormally.) Among all of the
characters, the weight of Zords (b2) and Ultraman villains (b4) and the height
of Godzilla monsters (a3) agree very well with a lognormal distribution. Some
of the other Q-Q plots show that a few characters deviate from the lognormal
distribution in large- or small-sized regions. These deviations have a common
tendency; large (tall or heavy) characters tend to have sizes greater than
those expected by the lognormal distribution consistently (points in Fig. 2
are above the solid diagonal lines), and small characters tend to be less than
the lognormal distribution (points are below the diagonal line). We surmise
that the size of large characters can be overstated and those of small
characters can be understated; for example, heavy-looking characters will be
given excessively heavy weights to highlight their heaviness. However, as a
whole, the character size follows a lognormal distribution, particularly in
the intermediate region.

a1 a2 a3 a4 a5
b1 b2 b3 b4 b5

Figure 2:  (Color online) Q-Q plots of the height (a) and weight (b) of
Pokémon (1), Zords (2), Godzilla monsters (3), Ultraman villains (4), and
Dragon Ball characters (5). The diagonal line in each panel indicates the
expected results for the case in which the sizes are lognormally distributed.

Here, we propose a theoretical mechanism governing the common lognormal
behavior of character sizes. We introduce a random variable $X$ for the
character size. Because the characters are fictional, their sizes are free
from physical, biological, or mechanical constraints. Instead, the character
sizes most likely reflect how humans interpret and perceive numbers.

The Weber-Fechner law states that the subjective intensity of a sensation
(e.g., vision, hearing, or touch) is proportional not to the stimulus
intensity but to its logarithm [19]. In other words, this law implies that our
mental number line has a logarithmic scale. Notably, the Weber-Fechner law
also governs our recognition of numbers [20]. Furthermore, the Weber-Fechner
law has been observed in neural [21] and mathematical [22] studies.

A well-known example of the Weber-Fechner law is the perception of musical
pitches. We perceive that the pitch interval between the musical tones by two
adjacent keys in piano is constant. However, an octave rise in pitch
corresponds to a doubling of frequency [23]. The frequency $f$ of the pitch
$n$ octave above the frequency $f_{0}$ is written as $f=2^{n}f_{0}$. Its
logarithm, $\ln f=n\ln 2+\ln f_{0}$, indicates that $\ln f$ increases at a
constant rate $\ln 2$ with the increase in $n$. Therefore, the logarithm of
frequency matches the perception of pitches, which is a manifestation of the
Weber-Fechner law.

A typical character size appears to exist for each work; for instance, the
sizes of Pokémon are similar to those of human children. Hence, in the
simplest view, the size of a character is given by this typical size with
fluctuations due to the individual differences. Combined with the Weber-
Fechner law, in which character sizes are mentally measured as $\ln X$, this
condition is expressed as

$E[\ln X]=\mu,\quad V[\ln X]=\sigma^{2},$ (2)

where $E$ and $V$ represent the average and variance, respectively, and $\mu$
and $\sigma$ are associated with the typical character size and fluctuation,
respectively.

According to the principle of maximum entropy [24], when we have no knowledge
about $X$ except for Eq. (2), the best probability density function $f(x)$ of
$X$ is given by maximizing the entropy $-\int_{0}^{\infty}f(x)\ln f(x)dx$
under constraint (2). We employ the method of Lagrange multipliers and set

$\displaystyle H[f]$ $\displaystyle=-\int_{0}^{\infty}f(x)\ln
f(x)dx-\lambda_{0}\left(\int_{0}^{\infty}f(x)dx-1\right)$
$\displaystyle\quad-\lambda_{1}\left(\int_{0}^{\infty}f(x)\ln xdx-\mu\right)$
$\displaystyle\quad-\lambda_{2}\left(\int_{0}^{\infty}f(x)(\ln
x-\mu)^{2}dx-\sigma^{2}\right).$

Multipliers $\lambda_{1}$ and $\lambda_{2}$ correspond to constraints shown in
Eq. (2), and $\lambda_{0}$ is needed for the normalization
$\int_{0}^{\infty}f(x)dx=1$. To find $f$ such that the functional $H[f]$ takes
a stationary value, we calculate

$\frac{\delta H}{\delta f}=-\ln f-1-\lambda_{0}-\lambda_{1}\ln
x-\lambda_{2}(\ln x-\mu)^{2}=0,$

which directly leads to

$f(x)=e^{-1-\lambda_{0}}\frac{1}{x}\exp\left(-\lambda_{2}(\ln
x-\mu)^{2}+(1-\lambda_{1})\ln x\right).$

The exponent of the exponential function is a quadratic of $\ln x$; thus, $f$
is a lognormal-type function. By determining the multipliers
$\lambda_{0},\lambda_{1}$, and $\lambda_{2}$, the function $f$ is found to be
the probability density of the lognormal distribution with parameters $\mu$
and $\sigma$:

$f(x)=\frac{1}{\sqrt{2\pi\sigma^{2}}x}\exp\left(-\frac{(\ln
x-\mu)^{2}}{2\sigma^{2}}\right).$

Therefore, the principle of maximum entropy combined with the Weber-Fechner
law can yield a lognormal distribution. Other mechanisms for lognormal
distributions based on the Weber-Fechner law have been proposed for the length
of user posts on the Internet [25], the length of English words and the number
of strokes in Chinese characters [26], and the size of human tumors [27].

We find that the lognormal distribution is a standard distribution for
fictional character sizes. We also note that the above conclusion of lognormal
distribution is derived from the simplest assumption. Because character sizes
are set arbitrarily, a designer can intentionally determine the character
sizes that do not follow a lognormal distribution. We believe that the
lognormal distribution is natural, in the sense that the character-size
distribution tends to be lognormal when the size is set without substantial
thought.

We compare the size distributions of fictional characters and real animals.
Figures 3 a and b show the length and weight distributions of 564 species of
mammals (circles) and 124 species of fish (squares), obtained from a visual
guide of animals [28]; we included only species for which both the length and
weight were given. Although the circle points in Fig. 3 a and b deviate
slightly from the solid lognormal fitting curves in the large-sized regions
(the author does not know why the deviation occurs), the overall distributions
can be approximated by a lognormal distribution.

a b c d

Figure 3:  (Color online) (a) Cumulative length distributions of 564 mammals
(circles) and 124 fish (squares). The solid curves are lognormal
distributions, with $\mu_{\mathrm{L}}=-0.565$ and $\sigma_{\mathrm{L}}=1.21$
for mammals and $\mu_{\mathrm{L}}=0.051$ and $\sigma_{\mathrm{L}}=0.992$ for
fish. (b) Cumulative weight distributions of mammals and fish. The lognormal
parameters are $\mu_{\mathrm{W}}=1.61$ and $\sigma_{\mathrm{W}}=3.43$ for
mammals and $\mu_{\mathrm{W}}=2.36$ and $\sigma_{\mathrm{W}}=2.76$ for fish.
(c) Correlation between the length and weight of mammals. The solid line
represents the scaling $W\propto L^{3}$ based on the principle of similitude.
(d) The length and weight of fish.

Equation (1) indicates that the lognormality of real animals of a single
species arises from the randomness in their growth. However, this equation
cannot be directly applied to the sizes of different species, as shown in Fig.
3 a and b. Similarly, the lognormal life-span distribution of invertebrates
has been reported [29]. The possibility of the existence of a multiplicative
stochastic effect in evolutionary processes is indicated as the cause of this
lognormality; however, this hypothesis has not been completely verified.
Although the principle behind the lognormal distribution in Fig. 3 a and b has
not been accurately determined, it is evident that growth and evolution are
not associated with the lognormality of fictional characters. In fact,
characters usually do not grow or age; child characters occasionally grow, but
they do not grow continuously as described by Eq. (1). Incidentally, the
“evolution” of some Pokémon does not cause a multiplicative effect, because
Pokémon can evolve, at most, only twice, which is insufficient to yield a
lognormal distribution. Therefore, although both fictional characters and real
animals exhibit lognormal size distribution, their principles of generation
are completely different.

One might assume that the lognormal behavior of fictional characters arises
from the imitation of real creatures, whose sizes are distributed lognormally;
for instance, Pikachu in Pokémon is modeled from a mouse [13]. To determine
whether this hypothesis is valid, we focus on the value of the lognormal
fitting parameter $\sigma$. Whereas
$(\sigma_{\mathrm{L}},\sigma_{\mathrm{W}})=(1.21,3.43)$ for mammals and
$(0.992,2.76)$ for fish, the values of
$(\sigma_{\mathrm{H}},\sigma_{\mathrm{W}})$ for fictional characters are much
smaller (see Table Analysis of size distributions of fictional characters:
from Pokémon to Godzilla). (Note that $\sigma_{\mathrm{H}}$ for character
height is the counterpart of $\sigma_{\mathrm{L}}$ for animal length because
height and length have linear dimensions.) By comparing the parameter
$\sigma$, the lognormality of characters is found to be independent of the
size of real creatures.

The difference between the size of fictional characters and that of real
animals is further clarified by the correlation between their weight and
height (or length). If animals had a homothetic body shape and a constant
density, their weight $W$ and length $L$ would satisfy $W\propto L^{3}$, known
as the principle of similitude [30]. As shown in Fig. 3 c and d, the scatter
plots of the length and weight for mammals and fish are both consistent with
the principle of similitude (solid lines). Taking the logarithm, we have $\ln
W=3\ln L+\text{constant}$. Because the parameters $\sigma_{L}$ and
$\sigma_{W}$ of the lognormal distribution represent the standard deviations
of $\ln L$ and $\ln W$, respectively, we have
$\sigma_{\mathrm{W}}=3\sigma_{\mathrm{L}}$. In other words, the ratio
$\sigma_{\mathrm{W}}/\sigma_{\mathrm{L}}$ is a good estimate for the
dimensionality of animals. Indeed, for the data in Fig. 3,
$\sigma_{\mathrm{W}}/\sigma_{\mathrm{L}}=2.86$ for mammals and
$\sigma_{\mathrm{W}}/\sigma_{\mathrm{L}}=2.78$ for fish, which are both close
to three.

a b c d e

Figure 4:  (Color online) Scatter plots of the height and weight of Pokémon
(a), Zords (b), Godzilla monsters (c), Ultraman villains (d), and Dragon Ball
characters (e). The solid line in each panel is based on the principle of
similitude, $W\propto H^{3}$.

Scatter plots for the height $H$ and weight $W$ of characters are shown in
Fig. 4. Only the Dragon Ball characters (e) follow the scaling $W\propto
H^{3}$ ($\sigma_{\mathrm{W}}/\sigma_{\mathrm{H}}=3.06$). We believe that
Dragon Ball characters can easily be assigned realistic height and weight,
because many of the characters are humans or human-shaped aliens. The other
plots, a–d, exhibit a roughly positive correlation, but the fluctuations are
large compared with those of mammals and fish, as shown in Fig. 3 c and d.
Thus, small but heavy characters and large but light characters are included.
The most extreme character is Cosmoem in Pokémon [13], which is
$0.1\text{\,}\mathrm{m}$ tall but $999.9\text{\,}\mathrm{kg}$ heavy. Such
unrealistic combinations of height and weight may help emphasize the
peculiarity of a character. The estimated
$\sigma_{\mathrm{W}}/\sigma_{\mathrm{H}}$ of dimensionality is considerably
smaller than three (close to two), in contrast to the finding for real
animals.

In summary, the height and weight of fictional characters in animations,
movies, and other media approximately follow a lognormal distribution, even
though character sizes are set arbitrarily for each work and are not
associated with the size of real animals. In this letter, we propose that this
lognormal behavior can be explained by entropy maximization under the
constraints where mean and variance of the size, determined by applying the
Weber-Fechner law, are fixed. This study implies that statistical regularity
and commonality arise from the process of perception and generation of numbers
by humans. We expect this work to motivate further studies on the complex
thought process and behavior of humans.

The present study was supported by the Hayao Nakayama Foundation for Science &
Technology and Culture (H29-B-41) and by a Grant-in-Aid for Scientific
Research (C) (19K03656) from the Japan Society for the Promotion of Science.

## References

  * [1] C. Castellano, Rev. Mod. Phys. 81, 591 (2009).
  * [2] M. Buchanan, Ubiquity (Weidenfeld and Nicolson, London, 2000).
  * [3] S. Foss, D. Korshunov, and S. Zachary, An Introduction to Heavy-Tailed and Subexponential Distributions (Springer, New York, 2011).
  * [4] M. Mitzenmacher, Internet Math. 1, 226 (2004).
  * [5] M. E. J. Newman, Contemp. Phys. 46, 323 (2005).
  * [6] A. L. Koch, J. Theor. Biol. 12, 276 (1966).
  * [7] E. Limpert, W. A. Stahel, and M. Abbt, BioScience 51, 341 (2001).
  * [8] K. Yamamoto and J. Wakita, J. Phys, Soc. Jpn. 85, 074004 (2016).
  * [9] K. Koyama, K. Yamamoto, and M. Ushio, Proc. R. Soc. B 284, 20162395 (2017).
  * [10] N. Kobayashi, H. Kuninaka, J. Wakita, and M. Matsushita, J. Phys. Soc. Jpn. 80, 072001 (2011).
  * [11] A. N. Kolmogorov, Dokl. Akad. Nauk. 31, 99 (1941).
  * [12] K. Yamamoto, JPS Conf. Proc. 16, 011015 (2017).
  * [13] Pokédex https://www.pokemon.com/us/pokedex/
  * [14] RangerWiki https://powerrangers.fandom.com/wiki/RangerWiki
  * [15] Dragon Ball Wiki https://dragonball.fandom.com/wiki/Main_Page
  * [16] Kodansha (ed.), Ketteiban Godzilla DaiKaijuu Perfect Chou Hyakka (Kodansha, Tokyo, 2016). [in Japanese]
  * [17] Kodansha (ed.), Ketteiban Zen Ultra Kaijuu Kanzen Chou Hyakka (Kodansha, Tokyo, 2005). [in Japanese]
  * [18] H. C. Thode, Jr., Testing for Normality (Marcel Dekker, New York, 2002).
  * [19] E. Maor, e: The Story of a Number (Princeton University Press, Princeton, New Jersey, 2011).
  * [20] S. Dehaene, The Number Sense (Oxford University Press, Oxford, 2011).
  * [21] S. Dehaene, Trends in Cognitive Sciences 4, 145 (2003).
  * [22] R. D. Portugal and B. F. Svaiter, Minds and Machines 21, 73 (2011).
  * [23] E. Agmon, The Languages of Western Tonality (Springer, Berlin, 2013).
  * [24] E. T. Jaynes, Probability Theory: The Logic of Science (Cambridge University Press, Cambridge, 2003).
  * [25] P. Sobkowicz, M. Thelwall, K. Buckley, G. Paltoglou, and A. Sobkowicz, EPJ Data Sci. 2, 2 (2013).
  * [26] J. Huang, PLoS One 8, e74515 (2013).
  * [27] J. S. Spratt, Jr., J. Surg. Res. 9, 151-157 (1969).
  * [28] D. E. Wilson and D. Burnie, Animal: The Definitive Visual Guide to the World’s Wildlife (Dorling Kindersley, London, 2001).
  * [29] N. Kobayashi, Y. Sasaki, O. Moriyama, S. Matsushita, and M. Matsushita, Nonlinear Phenomena in Complex Systems 9, 276 (2006).
  * [30] D. Thompson, On Growth and Form (Cambridge University Press, Cambridge, 1961).


verification (see Table II) can further reduce the labeling error and ensure
the effectiveness of SATA.

Next, we discuss the potential annotation bias regarding SATA due to using an
off-the-shelf deep tracking model (i.e., SiamRPN++ [9]). The assumption for
semi-automatic labeling is that within a short segment, the changes in the
target itself (e.g., appearance, size, scale, and motion) and the surrounding
environment (e.g., illumination and background) are relatively small; current
advanced trackers, such as [9], can achieve accurate target tracking. Based on
the above assumption, we make some efforts to reduce the potential bias of
automatic tracking.

First, the proposed interactive semi-automatic annotation pipeline SATA allows
the annotator to divide the video sequence into multiple short segments in a
human-computer interaction manner. Therefore, the annotator can use the
tracker to generate accurate bounding boxes in each short segment
automatically. When low-quality tracking results appear, the annotator can
conveniently re-select the starting point for semi-automatic labeling. Second,
[9] is a powerful deep tracking model with good adaptability to target size,
appearance changes, etc. In short segments, it can achieve stable and accurate
tracking. Since the tracking speed of [9] is fast, it helps us improve the
annotation speed. However, in some complex situations (e.g., long-term
occlusion, fast motion, and similar distractors), we still need to perform a
manual intervention to reduce the labeling bias. Third, to further reduce the
labeling bias, we design a strict quality control process (see Table II) for
the whole data construction, including data annotation and verification.

TABLE C:  Performance comparison on WebUAV-3M test set between tracking via joint natural language and bounding box (NL+BBox), and tracking via bounding box only (BBox). We report the results of the latest state-of-the-art vision-language trackers (VLTSCAR and VLTTT) and their corresponding baseline visual trackers (SiamCAR and TransT). Type | Tracker | Publication | Pre | nPre | AUC | cAUC | mAcc
---|---|---|---|---|---|---|---
Tracking via BBox | SiamCAR [68] | CVPR-2020 | 0.642 | 0.512 | 0.412 | 0.378 | 0.415
TransT [82] | CVPR-2021 | 0.618 | 0.509 | 0.448 | 0.422 | 0.453
Tracking via NL+BBox | VLTSCAR-IV-got10k [96] | NeurIPS-2022 | 0.501 | 0.386 | 0.358 | 0.345 | 0.361
VLTSCAR-III-lasotext [96] | NeurIPS-2022 | 0.584 | 0.475 | 0.431 | 0.420 | 0.435
VLTSCAR-II-lasot-tnl2k [96] | NeurIPS-2022 | 0.594 | 0.480 | 0.440 | 0.428 | 0.444
VLTSCAR-I-otb99 [96] | NeurIPS-2022 | 0.600 | 0.490 | 0.449 | 0.438 | 0.453
VLTTT-IV-lasotext [96] | NeurIPS-2022 | 0.520 | 0.406 | 0.384 | 0.371 | 0.385
VLTTT-III-got10k [96] | NeurIPS-2022 | 0.531 | 0.414 | 0.388 | 0.375 | 0.390
VLTTT-II-lasot-otb99 [96] | NeurIPS-2022 | 0.620 | 0.503 | 0.466 | 0.457 | 0.472
VLTTT-I-tnl2k [96] | NeurIPS-2022 | 0.638 | 0.511 | 0.470 | 0.460 | 0.475

(a)

(b)

(c)

(d)

Figure D: Benchmark results of 43 baseline trackers on WebUAV-3M test set
using a precision plot, normalized precision plot, success plot, and complete
success plot. Best viewed by zooming in.

##  C Additional Results

###  C.1 Results of Tracking by Joint Language and Bounding Box

To advance research on multi-modal tracking, we evaluate two recent vision-
language trackers (VLTSCAR [96] and VLTTT [96]) and their baseline visual
trackers (SiamCAR and TransT) on the WebUAV-3M test set. In [96], Guo et al.
propose to learn adaptive vision-language representations using modality mixer
and asymmetrical ConvNet search. They first use the training splits of COCO,
ImageNet VID, ImageNet DET, Youtube-BB, GOT-10k, LaSOT, and TNL2K to search a
modeling structure for vision-language tracking with a supernet [96]. Then,
they follow the training strategy of the baselines SiamCAR and TransT to
optimize VLTSCAR and VLTTT, respectively. In the process of optimization, the
language embeddings of the datasets (i.e., COCO, ImageNet VID, ImageNet DET,
and Youtube-BB) without language annotations are replaced by 0-tensors or
pooled visual features. For more details about VLTSCAR and VLTTT, we kindly
refer readers to [96] and their project
page333https://github.com/JudasDie/SOTS. In Table C, we comprehensively
evaluate 8 tracking models (i.e., VLTSCAR-I-otb99, VLTSCAR-II-lasot-tnl2k,
VLTSCAR-III-lasotext, VLTSCAR-IV-got10k, VLTTT-I-tnl2k, VLTTT-II-lasot-otb99,
VLTTT-III-got10k, and VLTTT-IV-lasotext) on the WebUAV-3M test set using the
pretrained network weights provided by the original authors.

We have the following three observations. First, comparing SiamCAR with
TransT, the Siamese network-based tracker (SiamCAR) is more accurate for the
target center prediction (higher Pre and nPre scores), but the CNN-
Transformer-based tracker (TransT) can achieve better target state estimation
(higher AUC, cAUC, and mAcc scores). Second, adding natural language
annotations does not always improve tracking performance. For example, the
improved version VLTTT-I-tnl2k outperformers the baseline TransT by $2.0\%$,
$0.2\%$, $2.2\%$, $3.8\%$, and $2.2\%$ in terms of Pre, nPre, AUC, cAUC, and
mAcc scores, respectively. While the tracking performance of the advanced
VLTSCAR-I-otb99 degrades (e.g., $0.642\\!\rightarrow\\!0.600$ and
$0.512\\!\rightarrow\\!0.490$ in terms of Pre and nPre scores, respectively).
We argue that the high-level semantics in natural language can provide
auxiliary help for tracking, but vision-language trackers can hardly benefit
from limited multi-modal data. This motivates us to construct the large-scale
dataset WebUAV-3M with visual box annotations, natural language
specifications, and audio descriptions. Third, the performance of recent
vision-language trackers falls far behind the state-of-the-art visual trackers
(see Table V and Table C). For example on our WebUAV-3M test set, the gaps
between the most advanced vision-language tracker (VLTTT-I-tnl2k) and the
visual tracker (AlphaRefine) are absolute $11.5\%$, $13.2\%$, $12.3\%$,
$10.2\%$, and $12.7\%$ in terms of Pre, nPre, AUC, cAUC, and mAcc scores,
respectively. Therefore, we propose the large-scale multi-modal dataset
WebUAV-3M and expect that the community will pay more attention to vision-
language tracking.

###  C.2 Overall Performance

The precision, normalized precision, success, and complete success curves of
all baseline trackers are shown in Fig. D, ranked by the Pre, nPre, AUC, and
cAUC scores, respectively. Note that SiamRPNpp and SiamFCpp refer to SiamRPN++
and SiamFC++, respectively.

###  C.3 Attribute-Based Performance

From Fig. E, we find that AlphaRefine and KeepTrack rank in the top two for
all 17 attributes, which is consistent with the results obtained on the entire
test set. The performance of RPT improves on the LR subset, where its ranking
increases by one place (from 4th to 3rd) compared to its ranking on the whole
test set. In fact, the tracker can easily drift in LR videos due to its
ineffective representations of small targets. We argue that the feature
degradation caused by low resolution may be enhanced by a more refined
representation with a set of learned representative points, leading to better
performance. For videos with PO, FO, OV, FM, CM, and VC, the trackers are
prone to losing the target because most of the existing trackers usually
perform localization based on a small local region. To address these
challenging factors, state-of-the-art deep trackers have introduced some
practical solutions, such as extracting and maintaining as much detailed
spatial information as possible (e.g., AlphaRefine), keeping track of
distractor objects to continue tracking the target of interest (e.g.,
KeepTrack), predicting the conditional probability density of the target state
given an input image (e.g., PrDiMP), combining templates and searching region
features using attention (e.g., TransT). On the subsets with ROT, DEF, SV, and
ARV, AlphaRefine, KeepTrack, and PrDiMP have significant advantages over
STRCF, ECO, and AutoTrack. This result demonstrates that the target-specific
features learned by the intersection-over-union network (IoU-Net) increase the
accuracy of target estimation over that of classic multiscale search methods.
Trackers are more likely to drift on subsets with BC, IV, and MB due to the
presence of more minor discriminative representation features between the
target and background distractors. A practical solution for alleviating this
issue is to exploit both target and background appearance information to
achieve enhanced discriminability (e.g., PrDiMP). In addition, we observe that
the brutal, small-sized, big-sized, and long videos are challenging for
current deep trackers, causing all the baseline trackers to exhibit
significant performance degradations.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

(n)

(o)

(p)

(q)

(r)

(s)

(t)

(u)

(v)

(w)

Figure E: Performance of 43 baseline trackers in terms of 17 attributes (shown
using a complete success plot). For clarity, only the top 21 trackers are
shown. Best viewed by zooming in.

###  C.4 More Qualitative Results

To qualitatively analyze different methods, we demonstrate the visual tracking
results of seven state-of-the-art deep trackers (i.e., SiamRPN++, Ocean, DiMP,
AlphaRefine, TrDiMP, TransT, and KeepTrack) in six complex scenario challenges
(i.e., long-term occlusion, target distortions, dual-dynamic disturbances,
small targets, high-speed motion, and low light). From Fig. F, we observe that
none of these deep trackers can track the target in each frame in all
scenarios, suggesting that tracking in real-world application scenarios is
challenging and has still not been completely solved.

Figure F: Illustration of the qualitative evaluation results obtained in six
hard scenario challenges: minivan$\\_$37 with long-term occlusion,
motorboat$\\_$31 with dual-dynamic disturbances, running$\\_$20 with high-
speed motion, pagoda$\\_$29 with target distortions, sheepdog$\\_$2 with small
targets and suv$\\_$66 with low light. Best viewed by zooming in.