E}\frac{2}{k^{2}(k-1)^{2}}\log\left(\frac{\frac{1}{k^{2}}\cdot\frac{1}{k^{2}}}{2\cdot\frac{2}{k^{2}(k-1)^{2}}}\right)=\log
k^{2}+d\log\left(\frac{1}{2}\left(1-\frac{1}{k}\right)\right),$

we have

$\displaystyle\mathbf{E}Y^{2}$ $\displaystyle=\sum_{A\text{
s.t.}\eqref{eq:Acons},\ B\text{ s.t.}\eqref{eq:Bcons}}p(A,B,n)e^{nf(A,B)}$
$\displaystyle=\sum_{\ell\in(\Lambda+\ell_{n})\cap nK}a_{n}(\ell)$
$\displaystyle\leq h_{d,k}(2\pi n)^{r/2}\psi(z_{0})b_{n}e^{n\phi(z_{0})}$
$\displaystyle=C_{d,k}\cdot
k^{k}\left(\frac{k-1}{2\pi(k-2)}\right)^{(k-1)}n^{-(k-1)}k^{2n}\left(\frac{1}{2}\left(1-\frac{1}{k}\right)\right)^{dn}$
$\displaystyle=C_{d,k}(\mathbf{E}Y)^{2}$ (38)

where $C_{d,k}$ is some positive constant depending on $d$ and $k$. ∎

We conclude this section by proving the following proposition.

######
Proposition 5.14.

For $k\geq 3$ such that a doubly regular tournament exists on $k$ vertices and
$d<\ell_{k}$, with positive probability
${\chi_{o}}(\vec{\mathcal{C}}(n,d))\leq k$.

###### Proof.

By the Paley-Zygmund inequality,

$\mathbf{Pr}[Y>0]>\frac{(\mathbf{E}Y)^{2}}{\mathbf{E}(Y^{2})}\sim\frac{(\mathbf{E}Y)^{2}}{C_{d,k}(\mathbf{E}Y)^{2}}=\frac{1}{C_{d,k}}>0$

and thus with positive probability there exists a $T_{k}$-colouring of
$\vec{\mathcal{C}}(n,d)$ and therefore ${\chi_{o}}(\vec{\mathcal{C}}(n,d))\leq
k$. ∎

##  6 Range of Possible Values of the Oriented Chromatic Number

In this section, we adapt an argument of Łuczak [37] who proved that for every
$p=\frac{d}{n}$ with $d<n^{1/6-\varepsilon}$, the chromatic number of
$\mathcal{G}(n,p)$ is concentrated in an interval of length two. (We note that
our adaptation is closely based on that of Achlioptas and Moore [2].) We prove
a weaker result for $\vec{\mathcal{C}}(n,d)$ and $\vec{\mathcal{M}}(n,m=cn)$,
showing that a.a.s. their chromatic numbers are concentrated in an interval of
length linear in the number of colours.

We start with a result regarding the oriented chromatic number of sparse
digraphs.

######
Lemma 6.1 ([10, Theorem 1]).

Let $\vec{G}$ be directed graph with the property that any subgraph of
$\vec{G}$ has average degree strictly smaller than three. Then
$\chi_{o}(\vec{G})\leq 11$.

Now we argue that a.a.s. subgraphs of $\vec{\mathcal{C}}(n,d)$ of sub-linear
size are sparse.

######
Lemma 6.2.

For any $0<\varepsilon<\frac{1}{2}$ and constant $d$, with high probability
every subgraph of $\vec{C}\sim\vec{\mathcal{C}}(n,d)$ induced by $s\leq
e^{-5}d^{-3}n^{1-\varepsilon}$ vertices contains at most
$(\frac{3}{2}-\varepsilon)s$ edges.

It should be noted that it is possible to prove a stronger version of Lemma
6.2 where $d$ is allowed to grow bounded by a function of $n$ rather than
being constant; however, this simpler version meets our current needs.

###### Proof.

Let $\vec{C}\sim\vec{\mathcal{C}}(n,d)$ and let $S\subseteq V(\vec{C})$ such
that $|S|=s$. Let $v\in S$ and $(u,v)\in E(\vec{C})$. The probability $u\in S$
is at most $\frac{s}{n}$. Thus

$\mathbf{Pr}[\text{$S$ has at least $k$
edges}]\leq\binom{ds}{k}\left(\frac{s}{n}\right)^{k}$

and

$\mathbf{Pr}[\text{There exists a set $S$ with at least $k$
edges}]\leq\binom{n}{s}\binom{ds}{k}\left(\frac{s}{n}\right)^{k}.$

Using $k=\frac{3}{2}-\varepsilon,1\leq s\leq e^{-5}d^{-3}n^{1-\varepsilon}$,
and $0<\varepsilon<\frac{1}{2}$ we get

$\binom{n}{s}\binom{ds}{k}\left(\frac{s}{n}\right)^{k}<\frac{de^{2}}{n^{\varepsilon(\frac{1}{2}-\varepsilon)}}=o(1)$

as $\varepsilon(\frac{1}{2}-\varepsilon)>0$ for $0<\varepsilon<\frac{1}{2}$.
Therefore the probability such a set $S$ exists approaches zero as $n$
approaches infinity. ∎

Next we appeal to a martingale result of Wormald on undirected configurations.

######
Theorem 6.3 ([55, Theorem 2.19]).

Given an undirected configuration $C$, we define a _switching_ in $C$ to be
the replacement of two edges $\\{v_{1},v_{2}\\}$, $\\{v_{3},v_{4}\\}$ by the
edges $\\{v_{1},v_{3}\\}$ and $\\{v_{2},v_{4}\\}$ or by the edges
$\\{v_{1},v_{4}\\}$ and $\\{v_{3},v_{2}\\}$. Let $X_{n}$ be a random variable
defined on $\mathcal{C}(n,d)$ such that for any configurations $C,C^{\prime}$
that differ by a switching

$|X_{n}(C)-X_{n}(C^{\prime})|\leq b$

for some constant $b>0$. Then for every $t>0$,

$\mathbf{Pr}[X_{n}\leq\mathbf{E}[X_{n}]-t]\leq\exp\left(\frac{-t^{2}}{dnb^{2}}\right)\quad\text{and}\quad\mathbf{Pr}[X_{n}\geq\mathbf{E}[X_{n}]+t]\leq\exp\left(\frac{-t^{2}}{dnb^{2}}\right).$

As long as the value $b$ does not depend on the orientations chosen for the
new edges, we can extend Wormald’s result to directed configurations by
“forgetting” the orientations, applying the result, and then reorienting the
edges, including assigning new orientations to the new edges.

Our next step is to prove that as soon as there is some small probability that
$k$ colours are sufficient to colour $\vec{C}\sim\vec{\mathcal{C}}(n,d)$, we
can almost surely $k$-colour all but a small number of vertices.

######
Lemma 6.4 ([2, Lemma 2]).

For a given function $\omega(n)$, let $k=k(n,d,\omega(n))$ be the smallest $k$
such that

$\mathbf{Pr}[{\chi_{o}}(\vec{\mathcal{C}}(n,d))\leq k]\geq 1/\omega(n).$

With probability greater than $1-1/\omega(n)$, all but
$8\sqrt{nd\log\omega(n)}$ vertices of $\vec{\mathcal{C}}(n,d)$ can be properly
oriented-coloured using $k$ colours.

###### Proof.

For $\vec{C}\sim\vec{\mathcal{C}}(n,d)$, let $Y_{j}(\vec{C})$ be the minimal
size of a set of vertices $S$ such that $\vec{C}-S$ is $j$-oriented-
colourable. For any $j$ and $\vec{C}$, switching two arcs of $\vec{C}$ can
affect $Y_{j}(\vec{C})$ by at most 4 as, in the worst case, we can add all
four vertices to $S$ and still $j$-oriented-colour $\vec{C}-S$. By Theorem
6.3, with $\mu_{j}=\mathbf{E}[Y_{j}(\vec{\mathcal{C}}(n,d))]$,

$\mathbf{Pr}[Y_{j}\leq\mu_{j}-\lambda\sqrt{n}]<e^{-\frac{\lambda^{2}}{16d}}\quad\text{and}\quad\mathbf{Pr}[Y_{j}\geq\mu_{j}+\lambda\sqrt{n}]<e^{-\frac{\lambda^{2}}{16d}}.$

Choose $\lambda=\lambda(n)=4\sqrt{d\log\omega(n)}$ so that
$e^{-\frac{\lambda^{2}}{16d}}=\frac{1}{\omega(n)}$. Then, recalling the
definition of $k$,

$\mathbf{Pr}[Y_{k}\leq\mu_{k}-\lambda\sqrt{n}]<\frac{1}{\omega(n)}\leq\mathbf{Pr}[{\chi_{o}}(\vec{C})\leq
k]=\mathbf{Pr}[Y_{k}=0].$

If $\mu_{k}\geq\lambda\sqrt{n}$, then the event $Y_{k}=0$ implies the event
$Y_{k}\leq\mu_{k}-\lambda\sqrt{n}$; since we have
$\mathbf{Pr}[Y_{k}\leq\mu_{k}-\lambda\sqrt{n}]<\mathbf{Pr}[Y_{k}=0]$, this
must not be the case and instead we must have $\mu_{k}<\lambda\sqrt{n}$.
Therefore

$\frac{1}{\omega(n)}=e^{-\frac{\lambda^{2}}{16d}}>\mathbf{Pr}[Y_{k}\geq\mu_{k}+\lambda\sqrt{n}]\geq\mathbf{Pr}[Y_{k}\geq
2\lambda\sqrt{n}]$

which completes the proof. ∎

Finally, we prove that the oriented chromatic number of
$\vec{\mathcal{C}}(n,d)$ is concentrated in an interval of length linear in
the number of colours.

######
Proposition 6.5.

For every integer $d$, there exists an integer $k=k(d)$ such that a.a.s.

${\chi_{o}}(\vec{\mathcal{C}}(n,d))\in[k,3k+11].$

###### Proof.

Let $d$ be given and let $k=k(d,n)$ be the smallest integer for which the
probability that $\vec{\mathcal{C}}(n,d)$ is $k$-colourable is at least
$1/\log\log n$. Fix $\vec{C}\sim\vec{\mathcal{C}}(n,d)$. By Lemma 6.4, with
high probability there exists a set of vertices $S$ such that $\vec{C}-S$ can
be $k$-oriented-coloured and $|S|<8\sqrt{nd\log\log\log n}<\sqrt{nd}\log
n\equiv s_{0}$. From $S$, we will construct an increasing sequence of sets of
vertices $\\{U_{i}\\}$ as follows. $U_{0}=S$; for $i\geq 0,U_{i+1}=U_{i}\cup
W$, where either $W=\\{w_{1},w_{2}\\}$ for some $w_{1},w_{2}\notin U_{i}$
which are adjacent and each of which has some neighbour in $U_{i}$ or
$W=\\{w\\}$ for some $w\notin U_{i}$ for which there are $u_{1},u_{2}\in
U_{i}$ such that $(u_{1},w)$ and $(w,u_{2})$ are arcs in $\vec{C}$. The
construction ends, with $U_{t}$, when no such pair exists.

Define $N=\\{v\in\vec{G}:v\notin U_{t}\ \text{and}\ \exists u\in U_{t}\
\text{such that}\ u\sim v\\}$ to be the neighbourhood of $U_{t}$ in the rest
of the graph. Note that $N$ is an independent set; if $v_{1},v_{2}\in N$ and
$v_{1}\sim v_{2}$, then we could have continued in the construction with
$U_{t+1}=U_{t}\cup\\{v_{1},v_{2}\\}$. Furthermore, $N=N_{I}\cup N_{O}$ where
each edge is directed from $U_{t}$ into $N_{I}$ and each edge is directed from
$N_{O}$ out to $U_{t}$; if some $v\in N$ satisfies neither of these
constraints, then there are $u_{1},u_{2}\in U_{t}$ such that $(u_{1},v)$ and
$(v,u_{2})$ are arcs of $\vec{C}$ and we could have continued the construction
with $U_{t+1}=U_{t}\cup\\{v\\}$.

We claim we can properly $11$-oriented-colour $U_{t}$ with high probability.
Set $\varepsilon=0.1$ and let $n$ be large enough so that

$\frac{s_{0}(1+2\log n)}{s_{0}(1+2\log
n)+2}>1-\frac{\varepsilon}{3},\quad\frac{3\log n}{1+2\log
n}>\frac{3}{2}-\frac{\varepsilon}{2},$

and that $n^{1/2-\varepsilon}>3e^{5}d^{7/2}(\log n)^{2}$. It suffices to show
that $|U_{t}|<s_{0}(1+2\log n)$: then

$s_{0}(1+2\log n)=\sqrt{nd}\log n(1+2\log n)\leq 3\sqrt{nd}(\log n)^{2}\leq
e^{-5}d^{-3}n^{1-\varepsilon}$

so Lemma 6.2 ensures the condition of Lemma 6.1.

Assume for contradiction that $|U_{t}|\geq s_{0}(1+2\log n)$ and let
$i^{\ast}$ be the first step at which $|U_{i^{\ast}}|\geq s_{0}(1+2\log n)$.
Because $|U_{0}|=s_{0}$, at least $2s_{0}\log n$ vertices have been added. At
step $i^{\ast}$ we added at most two vertices to $U_{i^{\ast}-1}$, and
therefore $|U_{i^{\ast}}|\leq s_{0}(1+2\log n)+2$. Note that in steps in which
two vertices are added to $U_{i}$, three edges are added, and in steps in
which one vertex is added, we add two edges to $U_{i}$. Thus each vertex added
to $U_{i^{\ast}}$ also added at least $\frac{3}{2}$ edges to $U_{i^{\ast}}$,
from which we conclude $U_{i^{\ast}}$ contains at least
$\frac{3}{2}(2s_{0}\log n)=3s_{0}\log n$ edges. But then

$e(U_{i^{\ast}})=3s_{0}\log n=(s_{0}(1+2\log n)+2)\cdot\frac{s_{0}(1+2\log
n)}{s_{0}(1+2\log n)+2}\cdot\frac{3\log n}{1+2\log
n}>|U_{i^{\ast}}|(1-\tfrac{\varepsilon}{3})(\tfrac{3}{2}-\tfrac{\varepsilon}{2})>|U_{i^{\ast}}|(\tfrac{3}{2}-\varepsilon).$

This contradicts Lemma 6.2 as

$|U_{i^{\ast}}|\leq s_{0}(1+2\log n)+2=\sqrt{nd}\log n(1+2\log n)+2\leq
3\sqrt{nd}(\log n)^{2}\leq e^{-5}d^{-3}n^{1-\varepsilon}.$

Now recall that $\vec{C}-S$ is $k$-oriented-colourable, say by
${\chi_{o}}:\vec{C}-S\to[k]$. We colour $\vec{C}$ as follows. First, for
$v\in\vec{C}-U_{t}-N$, colour $v$ with $({\chi_{o}}(v),0)$. As
$N\subseteq\vec{C}-U_{t}\subseteq\vec{C}-S$, each vertex in $N$ is also
coloured by ${\chi_{o}}$. Colour each $v\in N_{I}$ with colour
$({\chi_{o}}(v),1)$ and each $v\in N_{O}$ with colour $({\chi_{o}}(v),2)$.
Finally, use the eleven unique colours $(1,4),\ldots,(11,4)$ to colour
$U_{t}$. We claim this is a proper oriented $(3k+11)$-colouring of $\vec{C}$.
First, no adjacent vertices share a colour: $U_{t}$ is properly coloured by
Lemma 6.1, $\vec{C}-U_{t}$ is properly $k$-oriented-coloured as $\vec{C}-S$
was, and the vertices in $U_{t}$ are coloured with colours distinct from those
in $\vec{C}-U_{t}$. The only other issue would be a directed path $v_{1}\to
v_{2}\to v_{3}$ such that $v_{1}$ and $v_{3}$ receive the same colour.
Consider any directed path $v_{1}\to v_{2}\to v_{3}$. If $v_{1},v_{3}\notin
U_{t}$ then in particular they are not in $S$ and thus
${\chi_{o}}(v_{1})\neq{\chi_{o}}(v_{3})$. If exactly one of $v_{1},v_{3}\in
U_{t}$ then one is coloured with second coordinate 4 and the other is not.
Finally, if $v_{1},v_{3}\in U_{t}$ then $v_{2}\in U_{t}$ as well because
$U_{t}$ only has edges directed internally and towards $N_{I}$, but $N_{I}$
has no edges directed back towards $U_{t}$. Then $v_{1}$ and $v_{3}$ receive
different colours as $U_{t}$ was properly coloured. ∎

A version of Proposition 6.5 holds for $\vec{\mathcal{M}}(n,m)$ holds for
$m=cn,c>0$ as well.

######
Proposition 6.6.

For every $c>0$, there exists an integer $k=k(c)$ such that a.a.s.

${\chi_{o}}(\vec{\mathcal{M}}(n,m=cn))\in[k,3k+11].$

The proof of Proposition 6.6 is nearly identical to that of Proposition 6.5,
so rather than repeat each of the intermediate results, we summarize the small
changes in the proofs. In Lemma 6.2, the probability that a “bad” subset
exists is $\binom{n}{s}\binom{m}{k}(\binom{s}{2}/\binom{n}{2})^{k}$. This
probability is still less than
$(de^{2})/n^{\varepsilon(\frac{1}{2}-\varepsilon)}$, so the corresponding
result holds. Instead of appealing to Theorem 6.3, we can use Azuma’s
inequality directly by exposing the edges of the graph one at a time. This has
the effect of changing the size of the uncoloured set in Lemma 6.4 by a
constant multiple. That difference disappears in the step of the proof of
Proposition 6.5 in which we set $s_{0}=\sqrt{nd}\log n$.

##  7 Proofs of Main Theorems

######
Lemma 7.1.

For any constant $c>0$ and $m\leq cn+n^{2/3}$, the probability that
$\vec{\mathcal{M}}(n,m)$ is a simple oriented graph (without loops or multiple
edges) is at least $\exp(-5c(c+1))>0$.

###### Proof.

The probability that $\vec{M}\sim\vec{\mathcal{M}}(n,m)$ is an orientation of
a simple graph is

$\displaystyle\frac{1}{n^{2m}}\prod_{j=0}^{m-1}n(n-1)-2j$
$\displaystyle\geq\left(\frac{n^{2}-2(m+n)}{n^{2}}\right)^{m}$
$\displaystyle=\left(1-\frac{2(m+n)}{n^{2}}\right)^{m}$
$\displaystyle\geq\exp\left(-\frac{4(m+n)}{n^{2}}\cdot m\right)$ (for $n$
large enough)
$\displaystyle\geq\exp\left(-\frac{4((cn+n^{2/3}+n)(cn+n^{2/3})}{n^{2}}\right)$
$\displaystyle=\exp\left(-4c^{2}-\frac{8c}{n^{1/3}}-\frac{4}{n^{2/3}}-4c-\frac{4}{n^{1/3}}\right)$
$\displaystyle\geq\exp\left(-5c(c+1)\right).$ (for $n$ large enough)

∎

######
Corollary 7.2.

For any constant $c>0$, any event $A$ in both $\vec{\mathcal{G}}(n,p)$ and
$\vec{\mathcal{M}}(n,m)$, and any $m\leq cn+n^{2/3}$,

$\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}(n,p=\frac{d}{n})}[A\mid
e(\vec{G})=m]\leq
e^{5c(c+1)}\mathbf{Pr}_{\vec{M}\sim\vec{\mathcal{M}}(n,m)}[A].$

###### Proof.

The key idea is that $\vec{G}\sim\vec{\mathcal{G}}(n,p)$ conditioned on having
$m$ edges and $\vec{M}\sim\vec{\mathcal{M}}(n,m)$ conditioned on being simple
are both uniform over the collection of graphs of order $n$ with $m$ edges.
Thus

$\displaystyle\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}(n,p=\frac{d}{n})}[A\mid
e(\vec{G})=m]$
$\displaystyle=\mathbf{Pr}_{\vec{M}\sim\vec{\mathcal{M}}(n,m)}[A\mid\text{$\vec{M}$
is simple}]$
$\displaystyle=\frac{\mathbf{Pr}_{\vec{M}\sim\vec{\mathcal{M}}(n,m)}[A\text{
and $\vec{M}$ is
simple}]}{\mathbf{Pr}_{\vec{M}\sim\vec{\mathcal{M}}(n,m)}[\text{$\vec{M}$ is
simple}]}$ $\displaystyle\leq
e^{5c(c+1)}\mathbf{Pr}_{\vec{M}\sim\vec{\mathcal{M}}(n,m)}[A]$
$\displaystyle\text{Lemma~{}\ref{lem:gnm_simple}}.$

∎

######
Lemma 7.3.

For any constant $d>0$, the number of edges of
$\vec{G}\sim\vec{\mathcal{G}}(n,p=\frac{d}{n})$ satisfies

$\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}(n,p=\frac{d}{n})}[|e(\vec{G})-dn/2|\geq
n^{2/3}]\leq 2\exp\left(-\frac{n^{1/3}}{4d}\right)=o(1).$

###### Proof.

Set $c=d/2$. By standard concentration results, for
$\vec{G}\sim\vec{\mathcal{G}}(n,p=\frac{d}{n})$, since
$\mathbf{E}(e(\vec{G}))=\binom{n}{2}p=\frac{d(n-1)}{2}=c(n-1)$,

$\displaystyle\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}(n,p=\frac{d}{n})}[|e(\vec{G})-cn|\geq
n^{2/3}]$
$\displaystyle\leq\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}(n,p=\frac{d}{n})}[|e(\vec{G}))-\mathbf{E}(e(\vec{G}))|\geq
n^{2/3}-c]$ $\displaystyle\leq
2\exp\left(-\frac{(n^{2/3}-c)^{2}}{2(\binom{n}{2}\frac{d}{n}+(n^{2/3}-c)/3)}\right)$
$\displaystyle\leq 2\exp\left(-\frac{n^{4/3}/2}{d(n-1)+n^{2/3}}\right)$
$\displaystyle\leq 2\exp\left(-\frac{n^{1/3}}{4d}\right)$ (for $n$ large
enough) $\displaystyle=o(1).$

∎

###### Proof of Theorem 1.1.

Let $d>1$ be given and let $k_{1}$ be an integer satisfying $d>u_{(k_{1}-1)}$.
Set $c=\frac{d}{2}$. By Corolloary 7.2, letting $A$ be the event that the
chromatic number is at most $k_{1}-1$, for any $m\leq cn+n^{2/3}$,

$\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}(n,p=\frac{d}{n})}[{\chi_{o}}(\vec{G})\leq
k_{1}-1\mid e(\vec{G})=m]\leq
e^{5c(c-1)}\mathbf{Pr}_{\vec{M}\sim\vec{\mathcal{M}}(n,m)}[{\chi_{o}}(\vec{M})\leq
k_{1}-1].$

Thus, by Lemma 7.3, the law of total probability, and noting that the
probability that $\vec{M}\sim\vec{\mathcal{M}}_{n,m}$ is simple decreases as
$m$ increases, with $\vec{\mathcal{G}}=\vec{\mathcal{G}}(n,p=\frac{d}{n})$,

$\displaystyle\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}}[{\chi_{o}}(\vec{G})\leq
k_{1}-1]$
$\displaystyle=\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}}[{\chi_{o}}(\vec{G})\leq
k_{1}-1\text{ and }|e(\vec{G})-cn|\leq n^{2/3}]\quad+$
$\displaystyle\qquad\qquad\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}}[{\chi_{o}}(\vec{G})\leq
k_{1}-1\text{ and }|e(\vec{G})-cn|>n^{2/3}]$ $\displaystyle\leq\sum_{m=\lceil
cn-n^{2/3}\rceil}^{\lfloor
cn+n^{2/3}\rfloor}\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}}[{\chi_{o}}(\vec{G})\leq
k_{1}-1\mid
e(\vec{G})=m]\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}}[e(\vec{G})=m]\quad+$
$\displaystyle\qquad\qquad\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}}[|e(\vec{G})-cn|>n^{2/3}]$
$\displaystyle\leq
e^{5c(c+1)}\mathbf{Pr}_{\vec{M}\sim\vec{\mathcal{M}}(n,cn-n^{2/3})}[{\chi_{o}}(\vec{M})\leq
k_{1}-1]\sum_{m=\lceil cn-n^{2/3}\rceil}^{\lfloor
cn+n^{2/3}\rfloor}\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}}[e(\vec{G})=m]+o(1)$
$\displaystyle\leq
e^{5c(c+1)}\mathbf{Pr}_{\vec{M}\sim\vec{\mathcal{M}}(n,cn-n^{2/3})}[{\chi_{o}}(\vec{M})\leq
k_{1}-1]+o(1)$

Pick $c^{\prime}$ satisfying $c>c^{\prime}>\frac{1}{2}u_{(k_{1}-1)}$ and let
$n$ be large enough that $cn-n^{2/3}\geq c^{\prime}n$. Then by Proposition
4.1, noting the probability that an oriented $(k_{1}-1)$-colouring exists is
decreasing in the number of edges,

$e^{5c(c+1)}\mathbf{Pr}_{\vec{M}\sim\vec{\mathcal{M}}(n,cn-n^{2/3})}[{\chi_{o}}(\vec{M})\leq
k_{1}-1]\leq
e^{5c(c+1)}\mathbf{Pr}_{\vec{M}\sim\vec{\mathcal{M}}(n,m=c^{\prime}n)}[{\chi_{o}}(\vec{M})\leq
k_{1}-1]=o(1)$

and therefore a.a.s. ${\chi_{o}}(\vec{\mathcal{G}}(n,p=\frac{d}{n}))>k_{1}-1$.

Now let $k_{2}\geq 3$ such that $d<\ell_{k_{2}}$ and there exists a doubly
regular tournament of order $k_{2}$. Set $c=d/2$, let $c^{\prime}$ be such
that $c<c^{\prime}<\frac{1}{2}\ell_{k_{2}}$ and let $n$ be large enough that
$cn+n^{2/3}\leq c^{\prime}n$. Using Corollary 7.2 where $A$ is the event that
the chromatic number is greater than $3k_{2}+11$, for any $m\leq
c^{\prime}n+n^{2/3}$,

$\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}(n,p=\frac{d}{n})}[{\chi_{o}}(\vec{G})>3k_{2}+11\mid
e(\vec{G})=m]\leq
e^{5c^{\prime}(c^{\prime}+1)}\mathbf{Pr}_{\vec{M}\sim\vec{\mathcal{M}}_{n,m}}[{\chi_{o}}(\vec{M})>3k_{2}+11].$

Thus, using Lemma 7.3, that the probability the oriented chromatic number is
at least $3k_{2}+11$ is increasing in the number of edges, and the law of
total probability, with
$\vec{\mathcal{G}}=\vec{\mathcal{G}}(n,p=\frac{d}{n})$,

$\displaystyle\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}}[{\chi_{o}}(\vec{G})>3k_{2}+11]$
$\displaystyle=\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}}[{\chi_{o}}(\vec{G})>3k_{2}+11\text{
and }e(\vec{G})>c^{\prime}n]\quad+$
$\displaystyle\qquad\qquad\sum_{m=0}^{\lfloor
c^{\prime}n\rfloor}\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}}[{\chi_{o}}(\vec{G})>3k_{2}+11\text{
and }e(\vec{G})=m]$
$\displaystyle\leq\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}}[e(\vec{G})>c^{\prime}n\geq
cn+n^{2/3}]\quad+$ $\displaystyle\qquad\qquad
e^{5c^{\prime}(c^{\prime}+1)}\mathbf{Pr}_{\vec{M}\sim\vec{\mathcal{M}}(n,m=c^{\prime}n)}[{\chi_{o}}(\vec{M})>3k_{2}+11]\sum_{m=0}^{\lfloor
c^{\prime}n\rfloor}\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}}[e(\vec{G})=m]$
$\displaystyle\leq
o(1)+e^{5c^{\prime}(c^{\prime}+1)}\mathbf{Pr}_{\vec{M}\sim\vec{\mathcal{M}}(n,m=c^{\prime}n)}[{\chi_{o}}(\vec{M})>3k_{2}+11].$

Then by Proposition 5.4, as $1<c^{\prime}<\frac{1}{2}\ell_{k_{2}}$,
$\vec{M}\sim\vec{\mathcal{M}}(n,m=c^{\prime}n)$ has a proper oriented
$k_{2}$-colouring with positive probability. Proposition 6.6 then guarantees
$\mathbf{Pr}_{\vec{M}\sim\vec{\mathcal{M}}(n,m=c^{\prime}n)}[{\chi_{o}}(\vec{M})>3k_{2}+11]=o(1)$.
We conclude a.a.s.

${\chi_{o}}(\vec{\mathcal{G}}(n,p=\tfrac{d}{n}))\in[k_{1},3k_{2}+11].$

∎

###### Proof of Theorem 1.2.

It is well-known (see, for example, [7]) that the (undirected) configuration
model produces a simple graph with probability tending toward
$\exp(-\frac{1}{2}(d-1)-\frac{1}{4}(d-1)^{2})=:\kappa>0$. Orienting an
undirected simple graph produces a simple oriented graph, so with positive
probability $\vec{C}\sim\vec{\mathcal{C}}(n,d)$ is a simple digraph.
Furthermore, these simple digraphs are uniformly distributed as each simple
graph corresponds to the same number of configurations. Therefore, if $A$ is
any event in both $\vec{\mathcal{G}}(n,d)$ and $\vec{\mathcal{C}}(n,d)$, then

$\displaystyle\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}(n,d)}[A]$
$\displaystyle=\mathbf{Pr}_{\vec{C}\sim\vec{\mathcal{C}}(n,d)}[A\mid\text{$\vec{C}$
is simple}]$
$\displaystyle=\frac{\mathbf{Pr}_{\vec{C}\sim\vec{\mathcal{C}}(n,d)}[A\text{
and $\vec{C}$ is
simple}]}{\mathbf{Pr}_{\vec{C}\sim\vec{\mathcal{C}}(n,d)}[\text{$\vec{C}$ is
simple}]}$
$\displaystyle\leq\kappa^{-1}\mathbf{Pr}_{\vec{C}\sim\vec{\mathcal{C}}(n,d)}[A]$

For $k_{1}\geq 2$ and $d\geq u_{(k_{1}-1)}$, Proposition 4.2 assures
$\mathbf{Pr}_{\vec{C}\sim\vec{\mathcal{C}}(n,d)}[{\chi_{o}}(\vec{C})\leq
k_{1}-1]=o(1)$ and therefore

$\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}(n,d)}[{\chi_{o}}(\vec{G})\leq
k_{1}-1]\leq\kappa^{-1}\cdot o(1)=o(1).$

On the other hand, if there is a $k_{2}\geq 3$ such that $d<\ell_{k_{2}}$ and
there exists a doubly regular tournament of order $k_{2}$, then Proposition
5.14 gives ${\chi_{o}}(\vec{\mathcal{C}}(n,d))\leq k_{2}$ with positive
probability. Then Proposition 6.5 guarantees
$\mathbf{Pr}_{\vec{C}\sim\vec{\mathcal{C}}(n,d)}[{\chi_{o}}(\vec{C})>3k_{2}+11]=o(1)$,
so

$\mathbf{Pr}_{\vec{G}\sim\vec{\mathcal{G}}(n,d)}[{\chi_{o}}(\vec{G})>3k_{2}+11]\leq\kappa^{-1}\cdot
o(1)=o(1).$

We conclude a.a.s.

${\chi_{o}}(\vec{\mathcal{G}}(n,d))\in[k_{1},3k_{2}+11].$

∎

###### Proof of Corollary 1.3.

Let $d>1$ be given and set $k=2^{d/2}$. Then

$u_{k}<\frac{2}{\log 2}\log(k)=d$

Setting $k^{\prime}=k^{1/\log 2}+\frac{2}{\log 2}\log k+1=e^{d/2}+d+1$,

$d<2\left(1-\frac{2}{k^{\prime}+1}\right)\log(k^{\prime}-1)<\ell_{k^{\prime}}.$

Thus we can apply Theorems 1.1 and 1.2 for any $k^{\prime\prime}\geq
k^{\prime}$ such that there exists a doubly regular tournament of order
$k^{\prime\prime}$. Lemma 3.9 guarantees the smallest $k^{\prime\prime}$ for
which this holds is at most $2k^{\prime}$, and thus

${\chi_{o}}(\vec{\mathcal{G}}(n,p=\tfrac{d}{n})),{\chi_{o}}(\vec{\mathcal{G}}(n,d))\in(k,3(2k^{\prime})+11]=(2^{d/2},6e^{d/2}+6d+17].$

∎

##  8 Further Discussion

###  8.1 Very sparse or very dense graphs

Throughout the majority of this paper, we have focused on the case of oriented
graphs with edge density $\frac{d}{2}$, mainly for $d$ fixed and large.
However, in the case that $d\leq 2$ it is possible to use the properties of
random graphs and constraints on oriented colourings with a small number of
colours to say something more precise than what is given by the second moment
argument. What makes these cases more tractable for analysis is that there
are, up to isomorphism, only two different tournaments on $3$ vertices
($C_{3}$ and $T_{3}$ in Figure 1) and there are characterizations of when an
oriented unicyclic graph can be properly coloured by either one.

$1$$2$$3$$C_{3}$

$1$$2$$3$$T_{3}$

$1$$2$$3$$4$$T_{4}$

$1$$2$$3$$4$$5$$T_{5}$

Figure 1: Small tournaments for colouring oriented $2$-regular graphs

In his survey, Sopena [50] gave a complete characterization of the oriented
chromatic number of oriented cycles, showing that for an oriented cycle
$\vec{C}$, the possible values of $\chi_{o}(\vec{C})$ are $2,3,4$, or $5$,
exactly characterizing each case. The proofs can be modified to give the
corresponding results for here for $2$-regular oriented graphs that are not
necessarily connected. The main ideas of the proofs are that both of the
tournaments $T_{4}$ and $T_{5}$ in Figure 1 contain directed $3$-cycles,
directed $4$-cycles, and the transitive tournament on $3$ vertices. This can
be used to show that every directed cycle can be properly coloured with either
one, except in the case of the directed $5$-cycle that can only be properly
$T_{5}$-coloured. Since both tournaments $T_{4}$ and $T_{5}$ have the property
that every vertex has non-zero in-degree and out-degree, the rest follows by
induction on the number of source or sink vertices, with a few special cases
to check. Since both tournaments $T_{4}$ and $T_{5}$ have the property that
every vertex has both in-neighbours and out-neighbours, any proper colouring
of the cycle in an orientation of a unicyclic graph can be extended to a
colouring of the remaining vertices.

######
Proposition 8.1 (see Sopena [50, Proposition 10]).

If $\vec{G}$ is an orientation of a graph in which each component is a tree or
unicyclic, then $\chi_{o}(\vec{G})\leq 5$ and $\vec{G}$ can be properly
$5$-coloured by the tournament $T_{5}$ in Figure 1. Moreover, if no component
of $\vec{G}$ contains a directed $5$-cycle, then $\chi_{o}(\vec{G})\leq 4$ and
$\vec{G}$ can be properly $4$-coloured by the tournament $T_{4}$ in Figure 1.

Within the proof, Sopena [50, Proposition 10] notes the following
straightforward characterization of the $2$-regular oriented graphs that have
oriented $3$-colourings. Up to isomorphism, there are only two different
tournaments on $3$ vertices: the directed $3$-cycle ($C_{3}$) and the
transitive tournament on $3$ vertices ($T_{3}$). Let $\vec{G}$ be an oriented
cycle with vertices labelled around the cycle $u_{1},u_{2},\ldots,u_{k}$. Call
an arc a _forward arc_ if it is directed $u_{i}\to u_{i+1}$ (indices computed
modulo $k$) and a _backward arc_ if it is directed $u_{i+1}\to u_{i}$. Then
$\vec{G}$ has a proper $C_{3}$-colouring iff the difference between the number
of forward arcs and the number of backward arcs is divisible by $3$. The graph
$\vec{G}$ has a proper $T_{3}$-colouring iff there are no 3 consecutive arcs
in the same direction. Neither of these properties depends on the choice of
starting vertex for the cycle’s labelling, nor the direction of the labelling.
Using these properties it is possible to show that with high probability, some
component of a large $2$-regular oriented graph does not satisfy either
property.

To see that a proper $C_{3}$-colouring is not likely, one can show, by
induction, that for any $k\geq 3$, in a random orientation of a $k$-cycle,
with probability at most $1/2$, the difference between the number of forward
arcs and backward arcs is divisible by $3$. One can check that in a random
$2$-regular graph on $n$ vertices, with high probability, there are at least
$\log n$ components. Thus, the probability that a random orientation of a
random $2$-regular graph is $C_{3}$-colourable is $o(1)$.

We now consider the property of being $T_{3}$-colourable, which is equivalent
to not having three consecutive arcs in the same direction. The number of
orientations of a $k$-cycle with this property is the same as the number of
cyclic sequences of $0$s and $1$s of length $k$ that start with a $1$ and have
no substring $000$ or $111$. This is bounded above by the number of binary
strings (not cyclic) of length $k$ that start with a $1$ and have no three
consecutive $0$s nor three consecutive $1$s. By checking cases for how such a
string can begin, one can give a linear recurrence for this number and show
that, if $\phi=\frac{1+\sqrt{5}}{2}$, the number of such strings is bounded
above by $\phi^{k}$. Since the sum of all cycle lengths in a $2$-regular graph
on $n$ vertices is $n$, this shows that the probability that
$\vec{G}\sim\vec{\mathcal{G}}_{n,2}$ is properly $T_{3}$-colourable is at most
$\left(\frac{\phi}{2}\right)^{n}=o(1)$.

Thus, with high probability, for $\vec{G}\sim\vec{\mathcal{G}}(n,2)$,
$\chi_{o}(\vec{G})>3$.

Every oriented $2$-regular graph has a proper oriented $5$ colouring and
Proposition 8.1 shows that whether $5$ colours are needed depends on the
presence of a directed $5$-cycle. Since the number of $5$-cycles in the
undirected graph $G_{n,2}$ is asymptotically distributed as a Poisson random
variable with mean $\frac{1}{2\cdot 5}$, the number of directed $5$-cycles is
a asymptotically distributed as a Poisson random variable with mean
$\frac{1}{2\cdot 5}\cdot\frac{1}{2^{4}}$. This gives the following complete
result for random $2$-regular oriented graphs.

######
Theorem 8.2.

For $\vec{G}\sim\vec{\mathcal{G}}(n,2)$, with high probability,
$\chi_{o}(\vec{G})\in\\{4,5\\}$ with

$\displaystyle\mathbf{Pr}(\chi_{o}(\vec{G})=4)$
$\displaystyle=e^{-1/160}(1+o(1))$
$\displaystyle\mathbf{Pr}(\chi_{o}(\vec{G})=5)$
$\displaystyle=\left(1-e^{-1/160}\right)(1+o(1)).$

A similar analysis can be applied to the random binomial graph
$\vec{\mathcal{G}}(n,p)$ in the case that $p<1/n$ to show that in that case,
with high probability, the oriented chromatic number takes at one of $3$
possible values, each with positive probability.

######
Theorem 8.3.

For $d$ constant with $0<d<1$ and
$\vec{G}\sim\vec{\mathcal{G}}(n,p=\frac{d}{n})$, with high probability,
$\chi_{o}(\vec{G})\in\\{3,4,5\\}$ with

$\displaystyle\mathbf{Pr}(\chi_{o}(\vec{G}))=3)$
$\displaystyle>(1-d)^{1/2}\exp\left(\frac{d}{2}+\frac{d^{2}}{4}\right)(1+o(1)),$
$\displaystyle\mathbf{Pr}(\chi_{o}(\vec{G}))=4)$
$\displaystyle>\frac{d^{5}}{32}e^{-d^{5}/10},$
$\displaystyle\mathbf{Pr}(\chi_{o}(\vec{G}))=5)$
$\displaystyle=(1-\exp(-\frac{d^{5}}{160}))(1+o(1))$

###### Proof.

For $p=d/n$, with $d<1$, Erdős and Rényi [18] showed that with high
probability, for $G\sim\mathcal{G}(n,p)$, every component of $G$ is either a
tree or unicyclic. By Proposition 8.1, then with high probability
$\chi_{o}(\vec{G})\leq 5$ and $\chi_{o}(\vec{G})=5$ if and only if some
component of $\vec{G}$ contains a directed $5$-cycle. Again, due to results of
Erdős and Rényi [18], the number of $5$-cycles in $\vec{G}$ is asymptotically
a Poisson random variable with mean $\frac{d^{5}}{10}$. Thus, the probability
that there is at least one directed $5$-cycle in $\vec{G}$ is asymptotically
$(1-\exp(-\frac{d^{5}}{10}\cdot\frac{1}{16}))$. This is precisely the
probability that $\vec{G}$ has oriented chromatic number equal to $5$.

By a similar argument, with probability asymptotically,
$\frac{d^{5}}{10}e^{-d^{5}/10}\cdot\frac{5}{16}$, there is exactly one
$5$-cycle in $\vec{G}$ and it is oriented isomorphically to the cycle in
Figure 2. If this is the case, then $\chi_{o}(\vec{G})=4$.

Figure 2: Oriented $5$-cycle with $\chi_{o}(C)=4$

On the other hand, based on results of Takács [51] or Janson [27], the
probability that $G\sim\mathcal{G}(n,p=\frac{d}{n})$ is a forest is
asymptotically $(1-d)^{1/2}e^{d/2+d^{2}/4}$. If $G$ is a forest, then any
orientation of $G$ can be properly $3$-coloured by the directed $3$-cycle. On
the other hand, to see that $\chi_{o}(\vec{G})>2$, note that by
straightforward second moment arguments, with high probability, $\vec{G}$
contains a directed path of length $2$, which has no proper oriented
$2$-colouring. ∎

It was noted by Bensmail, Duffy, and Sen [6] that looking at a uniform random
oriented graph on $n$ vertices, that is $\vec{G}\sim\vec{\mathcal{G}}(n,1/2)$,
with high probability, every pair of vertices are joined by a directed path of
length $2$ (in one direction or the other) and hence none can be coloured with
the same colour in any oriented colouring. Klostermeyer and MacGillivray [32]
called such graphs _oriented cliques_ and noted that the condition of having
weak diameter $2$ is equivalent to having oriented chromatic number equal to
the number of vertices. Using a standard first moment argument shows that in a
large range of values for $p$, $\vec{G}\sim\vec{\mathcal{G}}(n,p)$ is an
oriented clique.

######
Proposition 8.4.

For any function $\omega(n)\to\infty$, if $p=p(n)$ is such that $p^{2}n=4\log
n+\omega(n)$, then with high probability, for
$\vec{G}\sim\vec{\mathcal{G}}(n,p)$, $\chi_{o}(\vec{G})=n$.

###### Proof.

Since there are two different directed paths of length $2$ between two given
vertices, via a third. Therefore, the expected number of pairs of vertices in
$\vec{G}$ not joined by a directed path of length $2$ is

$\binom{n}{2}(1-p^{2}/2)^{n-2}\leq\frac{n^{2}}{2}\exp\left(-(n-2)\frac{p^{2}}{2}\right)\leq\frac{e}{2}\exp\left(2\log
n-\frac{np^{2}}{2}\right)$

and the result follows. ∎

###  8.2 Precise value of the second moment

To improve the results of Achlioptas and Moore [2] from a collection of three
possible values for $\chi(\mathcal{G}(n,d))$ to two values, Kemkes at al. [30]
used the small subgraph conditioning method of Robinson and Wormald (see [29,
Chapter 9] and [55]). The small subgraph conditioning method explains that
$\mathbf{E}Y^{2}$ exceeds $(\mathbf{E}Y)^{2}$ because the presence or absence
of small cycles artificially inflates the variance. In cases where the small
subgraph conditioning method is useful, conditioning on the presence of these
cycles “luckily and yet mysteriously” accounts for the difference between
$\mathbf{E}Y^{2}$ and $(\mathbf{E}Y)^{2}$. The method requires accurate
estimates for the first and second moments as well as certain joint moments.

In Section 5.2.3, we were unable to calculate $\det(-H|_{\mathbb{V}})$
exactly. With an exact value for $\det(-H|_{\mathbb{V}})$, we could have
gotten an exact value for $C_{d,k}$ in Equation (38). Though we have not done
so carefully, it seems likely that there is an extension of the small subgraph
conditioning method to directed graphs. With such an extension and an exact
value for $C_{d,k}$, one could use Proposition 2 of Kemkes et al. [30] to
calculate the required joint factorials and replace “with positive
probability” in Proposition 5.14 with “almost surely.” This argument would
supersede Section 6 and allow for the marginally stronger result

${\chi_{o}}(\mathcal{G}(n,d))\in(2^{d/2},e^{d/2}+d+1].$

Extending the small subgraph conditioning method to directed graphs would also
open up the possibility of improving the bounds on
${\chi_{o}}(\mathcal{G}(n,m))$. In addition, one would need to calculate the
joint factorial moments of small cycles in $\mathcal{M}(n,m)$. We chose not to
pursue this approach because the it only offers a scalar improvement, a
marginal difference compared to the exponential gap between the upper and
lower bounds.

###  8.3 Upper bounds when $k$ does not divide $n$

In Section 5 we calculated upper bounds for
${\chi_{o}}(\vec{\mathcal{M}}(n,m=cn))$ and
${\chi_{o}}(\vec{\mathcal{C}}(n,d))$ under the assumption that $n$ was
divisible by $k$. In this section we discuss how to remove that condition
using ideas of [40].

Suppose $n=qk+r$ where $r\in[0,k-1]$. We extend the concept of equitable
colourings by requiring every colour classes 1 through $r$ to contain $q+1$
vertices and colour classes $r+1$ through $k$ to contain $q$ vertices. (Note
that for $r=0$ this coincides with our original definition of equitable.) The
strategy to adapt Propositions 5.4 and 5.14 for $r>0$ is to show that fixing
these $r=O(1)$ vertices does not affect the ratio
$(\mathbf{E}Y)^{2}/(\mathbf{E}Y^{2})$. To get a feeling for the argument, we
prove the following proposition.

######
Proposition 8.5.

Let $k$ be an integer such that there exists a doubly regular tournament of
order $k$ and let $c>0$. Fix a doubly regular tournament $T_{k}$. For
$n=qk+r,r\in[0,k-1]$, let $Y_{n}$ count the number of equitable oriented
$T_{k}$-colourings of $\vec{\mathcal{M}}(n,m=cn)$. Let $n^{\prime}=n-r$. Then

$\mathbf{E}Y_{n}^{2}\sim\left(k\left(\frac{1}{2}\left(1-\frac{1}{k}\right)\right)^{c}\right)^{2r}\mathbf{E}Y_{n^{\prime}}^{2}.$

Before proving Proposition 8.5, we introduce a few ideas of Pérez and the
second author. Recall that in the proof of Lemma 5.3, we defined the set
$\mathbb{X}_{n}$ which contained, for each $n$, the valid overlap matrices on
$n$ vertices. We proved that the exponential contribution to each term of the
sum was maximized at $\hat{x}$, the vector with every entry $\frac{n}{k^{2}}$.
As seen in Equation (21), the second moment is a sum containing polynomially
many exponential terms, and thus the terms close to this exponential maximum
contribute all but a negligible portion of the sum. This fact is captured in
the following result:

######
Proposition 8.6 (see [40, Proposition 3.5]).

Suppose the same set of conditions hold as in Theorem 5.2. In addition,
suppose there is $N>0$ such that $\psi(x)\leq n^{N}$ for each
$\text{\boldmath$x$}\in K_{1}$. For any $\gamma>0$, define
$\mathbb{Y}_{n}(\gamma)\subseteq\mathbb{X}_{n}$ as

$\mathbb{Y}_{n}(\gamma)=\left\\{\text{\boldmath$x$}\in\mathbb{X}_{n}:||\text{\boldmath$\hat{x}$}-\text{\boldmath$x$}||_{\infty}<\gamma\frac{\log
n}{\sqrt{n}}\right\\}.$

Then

$\sum_{\text{\boldmath$x$}\in\mathbb{Y}_{n}(\gamma)}T_{n}(\text{\boldmath$x$})\sim\sum_{\text{\boldmath$x$}\in\mathbb{X}_{n}}T_{n}(\text{\boldmath$x$}).$

We now prove Proposition 8.5, following the proof of Proposition 7.1 in [40].

###### Proof of Proposition 8.5.

Given $\text{\boldmath$A$}\in\mathbb{Y}_{n}(1)$, define

$\text{\boldmath$A$}^{\ast}=\left(\frac{1}{n^{\prime}}(na_{ij}-\delta_{ij})\right)_{i,j\in[k]}$

where

$\delta_{ij}=\begin{cases}1&i=j\leq r\\\ 0&\text{else}\end{cases}.$

Then $\text{\boldmath$A$}^{\ast}$ defines the overlap matrix of a pair of
equitable oriented $T_{k}$-colourings of $\vec{\mathcal{M}}(m,cn)$ as we have
removed the $r$ vertices of prescribed colours 1 through $r$. As
$\text{\boldmath$A$}\in\mathbb{Y}_{n}(1)$, we know
$\text{\boldmath$A$}^{\ast}$ is non-negative.

Recall from Equation (20) that the number of oriented $T_{k}$-colourings
respecting $A$ is

$\frac{n!}{\prod_{v\in V}(na_{v})!}\left(\sum_{uv\in E(T^{\otimes
2})}a_{u}a_{v}\right)^{m}=:\ell(\text{\boldmath$A$}).$

We have

$\frac{\ell(\text{\boldmath$A$})}{\ell(\text{\boldmath$A$}^{\ast})}=\frac{n_{(r)}}{n^{r}}\cdot\frac{1}{\prod_{i=1}^{r}a_{ii}}\cdot\left(\frac{n-r}{n}\right)^{2cr}\cdot\frac{(\sum_{uv\in
E}a_{u}a_{v})^{cn}}{(\sum_{uv\in
E}(a_{u}a_{v}-\frac{1}{n}(a_{u}\delta_{v}+a_{v}\delta_{u})+\frac{1}{n^{2}}\delta_{u}\delta_{v}))^{c(n-r)}}.$

Note that $\delta_{u}\delta_{v}=1$ if and only if $u=(i,i),v=(j,j)$, and
$i\neq j\leq r$. Therefore

$\sum_{uv\in E(T^{\otimes 2})}\delta_{u}\delta_{v}=\binom{r}{2}.$

Furthermore,

$0\leq\sum_{uv\in E(T^{\otimes
2})}(a_{u}\delta_{v}+a_{v}\delta_{u})\leq\sum_{uv\in E(T^{\otimes
2})}(a_{u}+a_{v})=\frac{(k-1)^{2}}{2}\sum_{v\in V(T^{\otimes
2})}a_{v}=\frac{(k-1)^{2}}{2}$

as each $v\in T^{\otimes 2}$ has degree $\frac{(k-1)^{2}}{2}$. Therefore,
keeping in mind $\text{\boldmath$A$}\in\mathbb{Y}_{n}(1)$, we have

$\frac{\ell(\text{\boldmath$A$})}{\ell(\text{\boldmath$A$}^{\ast})}\geq\frac{n_{(r)}}{n^{r}}\cdot\left(\frac{n-r}{n}\right)^{2cr}\cdot\frac{(\sum_{uv\in
E}(\frac{1}{k^{2}}-\frac{|logn}{\sqrt{n}})^{2})^{cn}}{(\frac{1}{k^{2}}+\frac{\log
n}{\sqrt{n}})^{r}(\sum_{uv\in E}(\frac{1}{k^{2}}+\frac{\log
n}{\sqrt{n}})^{2}+\frac{1}{n^{2}}\binom{r}{2})^{c(n-r)}}\to\left(k\left(\frac{1}{2}\left(1-\frac{1}{k}\right)\right)^{c}\right)^{2r}$

and

$\frac{\ell(\text{\boldmath$A$})}{\ell(\text{\boldmath$A$}^{\ast})}\leq\frac{n_{(r)}}{n^{r}}\cdot\left(\frac{n-r}{n}\right)^{2cr}\cdot\frac{(\sum_{uv\in
E}(\frac{1}{k^{2}}+\frac{|logn}{\sqrt{n}})^{2})^{cn}}{(\frac{1}{k^{2}}-\frac{\log
n}{\sqrt{n}})^{r}(\sum_{uv\in E}(\frac{1}{k^{2}}-\frac{\log
n}{\sqrt{n}})^{2}-\frac{(k-1)^{2}}{2n})^{c(n-r)}}\to\left(k\left(\frac{1}{2}\left(1-\frac{1}{k}\right)\right)^{c}\right)^{2r}$

from which we conclude

$\frac{\ell(\text{\boldmath$A$})}{\ell(\text{\boldmath$A$}^{\ast})}\to\left(k\left(\frac{1}{2}\left(1-\frac{1}{k}\right)\right)^{c}\right)^{2r}.$

Let
$\mathcal{A}=\\{\text{\boldmath$A$}^{\ast}\mid\text{\boldmath$A$}\in\mathbb{Y}_{n}(1)\\}$.
Then if there is $\gamma>0$ such that
$\mathbb{Y}_{n}(\gamma)\subseteq\mathcal{A}$, Proposition 8.6 gives

$\displaystyle\left(k\left(\frac{1}{2}\left(1-\frac{1}{k}\right)\right)^{c}\right)^{2r}\mathbf{E}Y_{n^{\prime}}^{2}$
$\displaystyle\sim\sum_{\text{\boldmath$A$}\in\mathbb{Y}_{n^{\prime}}(\gamma)}\left(k\left(\frac{1}{2}\left(1-\frac{1}{k}\right)\right)^{c}\right)^{2r}p(n,\text{\boldmath$A$})\exp(nf(\text{\boldmath$A$}))$
$\displaystyle\leq\sum_{\text{\boldmath$A$}\in\mathcal{A}}\left(k\left(\frac{1}{2}\left(1-\frac{1}{k}\right)\right)^{c}\right)^{2r}p(n,\text{\boldmath$A$})\exp(nf(\text{\boldmath$A$}))\sim\mathbf{E}Y_{n}^{2}$
$\displaystyle\leq\sum_{\text{\boldmath$A$}\in\mathbb{X}_{n^{\prime}}}\left(k\left(\frac{1}{2}\left(1-\frac{1}{k}\right)\right)^{c}\right)^{2r}p(n,\text{\boldmath$A$})\exp(nf(\text{\boldmath$A$}))$
$\displaystyle=\left(k\left(\frac{1}{2}\left(1-\frac{1}{k}\right)\right)^{c}\right)^{2r}\mathbf{E}Y_{n^{\prime}}^{2},$

completing the proof of the proposition.

Thus it suffices to show for some $\gamma>0$ and all
$\text{\boldmath$\tilde{A}$}\in\mathbb{Y}_{n^{\prime}}(\gamma)$ there is
$\text{\boldmath$A$}\in\mathbb{Y}_{n}(1)$ such that
$\text{\boldmath$A$}^{\ast}=\text{\boldmath$\tilde{A}$}$. Each
$\tilde{a}_{v}\in\text{\boldmath$\tilde{A}$}$ satisfies

$\frac{1}{k^{2}}-\gamma\frac{\log
n^{\prime}}{\sqrt{n^{\prime}}}\leq\tilde{a}_{v}\leq\frac{1}{k^{2}}+\gamma\frac{\log
n^{\prime}}{\sqrt{n^{\prime}}}$

and we want

$\frac{1}{n^{\prime}}(na_{v}-\delta_{v})=\tilde{a}_{v}$

where $a_{v}$ must satisfy

$\frac{1}{k^{2}}-\frac{\log n}{\sqrt{n}}\leq
a_{v}\leq\frac{1}{k^{2}}+\frac{\log n}{\sqrt{n}}.$

Thus it suffices to pick $\gamma$ so that

$\frac{1}{k^{2}}-\frac{\log
n}{\sqrt{n}}\leq\frac{n^{\prime}}{n}\left(\frac{1}{k^{2}}-\gamma\frac{\log
n^{\prime}}{\sqrt{n^{\prime}}}\right)$

and

$\frac{1}{n}\left(n^{\prime}\left(\frac{1}{k^{2}}+\gamma\frac{\log
n^{\prime}}{\sqrt{n^{\prime}}}\right)+1\right)\leq\frac{1}{k^{2}}+\frac{\log
n}{\sqrt{n}}.$

These are identical conditions to those of [40], where the authors show
$\gamma=0.4$ suffices. ∎

To complete the argument that ${\chi_{o}}(\vec{\mathcal{M}}(n,m=cn))\leq k$
with positive probability, one should prove that

$\mathbf{E}Y_{n}\sim\left(k\left(\frac{1}{2}\left(1-\frac{1}{k}\right)\right)^{c}\right)^{r}\mathbf{E}Y_{n^{\prime}}$

in a similar (but easier) manner; then

$\mathbf{Pr}[Y_{n}>0]\geq\frac{(\mathbf{E}Y_{n})^{2}}{\mathbf{E}(Y_{n}^{2})}\sim\frac{(\mathbf{E}Y_{n^{\prime}})^{2}}{\mathbf{E}(Y_{n^{\prime}}^{2})}\sim\frac{(\mathbf{E}Y)^{2}}{\mathbf{E}(Y^{2})}\sim\left(\frac{((k-1)^{2}-2c)^{2}-4c^{2}k^{2}}{(k-1)^{4}}\right)^{(k-1)^{2}/4}>0.$

In proving the upper bound for ${\chi_{o}}(\vec{\mathcal{C}}(n,d))$, we used
the Laplace Summation technique in [24], rather than that in [40]; however,
the latter is an extension of the former and thus a version of Proposition 8.6
holds under the conditions of Theorem 5.8 as well. Then one should prove a
version of Proposition 8.5 for the first and second moments of
$\vec{\mathcal{C}}(n,d)$.

###  8.4 Colouring with tournaments that are not doubly-regular

The exponential gap between the bounds in Theorem 1.2 comes from the different
constants in $u_{k}$ and $\ell_{k}$; $u_{k}$ behaves like $\frac{2}{\log
2}\log k$ while $\ell_{k}$ grows as $2\log k$. While the argument for the
lower bound is straightforward, one might reasonably ask if a better constant
for $\ell_{k}$ could be found by counting equitable colourings of a different
tournament, hoping to improve Corollary 3.8. In the calculations of the second
moment for the number of equitable oriented colourings in Lemma 5.3 and
Section 5.2.1, the initial computation of the second moment would apply
equally well to colouring by _any_ tournament on $k$ vertices, not just a
doubly-regular tournament. Similarly, the function, $\gamma_{d}$, defined in
Proposition 1.4 can be defined with the Lagrangian part given for any graph
$G$. In the case where a tournament $T$ is not regular, that is, not all
vertices have the same in-degree or out-degree, the product graph
$G=T^{\otimes 2}$ will not be regular.

If $G$ is not regular, then subject to the condition that the matrix $A$ be
doubly-stochastic, the point at $\text{\boldmath$A$}=\frac{1}{k}J_{k}$ is not
a critical point for the function $-\frac{1}{k}\sum_{v\in V(G)}a_{v}\log
a_{v}+\frac{d}{2}\log\left(\frac{2\sum_{uv\in E}a_{u}a_{v}}{k^{2}}\right)$ and
so cannot be the location of the maximum value. This would mean that the
maximum value is strictly greater and so the exponential part of the second
moment of the number of equitable $T$-colourings has a larger base that the
square of the expected value and a standard second moment method argument
would not yield a positive probability of finding an equitable $T$-colouring.

Among the regular tournaments, one might seek a tournament whose Kronecker
square has a smaller second-largest eigenvalue to improve the bound on $d$
obtained from Proposition 1.4. However, one can show that the signed adjacency
matrix of any regular tournament of order $k$ has an eigenvalue $\lambda$ with
$|\lambda|\geq\sqrt{k}$ and use this fact to prove that the second-largest
eigenvalue has size at least $\frac{1}{2}(1+\lambda^{2})\geq\frac{k+1}{2}$,
precisely the value of the second-largest eigenvalue of the Kronecker square
of a doubly regular tournament. The fact that the signed adjacency matrix of a
regular tournament of order $k$ has an eigenvalue of modulus at least
$\sqrt{k}$ follows from a result by Brauer and Gentry [11] on the unsigned
adjacency matrices of regular tournaments, but one can also prove it directly
by showing that if $M$ is the signed adjacency matrix of a regular tournament
of order $k$ and $\mathbf{v}$ is any column of $M$, then
$||M\mathbf{v}||_{2}/||\mathbf{v}||_{2}\geq\sqrt{k}$. From this, one can show
that the largest eigenvalue of $T^{\otimes 2}$ is exactly
$\frac{(k-1)^{2}}{2}$ and the second-largest eigenvalue is at least
$\frac{k+1}{2}$. Thus, for the approach of finding oriented colourings using
the second-moment method, doubly-regular tournaments will give the best
results.

## Acknowledgements

The authors would like to thank Stephen Kirkland for help with references on
the algebraic properties of tournaments and Siddarth Sankaran for assistance
with reference for number theoretic results. They also thank Xavier Pérez for
offering his expertise on the history of problems on random graphs of bounded
degree and Cris Moore for helpful clarifications about the results for
undirected regular graphs.

## References

  * [1] D. Achlioptas and E. Friedgut.  A sharp threshold for $k$-colorability.  Random Structures Algorithms, 14(1):63–70, 1999.
  * [2] D. Achlioptas and C. Moore.  The chromatic number of random regular graphs.  In Lecture notes in computer science, pages 219–228, Berlin, 2004\. Springer.
  * [3] D. Achlioptas and A. Naor.  The two possible values of the chromatic number of a random graph.  Ann. of Math. (2), 162(3):1335–1351, 2005.
  * [4] N. Alon and J. H. Spencer.  The Probabilistic Method.  Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, fourth edition, 2016.
  * [5] M. A. Bennett, G. Martin, K. O’Bryant, and A. Rechnitzer.  Explicit bounds for primes in arithmetic progressions.  Illinois J. Math., 62(1-4):427–532, 2018.
  * [6] J. Bensmail, C. Duffy, and S. Sen.  Analogues of cliques for $(m,n)$-colored mixed graphs.  Graphs Combin., 33(4):735–750, 2017.
  * [7] B. Bollobás.  A probabilistic proof of an asymptotic formula for the number of labelled regular graphs.  European J. Combin., 1(4):311–316, 1980.
  * [8] B. Bollobás.  The chromatic number of random graphs.  Combinatorica, 8(1):49–55, 1988.
  * [9] B. Bollobás.  Random Graphs, volume 73 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, second edition, 2001.
  * [10] O. V. Borodin, A. V. Kostochka, J. Nešetřil, A. Raspaud, and E. Sopena.  On the maximum average degree and the oriented chromatic number of a graph.  volume 206, pages 77–89. 1999.  Combinatorics and number theory (Tiruchirappalli, 1996).
  * [11] A. Brauer and I. C. Gentry.  Some remarks on tournament matrices.  Linear Algebra Appl., 5:311–318, 1972.
  * [12] P. Chebolu and A. Frieze.  Hamilton cycles in random lifts of directed graphs.  SIAM J. Discrete Math., 22(2):520–540, 2008.
  * [13] A. Coja-Oghlan, C. Efthymiou, and S. Hetterich.  On the chromatic number of random regular graphs.  arXiv e-prints, page arXiv:1308.4287, Aug 2013.
  * [14] B. Courcelle.  The monadic second order logic of graphs. VI. On several representations of graphs by relational structures.  volume 54, pages 117–149. 1994.  Efficient algorithms and partial $k$-trees.
  * [15] R. Dawes and H. Meijer.  Arc-minimal digraphs of specified diameter.  In Proceedings of the first Carbondale combinatorics conference (Carbondale, Ill., 1986), volume 1, pages 85–96, 1987.
  * [16] C. Duffy.  Colourings of oriented connected cubic graphs.  Discrete Math., 343(10):112021, 6, 2020.
  * [17] C. Duffy, G. MacGillivray, and E. Sopena.  Oriented colourings of graphs with maximum degree three and four.  Discrete Math., 342(4):959–974, 2019.
  * [18] P. Erdős and A. Rényi.  On the evolution of random graphs.  Magyar Tud. Akad. Mat. Kutató Int. Közl., 5:17–61, 1960\.
  * [19] P. Erdős, A. Rényi, and V. T. Sós.  On a problem of graph theory.  Studia Sci. Math. Hungar., 1:215–235, 1966.
  * [20] P. Erdös.  Über die Primzahlen gewisser arithmetischer Reihen.  Math. Z., 39(1):473–491, 1935.
  * [21] A. M. Frieze and T. Łuczak.  On the independence and chromatic numbers of random regular graphs.  J. Combin. Theory Ser. B, 54(1):123–132, 1992.
  * [22] Z. Füredi, P. Horak, C. M. Pareek, and X. Zhu.  Minimal oriented graphs of diameter $2$.  Graphs Combin., 14(4):345–350, 1998.
  * [23] C. Godsil and G. Royle.  Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 2001.
  * [24] C. Greenhill, S. Janson, and A. Ruciński.  On the number of perfect matchings in random lifts.  Combin. Probab. Comput., 19(5-6):791–817, 2010.
  * [25] G. R. Grimmett and C. J. H. McDiarmid.  On colouring random graphs.  Math. Proc. Cambridge Philos. Soc., 77:313–324, 1975.
  * [26] M. Hall, Jr.  Combinatorial theory.  Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Inc., New York, second edition, 1986.  A Wiley-Interscience Publication.
  * [27] S. Janson.  Poisson convergence and Poisson processes with applications to random graphs.  Stochastic Process. Appl., 26(1):1–30, 1987.
  * [28] S. Janson.  On concentration of probability.  In Contemporary combinatorics, volume 10 of Bolyai Soc. Math. Stud., pages 289–301. János Bolyai Math. Soc., Budapest, 2002.
  * [29] S. Janson, T. Łuczak, and A. Rucinski.  Random Graphs.  Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.
  * [30] G. Kemkes, X. Pérez-Giménez, and N. Wormald.  On the chromatic number of random $d$-regular graphs.  Adv. Math., 223(1):300–328, 2010.
  * [31] W. F. Klostermeyer and G. MacGillivray.  Analogues of cliques for oriented coloring.  Discuss. Math. Graph Theory, 24(3):373–387, 2004.
  * [32] W. F. Klostermeyer and G. MacGillivray.  Homomorphisms and oriented colorings of equivalence classes of oriented graphs.  Discrete Math., 274(1-3):161–172, 2004.
  * [33] A. V. Kostochka, T. Łuczak, G. Simonyi, and E. Sopena.  On the minimum number of edges giving maximum oriented chromatic number.  In Contemporary trends in discrete mathematics (Štiřín Castle, 1997), volume 49 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 179–182. Amer. Math. Soc., Providence, RI, 1999.
  * [34] A. V. Kostochka, E. Sopena, and X. Zhu.  Acyclic and oriented chromatic numbers of graphs.  J. Graph Theory, 24(4):331–340, 1997.
  * [35] C. Koukouvinos and S. Stylianou.  On skew-Hadamard matrices.  Discrete Math., 308(13):2723–2731, 2008.
  * [36] T. Łuczak.  The chromatic number of random graphs.  Combinatorica, 11(1):45–54, 1991.
  * [37] T. Łuczak.  A note on the sharp concentration of the chromatic number of random graphs.  Combinatorica, 11(3):295–297, 1991.
  * [38] M. Molloy.  The chromatic number of sparse random graphs.  PhD thesis, University of Waterloo, 1992.
  * [39] T. S. Motzkin and E. G. Straus.  Maxima for graphs and a new proof of a theorem of Turán.  Canadian J. Math., 17:533–540, 1965.
  * [40] J. Nir and X. P. Giménez.  The chromatic number of random lifts of complete graphs.  arXiv e-prints, page arXiv:2109.13347, 2021.
  * [41] R. Onodera.  Number of trees in a complete n-partite graph.  MATRIX AND TENSOR QUARTERLY, 23(4):142–146, 1973.
  * [42] O. Ramaré and R. Rumely.  Primes in arithmetic progressions.  Math. Comp., 65(213):397–425, 1996.
  * [43] A. Raspaud and E. Sopena.  Good and semi-strong colorings of oriented planar graphs.  Inform. Process. Lett., 51(4):171–174, 1994.
  * [44] K. B. Reid and E. Brown.  Doubly regular tournaments are equivalent to skew Hadamard matrices.  J. Combinatorial Theory Ser. A, 12:332–338, 1972.
  * [45] R. W. Robinson and N. C. Wormald.  Almost all regular graphs are Hamiltonian.  Random Structures Algorithms, 5(2):363–374, 1994.
  * [46] S. Sen.  The maximum order of a planar o-clique is 15.  In Proc. 23rd International Workshop on Combinatorial Algorithms, IWOCA’12, volume 7643 of Lecture Notes in Computer Science (LNCS), pages 130–142. 2021.
  * [47] E. Shamir and J. Spencer.  Sharp concentration of the chromatic number on random graphs $G_{n,p}$.  Combinatorica, 7(1):121–129, 1987.
  * [48] L. Shi and N. Wormald.  Colouring random regular graphs.  Combin. Probab. Comput., 16(3):459–494, 2007.
  * [49] S. S. Shrikhande and Bhagwandas.  Duals of incomplete block designs.  J. Indian Statist. Assoc., 3:30–37, 1965.
  * [50] E. Sopena.  Homomorphisms and colourings of oriented graphs: an updated survey.  Discrete Math., 339(7):1993–2005, 2016.
  * [51] L. Takács.  On the limit distribution of the number of cycles in a random graph.  Number Special Vol. 25A, pages 359–376. 1988.  A celebration of applied probability.
  * [52] J. Wallis.  Some $(1,\,-1)$ matrices.  J. Combinatorial Theory Ser. B, 10:1–11, 1971.
  * [53] J. Williamson.  Hadamard’s determinant theorem and the sum of four squares.  Duke Math. J., 11:65–81, 1944.
  * [54] D. R. Wood.  On the oriented chromatic number of dense graphs.  Contrib. Discrete Math., 2(2):145–152, 2007.
  * [55] N. C. Wormald.  Models of random regular graphs.  In Surveys in combinatorics, 1999 (Canterbury), volume 267 of London Math. Soc. Lecture Note Ser., pages 239–298. Cambridge Univ. Press, Cambridge, 1999.
  * [56] Š. Znám.  The minimal number of edges of a directed graph with given diameter.  Acta Fac. Rerum Natur. Univ. Comenian. Math., 24:181–185, 1970\.


# Light-weight Flexible Magnetic Shields For Large-Aperture Photomultiplier
Tubes

P. DeVore  D. Escontrias  T. Koblesky  C. J. Lin  D. W. Liu  K. B. Luk  J.
Ngan  J. C. Peng  C. Polly  J. Roloff  H. Steiner  S. Wang  J. Wong  M. Yeh
Department of Physics, University of California, Berkeley, CA 94720, U.S.A.
Physics Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720,
U.S.A.  Department of Physics, University of Illinois at Urbana-Champaign,
Urbana, IL 61801, U.S.A.  Department of Physics, Chinese University of Hong
Kong, Hong Kong, China  Chemistry Department, Brookhaven National Laboratory.
Upton, NY 11973, U.S.A.

(August 20, 2013)

###### Abstract

Thin flexible sheets of high-permeability FINEMET® foils encased in thin
plastic layers have been used to shield various types of 20-cm-diameter
photomultiplier tubes from ambient magnetic fields. In the presence of the
Earth’s magnetic field this type of shielding is shown to increase the
collection efficiency of photoelectrons and can improve the uniformity of
response of these photomultiplier tubes.

###### keywords:

Magnetic Shield , Photomultiplier tube , FINEMET

###### PACS:

07.55.Nk , 85.60.Ha

, , , , , , , , , , , , ,

##  1 Introduction

It is well known that the performance of most photomultiplier tubes (PMTs) is
susceptible to even small local magnetic field such as that of the Earth,
which is typically in the range of 0.4 to 0.5 gauss [1]. The impact of this
kind of weak magnetic field can be reduced by shielding the PMT, especially
the region near the photocathode, with high-permeability materials such as mu-
metal.

We describe here a new type of magnetic shield that has been developed at the
Lawrence Berkeley National Laboratory for use in the Daya Bay Reactor Neutrino
Oscillation Experiment [2]. It utilizes FINEMET, a novel thin flexible high-
permeability material, to form a truncated cone around a large-aperture PMT
behind the photocathode. In the following sections we describe the detailed
characteristics of this shield, and present experimental results showing its
impact on the performance of some selected PMTs. In particular we will show
that it reduces variations in the PMT response caused by changes in the
relative orientation of the PMT and magnetic field, and that it significantly
improves the electron collection efficiency of the PMT. These improvements
have a direct impact on the physics objectives of an experiment in that they
result in a greater uniformity of response of the detector, and thereby yield
a more reliable measurement of the energy of an event.

##  2 Effect of Magnetic Field on PMT

We have investigated the effect of the magnetic field on the gain and charge
collection of some large-aperture PMTs. These results are of particular
relevance to experiments where the events of interest produce at most a few
photoelectrons (PEs) in a given PMT. The magnetic field also affects multi-
photoelectron events, but in this case it is not possible to separate the
effects caused by gain variation from those attributable to collection
efficiency. In this study we used Electron Tubes 9354KB [3], Hamamatsu R5912
[4], and Photonis XP1806 [5] 20-cm PMTs.

###  2.1 Effect of Magnetic Field on Collected Amount of Charge

We determined the effect of the local magnetic field on the response of a PMT
by positioning the PMT with its polar axis perpendicular to the field, as
shown in Figure 1(a). The PMT was mounted on a holder that could be rotated
about the polar axis from outside of the dark box containing the PMT. Light
from a pulsing blue LED illuminated the entire photocathode, and its intensity
could be controlled as needed in the study. The charge associated with the PMT
signal was measured with an analog-to-digital converter (ADC) as a function of
the angle between the local magnetic field and a reference on the PMT, denoted
by $\phi$. In this study, the polarized key on the socket of the PMT, shown in
Figure 1(b), was chosen as the reference direction. When this reference
direction was parallel (normal) to the local field, $\phi$ was $0^{\circ}$
($90^{\circ}$).

Figure 1: (a) Orientation of the PMT with respect to the local magnetic field
for evaluating response. (b) PMT reference direction: the polarized key
between pin 1 and pin 20 indicated by the arrow is used as the PMT reference
direction.

The $\phi$-dependence of the charge variation at some operating high voltages
for the Electron Tubes 9354KB, Hamamatsu R5912, and Photonis XP1806 PMTs is
shown in Figures 2, 3 and 4 respectively. The charge variation, $\Delta Q$, is
defined as

$\Delta Q(\phi)=\left(\frac{Q(\phi)-\overline{Q}}{\overline{Q}}\right)\times
100\%$ (1)

where $Q(\phi)$ is the amount of charge collected at angle $\phi$, and
$\overline{Q}$ is the average amount of collected charge given by

$\overline{Q}=\frac{1}{N}\sum_{i=1}^{N}Q(\phi_{i})$ (2)

with $N$ being the number of measurements done at various $\phi$ values.

For each type of PMT the result is quite insensitive to the applied voltage.
The difference in the observed behaviour between the three PMT models is a
consequence of the different designs of the dynode structure and focussing
scheme. Figure 5 shows the opening to the first dynode for these three kinds
of PMTs. Electron Tubes 9354KB has the smallest opening (most affected)
whereas Photonis XP1806 has the largest opening (least affected).

Figure 2: Effect of magnetic field on collecting charge for an unshielded
Electron Tube 9354KB PMT as a function of the angle between the PMT reference
direction and the magnetic field. Figure 3: Effect of magnetic field on
collecting charge for an unshielded Hamamatsu R5912 PMT as a function of the
angle between the PMT reference direction and the magnetic field. Figure 4:
Effect of magnetic field on collecting charge for an unshielded Photonis
XP1806 PMT as a function of the angle between the PMT reference direction and
the magnetic field. Figure 5: Opening to the first dynode. From left to right:
Electron Tubes 9354KB, Hamamatsu R5912, and Photonis XP1809.

###  2.2 Effect of Magnetic Field on Single-photoelectron (SPE) Spectrum

A revealing way to study the influence of the magnetic field on the detected
charge is to use single-photoelectron events. By making this measurement
without a magnetic shield we can directly determine how the shield affects
both the gain and the collection efficiency of the PMT. The SPE spectrum can
be obtained by reducing the light intensity on the photocathode until only
about 10% of the triggers produce a signal. From Poisson statistics about 95%
of the observed pulses are produced by SPEs. The spectrum of the charge
collected at the anode under this condition is shown in Figure 6. Since the
charge of a single electron is known a priori, the calibrated ADC channel of
the SPE peak can be used to determine the absolute gain of the PMT.
Photoelectrons generated at the photocathode are directed to the first dynode
by a set of focussing electrodes. The configuration of the focussing elements
and the effective area of the first dynode determines the collection
efficiency. The Lorentz force, v $\times$ B, on the photoelectrons in the
rather long distance between the photocathode and the first dynode causes some
of them to be swept away from the first dynode and thereby reduces the
collection efficiency. The number of events in the SPE distribution is
proportional to the efficiency of collecting the produced SPE by the first
dynode of the PMT.

Using a Hamamatsu R5912 without a magnetic shield we have obtained SPE spectra
with the PMT reference direction parallel ($\phi=0^{\circ}$) and perpendicular
($\phi=90^{\circ}$) to the local magnetic field. The observed ADC spectrum of
each orientation, a convolution of the SPE distribution and the pedestal, is
shown in Figure 6. The observed spectrum was fitted to two Gaussian functions,
one for the pedestal and the other one for the SPE distribution, and an
exponential function for modeling the non-Gaussian component of the pedestal.
The gain , peak-to-valley ratio (P/V ratio) and charge resolution of the PMT
were obtained from the best fits which are displayed in Figure 6. The results
are tabulated in Table 1. It is interesting to note that the change in gain
between the two orientations is small. From Figure 3, we see a 15% difference
in the charge variation between these two angular positions; that is, the
collection efficiency has changed by about 15%. This result suggests that the
majority of the secondary electrons produced within the dynodes are not
significantly affected by the magnetic field. However, the peak-to-valley
ratio gets worse when the magnetic effect is more pronounced. A series of
measurements was made to determine how the collection efficiency in the
presence of a magnetic field depends on the potential difference between the
photocathode and first dynode. The results showed almost no effect on the
collection efficiency when the potential difference was within 250 V of its
nominal value, typically several hundred volts, for a gain of $10^{7}$.

Figure 6: Magnetic effect on the SPE distribution of a Hamamatsu R5912 without shielding. Figure on the left is obtained with the PMT reference direction parallel to the magnetic field ($\phi=0^{\circ}$); figure on the right is determined with the magnetic field perpendicular to the PMT reference direction ($\phi=90^{\circ}$). The red curve in each figure is the best fit to the spectrum. Table 1: SPE Spectra of a Hamamatsu R5912 in the presence of magnetic field. PMT Orientation | Gain | P/V Ratio | Charge Resolution
---|---|---|---
$\varparallel$ magnetic field ($\phi=0^{\circ}$) | $(1.030\pm 0.003)\times 10^{7}$ | 2.77 $\pm$ 0.12 | 0.343 $\pm$ 0.003
$\perp$ magnetic field ($\phi=90^{\circ}$) | $(1.043\pm 0.004)\times 10^{7}$ | 2.13 $\pm$ 0.11 | 0.333 $\pm$ 0.003

##  3 FINEMET magnetic shield

In this section we describe the magnetic shield made of FINEMET, the material
we used for reducing the effect of magnetic field on the Electron Tubes
9354KB, Hamamatsu R5912, and Photonis XP1806 PMTs.

###  3.1 FINEMET®

FINEMET is a trademark of Hitachi Materials Ltd. for an amorphous metallic
alloy ribbon made up of nano-crystalline grains of iron, silicon, boron, and
small amounts of copper and niobium [6]. As shown in Table 2, this novel soft
magnetic alloy has high saturation magnetic flux density, low core loss, and
high permeability over a wide range of frequencies. Its permeability varies by
less than $\pm$10% between $-50~{}^{\circ}$C and $150~{}^{\circ}$C, with very
small aging effects. We used 0.12-mm-thick FINEMET sheets for fabricating the
magnetic shields. This thin flexible material is made of a layer of 18
$\mu$m-thick FINEMET FT-3M tape laminated with 25-$\mu$m-thick hot-melt
adhesive between two polyethylene terephthalate (PET) films. It can operate in
a temperature range between $-40~{}^{\circ}$C and $80~{}^{\circ}$C. It is
interesting to note that one layer of FINEMET can reduce the local magnetic
field of $4\times 10^{-5}$ T by about 20 dB (from Figure 4 of reference [7]).

Property | Value
---|---
Density | 7300 kg/m3
Resistivity | 1.2 $\mu\Omega$-m
Curie temperature |  570 ∘C
Magnetic flux density (DC H = 800 A/m) | 1.23 T
Maximum relative permeability (DC) | 70,000
Table 2: Selected physical properties of Hitachi FINEMET FT-3M [7].

In addition to the physical properties provided by the manufacturer and listed
in Table 2, we have measured the amount of natural radioactivity of a few
samples of FINEMET. Our results were $(18\pm 5)$ ppb for the 238U series,
$(15\pm 5)$ ppb for the 232Th series, and $(4\pm 2)$ ppm for K, which
translate to decay rates of about 0.2 Bq/kg, 0.06 Bq/kg, and 0.1 Bq/kg for
238U, 232Th, and 40K respectively. We have observed that if it is not stored
in a ventilated location progenies of radon can accumulate gradually on the
surfaces of the laminated FINEMET foil.

Besides radioactivity, we have also investigated the compatibility of FINEMET
with mineral oil and 18-M$\Omega$ ultra-pure water, which are commonly used in
nuclear and particle-physics experiments. By submerging a piece of FINEMET
sample with known dimensions in each liquid at elevated temperature for
accelerated aging studies, the absorbance of the liquid was monitored as a
function of time. For mineral oil at 40 ∘C, with a ratio of contact surface to
liquid volume (S/V) of 0.39 cm-1, its absorbance as a function of wavelength
and time is shown in Figure 7. The change in absorbance due to the presence of
FINEMET is minute for wavelengths between 300 nm and 650 nm. The absorbance of
purified water at 70 ∘C for a FINEMET sample with a S/V of 0.32 cm-1 is
summarized in Figure 8. In the vicinity of 350 nm, the rate of change in
absorbance levels off in about two weeks after a relatively fast degradation
in the beginning. Note that the integrity of FINEMET has not changed in both
liquids.

Figure 7: Absorbance of mineral oil at $40~{}^{\circ}$C as a function of
wavelength for a submerged FINEMET sample. Figure 8: Absorbance of purified
water at $70~{}^{\circ}$C as a function of wavelength for a submerged FINEMET
sample.

###  3.2 Fabrication of Magnetic Shield

As illustrated in Figure 9, a truncated conical magnetic shield for the
Hamamatsu R5912 PMTs used in the Daya Bay Experiment was realized by cutting a
two-dimensional fan out of a piece of FINEMET foil with a water jet. The
conically shaped shield was made by wrapping the fan around the PMT as shown
in Figure 10. It was firmly held in place between the equator of the glass
bulb and the acrylic potting shell surrounding the base by tucking the tabs
into the pre-cut slots. The shield is flexible, so any deformation of the cone
can be taken out easily by simple manipulation of the surface. The weight of
such a FINEMET shield for a typical 20-cm PMT is about 20 g.

Figure 9: Two-dimensional pattern of an unfolded truncated conical FINEMET
magnetic shield. Figure 10: Cross section of a Hamamatsu R5912 PMT used in
Daya Bay with a truncated conical magnetic shield. The dashed line is the
photocathode.

###  3.3 Performance of the FINEMET magnetic shield

The effectiveness of the truncated conical FINEMET shield depends on the slant
height of the cone. For the Hamamatsu R5912 assembly used in the Daya Bay
experiment, the magnetic shield extends from the acrylic sealing shell to the
equator of the bulb, where the photocathode ends. We have evaluated the
performance of the FINEMET magnetic shields with slant heights of 15.4 cm,
16.7 cm, 18.1 cm, 19.2 cm, and 23.0 cm, where the 23 cm-long shield extends to
the plane tangent to the apex of the PMT bulb. The nominal slant height of the
shield used in Daya Bay is 15.4 cm, ending right at the contact point of the
bulb near the equator. For the Photonis XP1806 PMT assembly we used shields
with slant heights of 14.3 cm and 23.6 cm which extended to the equator and
the apex of the PMT bulb respectively. The corresponding slant heights are
14.5 cm and 22.5 cm for the Electron Tubes 5394KB PMT.

####  3.3.1 Improvement on the collection efficiency

With the polar axis of the PMT normal to the local magnetic field as shown in
Figure 1, the amount of collected charge relative to the one without shielding
at $\phi=0^{\circ}$ (relative collection efficiency) for the Hamamatsu R5912
PMT as a function of the slant height of the FINEMET shield for different
$\phi$ angles is shown in Figure 11. The magnetic shield clearly improves the
collection of charge. Relative to the case of without any shielding, a FINEMET
shield with a slant height of 15.4 cm (23.0 cm) improves the average
collection efficiency by 8% (19%). Furthermore, as shown in Figure 12, the
charge variation as a function of the $\phi$ angle is reduced when the slant
height increases. For example, without shielding, the peak-to-peak difference
in the charge variation is about 23%. A FINEMET shield with a slant height of
23.0 cm shrinks this difference to approximately 5%. Even a shield that covers
only up to the equator (15.4 cm) allows us to achieve almost the same
performance. This implies that the shield provides a less non-uniform
collection efficiency to this level over the entire photocathode.

Similarly, the results on collecting charge and minimizing the variation of
the collection efficiency for the Photonis XP1806 and Electron Tubes 9354KB
PMTs with FINEMET shields are depicted in Figures 13, 14, 15 and 16. For the
Photonis XP1806 PMT, on average, the collection efficiency is increased by
about 5% (14%) for a shield with a slant height of 14.3 cm (23.6 cm), and the
variation in the amount of charge collected is reduced from 10% to 1.3% which
is close to our systematic limit. The most dramatic improvement is achieved
with the Electron Tubes 9354KB PMT. In this case the average collection
efficiency is up by about 25% for a FINEMET shield extending to the equator
and 40% for shields reaching to the apex of the PMT bulb. The variation in the
collection efficiency is reduced from 46% with no shield to 21% (5%) for a
shield with a slant height of 14.5 cm (22.5 cm).

Figure 11: Relative collection efficiency as a function of the slant height of
truncated conical FINEMET shield for a Hamamatsu R5912 PMT oriented at
different $\phi$ angles. Figure 12: Charge variation due to magnetic field for
Hamamatsu R5912 PMT with FINEMET shields of different slant heights. Figure
13: Relative collection efficiency as a function of slant height of truncated
conical FINEMET shield for a Photonis XP1806 PMT oriented at different $\phi$
angles. Figure 14: Charge variation due to magnetic field for Photonis XP1806
PMT with FINEMET shields of different slant heights. Figure 15: Relative
collection efficiency as a function of slant height of truncated conical
FINEMET shield for an Electron Tubes 9354KB PMT oriented at different $\phi$
angles. Figure 16: Charge variation due to magnetic field for Electron Tubes
9354KB PMT with FINEMET shields of different slant heights.

####  3.3.2 Improvement on the SPE Spectrum

In Table 3 we summarize the results on the SPE spectrum for the Hamamatsu
R5912 PMT with FINEMET shields of different sizes. Compared to the results for
the case without shielding (Table 1), we see that the shield can improve the
gain by 5%, P/V ratio by up to 17% (34%) for $\phi=0^{\circ}$ ($90^{\circ}$),
and charge resolution by less than 10%. Furthermore, the variation of the P/V
ratio due to different orientation of the PMT relative to the magnetic field
is significantly reduced. Consequently the systematic uncertainty in the
charge measurement is minimized.

Table 3: Characteristics of the SPE Spectrum for a Hamamatsu R5912 PMT with FINEMET magnetic shields of different slant heights. PMT Reference Direction | Gain | P/V Ratio | Charge Resolution
---|---|---|---
Slant height = 15.4 cm
$\varparallel$ magnetic field ($\phi=0^{\circ}$) | $(1.080\pm 0.003)\times 10^{7}$ | 3.27 $\pm$ 0.18 | 0.316 $\pm$ 0.002
$\perp$ magnetic field ($\phi=90^{\circ}$) | $(1.092\pm 0.003)\times 10^{7}$ | 2.86 $\pm$ 0.14 | 0.324 $\pm$ 0.003
Slant height = 18.1 cm
$\varparallel$ magnetic field ($\phi=0^{\circ}$) | $(1.091\pm 0.003)\times 10^{7}$ | 3.17 $\pm$ 0.16 | 0.311 $\pm$ 0.002
$\perp$ magnetic field ($\phi=90^{\circ}$) | $(1.088\pm 0.03)\times 10^{7}$ | 3.03 $\pm$ 0.15 | 0.318 $\pm$ 0.003
Slant height = 23.0 cm
$\varparallel$ magnetic field ($\phi=0^{\circ}$) | $(1.081\pm 0.003)\times 10^{7}$ | 3.20 $\pm$ 0.16 | 0.315 $\pm$ 0.002
$\perp$ magnetic field ($\phi=90^{\circ}$) | $(1.085\pm 0.003)\times 10^{7}$ | 2.93 $\pm$ 0.14 | 0.311 $\pm$ 0.002

####  3.3.3 Position-dependence of PMT Response

We determined the response of a Hammamatsu R5912 PMT at each point of a grid
on the photocathode by measuring the PE spectrum with a pulsing LED [8]. The
orientation of the PMT is shown in Figure 17. We split the light pulse from
the LED into two parts with optical fibers. One part of the LED light was sent
to a reference PMT to monitor the intensity of the LED, and the other part to
the photocathode of the Hamamatsu PMT. A collimator was used to limit the spot
size of the incident light at the photocathode to a circle with a radius of 2
mm. The LED intensity was set to produce at least 20 photoelectrons per pulse
on the photocathode. Runs of ten seconds duration at a pulse rate of 100 Hz
were used to measure the response of the PMT for every point on the
photocathode. An ADC was gated by the pulse generator used to drive the LED. A
computer recorded the integrated counts in each ADC channel for each run. The
light source was moved under computer control to the next point on the grid
until the whole surface of the photocathode was scanned.

Figure 17: (a) Orientation of the photocathode of a Hamamatsu R5912 PMT with
respect to the local magnetic field. The x-y plane is normal to the polar axis
of the PMT. The magnetic field is along the negative-y direction. (b)
Position-dependent response of a Hamamatsu R5912 PMT with no magnetic shield.
The colored scale is the average number of detected PEs. Figure 18: Position-
dependent response of a Hamamatsu R5912 PMT with a FINEMET shield (a) with a
slant height of 15.4 cm, (b) with a slant height of 20.5 cm. The colored scale
is the average number of detected PEs.

In the absence of any magnetic field we expect rather uniform collection
efficiency over the photocathode. However, the Earth’s magnetic field in the
transverse direction creates a position-dependent response. In this case the
field acting on a PMT with no shielding produces large non-uniformity as shown
in Figure 17. The lowest collection efficiency occurs in a region centered at
x $\approx$ 6 cm and y = 0 cm. In addition, the response of the PMT is almost
symmetric about the x-axis. This result is a direct consequence of the fact
that the internal structure of the PMT is symmetric about the x-axis, so that
with the magnetic field in the negative y-direction the response of the PMT
should be symmetric across the x-axis. This symmetry should not exist for the
y-axis because the internal structure of the PMT is different across the
y-axis, and also because a magnetic field in the negative y-direction will
affect the motion of electrons in the x-direction.

A FINEMET shield around the PMT makes the response more uniform over the whole
photocathode. The results for the shields with slant height of 15.4 cm and
20.5 cm are presented in Figure 18. The 20.5-cm shield has a more uniform
response than the 15.4-cm shield, although even with this long shield there
are still significant residual non-uniformities. However, both of these
shields clearly produce a better performance for the PMT than that obtained
with no shield.

##  4 Conclusions

We have presented the performance of a truncated conical magnetic shield made
of FINEMET. Mechanically, it is thin, light, flexible, relative cheap, and
easy to handle. In addition, the laminated FINEMET sheet is compatible with
mineral oil and purified water. We have demonstrated that FINEMET is very
effective in shielding large-aperture PMTs against magnetic field. As a
result, the collection efficiency of the PMT is improved and the response of
the PMT is more uniform across the entire photocathode.

##  5 Acknowledgements

We would like to express our gratitude to the technical staffs of the Lawrence
Berkeley National Laboratory for their excellent support. This work was
partially supported by the Director, Office of Science, Office of Basic Energy
Sciences, Office of High Energy Physics, of the U.S. Department of Energy
under Contract No. DE-AC02-05CH11231and DE-AC02-98CH10886, the U.S. National
Science Foundation, the Research Grant Council of the Hong Kong Special
Administrative Region, China (Project Nos. CUHK 1/07C and CUHK3/CRF/10). J.N.
and J. W. were also partially supported by the Department of Physics, Chinese
University of Hong Kong.

## References

  * [1] Hamamatsu Photonics, ”Photomultiplier Tubes: Basics and Applications”, 3rd Edition, (2007).
  * [2] X. Guo et. al. (Daya Bay Collaboration), hep-ex/0701029 (2007).
  * [3] Electron Tubes 9354KB Data Sheet, Electron Tubes Inc., Sept., 2002.
  * [4] Hamamatsu R5912 Data Sheet, Hamamatsu Co., Sept., 1998.
  * [5] Photonis Hemispherical PMT Data Sheet, Photonis Co, Sept., 2006.
  * [6] R. Lebourgeois et al., J. Magn. Magn. Mater. 254-255, 191 (2003).
  * [7] Catalog number HL-FM16-F, Hitachi Metals, Ltd. (http://www.hitachi-metals.co.jp).
  * [8] T. Koblesky et. al., Nucl. Instrum. Method A670, 40 (2012).