# Weighted Domination and Colouring in Random Graphs

Ghurumuruhan Ganesan

IISER, Bhopal E-Mail<EMAIL_ADDRESS>
###### Abstract

In the first part of this paper, we consider weighted domination in the case
where the vertices of the complete graph on $n$ vertices are equipped with
independent and identically distributed (i.i.d.) weights. We use the
probabilistic iteration to determine sufficient conditions for maximizing the
weighted domination probability. In the second part, we study a weighted
generalization of the chromatic number and estimate the minimum number of
colours needed to satisfy the constraints when the weights themselves are
random. We show that the “extra” cost incurred for weighted colouring is small
if the weights have sufficiently large moments. We also consider inhomogenous
random graphs where the edge probabilities are not necessarily all same and
obtain bounds for the chromatic number in terms of its averaged edge
probabilities.

Key words: Weighted Domination; Maximum Domination Probability; Weighted
Colouring; Inhomogenous Random graphs,

AMS 2020 Subject Classification: Primary: 60C05.

##  1 Introduction

In this section, we describe briefly the two problems studied in this paper.

### Weighted Domination

Records in a sequence of independent and identically distributed (i.i.d.)
random variables have been extensively studied in the context of statistical
estimation. The probability that the $k^{th}$ random variable is a record (as
compared to the previous $k-1$ values) grows inversely in the index $k$ and
the corresponding record events are mutually independent [15]. Various aspects
of record properties with differing assumptions have been studied since and as
examples, [4] study large deviation properties for weak records and [11]
studies characterizations of geometric distributions based on $k^{th}$ record
values. Also, [7] study records in a sequence of maximally dependent random
variables and obtain expressions for corresponding record moments and
distributions.

In this paper, we study records from a graph theoretic view point and use
probabilistic iteration to estimate the probability that a given set of
vertices form a weighted dominating set.

### Weighted Colouring

The chromatic number $\chi(G)$ of a graph $G$ is the smallest number of
colours needed for a proper colouring of $G$ and many upper and lower bounds
for $\chi(G)$ exist in terms of various graph parameters like maximum vertex
degree, independence number, clique number etc. (see Chapter $5,$ [19]). For
homogenous random graphs where each edge is present with the same probability
$p_{n},$ concentration of the chromatic number around its mean has been well-
studied [18, 6, 17]. Many bounds for the expected chromatic number have also
been derived using clique sizes in the complement graph and a combination of
second moment and martingale methods [5, 2]. The paper [16] uses counting
arguments to obtain sharp lower bounds on the chromatic number. In a related
direction, [3] obtain two point concentration of the chromatic number for edge
probability $p_{n}=n^{-1/2-\delta}$ with $\delta>0.$ The analysis proceeds
through $k-$choosable graphs. Extending this to $p_{n}=\frac{d}{n},$ [1] use
analytical techniques to obtain the two possible values of the chromatic
number for $d>0$ a constant.

Recently, in [10] we have studied the chromatic number of homogenous random
graphs whose edge probabilities do not necessarily form a convergent sequence.
In the first part of this paper, we obtain estimates for the chromatic number
of an inhomogenous graph in terms of averaged edge probabilities. We use an
auxiliary bound for chromatic number of a deterministic graph, in terms of its
maximum averaged degree, that is of independent interest.

In the second part of this paper, we study weighted colouring in random
graphs. Generalizing radio labelling of graphs [8, 12] which we call as
weighted colouring number, we use the probabilistic method to estimate the
weighted colouring number when the edge weights themselves are random. Such
situations arise frequently in applications and we show that if the weights
have sufficiently large moments, then the “cost” incurred due to the
unboundedness of weights is small.

The paper is organized as follows: In the following section, we state and
prove our first main result regarding maximizing the domination probability in
weighted random graphs. Next, in Section 3 we state and prove our two main
results regarding weighted and constrained colouring in random graphs and
finally, in Section 4, we collect the auxiliary combinatorial lemmas used in
the proof of the main theorems.

##  2 Weighted Domination

In this section, we study domination in weighted random graphs obtained as
follows. Let $K_{n}$ be the complete graph on $n$ vertices and equip vertex
$v$ with a random weight $S_{v}.$ The random variables $\\{S_{v}\\}_{1\leq
v\leq n}$ are i.i.d. continuous with a common cumulative distribution function
(cdf) $F.$ For each vertex $v,$ we now associate a _deterministic_ domination
neighbourhood ${\cal D}(v)\subset\\{1,2,\ldots,n\\}\setminus\\{v\\}$ and say
that $v$ is a _weighted dominating vertex_ if $S_{v}>\max_{u\in{\cal
D}(v)}S_{u}.$ Similarly, we say that a finite set of vertices ${\cal
V}:=\\{v_{1},\ldots,v_{k}\\}$ is a _weighted dominating set_ if each vertex in
${\cal V}$ is a weighted dominating vertex.

Let $E_{dom}=E_{dom}({\cal V})$ be the event that ${\cal V}$ is a weighted
dominating set and also let $R_{tot}:=\sum_{1\leq l\leq k}1{1}(A_{v_{l}})$ be
the total number of weighted dominating vertices in ${\cal V}.$ For any vertex
$v,$ we have by symmetry that $\mathbb{P}(A_{v})=\frac{1}{d(v)},$ where
$d(v)=1+\\#{\cal D}(v)$ and $\\#{\cal D}(v)$ is the size of the domination
neighbourhood of $v.$ Therefore if the vertices in ${\cal V}$ have disjoint
domination neighbourhoods, then the events $A_{v},v\in{\cal V}$ are
independent and so

$\mathbb{P}(E_{dom})=\prod_{l=1}^{k}\frac{1}{d(v_{l})}=:p_{dom}.$

In general, if the domination neighbourhoods are not disjoint, the events
$A_{v},v\in{\cal V}$ are correlated and so we expect that $E_{dom}$ occurs
with lesser probability, as described in the following result. Recalling that
${\cal V}=\\{v_{1},\ldots,v_{k}\\}$ with $v_{1}<v_{2}<\ldots<v_{k},$ we define
${\cal C}(v_{l}):=\bigcup_{j=1}^{l}{\cal D}(v_{j})$ and set
$c(v_{l}):=1+\\#{\cal C}(v_{l})$ for $1\leq l\leq k.$

######  Theorem 1.

If $\int_{0}^{x}F^{k-1}(y)dF(y)=\frac{F^{k}(x)}{k}$ for each integer $k\geq 1$
and $x>0$ and

$v_{k}\notin{\cal C}(v_{k})\text{ and }v_{l}\in{\cal D}(v_{l+1})\setminus{\cal
C}(v_{l})\text{ for each }1\leq l\leq k-1,$ (2.1)

then

$\mathbb{P}\left(E_{dom}\right)=\prod_{1\leq l\leq k}\frac{1}{c(v_{l})}\leq
p_{dom}\text{ and
}var(R_{tot})\leq\mathbb{E}R_{tot}=\sum_{l=1}^{k}\frac{1}{d(v_{l})}.$ (2.2)

Moreover, the events $\\{A_{v_{l}}\\}_{1\leq l\leq k}$ are mutually
independent if and only if
${\cal D}(v_{l})\subset{\cal D}(v_{l+1})$ strictly, for each $1\leq l\leq
k-1.$

In words, the above result says that if the domination neighbourhoods satisfy
the “weak-nested” property (2.1), then $p_{dom}$ is the maximum possible
weighted domination probability and moreover, this value is achieved only if
the neighbourhoods satisfy a strong-nested property.

From a statistical view point, we could also interpret Theorem 1 as a “graph-
theoretic” version of records. For context, we recall that “time-based” record
events in a sequence of i.i.d. random variables are known to be mutually
independent when the comparison set consists of the entire past [15]. From
Theorem 1, we see that graph-theoretic record events are _negatively
correlated_ for weakly nested neighbourhoods and are mutually independent for
strongly nested neighbourhoods.

_Proof of Theorem 1_: Let $B_{k}:=\bigcap_{j=1}^{k}A_{v_{j}}$ and for $x>0$
define

$A_{v_{k}}(x):=A_{v_{k}}\bigcap\left\\{S_{v_{k}}<x\right\\}=\left\\{\max_{j\in{\cal
D}(v_{k})}S_{j}<S_{v_{k}}<x\right\\}$ (2.3)

and $B_{k}(x):=B_{k-1}\bigcap A_{v_{k}}(x),$ with the notation that the
maximum of the empty set is zero and $B_{0}=\Omega.$ We first show by
induction that for every $x>0,$

$\mathbb{P}(B_{k}(x))=\frac{F^{c(v_{k})}(x)}{c(v_{1})\cdots
c(v_{k})}=\mathbb{P}(B_{k})\cdot F^{c(v_{k})}(x).$ (2.4)

For the basis step, we see that the random variable $X$ with cdf $F$ is
continuous and so $F(x)=\mathbb{P}(X\leq x)=\mathbb{P}(X<x).$ Conditioning on
$S_{v_{1}}=y,$ we therefore get that
$\mathbb{P}\left(B_{1}(x)\right)=\int_{0}^{x}\mathbb{P}\left(\max_{j\in{\cal
D}(v_{1})}S_{j}<y\right)dF(y)$ equals

$\int_{0}^{x}\mathbb{P}\left(\bigcap_{j\in{\cal
D}(v_{1})}\\{S_{j}<y\\}\right)dF(y)=\int_{0}^{x}F^{d(v_{1})-1}(y)dF(y)=\frac{F^{d(v_{1})}(x)}{d(v_{1})}.$
(2.5)

Since $d(v_{1})=c(v_{1})$ this proves the basis step.

To prove the induction step, we now assume that the relation (2.4) is true for
the event $B_{k-1}(x)$ and consider the event $B_{k}(x).$ If
$B_{k-1}=\bigcap_{j=1}^{k-1}A_{v_{j}}$ occurs, then using the weak nested
property in the statement of the theorem, we already have
$S_{v_{k-1}}>\max_{l\in{\cal C}(v_{k-1})}S_{v_{l}}$ and so $S_{v_{k}}$ is a
record if and only if $S_{v_{k}}>\max_{j\in{\cal E}_{k}}S_{j}$ and
$S_{v_{k}}>S_{v_{k-1}},$ where ${\cal E}_{k}:={\cal
D}(v_{k})\setminus\left({\cal C}(v_{k-1})\cup v_{k-1}\right).$ Letting
$1{1}(.)$ denote the indicator function, we then have that

$\displaystyle 1{1}\left(B_{k}(x)\right)$ $\displaystyle=$ $\displaystyle
1{1}\left(A_{v_{k}}(x)\bigcap B_{k-1}\right)$ (2.6) $\displaystyle=$
$\displaystyle 1{1}\left(x>S_{v_{k}}>\max_{j\in{\cal
E}_{k}}S_{j}\right)1{1}(x>S_{v_{k}}>S_{v_{k-1}})1{1}(B_{k-1})$

and since the event $B_{k-1}$ depends only on the values of
$\\{S_{j}\\}_{j\in{\cal C}(v_{k-1})\cup\\{v_{k-1}\\}},$ we condition on
$S_{v_{k}}=z$ and get from (2.6) that
$\mathbb{P}\left(B_{k}(x)\right)=\int_{z=0}^{x}t_{k}(z)dF(z)$ where

$\displaystyle t_{k}(z)$ $\displaystyle:=$
$\displaystyle\mathbb{P}\left(\max_{j\in{\cal
E}_{k}}S_{j}<z\right)\mathbb{P}\left(B_{k-1}\bigcap\left\\{S_{v_{k-1}}<z\right\\}\right)$
(2.7) $\displaystyle=$ $\displaystyle\prod_{j\in{\cal
E}_{k}}\mathbb{P}(S_{j}<z)\mathbb{P}\left(B_{k-1}\bigcap\left\\{S_{v_{k-1}}<z\right\\}\right).$

To evaluate (2.7), we use the weak nested property $v_{k-1}\in{\cal
D}(v_{k})\setminus{\cal C}(v_{k-1})$ to get that ${\cal E}_{k}={\cal
D}(v_{k})\setminus\left({\cal C}(v_{k-1})\cup v_{k-1}\right)$ has cardinality
$c(v_{k})-c(v_{k-1})-1.$ Consequently

$\displaystyle t_{k}(z)$ $\displaystyle=$ $\displaystyle
F^{c(v_{k})-c(v_{k-1})-1}(z)\mathbb{P}\left(B_{k-1}\bigcap\left\\{S_{v_{k-1}}<z\right\\}\right)$
$\displaystyle=$ $\displaystyle
F^{c(v_{k})-c(v_{k-1})-1}(z)\mathbb{P}\left(B_{k-1}(z)\right)$

and substituting this into the expression for $\mathbb{P}(B_{k}(x))$
determined prior to (2.7), we get

$\mathbb{P}\left(B_{k}(x)\right)=\int_{0}^{x}F^{c(v_{k})-c(v_{k-1})-1}(z)\mathbb{P}\left(B_{k-1}(z)\right)dF(z).$

By induction assumption we have
$\mathbb{P}\left(B_{k-1}(z)\right)=\frac{F^{c(v_{k-1})}(z)}{c(v_{1})\cdot
c(v_{2})\cdots c(v_{k-1})}$ and so

$\displaystyle\mathbb{P}\left(B_{k}(x)\right)$ $\displaystyle=$
$\displaystyle\frac{1}{c(v_{1})\cdot c(v_{2})\cdots
c(v_{k-1})}\int_{0}^{x}F^{c(v_{k})-1}(z)dF(z)$ (2.8) $\displaystyle=$
$\displaystyle\frac{1}{c(v_{1})\cdot c(v_{2})\cdots c(v_{k})}F^{c(v_{k})}(x).$

This proves the induction step and therefore completes the proof of (2.4).

The first relation in (2.2) follows directly from (2.4) by setting $x=\infty.$
Moreover, $var(R_{tot})=V_{1}+2V_{2}$ where

$V_{1}=\sum_{l=1}^{k}\mathbb{P}(A_{v_{l}})-\left(\mathbb{P}(A_{v_{l}})\right)^{2}=\sum_{l=1}^{k}\left(\frac{1}{d(v_{l})}-\frac{1}{d^{2}(v_{l})}\right)\leq\sum_{l=1}^{k}\frac{1}{d(v_{l})}=\mathbb{E}R_{tot}$

and $V_{2}=\sum_{1\leq l_{1}<l_{2}\leq k}\left(\mathbb{P}(A_{v_{l_{1}}}\cap
A_{v_{l_{2}}})-\mathbb{P}(A_{v_{l_{1}}})\mathbb{P}(A_{v_{l_{2}}})\right)\leq
0$ by the first relation in (2.2). This completes the proof of (2.2).

For the mutual independence part, suppose that ${\cal D}(v_{l})\subset{\cal
D}(v_{l+1})$ so that
$c(v_{l})=d(v_{l})$ for $1\leq l\leq k.$ From (2.4), we then get that

$\displaystyle\mathbb{P}\left(B_{k}(x)\right)$ $\displaystyle=$
$\displaystyle\frac{1}{d(v_{1})\cdot d(v_{2})\cdots
d(v_{k-1})}\frac{F^{d(v_{k})}(x)}{d(v_{k})}$ (2.9) $\displaystyle=$
$\displaystyle\left(\prod_{j=1}^{k-1}\mathbb{P}\left(A_{v_{j}}\right)\right)\mathbb{P}\left(A_{v_{k}}(x)\right)$

and so the events $\\{A_{v_{l}}\\}_{1\leq l\leq k-1}\cup A_{v_{k}}(x)$ are
also mutually independent. Setting $x=\infty$ and using induction on $k,$ we
then get that $\\{A_{v_{l}}\\}_{1\leq l\leq k}$ are mutually independent.

Conversely suppose that $\\{A_{v_{l}}\\}_{1\leq l\leq k}$ are mutually
independent. By definition we know that $d(v_{1})=c(v_{1})$ and by (2.2), we
have that

$\frac{1}{c(v_{1})\cdot c(v_{2})}=\mathbb{P}\left(A_{v_{1}}\bigcap
A_{v_{2}}\right)=\mathbb{P}(A_{v_{1}})\mathbb{P}(A_{v_{2}})=\frac{1}{d(v_{1})}\cdot\frac{1}{d(v_{2})}.$

Consequently $c(v_{2})=d(v_{2})$ and so using

$\displaystyle c(v_{2})$ $\displaystyle=$ $\displaystyle 1+\\#\left({\cal
D}(v_{1})\cup{\cal D}(v_{2})\right)$ $\displaystyle=$ $\displaystyle
1+\\#\left({\cal D}(v_{2})\right)+\\#\left({\cal D}(v_{1})\setminus{\cal
D}(v_{2})\right)$ $\displaystyle=$ $\displaystyle d(v_{2})+\\#\left({\cal
D}(v_{1})\setminus{\cal D}(v_{2})\right),$

we get that ${\cal D}({v_{1}})\setminus{\cal D}(v_{2})=\emptyset.$ In other
words ${\cal D}(v_{1})\subseteq{\cal D}(v_{2})$ and since $v_{1}\in{\cal
D}(v_{2})\setminus{\cal D}(v_{1}),$ we get that ${\cal D}(v_{1})\subset{\cal
D}(v_{2}),$ strictly. The same argument repeated with the vertices $v_{2}$ and
$v_{3}$ gives that ${\cal D}(v_{2})\subset{\cal D}(v_{3}).$ Continuing this
way for $k$ iterations completes the proof of the Theorem.

##  3 Constrained Colouring

Let $K_{n}$ be the complete graph on $n$ vertices and let $X_{f},f\in K_{n}$
be independent and identically distributed (i.i.d.) Bernoulli random variables
with

$\mathbb{P}(X_{f}=1)=p(f)=1-\mathbb{P}(X_{f}=0)$ (3.1)

where $0\leq p(f)\leq 1.$ Let $G$ be the random subgraph of $K_{n}$ formed by
the set of all edges satisfying $X_{f}=1.$ If $p(f)=p$ for all edges $f,$ then
$G$ is said to be _homogenous_ ; otherwise we say that $G$ is _inhomogenous_.
In this paper, we are mainly interested in colouring numbers of inhomogenous
random graphs with constraints.

We begin with some well-known definitions. For an integer $k\geq 1,$ a proper
$k-$colouring of $G$ is a map $g:V\rightarrow\\{1,2,\ldots,k\\}$ such that
$g(u)\neq g(v)$ for all edges $(u,v)\in E.$ The chromatic number $\chi(G)$ is
the smallest integer $k$ such that $G$ admits a proper $k-$colouring. It is
well-known (see for example Theorem $2,$ Ganesan (2020)) that if $G$ is
homogenous with edge probability $p(f)=p=\frac{1}{n^{\beta}}$ for some
constant $0<\beta<1,$ then there are constants $C_{1},C_{2}>0$ such that

$\mathbb{P}\left(\frac{C_{1}n^{1-\beta}}{\log{n}}\leq\chi(G)\leq\frac{C_{2}n^{1-\beta}}{\log{n}}\right)=1-o(1),$
(3.2)

where $o(1)\longrightarrow 0$ as $n\rightarrow\infty.$

The following result obtains upper and lower bounds for the chromatic number
of an inhomogenous random graph $G,$ in terms of “averaged” edge
probabilities.

######  Theorem 2.

Suppose there are constants $0\leq\beta_{up}\leq\beta_{low}\leq\alpha$ and
positive constants $C_{1},C_{2}$ such that

$\frac{C_{1}}{n^{\beta_{low}}}\leq\frac{1}{{l\choose 2}}\sum_{u,v\in{\cal
V}}p(u,v)\leq\frac{C_{2}}{n^{\beta_{up}}}$ (3.3)

for any set ${\cal V}\subseteq V$ containing $l\geq n^{\alpha}(\log{n})^{3}$
vertices. There are positive constants $D_{i},1\leq i\leq 4$ such that

$\mathbb{P}\left(\chi(G)\geq\frac{n^{1-\alpha}}{(\log{n})^{3}}\right)\geq
1-\exp\left(-D_{2}\cdot n^{2\alpha-\beta_{low}}\cdot(\log{n})^{6}\right)$
(3.4)

and

$\mathbb{P}\left(\chi(G)\leq
D_{3}n^{\max(\alpha,1-\beta_{up})}\cdot(\log{n})^{4}\right)\geq
1-\exp\left(-D_{4}n^{2\alpha-\beta_{low}}\cdot(\log{n})^{5}\right)$ (3.5)

for all $n$ large.

We prove the lower bound in (3.5) by obtaining an upper bound for the maximum
size of a stable set and prove the upper bound in (3.5) using a maximum
average degree estimate for the chromatic number, obtained in Lemma 4 of
Section 4. We provide the details below. Throughout, we use the following
standard Deviation Estimate. Let $Z_{i},1\leq i\leq t$ be independent
Bernoulli random variables satisfying

$\mathbb{P}(Z_{i}=1)=p_{i}=1-\mathbb{P}(Z_{i}=0).$

If $W_{t}=\sum_{i=1}^{t}Z_{i}$ and $\mu_{t}=\mathbb{E}W_{t},$ then for any
$0<\epsilon<\frac{1}{2}$ we have that

$\mathbb{P}\left(\left|W_{t}-\mu_{t}\right|\geq\epsilon\mu_{t}\right)\leq
2\exp\left(-\frac{\epsilon^{2}}{4}\mu_{t}\right).$ (3.6)

For a proof of (3.6), we refer to Corollary $A.1.14,$ pp. $312,$ Alon and
Spencer (2008).

_Proof of ( 3.4) in Theorem 2_: For a set of vertices ${\cal V}$ of size
$\\#{\cal V}=l,$ let

$p_{av}({\cal V}):=\frac{1}{{l\choose 2}}\sum_{u,v\in{\cal V}}p(u,v)$ (3.7)

be the average edge probability of edges formed by the vertices of ${\cal V}.$
For a constant $0<\alpha<1$ set

$p_{low}:=\min_{{\cal V}}p_{av}({\cal V})\leq\max_{{\cal V}}p_{av}({\cal
V})=:p_{up}$ (3.8)

where the minimum and maximum are taken over all sets ${\cal V}$ of
cardinality $l$ satisfying $n^{\alpha}\cdot(\log{n})^{3}\leq l\leq n.$

If $\alpha(G)$ is the largest size of a stable set in the random graph $G,$
then we know that (Proposition $5.1.7,$ pp. 193, West (2000))

$\chi(G)\geq\frac{n}{\alpha(G)}.$ (3.9)

To estimate the probability of the event $\\{\alpha(G)\geq t\\},$ we let
${\cal V}$ be any set of $t$ vertices and let $F({\cal V})$ be the event that
${\cal V}$ is a stable set. We have that

$\mathbb{P}\left(F({\cal V})\right)=\prod_{u\neq v\in{\cal
V}}\left(1-p(u,v)\right)\leq e^{-{t\choose 2}\cdot p_{av}({\cal V})},$

where $p_{av}({\cal V})$ is as defined in (3.7). Using (3.3), we get that

$\mathbb{P}\left(F({\cal V})\right)\leq\left(-{t\choose
2}\cdot\frac{C_{1}}{n^{\beta_{low}}}\right)\leq e^{-D_{1}t^{2}\cdot
n^{-\beta_{low}}}$

for some constant $D_{1}>0.$ Therefore letting $F_{tot}:=\bigcup_{\cal
V}F({\cal V})$ where the union is over all sets of size $t,$ we get by the
union bound that

$\mathbb{P}\left(F_{tot}\right)\leq{n\choose t}\cdot e^{-D_{1}t^{2}\cdot
n^{-\beta_{low}}}\leq n^{t}\cdot e^{-D_{1}t^{2}\cdot n^{-\beta_{low}}}.$
(3.10)

For $t=n^{\alpha}\cdot(\log{n})^{3},$ we have that

$\displaystyle n^{t}\cdot e^{-D_{1}t^{2}\cdot n^{-\beta_{low}}}$
$\displaystyle=$
$\displaystyle\exp\left(-t\log{n}\left(D_{1}n^{\alpha-\beta_{low}}(\log{n})^{2}-1\right)\right)$
(3.11) $\displaystyle\leq$ $\displaystyle\exp\left(-2D_{2}\cdot
tn^{\alpha-\beta_{low}}\cdot(\log{n})^{3}\right)$ $\displaystyle=$
$\displaystyle\exp\left(-2D_{2}\cdot
n^{2\alpha-\beta_{low}}\cdot(\log{n})^{6}\right),$

for some constant $D_{2}>0.$

Substituting (3.11) into (3.10) we get that

$\mathbb{P}(F_{tot})\leq\exp\left(-2D_{2}\cdot
n^{2\alpha-\beta_{low}}\cdot(\log{n})^{6}\right)$

for all $n$ large. If the complement event $F^{c}_{tot}$ occurs, then the
largest size of the stable set $\alpha(H)\leq n^{\alpha}\cdot(\log{n})^{3}.$
Plugging this into (3.9), we get that

$\mathbb{P}\left(\chi(H)\geq\frac{n^{1-\alpha}}{(\log{n})^{3}}\right)\geq
1-\exp\left(-D_{2}\cdot n^{2\alpha-\beta_{low}}\cdot(\log{n})^{6}\right)$

and this proves (3.4).

_Proof of ( 3.5) in Theorem 2_: We prove (3.5) using the estimate (4.1) of
Lemma 4$(b)$ for $\chi(G)$ and the estimate (4.4) for the maximum average
degree $h_{av}(G),$ in the proof of Lemma 4$(a).$

For a set ${\cal V}\subseteq\\{1,2,\ldots,n\\}$ of size $\\#{\cal V}=l,$ let
$m({\cal V})$ be the random number of edges in the induced subgraph $H_{\cal
V}$ of $H$ formed by the vertices of ${\cal V}.$ The expected number of edges
in $H_{\cal V}$ is

$\mathbb{E}m({\cal V})={l\choose 2}p_{av}({\cal V})$

and so by the standard deviation estimate (3.6) we have for
$0<\epsilon<\frac{1}{2}$ that

$\mathbb{P}\left(m({\cal V})\geq{l\choose 2}p_{av}({\cal
V})(1+\epsilon)\right)\leq\exp\left(-\frac{\epsilon^{2}}{4}{l\choose
2}p_{av}({\cal V})\right).$

We henceforth set $\epsilon=\frac{1}{\sqrt{\log{n}}}.$ If
$n^{\alpha}\cdot(\log{n})^{3}\leq l\leq n$ then we have from (3.8) that

$\mathbb{P}(m({\cal V})\geq{l\choose
2}p_{up}(1+\epsilon))\leq\exp\left(-\frac{\epsilon^{2}}{4}{l\choose
2}p_{low}\right)\leq\exp\left(-\frac{l^{2}\epsilon^{2}}{16}p_{low}\right).$
(3.12)

Defining the event

$E_{bad}:=\bigcup_{n^{\alpha}\leq\\#{\cal V}=l\leq n}\left\\{m({\cal
V})\geq{l\choose 2}p_{up}(1+\epsilon)\right\\}$ (3.13)

we have from (3.12) and the union bound that

$\mathbb{P}(E_{bad})\leq\sum_{n^{\alpha}\leq l\leq n}{n\choose
l}\cdot\exp\left(-\frac{l^{2}\epsilon^{2}}{16}p_{low}\right)$ (3.14)

Using ${n\choose l}\leq n^{l}$ we have that

${n\choose l}\cdot\exp\left(-\frac{l^{2}\epsilon^{2}}{16}p_{low}\right)\leq
n^{l}\cdot\exp\left(-\frac{l^{2}\epsilon^{2}}{16}p_{low}\right)=\exp(-A_{l}),$
(3.15)

where $A_{l}=A_{l}(n):=l\left(\frac{l\epsilon^{2}\cdot
p_{low}}{16}-\log{n}\right).$ Since $\epsilon=\frac{1}{\sqrt{\log{n}}}$ and
$l\geq n^{\alpha}\cdot(\log{n})^{3},$ we have that

$l\epsilon^{2}\cdot p_{low}\geq n^{\alpha}p_{low}\cdot(\log{n})^{2}\geq
C_{1}\cdot n^{\alpha-\beta_{low}}\cdot(\log{n})^{2},$

by (3.3) and so using $\alpha\geq\beta_{low}$ and we get that

$A_{l}\geq l\cdot 2C\cdot n^{\alpha-\beta_{low}}\cdot(\log{n})^{2}\geq 2C\cdot
n^{2\alpha-\beta_{low}}\cdot(\log{n})^{5}$ (3.16)

for all $n$ large and some constant $C>0.$ Plugging (3.16) into (3.15) and
using (3.14) we get that

$\displaystyle\mathbb{P}(E_{bad})$ $\displaystyle\leq$
$\displaystyle\sum_{n^{\alpha}\leq l\leq
n}\exp\left(-2Cn^{2\alpha-\beta_{low}}\cdot(\log{n})^{5}\right)$ (3.17)
$\displaystyle\leq$ $\displaystyle
n\cdot\exp\left(-2Cn^{2\alpha-\beta_{low}}\cdot(\log{n})^{5}\right)$
$\displaystyle\leq$
$\displaystyle\exp\left(-Cn^{2\alpha-\beta_{low}}\cdot(\log{n})^{5}\right)$

for all $n$ large.

If the complement event $E^{c}_{bad}$ occurs, then in any induced subgraph
$H_{l}$ of $H$ containing $T:=n^{\alpha}\cdot(\log{n})^{3}\leq l\leq n$
vertices, the number of edges is at most $m(H_{l})\leq{l\choose
2}p_{up}(1+\epsilon)$ and so

$\max_{T+1\leq l\leq n}\frac{2m(H_{l})}{l}\leq(n-1)\cdot
p_{up}(1+\epsilon)\leq C_{2}\cdot n^{1-\beta_{up}}(1+\epsilon)$ (3.18)

where $C_{2}>0$ is the constant in (3.3). Substituting (3.18) into (4.4) and
using the fact that $\epsilon=\frac{1}{\sqrt{\log{n}}},$ we get that the
maximum average degree

$h_{av}\leq n^{\alpha}\cdot(\log{n})^{3}+C_{2}n^{1-\beta_{up}}(1+\epsilon)\leq
D\cdot n^{\max(\alpha,1-\beta_{up})}\cdot(\log{n})^{3}$ (3.19)

with probability at least $1-\omega_{n},$ for some constant $D>0.$ Here
$\omega_{n}$ is the final expression in (3.17). Plugging (3.19) into (4.1) of
Lemma 4$(b),$ we get the upper bound in (3.5). This completes the proof of
Theorem 2.

### Weighted Colouring

In this subsection, we study a weighted generalization of proper colouring
defined as follows. Equip each edge $h$ of the random graph $G$ obtained in
(3.1) with a deterministic weight $w(h)\geq 1.$ Let
$f:V\rightarrow\\{1,2,\ldots\\}$ be any map from the vertex set of $H$ to the
set of positive integers.

######  Definition 1.

We say that $f$ is a proper $w-$_weighted colouring_ or simply proper weighted
colouring of $H$ if for each edge $h=(u,v)\in E$ with endvertices $u$ and $v$
we have

$|f(u)-f(v)|\geq w(u,v).$ (3.20)

We define the weighted colouring number of $H$ as

$\chi_{w}=\chi_{w}(H):=\min_{f}\max_{(u,v)\in E}|f(u)-f(v)|,$ (3.21)

where the minimum is over all proper weighted colourings of $H.$

We could interpret $\chi_{w}(H)$ as a measure of the effect of weights on a
proper colouring of $H.$ Indeed if $w(u,v)=1$ for all edges, then the weighted
colouring number $\chi_{w}(H)=\chi(H),$ the chromatic number. In general,
$\chi_{w}(H)\geq\chi(H)$ and if $w(u,v)\leq K$ for some $K$ and all edges
$(u,v),$ then $\chi_{w}(H)\leq K\chi(H).$

Henceforth we consider weighted colouring number of $G$ when the edge weights
are random and unbounded. Formally, we equip the ${n\choose 2}$ edges of
$K_{n}$ with independent and identically distributed (i.i.d.) weights
$\\{w(h)\\}_{h\in K_{n}}$ having a constant mean $1\leq\mu_{0}<\infty$ and
satisfying $w(h)\geq 1$ a.s. for all edges $h\in K_{n}.$ The edge weights are
also independent of $G.$

For a realization $\omega$ of the random graph $G,$ let $\mathbb{P}_{\omega}$
be the probability measure associated with the edge weights of $\omega.$ For
constants
$C,\epsilon_{1},\epsilon_{2},\epsilon_{3}>0$ we define the event

$E_{good}(C,\epsilon_{1},\epsilon_{2}):=\left\\{\omega:\mathbb{P}_{\omega}\left(\chi_{w}(\omega)\leq
Cn^{\epsilon_{1}}\right)\geq 1-\frac{C}{n^{\epsilon_{2}}}\right\\}$

and have the following result regarding the weighted colouring number
$\chi_{w}(G).$ For a vertex $u,$ we define of the average edge probability
$p_{av}(u):=\frac{1}{n-1}\sum_{v\neq u}p(u,v).$

######  Theorem 3.

Suppose $\mathbb{E}w^{2s}(u,v)<\infty$ for some integer $s\geq 1.$
$(a)$ Suppose for each vertex $u$ the average edge probability satisfies
$\frac{C_{1}}{n^{\beta}}\leq p_{av}(u)\leq\frac{C_{2}}{n^{\beta}}$ for some
positive constants $C_{1},C_{2}$ and $0<\beta<1.$ For every
$s>\frac{1}{1-\beta}$ there is a constant $C>0$ such that

$\mathbb{P}\left(E_{good}(C,1-\beta,s(1-\beta)-1)\right)\geq
1-e^{-C^{-1}n^{1-\beta}}.$ (3.22)

$(b)$ Suppose the average edge probability $p_{av}:={n\choose
2}^{-1}\sum_{h}p(h)$ satisfies $\frac{C_{1}}{n^{\beta}}\leq
p_{av}\leq\frac{C_{2}}{n^{\beta}}$ for some $\frac{2}{s}<\beta<1.$ For every
$0<\gamma<\frac{\beta}{2}-\frac{1}{s},$ there is a constant $D>0$ such that

$\mathbb{P}(E_{good}(D,1-\gamma,\beta))\geq 1-e^{-D^{-1}n^{2-\beta}}$ (3.23)

Part $(a)$ of the above result essentially says that for nearly all
realizations, the weighted colouring number is at most of the order of
$n^{1-\beta}$ with high probability. From part $(b)$ of Theorem 3, we see that
even under the weaker condition on the overall edge probability average, the
weighted colouring number is still $o(n)$ with high probability, provided the
weights have a bounded $s^{th}$ moment for $s$ sufficiently large. Here and
henceforth $o(n)$ denotes a sequence satisfying $\frac{o(n)}{n}\longrightarrow
0$ as $n\rightarrow\infty.$

_Proof of Theorem 3$(a)$_: For $1\leq i\leq n$ let $N_{i}$ be the number of
neighbours of the vertex $i$ in the graph $G.$ From the bounds on the average
edge probability $p_{av}(i),$ we see that the expected number of neighbours
for vertex $i$ lies $C_{1}n^{1-\beta}$ and $C_{2}n^{1-\beta}.$ Therefore by
the concentration estimate (3.6) with $\epsilon=\frac{1}{2},$ we have that

$\mathbb{P}\left(\frac{C_{1}n^{1-\beta}}{2}\leq N_{i}\leq
2C_{2}n^{1-\beta}\right)\geq 1-e^{-Dn^{1-\beta}},$

for some positive constant $D.$ Letting $E_{nei}:=\bigcap_{1\leq i\leq
n}\\{\frac{C_{1}n^{1-\beta}}{2}\leq N_{i}\leq 2C_{2}n^{1-\beta}\\},$ we have
by the union bound that

$\mathbb{P}(E_{nei})\geq 1-ne^{-Dn^{1-\beta}}.$ (3.24)

Let $\omega\in E_{nei}$ be a realization of $G.$ To find an upper bound for
$\chi_{w}(\omega),$ we use the locally averaged bound (4.7) in Proposition 5.
For $1\leq i\leq n$ let $J_{i}:=\sum_{v\sim i}w(i,v)$ be the sum of the
weights of edges containing $i$ as an endvertex. Using the fact that there are
at most $2C_{2}n^{1-\beta}$ nodes adjacent to $i,$ we have that $J_{i}$ is
stochastically dominated by $\sum_{i=1}^{2C_{2}n^{1-\beta}}Z_{i}$ where
$Z_{i}$ are i.i.d. with the same distribution as the edge weights. Using the
fact that the edge weights have bounded $2s^{th}$ moment, we now show that
there are constants $D_{1},D_{2}>0$ such that

$\mathbb{P}\left(\sum_{i=1}^{2C_{2}n^{1-\beta}}Z_{i}\geq
D_{1}n^{1-\beta}\right)\leq\frac{D_{2}}{n^{s(1-\beta)}}.$ (3.25)

Indeed, denoting the expectation of $Z_{i}$ as $\mu_{Z}$ and using the Markov
inequality we have for any integer $t\geq 2s$ that

$\mathbb{P}\left(\sum_{i=1}^{t}Z_{i}\geq
2t\mu_{Z}\right)\leq\frac{\mathbb{E}\left(\sum_{i=1}^{t}(Z_{i}-\mu_{Z})\right)^{2s}}{(t\mu_{Z})^{2s}}.$
(3.26)

Expanding $\left(\sum_{i=1}^{t}(Z_{i}-\mu_{Z})\right)^{2s},$ we see that any
term of the form
$\prod_{j}(Z_{i_{j}}-\mu_{Z})^{b_{j}}$ has expectation zero, unless each
$b_{j}$ is even. This implies that the total number of terms with non-zero
expectation is $\sum_{l=1}^{s}{t\choose l}\leq s{t\choose s}\leq st^{s}$ by
the monotonicity of the binomial coefficient for $t\geq 2s.$ Thus

$\mathbb{E}\left(\sum_{i=1}^{t}(Z_{i}-\mu_{Z})\right)^{2s}\leq C_{1}st^{s}$

for some constant $C_{1}>0$ and plugging this into (3.26), we get that
$\mathbb{P}\left(\sum_{i=1}^{t}Z_{i}\geq
2t\mu_{Z}\right)\leq\frac{C_{2}}{t^{s}}.$ Setting $t=2C_{2}n^{1-\beta}$ then
gives us (3.25).

Letting $F_{wt}:=\bigcap_{1\leq i\leq n}\\{J_{i}\leq D_{1}n^{1-\beta}\\}$ and
using the union bound, we get from (3.25) that

$\mathbb{P}_{\omega}\left(F_{wt}\right)\geq 1-\frac{D_{2}}{n^{s(1-\beta)-1}}.$
(3.27)

If $F_{wt}$ occurs, then using (4.7), we get that $\chi_{w}\leq
D_{3}n^{1-\beta}$ for some constant $D_{3}>0.$ Thus we get (3.22) from (3.24)
and (3.27).

_Proof of Theorem 3_$(b)$: The expected number of edges in $G$ equals
${n\choose 2}p_{av}$ and so if $E_{edge}$ is the event that the number of
edges in the random graph $G$ lies between ${n\choose 2}\frac{p_{av}}{2}$ and
${n\choose 2}\frac{3p_{av}}{2},$ then by the concentration estimate (3.6) with
$\epsilon=\frac{1}{2},$ we have that

$\mathbb{P}(E^{c}_{edge})\leq\exp\left(-C_{1}{n\choose
2}p_{av}\right)\leq\exp\left(-C_{2}n^{2-\beta}\right)$ (3.28)

for some constants $C_{1},C_{2}>0.$

Let $\omega\in E_{edge}$ be any realization of $G$ and let $q=q(\omega)$ be
the number of edges in $\omega.$ By definition $q$ is at least of the order of
$n^{2-\beta}$ and so if $W_{tot}$ denotes the total weight of edges in
$\omega,$ then by Chebychev’s inequality, we have for constant $\epsilon>0$
that

$\mathbb{P}_{\omega}(|W_{tot}-q\mu_{0}|\geq\epsilon
q\mu_{0})\leq\frac{var(W_{tot})}{\epsilon^{2}q^{2}\mu_{0}^{2}}\leq\frac{C_{3}}{q}\leq\frac{C_{4}}{n^{2-\beta}}$
(3.29)

for some constants $C_{3},C_{4}>0.$ Next let $E_{wt}$ be the event that the
maximum edge weight in $\omega$ is at most $n^{(2+\delta)/s}$ for some
constant $\delta>0$ to be determined later. By the bounded $s^{th}$ moment
assumption of the edge weights and the Markov inequality we have for any edge
$h$ of $\omega$ that

$\mathbb{P}_{\omega}\left(w(h)\geq
n^{(2+\delta)/s}\right)\leq\frac{C_{5}}{n^{2+\delta}}$

for some constant $C_{5}>0.$ Since the number of edges of $\omega$ is at most
of the order of $n^{2-\beta},$ we get by the union bound that

$\mathbb{P}_{\omega}(E^{c}_{wt})\leq\frac{C_{6}}{n^{\beta+\delta}}$ (3.30)

for some constant $C_{6}>0.$

Set $\epsilon=1$ and suppose that $E_{tot}:=E_{wt}\cap\\{W_{tot}\leq
2q\mu_{0}\\}$ occurs. From (3.29) and (3.30), we get that

$\mathbb{P}_{\omega}(E_{tot})\geq
1-\frac{C_{7}}{n^{2-\beta}}-\frac{C_{7}}{n^{\beta+\delta}}$ (3.31)

for some constant $C_{7}>0.$ We choose $\delta>0$ small so that
$2-\beta>\beta+\delta$ and this is possible since $\beta<1.$ If the event
$E_{tot}$ occurs, then setting $K=n^{(2+\delta)/s}$ and $m\mu=W_{tot}$ in the
bound (4.8), we get that

$\chi_{w}(\omega)\leq C_{8}n^{\frac{2+\delta}{2s}}\cdot\sqrt{q}\leq
C_{9}n^{\frac{2+\delta}{2s}}n^{1-\frac{\beta}{2}}=C_{9}n^{1-\left(\frac{\beta}{2}-\frac{1}{s}-\frac{\delta}{2s}\right)}$

for some constants $C_{8},C_{9}>0.$ From the statement of the theorem we know
that $\beta>\frac{2}{s}$ and so we choose $\delta>0$ smaller if necessary so
that $\frac{\beta}{2}-\frac{1}{s}-\frac{\delta}{2s}>0$ as well. With this
choice of $\delta$ and setting $E_{good}=E_{edge},$ we obtain (3.23) from
(3.28) and (3.31).

##  4 Combinatorial Lemmas

In this section, we state and prove the combinatorial lemmas used in the proof
of the Theorems in the previous section. Throughout $H=(V,E)$ is a
deterministic graph with vertex set $V=\\{1,2,\ldots,n\\}$ and edge set $E.$

Our first result in concerns an upper bound for the chromatic number of a
graph in terms of its maximum average degree, used in the proof of Theorem 2.
We begin with a couple of definitions. For a graph $H=(V,E),$ we define the
maximum average degree as $h_{av}=h_{av}(H):=\max_{\Gamma}d_{av}(\Gamma),$
where the maximum is over all subgraphs $\Gamma\subseteq G$ and
$d_{av}(\Gamma)$ is the average vertex degree in $\Gamma.$ By definition, we
have that $d_{av}\leq h_{av}\leq\Delta,$ the maximum degree of a vertex in
$H.$ The following result obtains bounds for the chromatic number of $H$ in
terms of its maximum average degree.

######  Lemma 4.

For any graph $H$ containing $n$ vertices and $m$ edges, we have that the
chromatic number

$\chi(H)\leq 2\max(1,h_{av})\cdot\log\left(\frac{ne}{\max(1,h_{av})}\right),$
(4.1)

where $h_{av}$ satisfies $d_{av}\leq
h_{av}\leq\min\left(\sqrt{2m},6(m\Delta)^{1/3}\right).$

From the above Lemma, we see that if $H$ has bounded maximum average degree,
then $\chi(H)=O(\log{n}).$ For context we recall from the edge count bound
that if the average degree of $H$ is bounded, then $\chi(H)\leq
2\sqrt{m}=\sqrt{2d_{av}(G)}\cdot\sqrt{n}=O(\sqrt{n}).$ This is the best
possible since if $H$ contains a complete subgraph formed by $\sqrt{n}$
vertices, then the chromatic number is at least $\sqrt{n}.$ On the other hand,
if $H$ has bounded maximum average degree, then _every_ subgraph of $H$ is
also sparse and so we expect $H$ to have low chromatic number. This is
reflected in the estimate (4.1).

_Proof of Lemma 4_: A stable set in $H$ is a set of vertices no two of which
are adjacent in $H.$ Let ${\cal I}_{1}=\\{v_{1},\ldots,v_{t}\\}$ be a maximum
stable set, i.e. a stable set of maximum size, in $G_{1}:=H.$ We assign the
colour $1$ to all vertices in ${\cal I}_{1}.$ We remove all the vertices of
${\cal I}_{1}$ from $G_{1}$ to obtain a graph $G_{2}.$ We now repeat the above
procedure with $G_{2}.$ Letting ${\cal I}_{2}$ be the maximum stable set in
$G_{2},$ we assign the colour $2$ to all vertices in ${\cal I}_{2}.$
Continuing the above procedure, let $G_{k+1}$ be the graph obtained at the end
of $k$ iterations. The partial colouring of $H$ obtained so far uses $k$
colours and by construction is proper. Therefore if $G_{k+1}$ has $n_{k+1}$
vertices, then $\chi(G_{k+1})\leq n_{k+1}$ and so

$\chi(G)\leq k+n_{k+1}.$ (4.2)

To estimate $n_{k+1},$ we estimate the size of ${\cal I}_{i}$ for each $1\leq
i\leq k.$ Recalling that $d_{av}$ and $h_{av}\geq d_{av}$ are the average
degree and maximum average degree of $H,$ respectively, we get from Theorem
$3.2.1,$ pp. $29,$ Alon and Spencer (2008), that ${\cal I}_{1}$ has
cardinality

$\\#{\cal
I}_{1}\geq\frac{n}{2\max(1,d_{av})}\geq\frac{n}{2\max(1,h_{av})}:=n\alpha.$
(4.3)

From (4.3), we see that the graph $G_{2}$ has $n_{2}\leq n(1-\alpha)$
vertices. The graph $G_{2}$ has a maximum average degree of at most $h_{av}$
and so arguing as in (4.3) we get that $\\#{\cal I}_{2}\geq n_{2}\alpha.$ This
implies that $G_{3}$ has $n_{3}\leq n_{2}(1-\alpha)\leq n(1-\alpha)^{2}$
vertices. Continuing this way, we get that $G_{k+1}$ has $n_{k+1}\leq
n(1-\alpha)^{k}$ vertices and so from (4.2), we get that $\chi(G)\leq
k+ne^{-\theta k}=:g(k)$ where $\theta:=|\log(1-\alpha)|.$

We see that $g(k)$ is minimized if $k$ satisfies $1-n\theta\cdot e^{-\theta
k}=0$ and for this value of $k,$ we get that
$\chi(G)\leq\frac{\log(n\theta)+1}{\theta}.$ Using $|\log(1-x)|>x$ we get that
$\theta>\alpha$ and since $\alpha=\frac{1}{2\max(1,h_{av})}\leq\frac{1}{2},$
we also get that

$\theta=|\log(1-\alpha)|\leq\sum_{j\geq
1}\alpha^{j}=\frac{\alpha}{1-\alpha}\leq 2\alpha.$

In effect $\alpha\leq\theta\leq 2\alpha$ and so

$\chi(G)\leq\frac{\log(2\alpha\theta)+1}{\alpha}=2\max(1,h_{av})\cdot\left(\log\left(\frac{n}{\max(1,h_{av})}\right)+1\right).$

This proves (4.1).

To obtain the bounds for $h_{av},$ we use the fact that for any integer $1\leq
T\leq n,$ the maximum average degree satisfies

$\displaystyle h_{av}$ $\displaystyle=$ $\displaystyle\max\left(\max_{1\leq
l\leq T}\max_{H_{l}}d_{av}(H_{l}),\max_{T+1\leq l\leq
n}\max_{H_{l}}d_{av}(H_{l})\right)$ (4.4) $\displaystyle\leq$
$\displaystyle\max\left(T,\max_{T+1\leq l\leq
n}\max_{H_{l}}d_{av}(H_{l})\right)$ $\displaystyle=$
$\displaystyle\max\left(T,\max_{T+1\leq l\leq
n}\max_{H_{l}}\frac{2m(H_{l})}{l}\right)$

where $H_{l}$ is an _induced_ subgraph of $G$ containing $l$ vertices and
$m(H_{l})$ is the number of edges in $H_{l}.$ For any subgraph $H_{l}$ we have
that $m(H_{l})\leq m,$ the total number of edges in $H$ and so from (4.4) we
see that

$h_{av}(G)\leq\max\left(T,\max_{T+1\leq l\leq
n}\frac{2m}{l}\right)\leq\max\left(T,\frac{2m}{T}\right)$ (4.5)

and the final expression in (4.5) attains its maximum at $T=\sqrt{2m}.$ Thus
we get that $h_{av}(G)\leq\sqrt{2m}.$

For the final estimate $h_{av}\leq(m\Delta)^{1/3},$ we again use (4.4) as
follows. For $x>0,$ the probability that a randomly chosen vertex has degree
larger than $x$ is bounded above by the Markov inequality as
$\frac{d_{av}}{x}$ and so the number of vertices in $H$ with degree larger
than $x$ is at most $\frac{nd_{av}}{x}=\frac{m}{x}.$ For any subgraph $H_{l}$
on $l$ vertices, we therefore have that the number of edges
$m(H_{l})\leq\frac{m}{x}\cdot\Delta+lx$ and plugging this into (4.4), we get
that

$\displaystyle h_{av}$ $\displaystyle\leq$
$\displaystyle\max\left(T,\max_{T+1\leq l\leq n}\frac{2m\Delta}{lx}+2x\right)$
(4.6) $\displaystyle\leq$
$\displaystyle\max\left(T,\frac{2m\Delta}{Tx}+2x\right)$ $\displaystyle\leq$
$\displaystyle T+\frac{2m\Delta}{Tx}+2x.$

The final expression in (4.6) is minimized at $T=\sqrt{\frac{2m\Delta}{x}}$
and so

$h_{av}\leq 2\sqrt{\frac{2m\Delta}{x}}+2x.$

Setting $x=(m\Delta)^{1/3},$ we then get the desired bound
$h_{av}\leq(2\sqrt{2}+2)(m\Delta)^{1/3}$ and this completes the proof of the
Lemma.

To prove Theorem 3, we use the following deterministic result that obtains
bounds for the weighted colouring number $\chi_{w}(H)$ in terms of averaged
and locally averaged edge weights.

######  Lemma 5.

Suppose $H$ is a graph with $m$ edges and let $w(u,v)$ be the weight
associated with edge $(u,v).$
$(a)$ We have that

$\chi_{w}(H)\leq 1+\max_{v\in H}\sum_{u\sim v}(2w(u,v)-1).$ (4.7)

$(b)$ If $w(h)\leq K$ for some $K>0$ and all edges $h\in H,$ then

$\chi_{w}(H)\leq 2\sqrt{2mK\mu}$ (4.8)

where $\mu:=\frac{1}{m}\sum_{h}w(h)$ is the average edge weight in $H.$

The bound in part $(a)$ of Lemma 5 is a generalization of the maximum degree
bound $\chi(H)\leq\Delta+1.$ In fact if $w(u,v)=1$ for all edges $(u,v)\in H,$
then the right side of (4.7) reduces to $\Delta+1.$ As in the proof of the
maximum degree bound, we use a greedy colouring procedure to obtain (4.7).
Part $(b)$ of Proposition 5 establishes bounds for the weighted colouring
number in terms of the average edge weight. The bound in (4.8) is essentially
the best possible since if $H$ contains a clique of size $c\sqrt{m}$ for some
$c>0$ then using the fact that each edge weight is at least one, we get
$\chi_{w}(H)\geq c\sqrt{m}.$

We also remark here that a weaker upper bound of $\chi_{w}(H)\leq 2K\sqrt{m}$
can be obtained using a direct counting argument as follows: Let ${\cal
C}:=\\{K,2K,\ldots,rK\\},$ where $r=\chi(H)$ is the smallest possible integer
that allows a proper colouring of $G$ using only colours from ${\cal C}.$ Let
${\cal V}_{i}$ be the set of all vertices with colour $iK$ for $1\leq i\leq
r.$ By the minimality of $r,$ there must exist at least one edge between a
vertex in ${\cal V}_{i}$ and a vertex in ${\cal V}_{j},$ for any $i\neq j$ and
so ${r\choose 2}\leq m.$ Consequently $\chi_{w}\leq rK\leq 2K\sqrt{m}.$ For
$\mu\leq\frac{K}{3}$ the bound in (4.8) is stronger and is obtained using the
probabilistic method below.

We now prove Lemma 5 and Theorem 3 in that order below.
_Proof of Lemma 5$(a)$_: Let $L+1:=1+\max_{v\in H}\sum_{u\sim v}(2w(u,v)-1),$
the right hand side of (4.7). We iteratively colour the vertices of $H$ from
the set $\\{1,2,\ldots,L+1\\}.$ Pick a vertex $u_{1}$ and assign the colour
$l(u_{1})=1.$ For the $i^{th}$ iteration, $i\geq 2,$ we pick an uncoloured
vertex $u_{i}$ and let $l(v_{1}),\ldots,l(v_{t})$ be the colours of its
coloured neighbours. Let $I(v_{j})$ be the set of all integers $l$ satisfying
$|l-l(v_{j})|\leq w(u_{i},v_{j})-1.$ There are $2w(u_{i},v_{j})-1$ integers in
$I(v_{j})$ and so the number of integers in $\bigcup_{1\leq j\leq t}I(v_{j})$
is at most $L.$ We therefore assign a colour
$l(u_{i})\in\\{1,2,\ldots,L+1\\}\setminus\bigcup_{1\leq j\leq t}I(v_{j})$ to
the vertex $u_{i}.$ Continuing this process we obtain a proper weighted
colouring of $H$ and this proves Lemma 5$(a).$

_Proof of Lemma 5$(b)$_: For integer $\theta\geq 1$ to be determined later,
let $X_{i},1\leq i\leq n$ be independent and identically distributed (i.i.d.)
random variables uniformly randomly chosen from $\\{1,2,\ldots,\theta\\}.$ Say
that edge $h=(u,v)$ is bad if (3.20) does not hold. Let
$h_{i}=(u_{i},v_{i}),1\leq i\leq q$ be the set of all bad edges. We now
iteratively change the labels assigned to the vertices of bad edges until no
bad edge remains. We begin by setting $w_{1}:=u_{1}$ and $f(w_{1})=\theta+K$
and marking $u_{1}.$ We then pick an unmarked endvertex $w_{2}$ of some bad
edge and set $f(w_{2})=\theta+2K.$ We proceed this way until each endvertex of
a bad edge is marked. Finally, for the rest of the vertices we set
$f(u)=X_{u}.$

Since $w(h)\leq K$ for all $h,$ we have that $f$ is a proper weighted
colouring of $H.$ Moreover, if the number of bad edges is $N_{bad},$ then
$1\leq f(u)\leq\theta+N_{bad}K$ and so

$\chi_{w}\leq\theta+N_{bad}K.$ (4.9)

To bound $N_{bad},$ we first estimate $\mathbb{E}N_{bad}$ as follows. For any
two vertices $u$ and $v$ and any integer $1\leq j\leq\theta-1,$ we have that
$|X_{u}-X_{v}|=j$ if and only if either $X_{u}=l$ and $X_{v}=l+j$ for some
$1\leq l\leq\theta-j$ or $X_{v}=l$ and $X_{u}=l+j$ for some $1\leq
l\leq\theta-j.$ Thus
$\mathbb{P}(|X_{u}-X_{v}|=j)=\frac{2}{\theta^{2}}(\theta-j)$ and so for any
$t\leq\theta,$ we have that

$\mathbb{P}(|X_{u}-X_{v}|\leq t)=\frac{2}{\theta^{2}}\left(\theta
t-\frac{t(t+1)}{2}\right)\leq\frac{2t}{\theta}.$

For an edge $h$ with weight $w(h),$ we have that the probability that $h$ is
bad is at most $\frac{2w(h)}{\theta}$ and so

$\mathbb{E}N_{bad}\leq\sum_{h}\frac{2w(h)}{\theta}=\frac{2m\mu}{\theta}$
(4.10)

where $\mu=\frac{1}{m}\sum_{h}w(h)$ is the average edge weight.

From (4.10), we see that there exists a realization such that
$N_{bad}\leq\frac{2m\mu}{\theta}$ and plugging this into (4.9), we get that

$\chi_{w}\leq\theta+\frac{2mK\mu}{\theta}$ (4.11)

and the right side of (4.11) is minimized at $\theta=\sqrt{2mK\mu}.$ Thus
$\chi_{w}(H)\leq 2\sqrt{2mK\mu}$ and this completes the proof of the Lemma.

### Acknowledgement

I thank Professors Rahul Roy, Alberto Gandolfi, C. R. Subramanian and K.
Adhikari for crucial comments and also thank IMSc and IISER Bhopal for my
fellowships.

## References

  * [1] D. Achlioptas and A. Naor. (2005).  The Two Possible Values of the Chromatic Number of a Random Graph.  Annals of Mathematics, 162, pp. 1335–1351.
  * [2] N. Alon and M. Krivelevich. (1997).  The Concentration of the Chromatic Number of Random Graphs.  Combinatorica, 17(3), pp. 303–313.
  * [3] N. Alon and J. Spencer. (2008).  The Probabilistic Method.  Wiley Interscience.
  * [4] Bairamov, I. and Stepanov, A. (2006).  A note on large deviations of weak records.  Statistics and Probability Letters, 76, pp. 1449–1453.
  * [5] B. Bollobás. (1988).  The Chromatic Number of Random Graphs.  Combinatorica, 8, pp. 49–55.
  * [6] B. Bollobás. (2001).  Random Graphs.  Cambridge University Press.
  * [7] Charalambides, C. A. and Rychlik, T. (2008).  Distributions and moments of record values in a sequence of maximally dependent random variables.  Journal of Statistical Planning and Inference, 138, pp. 2253–2266.
  * [8] G. Chartrand, D. Erwin, P. Zhang, F. Harary. (2001).  Radio labelings of graphs.  Bull. Inst. Combin. Appl., 33 pp. 77-85.
  * [9] A. Frieze. (1990).  On the Independence Number of Random Graphs.  Discrete Mathematics, 81, pp. 171–176.
  * [10] G. Ganesan. (2020).  Cliques and Chromatic Number in Multiregime Random Graphs.  Sankhya, $doi:https://doi.org/10.1007/s13171-020-00205-4.$
  * [11] Jasiński, K. (2018).  Characterizations of geometric distributions based on $k^{th}$ record values.  Statistics, 52, pp. 1116–1127.
  * [12] D. Korze, Z. Shao and A. Vesel. (2021).  New results on radio $k-$labelings of distance graphs.  Discrete Applied Mathematics, Available online, September 2021.
  * [13] T. Luczak. (1991).  The Chromatic Number of Random Graphs.  Combinatorica, 11, pp. 45–54.
  * [14] M. Molloy and B. Reed. (2002).  Graph Colouring and the Probabilistic Method.  Springer.
  * [15] Nevzorov, V. B. (1986).  Records.  Theory of Probability and Applications, 32, pp. 201–223.
  * [16] K. Panagiotou and A. Steger. (2009).  A Note on the Chromatic Number of a Dense Random Graph.  Discrete Mathematics, 309, pp. 3420–3423.
  * [17] A. Scott. (2008).  On the Concentration of the Chromatic Number of Random Graphs.  Arxiv Link: https://arxiv.org/abs/0806.0178.
  * [18] E. Shamir and J. Spencer. (1987).  Sharp Concentration of the Chromatic Number on Random Graphs $G_{n,p}.$ Combinatorica, 7, pp. 121–129.
  * [19] D. West. (2000).  Introduction to Graph Theory.  Prentice Hall.


EUROPEAN ORGANIZATION FOR NUCLEAR RESEARCH (CERN)

 CERN-PH-EP-2014-002 LHCb-PAPER-2013-064

Search for Majorana neutrinos in $B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-}$
decays

The LHCb collaboration†††Authors are listed on the following pages.

A search for heavy Majorana neutrinos produced in the
$B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-}$ decay mode is performed using 3
$\mbox{\,fb}^{-1}$ of integrated luminosity collected with the LHCb detector
in $pp$ collisions at center-of-mass energies of 7 TeV and 8 TeV at the LHC.
Neutrinos with masses in the range $250-5000$ MeV and lifetimes from zero to
1000 ps are probed. In the absence of a signal, upper limits are set on the
branching fraction ${\cal{B}}(B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-})$ as
functions of neutrino mass and lifetime. These limits are on the order of
$10^{-9}$ for short neutrino lifetimes of 1 ps or less. Limits are also set on
the coupling between the muon and a possible fourth-generation neutrino.

Submitted to Phys. Rev. Lett.

© CERN on behalf of the LHCb collaboration, license CC-BY-3.0.

LHCb collaboration

R. Aaij40, B. Adeva36, M. Adinolfi45, A. Affolder51, Z. Ajaltouni5, J.
Albrecht9, F. Alessio37, M. Alexander50, S. Ali40, G. Alkhazov29, P. Alvarez
Cartelle36, A.A. Alves Jr24, S. Amato2, S. Amerio21, Y. Amhis7, L.
Anderlini17,g, J. Anderson39, R. Andreassen56, M. Andreotti16,f, J.E.
Andrews57, R.B. Appleby53, O. Aquines Gutierrez10, F. Archilli37, A.
Artamonov34, M. Artuso58, E. Aslanides6, G. Auriemma24,n, M. Baalouch5, S.
Bachmann11, J.J. Back47, A. Badalov35, V. Balagura30, W. Baldini16, R.J.
Barlow53, C. Barschel38, S. Barsuk7, W. Barter46, V. Batozskaya27, Th.
Bauer40, A. Bay38, J. Beddow50, F. Bedeschi22, I. Bediaga1, S. Belogurov30, K.
Belous34, I. Belyaev30, E. Ben-Haim8, G. Bencivenni18, S. Benson49, J.
Benton45, A. Berezhnoy31, R. Bernet39, M.-O. Bettler46, M. van Beuzekom40, A.
Bien11, S. Bifani44, T. Bird53, A. Bizzeti17,i, P.M. Bjørnstad53, T. Blake47,
F. Blanc38, J. Blouw10, S. Blusk58, V. Bocci24, A. Bondar33, N. Bondar29, W.
Bonivento15,37, S. Borghi53, A. Borgia58, M. Borsato7, T.J.V. Bowcock51, E.
Bowen39, C. Bozzi16, T. Brambach9, J. van den Brand41, J. Bressieux38, D.
Brett53, M. Britsch10, T. Britton58, N.H. Brook45, H. Brown51, A. Bursche39,
G. Busetto21,r, J. Buytaert37, S. Cadeddu15, R. Calabrese16,f, O. Callot7, M.
Calvi20,k, M. Calvo Gomez35,p, A. Camboni35, P. Campana18,37, D. Campora
Perez37, A. Carbone14,d, G. Carboni23,l, R. Cardinale19,j, A. Cardini15, H.
Carranza-Mejia49, L. Carson49, K. Carvalho Akiba2, G. Casse51, L. Castillo
Garcia37, M. Cattaneo37, Ch. Cauet9, R. Cenci57, M. Charles8, Ph.
Charpentier37, S.-F. Cheung54, N. Chiapolini39, M. Chrzaszcz39,25, K. Ciba37,
X. Cid Vidal37, G. Ciezarek52, P.E.L. Clarke49, M. Clemencic37, H.V. Cliff46,
J. Closier37, C. Coca28, V. Coco37, J. Cogan6, E. Cogneras5, P. Collins37, A.
Comerma-Montells35, A. Contu15,37, A. Cook45, M. Coombes45, S. Coquereau8, G.
Corti37, I. Counts55, B. Couturier37, G.A. Cowan49, D.C. Craik47, M. Cruz
Torres59, S. Cunliffe52, R. Currie49, C. D’Ambrosio37, J. Dalseno45, P.
David8, P.N.Y. David40, A. Davis56, I. De Bonis4, K. De Bruyn40, S. De
Capua53, M. De Cian11, J.M. De Miranda1, L. De Paula2, W. De Silva56, P. De
Simone18, D. Decamp4, M. Deckenhoff9, L. Del Buono8, N. Déléage4, D.
Derkach54, O. Deschamps5, F. Dettori41, A. Di Canto11, H. Dijkstra37, S.
Donleavy51, F. Dordei11, M. Dorigo38, P. Dorosz25,o, A. Dosil Suárez36, D.
Dossett47, A. Dovbnya42, F. Dupertuis38, P. Durante37, R. Dzhelyadin34, A.
Dziurda25, A. Dzyuba29, S. Easo48, U. Egede52, V. Egorychev30, S. Eidelman33,
S. Eisenhardt49, U. Eitschberger9, R. Ekelhof9, L. Eklund50,37, I. El Rifai5,
Ch. Elsasser39, A. Falabella16,f, C. Färber11, C. Farinelli40, S. Farry51, D.
Ferguson49, V. Fernandez Albor36, F. Ferreira Rodrigues1, M. Ferro-Luzzi37, S.
Filippov32, M. Fiore16,f, M. Fiorini16,f, C. Fitzpatrick37, M. Fontana10, F.
Fontanelli19,j, R. Forty37, O. Francisco2, M. Frank37, C. Frei37, M.
Frosini17,37,g, E. Furfaro23,l, A. Gallas Torreira36, D. Galli14,d, M.
Gandelman2, P. Gandini58, Y. Gao3, J. Garofoli58, J. Garra Tico46, L.
Garrido35, C. Gaspar37, R. Gauld54, E. Gersabeck11, M. Gersabeck53, T.
Gershon47, Ph. Ghez4, A. Gianelle21, V. Gibson46, L. Giubega28, V.V.
Gligorov37, C. Göbel59, D. Golubkov30, A. Golutvin52,30,37, A. Gomes1,a, H.
Gordon37, M. Grabalosa Gándara5, R. Graciani Diaz35, L.A. Granado Cardoso37,
E. Graugés35, G. Graziani17, A. Grecu28, E. Greening54, S. Gregson46, P.
Griffith44, L. Grillo11, O. Grünberg60, B. Gui58, E. Gushchin32, Yu. Guz34,37,
T. Gys37, C. Hadjivasiliou58, G. Haefeli38, C. Haen37, T.W. Hafkenscheid62,
S.C. Haines46, S. Hall52, B. Hamilton57, T. Hampson45, S. Hansmann-Menzemer11,
N. Harnew54, S.T. Harnew45, J. Harrison53, T. Hartmann60, J. He37, T. Head37,
V. Heijne40, K. Hennessy51, P. Henrard5, J.A. Hernando Morata36, E. van
Herwijnen37, M. Heß60, A. Hicheur1, D. Hill54, M. Hoballah5, C. Hombach53, W.
Hulsbergen40, P. Hunt54, T. Huse51, N. Hussain54, D. Hutchcroft51, D. Hynds50,
V. Iakovenko43, M. Idzik26, P. Ilten55, R. Jacobsson37, A. Jaeger11, E.
Jans40, P. Jaton38, A. Jawahery57, F. Jing3, M. John54, D. Johnson54, C.R.
Jones46, C. Joram37, B. Jost37, N. Jurik58, M. Kaballo9, S. Kandybei42, W.
Kanso6, M. Karacson37, T.M. Karbach37, I.R. Kenyon44, T. Ketel41, B. Khanji20,
C. Khurewathanakul38, S. Klaver53, O. Kochebina7, I. Komarov38, R.F.
Koopman41, P. Koppenburg40, M. Korolev31, A. Kozlinskiy40, L. Kravchuk32, K.
Kreplin11, M. Kreps47, G. Krocker11, P. Krokovny33, F. Kruse9, M.
Kucharczyk20,25,37,k, V. Kudryavtsev33, K. Kurek27, T. Kvaratskheliya30,37,
V.N. La Thi38, D. Lacarrere37, G. Lafferty53, A. Lai15, D. Lambert49, R.W.
Lambert41, E. Lanciotti37, G. Lanfranchi18, C. Langenbruch37, T. Latham47, C.
Lazzeroni44, R. Le Gac6, J. van Leerdam40, J.-P. Lees4, R. Lefèvre5, A.
Leflat31, J. Lefrançois7, S. Leo22, O. Leroy6, T. Lesiak25, B. Leverington11,
Y. Li3, M. Liles51, R. Lindner37, C. Linn11, F. Lionetto39, B. Liu15, G.
Liu37, S. Lohn37, I. Longstaff50, J.H. Lopes2, N. Lopez-March38, P. Lowdon39,
H. Lu3, D. Lucchesi21,r, J. Luisier38, H. Luo49, E. Luppi16,f, O. Lupton54, F.
Machefert7, I.V. Machikhiliyan30, F. Maciuc28, O. Maev29,37, S. Malde54, G.
Manca15,e, G. Mancinelli6, M. Manzali16,f, J. Maratas5, U. Marconi14, P.
Marino22,t, R. Märki38, J. Marks11, G. Martellotti24, A. Martens8, A. Martín
Sánchez7, M. Martinelli40, D. Martinez Santos41, D. Martins Tostes2, A.
Massafferri1, R. Matev37, Z. Mathe37, C. Matteuzzi20, A. Mazurov16,37,f, M.
McCann52, J. McCarthy44, A. McNab53, R. McNulty12, B. McSkelly51, B.
Meadows56,54, F. Meier9, M. Meissner11, M. Merk40, D.A. Milanes8, M.-N.
Minard4, J. Molina Rodriguez59, S. Monteil5, D. Moran53, M. Morandin21, P.
Morawski25, A. Mordà6, M.J. Morello22,t, R. Mountain58, I. Mous40, F.
Muheim49, K. Müller39, R. Muresan28, B. Muryn26, B. Muster38, P. Naik45, T.
Nakada38, R. Nandakumar48, I. Nasteva1, M. Needham49, S. Neubert37, N.
Neufeld37, A.D. Nguyen38, T.D. Nguyen38, C. Nguyen-Mau38,q, M. Nicol7, V.
Niess5, R. Niet9, N. Nikitin31, T. Nikodem11, A. Novoselov34, A. Oblakowska-
Mucha26, V. Obraztsov34, S. Oggero40, S. Ogilvy50, O. Okhrimenko43, R.
Oldeman15,e, G. Onderwater62, M. Orlandea28, J.M. Otalora Goicochea2, P.
Owen52, A. Oyanguren35, B.K. Pal58, A. Palano13,c, M. Palutan18, J. Panman37,
A. Papanestis48,37, M. Pappagallo50, L. Pappalardo16, C. Parkes53, C.J.
Parkinson9, G. Passaleva17, G.D. Patel51, M. Patel52, C. Patrignani19,j, C.
Pavel-Nicorescu28, A. Pazos Alvarez36, A. Pearce53, A. Pellegrino40, G.
Penso24,m, M. Pepe Altarelli37, S. Perazzini14,d, E. Perez Trigo36, P.
Perret5, M. Perrin-Terrin6, L. Pescatore44, E. Pesen63, G. Pessina20, K.
Petridis52, A. Petrolini19,j, E. Picatoste Olloqui35, B. Pietrzyk4, T.
Pilař47, D. Pinci24, A. Pistone19, S. Playfer49, M. Plo Casasus36, F. Polci8,
G. Polok25, A. Poluektov47,33, E. Polycarpo2, A. Popov34, D. Popov10, B.
Popovici28, C. Potterat35, A. Powell54, J. Prisciandaro38, A. Pritchard51, C.
Prouve45, V. Pugatch43, A. Puig Navarro38, G. Punzi22,s, W. Qian4, B.
Rachwal25, J.H. Rademacker45, B. Rakotomiaramanana38, M. Rama18, M.S. Rangel2,
I. Raniuk42, N. Rauschmayr37, G. Raven41, S. Redford54, S. Reichert53, M.M.
Reid47, A.C. dos Reis1, S. Ricciardi48, A. Richards52, K. Rinnert51, V. Rives
Molina35, D.A. Roa Romero5, P. Robbe7, D.A. Roberts57, A.B. Rodrigues1, E.
Rodrigues53, P. Rodriguez Perez36, S. Roiser37, V. Romanovsky34, A. Romero
Vidal36, M. Rotondo21, J. Rouvinet38, T. Ruf37, F. Ruffini22, H. Ruiz35, P.
Ruiz Valls35, G. Sabatino24,l, J.J. Saborido Silva36, N. Sagidova29, P.
Sail50, B. Saitta15,e, V. Salustino Guimaraes2, B. Sanmartin Sedes36, R.
Santacesaria24, C. Santamarina Rios36, E. Santovetti23,l, M. Sapunov6, A.
Sarti18, C. Satriano24,n, A. Satta23, M. Savrie16,f, D. Savrina30,31, M.
Schiller41, H. Schindler37, M. Schlupp9, M. Schmelling10, B. Schmidt37, O.
Schneider38, A. Schopper37, M.-H. Schune7, R. Schwemmer37, B. Sciascia18, A.
Sciubba24, M. Seco36, A. Semennikov30, K. Senderowska26, I. Sepp52, N.
Serra39, J. Serrano6, P. Seyfert11, M. Shapkin34, I. Shapoval16,42,f, Y.
Shcheglov29, T. Shears51, L. Shekhtman33, O. Shevchenko42, V. Shevchenko61, A.
Shires9, R. Silva Coutinho47, G. Simi21, M. Sirendi46, N. Skidmore45, T.
Skwarnicki58, N.A. Smith51, E. Smith54,48, E. Smith52, J. Smith46, M. Smith53,
H. Snoek40, M.D. Sokoloff56, F.J.P. Soler50, F. Soomro38, D. Souza45, B. Souza
De Paula2, B. Spaan9, A. Sparkes49, F. Spinella22, P. Spradlin50, F. Stagni37,
S. Stahl11, O. Steinkamp39, S. Stevenson54, S. Stoica28, S. Stone58, B.
Storaci39, S. Stracka22,37, M. Straticiuc28, U. Straumann39, R. Stroili21,
V.K. Subbiah37, L. Sun56, W. Sutcliffe52, S. Swientek9, V. Syropoulos41, M.
Szczekowski27, P. Szczypka38,37, D. Szilard2, T. Szumlak26, S. T’Jampens4, M.
Teklishyn7, G. Tellarini16,f, E. Teodorescu28, F. Teubert37, C. Thomas54, E.
Thomas37, J. van Tilburg11, V. Tisserand4, M. Tobin38, S. Tolk41, L.
Tomassetti16,f, D. Tonelli37, S. Topp-Joergensen54, N. Torr54, E.
Tournefier4,52, S. Tourneur38, M.T. Tran38, M. Tresch39, A. Tsaregorodtsev6,
P. Tsopelas40, N. Tuning40, M. Ubeda Garcia37, A. Ukleja27, A. Ustyuzhanin61,
U. Uwer11, V. Vagnoni14, G. Valenti14, A. Vallier7, R. Vazquez Gomez18, P.
Vazquez Regueiro36, C. Vázquez Sierra36, S. Vecchi16, J.J. Velthuis45, M.
Veltri17,h, G. Veneziano38, M. Vesterinen11, B. Viaud7, D. Vieira2, X.
Vilasis-Cardona35,p, A. Vollhardt39, D. Volyanskyy10, D. Voong45, A.
Vorobyev29, V. Vorobyev33, C. Voß60, H. Voss10, J.A. de Vries40, R. Waldi60,
C. Wallace47, R. Wallace12, S. Wandernoth11, J. Wang58, D.R. Ward46, N.K.
Watson44, A.D. Webber53, D. Websdale52, M. Whitehead47, J. Wicht37, J.
Wiechczynski25, D. Wiedner11, L. Wiggers40, G. Wilkinson54, M.P.
Williams47,48, M. Williams55, F.F. Wilson48, J. Wimberley57, J. Wishahi9, W.
Wislicki27, M. Witek25, G. Wormser7, S.A. Wotton46, S. Wright46, S. Wu3, K.
Wyllie37, Y. Xie49,37, Z. Xing58, Z. Yang3, X. Yuan3, O. Yushchenko34, M.
Zangoli14, M. Zavertyaev10,b, F. Zhang3, L. Zhang58, W.C. Zhang12, Y. Zhang3,
A. Zhelezov11, A. Zhokhov30, L. Zhong3, A. Zvyagin37.

1Centro Brasileiro de Pesquisas Físicas (CBPF), Rio de Janeiro, Brazil
2Universidade Federal do Rio de Janeiro (UFRJ), Rio de Janeiro, Brazil
3Center for High Energy Physics, Tsinghua University, Beijing, China
4LAPP, Université de Savoie, CNRS/IN2P3, Annecy-Le-Vieux, France
5Clermont Université, Université Blaise Pascal, CNRS/IN2P3, LPC, Clermont-
Ferrand, France
6CPPM, Aix-Marseille Université, CNRS/IN2P3, Marseille, France
7LAL, Université Paris-Sud, CNRS/IN2P3, Orsay, France
8LPNHE, Université Pierre et Marie Curie, Université Paris Diderot,
CNRS/IN2P3, Paris, France
9Fakultät Physik, Technische Universität Dortmund, Dortmund, Germany
10Max-Planck-Institut für Kernphysik (MPIK), Heidelberg, Germany
11Physikalisches Institut, Ruprecht-Karls-Universität Heidelberg, Heidelberg,
Germany
12School of Physics, University College Dublin, Dublin, Ireland
13Sezione INFN di Bari, Bari, Italy
14Sezione INFN di Bologna, Bologna, Italy
15Sezione INFN di Cagliari, Cagliari, Italy
16Sezione INFN di Ferrara, Ferrara, Italy
17Sezione INFN di Firenze, Firenze, Italy
18Laboratori Nazionali dell’INFN di Frascati, Frascati, Italy
19Sezione INFN di Genova, Genova, Italy
20Sezione INFN di Milano Bicocca, Milano, Italy
21Sezione INFN di Padova, Padova, Italy
22Sezione INFN di Pisa, Pisa, Italy
23Sezione INFN di Roma Tor Vergata, Roma, Italy
24Sezione INFN di Roma La Sapienza, Roma, Italy
25Henryk Niewodniczanski Institute of Nuclear Physics Polish Academy of
Sciences, Kraków, Poland
26AGH - University of Science and Technology, Faculty of Physics and Applied
Computer Science, Kraków, Poland
27National Center for Nuclear Research (NCBJ), Warsaw, Poland
28Horia Hulubei National Institute of Physics and Nuclear Engineering,
Bucharest-Magurele, Romania
29Petersburg Nuclear Physics Institute (PNPI), Gatchina, Russia
30Institute of Theoretical and Experimental Physics (ITEP), Moscow, Russia
31Institute of Nuclear Physics, Moscow State University (SINP MSU), Moscow,
Russia
32Institute for Nuclear Research of the Russian Academy of Sciences (INR RAN),
Moscow, Russia
33Budker Institute of Nuclear Physics (SB RAS) and Novosibirsk State
University, Novosibirsk, Russia
34Institute for High Energy Physics (IHEP), Protvino, Russia
35Universitat de Barcelona, Barcelona, Spain
36Universidad de Santiago de Compostela, Santiago de Compostela, Spain
37European Organization for Nuclear Research (CERN), Geneva, Switzerland
38Ecole Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland
39Physik-Institut, Universität Zürich, Zürich, Switzerland
40Nikhef National Institute for Subatomic Physics, Amsterdam, The Netherlands
41Nikhef National Institute for Subatomic Physics and VU University Amsterdam,
Amsterdam, The Netherlands
42NSC Kharkiv Institute of Physics and Technology (NSC KIPT), Kharkiv, Ukraine
43Institute for Nuclear Research of the National Academy of Sciences (KINR),
Kyiv, Ukraine
44University of Birmingham, Birmingham, United Kingdom
45H.H. Wills Physics Laboratory, University of Bristol, Bristol, United
Kingdom
46Cavendish Laboratory, University of Cambridge, Cambridge, United Kingdom
47Department of Physics, University of Warwick, Coventry, United Kingdom
48STFC Rutherford Appleton Laboratory, Didcot, United Kingdom
49School of Physics and Astronomy, University of Edinburgh, Edinburgh, United
Kingdom
50School of Physics and Astronomy, University of Glasgow, Glasgow, United
Kingdom
51Oliver Lodge Laboratory, University of Liverpool, Liverpool, United Kingdom
52Imperial College London, London, United Kingdom
53School of Physics and Astronomy, University of Manchester, Manchester,
United Kingdom
54Department of Physics, University of Oxford, Oxford, United Kingdom
55Massachusetts Institute of Technology, Cambridge, MA, United States
56University of Cincinnati, Cincinnati, OH, United States
57University of Maryland, College Park, MD, United States
58Syracuse University, Syracuse, NY, United States
59Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio), Rio de
Janeiro, Brazil, associated to 2
60Institut für Physik, Universität Rostock, Rostock, Germany, associated to 11
61National Research Centre Kurchatov Institute, Moscow, Russia, associated to
30
62KVI - University of Groningen, Groningen, The Netherlands, associated to 40
63Celal Bayar University, Manisa, Turkey, associated to 37

aUniversidade Federal do Triângulo Mineiro (UFTM), Uberaba-MG, Brazil
bP.N. Lebedev Physical Institute, Russian Academy of Science (LPI RAS),
Moscow, Russia
cUniversità di Bari, Bari, Italy
dUniversità di Bologna, Bologna, Italy
eUniversità di Cagliari, Cagliari, Italy
fUniversità di Ferrara, Ferrara, Italy
gUniversità di Firenze, Firenze, Italy
hUniversità di Urbino, Urbino, Italy
iUniversità di Modena e Reggio Emilia, Modena, Italy
jUniversità di Genova, Genova, Italy
kUniversità di Milano Bicocca, Milano, Italy
lUniversità di Roma Tor Vergata, Roma, Italy
mUniversità di Roma La Sapienza, Roma, Italy
nUniversità della Basilicata, Potenza, Italy
oAGH - University of Science and Technology, Faculty of Computer Science,
Electronics and Telecommunications, Kraków, Poland
pLIFAELS, La Salle, Universitat Ramon Llull, Barcelona, Spain
qHanoi University of Science, Hanoi, Viet Nam
rUniversità di Padova, Padova, Italy
sUniversità di Pisa, Pisa, Italy
tScuola Normale Superiore, Pisa, Italy

Neutrinos can either be their own anti-particles, in which case they are
called “Majorana” particles [1], or Dirac fermions. Heavy Majorana neutrinos
can be sought in heavy flavor decays and couplings to a single fourth neutrino
generation can be determined, or limits imposed, as in previous measurements
[2, *Aaij:2011ex, 4, *Seon:2011ni, *Weir:1989sq]. The lepton number violating
process $B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-}$, shown in Fig. 1, is forbidden
in the Standard Model, but can proceed via the production of on-shell Majorana
neutrinos. It is one of the most sensitive ways of looking for these particles
in $B$ meson decays, and has been modeled by Atre et al. [7]. Note that it is
possible for virtual Majorana neutrinos of any mass to contribute to this
decay. We investigate the $B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-}$ decay using
3 fb-1 of data acquired by the LHCb experiment in $pp$ collisions. (In this
Letter mention of a particular decay implies the use of the charge-conjugate
decay as well.) One third of the data was recorded at 7 TeV center-of-mass
energy, and the remainder at 8 TeV.

The search strategy is based on our previous analysis [2], but extends the
sensitivity to neutrino lifetimes, $\tau_{N}$, from the picosecond range up to
about 1000 ps. The selection is aimed at maximizing the efficiency squared
divided by the background yield. For lifetimes $\gtrsim$1 ps, the
$\pi^{+}\mu^{-}$ decay products can appear as significantly detached from the
$B^{-}$ decay vertex. Therefore, we use two distinct strategies, one for short
$\tau_{N}$ ($\cal{S}$) and another for $\tau_{N}$ up to 1000 ps ($\cal{L}$).

The LHCb detector is a single-arm forward spectrometer covering the
pseudorapidity range $2<\eta<5$, designed for the study of particles
containing $b$ or $c$ quarks [8]. The detector includes a high precision
tracking system consisting of a silicon-strip vertex detector surrounding the
$pp$ interaction region (VELO), a large-area silicon-strip detector located
upstream of a dipole magnet with a bending power of about $4{\rm\,Tm}$, and
three stations of silicon-strip detectors and straw drift tubes placed
downstream. The combined tracking system provides a momentum ($p$) measurement
with relative uncertainty that varies from 0.4% at 5 GeV to 0.6% at 100 GeV.
(We use natural units where $c$=1.) The impact parameter (IP) is defined as
the minimum track distance with respect to the primary vertex (PV). For tracks
with large transverse momentum ($p_{\rm T}$) with respect to the proton beam
direction, the IP resolution is approximately 20$\,\upmu\rm m$. Charged
hadrons are identified using two ring-imaging Cherenkov (RICH) detectors.
Photon, electron and hadron candidates are identified by a calorimeter system
consisting of scintillating-pad and pre-shower detectors, an electromagnetic
calorimeter and a hadronic calorimeter. Muons are identified by a system
composed of alternating layers of iron and multiwire proportional chambers.

Figure 1: Feynman diagram for $B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-}$ decay
via a Majorana neutrino labelled $N$.

The LHCb trigger [9] consists of a hardware stage, based on information from
the calorimeter and muon systems, followed by a software stage that performs
full event reconstruction. The hardware trigger selects either a single muon
candidate with $\mbox{$p_{\rm T}$}>1.64$ GeV, or two muons with the product of
their $p_{\rm T}$ values being greater than 1.69 GeV2. In the subsequent
software stage a muon candidate must form a vertex with one or two additional
tracks that are detached from the PV. The trigger efficiency decreases for
large lifetime Majorana neutrinos. Simulations are performed using Pythia [10]
with the specific tuning given in Ref. [11], and the LHCb detector description
based on Geant4 [12, *Agostinelli:2002hh] described in Ref. [14]. Decays of
$b$ hadrons are based on EvtGen [15]. Simulation of
$B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-}$ is carried out in two steps, the first
being the two body decay $B^{-}\rightarrow N\mu^{-}$, where $N$ is a putative
Majorana neutrino, and the second $N\rightarrow\pi^{+}\mu^{-}$.

In both categories $\cal{S}$ and $\cal{L}$, only tracks that start in the VELO
are used. We require muon candidates to have $p>3$ GeV and $\mbox{$p_{\rm
T}$}>0.75$ GeV, as muon detection provides fewer fakes above these values. The
hadron must have $p>2$ GeV and $\mbox{$p_{\rm T}$}>1.1$ GeV, in order to be
tracked well. Muon candidate tracks are required to have hits in the muon
chambers. The same criteria apply for the channel we use for normalization
purposes, $B^{-}\rightarrow{J\mskip-3.0mu/\mskip-2.0mu\psi\mskip 2.0mu}K^{-}$
with ${J\mskip-3.0mu/\mskip-2.0mu\psi\mskip 2.0mu}\rightarrow\mu^{+}\mu^{-}$.
Pion and kaon candidates must be positively identified in the RICH systems.
For the $\cal{S}$ case and the normalization channel, candidate $B^{-}$
combinations must form a common vertex with a $\chi^{2}$ per number of degrees
of freedom (ndf) less than 4. For the $\cal{L}$ candidates we require that the
$\pi^{+}\mu^{-}$ tracks form a neutrino candidate ($N$) decay vertex with a
$\chi^{2}<10$. A $B^{-}$ candidate decay vertex is searched for by
extrapolating the $N$ trajectory back to a near approach with another
$\mu^{-}$ candidate, which must form a vertex with the other muon having a
$\chi^{2}<4$. The distance between the $\pi^{+}\mu^{-}$ and the primary vertex
divided by its uncertainty must be greater than 10. The $p_{\rm T}$ of the
$\pi^{+}\mu^{-}$ pair must also exceed 700 MeV. For both $\cal{S}$ and
$\cal{L}$ cases, we require that the cosine of the angle between the $B^{-}$
candidate momentum vector and the line from the PV to the $B^{-}$ vertex be
greater than 0.99999. The two cases are not exclusive, with 16% of the event
candidates appearing in both.

The mass spectra of the selected candidates are shown in Fig. 2. An extended
unbinned likelihood fit is performed to the
${J\mskip-3.0mu/\mskip-2.0mu\psi\mskip 2.0mu}K^{-}$ mass spectrum with a
double-Crystal Ball function [16] plus a triple-Gaussian background to account
for partially reconstructed $B$ decays and a linear function for combinatoric
background. We find $282\,774\pm 543$ signal events in the normalization
channel. Backgrounds in the $\pi^{+}\mu^{-}\mu^{-}$ final state come from $B$
decays to charmonium and combinatoric sources. Charmonium backgrounds are
estimated using fully reconstructed ${J\mskip-3.0mu/\mskip-2.0mu\psi\mskip
2.0mu}K^{-}(\pi^{-})$ and $\psi(2S)K^{-}(\pi^{-})$ events and are indicated by
shaded regions; they can peak at the $B^{-}$ mass. No signal is observed in
either the ${\cal{S}}$ or ${\cal{L}}$ samples.

We use the $\text{CL}_{\text{s}}$ method to set upper limits [17], which
requires the determination of the expected background yields and total number
of events in the signal region. We define the signal region as the mass
interval within $\pm 2\sigma$ of the $B^{-}$ mass where $\sigma$ is the mass
resolution, specifically $5238.6-5319.8$ MeV. Peaking background shapes and
normalizations are fixed from exclusive reconstructions in data. We fit the
distributions outside of the $B^{-}$ signal region with a sum of the peaking
background tails, where both shape and normalization are fixed, and linear
functions to account for the combinatorial backgrounds. The interpolated
combinatoric background in each signal region is combined with the peaking
background to determine the total background.

Figure 2: Invariant mass distributions with fits overlaid of candidate mass
spectra for (a) ${J\mskip-3.0mu/\mskip-2.0mu\psi\mskip 2.0mu}K^{-}$, (b)
$\pi^{+}\mu^{-}\mu^{-}$ ($\cal{S}$) , and (c) $\pi^{+}\mu^{-}\mu^{-}$
($\cal{L}$). Backgrounds are (green) shaded; they peak under the signal in (b)
and (c). The dotted lines show the combinatorial backgrounds only. The solid
line shows the sum of both backgrounds.

In the signal $B$ mass range there are 19 events in the $\cal{S}$ sample and
60 events in the $\cal{L}$ sample. The $\cal{S}$ and $\cal{L}$ background fit
yields are 17.8$\pm$3.2, and 54.5$\pm$5.4, respectively, in the same region.

The detection efficiency varies as a function of neutrino mass, $m_{N}$, and
changes for the $\cal{L}$ sample with $\tau_{N}$. To quote an upper limit on
the branching fraction for the $\cal{S}$ sample we take the average detection
efficiency, as determined by simulation, with respect to the normalization
mode of 0.687$\pm$0.001. In computing the limit we include the uncertainties
on background yields obtained from the fit to the $m(\pi^{+}\mu^{-}\mu^{-})$
distribution, and the systematic uncertainty described below. The
normalization is obtained from the number of
${J\mskip-3.0mu/\mskip-2.0mu\psi\mskip 2.0mu}K^{-}$ events and the known rate
of ${\cal{B}}(B^{-}\rightarrow{J\mskip-3.0mu/\mskip-2.0mu\psi\mskip
2.0mu}K^{-},~{}{J\mskip-3.0mu/\mskip-2.0mu\psi\mskip
2.0mu}\rightarrow\mu^{+}\mu^{-})=(6.04\pm 0.26)\times 10^{-5}$ [18, 19]. We
find

${\cal{B}}(B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-})<4.0\times
10^{-9}\rm{~{}at~{}}95\%\rm{~{}confidence~{}level~{}(C.L.)}$

This limit is applicable for $\tau_{N}$ $\lesssim 1$ ps. The total systematic
uncertainty is 6.6%. The largest source is
${\cal{B}}(B^{-}\rightarrow{J\mskip-3.0mu/\mskip-2.0mu\psi\mskip 2.0mu}K^{-})$
(4.2%), followed by modeling of the efficiency ratio (3.5%) and backgrounds
(3.5%), relative particle identification efficiencies (0.5%), tracking
efficiency differences for kaons versus pions (0.5%), and yield of the
normalization channel (0.4%).

We also search for signals as a function of $m_{N}$. The $\pi^{+}\mu^{-}$ mass
spectra are shown in Fig. 3 for both $\cal{S}$ and $\cal{L}$ selections,
requiring that the $\pi^{+}\mu^{-}\mu^{-}$ mass be restricted to the $B^{-}$
signal range. There is an obvious peak around 3100 MeV from misidentified
${J\mskip-3.0mu/\mskip-2.0mu\psi\mskip 2.0mu}K^{-}$ (or $\pi^{-}$) events. The
$\pi^{+}\mu^{-}$ mass spectra are fitted with a function derived from fitting
the upper $B^{-}$ sideband regions, from $5319.8-5400.0$ MeV, for the
combinatoric background, and peaking background components obtained from
simulation.

Figure 3: Invariant $\pi^{+}\mu^{-}$ mass distribution for
$\pi^{+}\mu^{-}\mu^{-}$ candidates with masses restricted to $\pm 2\sigma$ of
$B^{-}$ mass for the (a) $\cal{S}$ and (b) $\cal{L}$ selections. The shaded
regions indicate the estimated peaking backgrounds. Backgrounds that peak
under the signal in (a) and (b) are (green) shaded. The dotted lines show the
combinatorial backgrounds only. The solid line the sum of both backgrounds.
(In (a) there are two combinations per event.)

As there is no evidence for a signal, upper limits are set by scanning across
the $m_{N}$ spectrum. At every 5 MeV step beginning at 250 MeV and ending at
5000 MeV we define a $\pm 3\sigma$ search region, where $\sigma$ ranges from
approximately 3 MeV at low mass to 24 MeV at high mass. The mass resolution is
determined from fitting signals in other LHCb data [2]. The fitted background
is then subtracted from the event yields in each interval. The upper limit at
$95\%$ C.L. of ${\cal{B}}(B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-})$ at each mass
value is computed using the CLs method. The simulated efficiency ratio to the
normalization mode averages about 0.8 up to 4000 MeV, and then approaching the
phase space boundary, sharply decreases to 0.2 at 5000 MeV. The results of
this scan are shown in Fig. 4.

Figure 4: Upper limit on ${\cal{B}}(B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-})$ at
$95\%$ C.L. as a function of $m_{N}$ in 5 MeV intervals for $\cal{S}$ selected
events.

The efficiency is highest for $\tau_{N}$ of a few ps, and decreases rapidly
until about 200 ps when it levels off until about 1000 ps, beyond which it
slowly vanishes as most of the decays occur outside of the vertex detector.
For $\cal{L}$ candidates, we set upper limits as a function of both $m_{N}$
and lifetime by performing the same scan in mass as before, but applying
efficiencies appropriate for individual lifetime values between 1 and 1000 ps.
The number of background events is extracted from the sum of combinatorial and
peaking backgrounds in the fit to the $m(\pi^{+}\mu^{-})$ distribution in the
same manner as for the $\cal{S}$ sample. The estimated signal yield is the
difference between the total number of events computed by counting the number
in the interval and the fitted background yield. We take the $\tau_{N}$
dependence into account by using different efficiencies for each lifetime
step. The two-dimensional plot of the upper limit on
${\cal{B}}(B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-})$, computed using the
$\text{CL}_{\text{s}}$ method, is shown in Fig. 5.

Figure 5: Upper limits on ${\cal{B}}(B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-})$
at 95% C.L. as a function of $m_{N}$, in 5 MeV intervals, for specific values
of $\tau_{N}$.

Model dependent upper limits on the coupling of a single fourth-generation
Majorana neutrino to muons, $|V_{\mu 4}|$, for each value of $m_{N}$ are
extracted using the formula from Atre et al. [7]

${\cal{B}}(B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-})=\frac{G_{F}^{4}f_{B}^{2}f_{\pi}^{2}m_{B}^{5}}{128\pi^{2}\hbar}{|V_{ub}V_{ud}|^{2}}\tau_{B}\left(1-\frac{m^{2}_{N}}{m_{B}^{2}}\right)\frac{m_{N}}{\Gamma_{N}}|V_{\mu
4}|^{4},$ (1)

with $G_{F}=1.166377\times 10^{-5}\mathrm{\,Ge\kern-1.00006ptV}^{-2}$,
$f_{B}=0.19\mathrm{\,Ge\kern-1.00006ptV}$,
$f_{\pi}=0.131\mathrm{\,Ge\kern-1.00006ptV}$, $|V_{ub}|=0.004$,
$|V_{ud}|=0.9738$, $m_{B}=5.279\mathrm{\,Ge\kern-1.00006ptV}$,
$\tau_{B}=1.671$ ps, and $\hbar=6.582\times
10^{-25}\mathrm{\,Ge\kern-1.00006ptV}\,\rm{\,s}$ [19]. The total neutrino
decay width, $\Gamma_{N}$, is a function of $m_{N}$ and proportional to
$|V_{\mu 4}|^{2}$. In order to set limits on $|V_{\mu 4}|^{2}$ a model for
$\Gamma_{N}$ is required. The purely leptonic modes are specified in Ref. [7].
For the hadronic modes we use the fraction of times the charged current
manifests itself as a single charged pion in $\tau^{-}$ and $B^{-}$ decays,
giving an additional $m^{3}_{N}$ dependent factor in $\Gamma_{N}$. The total
width for Majorana neutrino decay then is

$\Gamma_{N}=\left[3.95m^{3}_{N}+2.00m^{5}_{N}(1.44m^{3}_{N}+1.14)\right]10^{-13}|V_{\mu
4}|^{2},$ (2)

where $m_{N}$ and $\Gamma_{N}$ are in units of GeV. The first term corresponds
to fully leptonic three-body decays, while the second is for decays into one
lepton and hadrons.

To obtain upper limits on $|V_{\mu 4}|^{2}$ for each value of $m_{N}$ we
assume a value for $|V_{\mu 4}|$, and calculate $\Gamma_{N}$. This allows us
to determine the $\tau_{N}$ dependent detection efficiency. We then use Eq.
(1) to find the branching fraction. The value of $|V_{\mu 4}|$ is adjusted to
match the previously determined upper limit value (see Fig. 5). The resulting
95% C.L. limit on $|V_{\mu 4}|^{2}$ is shown in Fig. 6 as a function of
$m_{N}$. Limits have been derived by Atre et al. [7] for other experiments
using different assumptions about the dependence of $\Gamma_{N}$ with $m_{N}$,
and thus cannot be directly compared. More searches exist for higher mass
neutrinos [20, *Aad:2011vj, *ATLAS:2012ak]. The results presented here
supersede previous LHCb results [2, *Aaij:2011ex], significantly improve the
limits on the $B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-}$ branching fraction and
extend the lifetime range of the Majorana neutrino search from a few
picoseconds to one nanosecond.

Figure 6: Upper limits at 95% C.L. on $|V_{\mu 4}|^{2}$ are shown as a
function of $m_{N}$ for ${\cal{L}}$ events.

In conclusion, we have searched for on-shell Majorana neutrinos coupling to
muons in the $B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-}$ decay channel as a
function of $m_{N}$ between $250-5000$ MeV and for lifetimes up to
$\approx$1000 ps. In the absence of a significant signal, we set upper limits
on the $B^{-}\rightarrow\pi^{+}\mu^{-}\mu^{-}$ branching fraction and the
coupling $|V_{\mu 4}|^{2}$ as a function of the neutrino mass.

We express our gratitude to our colleagues in the CERN accelerator departments
for the excellent performance of the LHC. We thank the technical and
administrative staff at the LHCb institutes. We acknowledge support from CERN
and from the national agencies: CAPES, CNPq, FAPERJ and FINEP (Brazil); NSFC
(China); CNRS/IN2P3 and Region Auvergne (France); BMBF, DFG, HGF and MPG
(Germany); SFI (Ireland); INFN (Italy); FOM and NWO (The Netherlands); SCSR
(Poland); MEN/IFA (Romania); MinES, Rosatom, RFBR and NRC “Kurchatov
Institute” (Russia); MinECo, XuntaGal and GENCAT (Spain); SNSF and SER
(Switzerland); NAS Ukraine (Ukraine); STFC (United Kingdom); NSF (USA). We
also acknowledge the support received from the ERC under FP7. The Tier1
computing centres are supported by IN2P3 (France), KIT and BMBF (Germany),
INFN (Italy), NWO and SURF (The Netherlands), PIC (Spain), GridPP (United
Kingdom). We are indebted to the communities behind the multiple open source
software packages we depend on. We are also thankful for the computing
resources and the access to software R&D tools provided by Yandex LLC
(Russia).

## References

  * [1] E. Majorana, Teoria simmetrica dell$\,{}^{\prime}\\!$elettrone e del positrone, Nuovo Cim. 14 (1937) 171
  * [2] LHCb collaboration, R. Aaij et al., Searches for Majorana neutrinos in $B^{-}$ decays, Phys. Rev. D85 (2012) 112004, arXiv:1201.5600
  * [3] LHCb collaboration, R. Aaij et al., Search for the lepton number violating decays $B^{+}\rightarrow\pi^{-}\mu^{+}\mu^{+}$ and $B^{+}\rightarrow K^{-}\mu^{+}\mu^{+}$, Phys. Rev. Lett. 108 (2012) 101601, arXiv:1110.0730
  * [4] BaBar collaboration, J. P. Lees et al., Search for lepton-number violating $B^{+}\rightarrow X^{-}\ell^{+}\ell^{+}$ decays, arXiv:1310.8238
  * [5] BELLE collaboration, O. Seon et al., Search for lepton-number-violating $B^{+}\rightarrow D^{-}\ell^{+}\ell^{{}^{\prime}+}$ decays, Phys. Rev. D84 (2011) 071106, arXiv:1107.0642
  * [6] MARK II collaboration, A. J. Weir et al., Upper limits on $D^{\pm}$ and $B^{\pm}$ decays to two leptons plus $\pi^{\pm}$ or $K^{\pm}$, Phys. Rev. D41 (1990) 1384
  * [7] A. Atre, T. Han, S. Pascoli, and B. Zhang, The search for heavy Majorana neutrinos, JHEP 05 (2009) 030, arXiv:0901.3589
  * [8] LHCb collaboration, A. A. Alves Jr. et al., The LHCb detector at the LHC, JINST 3 (2008) S08005
  * [9] R. Aaij et al., The LHCb trigger and its performance in 2011, JINST 8 (2013) P04022, arXiv:1211.3055
  * [10] T. Sjöstrand, S. Mrenna, and P. Z. Skands, PYTHIA 6.4 Physics and Manual, JHEP 0605 (2006) 026, arXiv:hep-ph/0603175
  * [11] I. Belyaev et al., Handling of the generation of primary events in Gauss, the LHCb simulation framework, Nuclear Science Symposium Conference Record (NSS/MIC) IEEE (2010) 1155
  * [12] GEANT4 collaboration, J. Allison et al., Geant4 developments and applications, IEEE Trans. Nucl. Sci. 53 (2006) 270
  * [13] GEANT4 collaboration, S. Agostinelli et al., GEANT4: a simulation toolkit, Nucl. Instrum. Meth. A506 (2003) 250
  * [14] M. Clemencic et al., The LHCb simulation application, Gauss: design, evolution and experience, J. Phys. Conf. Ser. 331 (2011) 032023
  * [15] D. Lange, The EvtGen particle decay simulation package, Nucl. Instrum. Meth. A462 (2001) 152
  * [16] T. Skwarnicki, A study of the radiative cascade transitions between the Upsilon-prime and Upsilon resonances, PhD thesis, Institute of Nuclear Physics, Krakow, 1986, DESY-F31-86-02
  * [17] T. Junk, Confidence level computation for combining searches with small statistics, Nucl. Instrum. Meth. A434 (1999) 1435
  * [18] LHCb collaboration, R. Aaij et al., Amplitude analysis and branching fraction measurement of $\kern 1.79993pt\overline{\kern-1.79993ptB}{}^{0}_{s}\rightarrow{J\mskip-3.0mu/\mskip-2.0mu\psi\mskip 2.0mu}K^{+}\kern-1.60004ptK^{-}$, Phys. Rev. D87 (2013) 072004, arXiv:1302.1213
  * [19] Particle Data Group, J. Beringer et al., Review of particle properties, Phys. Rev. D86 (2012) 010001, and 2013 partial update for the 2014 edition
  * [20] CMS collaboration, S. Chatrchyan et al., Search for heavy Majorana neutrinos in $\mu^{+}\mu^{+}[\mu^{-}\mu^{-}]$ and $e^{+}e^{+}[e^{-}e^{-}]$ events in $pp$ collisions at $\sqrt{s}=7$ TeV, Phys. Lett. B717 (2012) 109, arXiv:1207.6079
  * [21] ATLAS collaboration, G. Aad et al., Inclusive search for same-sign dilepton signatures in $pp$ collisions at $\sqrt{s}=7$ TeV with the ATLAS detector, JHEP 1110 (2011) 107, arXiv:1108.0366
  * [22] ATLAS collaboration, G. Aad et al., Search for heavy neutrinos and right-handed $W$ bosons in events with two leptons and jets in $pp$ collisions at $\sqrt{s}=7$ TeV with the ATLAS detector, Eur. Phys. J. C72 (2012) 2056, arXiv:1203.5420