# Robust Domination in Random Graphs

Ghurumuruhan Ganesan

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

In this paper, we study “robust” dominating sets of random graphs that retain
the domination property even if a small _deterministic_ set of edges are
removed. We motivate our study by illustrating with examples from wireless
networks in harsh environments. We then use the probabilistic method and
martingale difference techniques to determine sufficient conditions for the
asymptotic optimality of the robust domination number. We also discuss robust
domination in sparse random graphs where the number of edges grows at most
linearly in the number of vertices.

Key words: Random Graphs; Robust Domination; Sparse Regime.

AMS 2000 Subject Classification: Primary: 06C05; 05C62;

##  1 Introduction

Domination of graphs is an important topic from both theoretical and
application perspectives and has been extensively studied in the random graph
context as well. Throughout, random graphs refer to the Bernoulli or Erdös-
Rényi random graph $G$ obtained by allowing each edge in the complete graph on
$n$ vertices to be present with a certain probability $p,$ independent of the
other edges (for formal definitions, please refer to Section 2). In wieland ,
two point concentration for the domination number of $G$ is obtained for the
case when $p$ is essentially a constant and this concentration phenomenon was
extended for a wide range of $p$ in glebov . Since then many other variants of
domination have also been studied (see for e.g. clark wang ).

Dominating sets also occur naturally in the design of wireless networks. In wu
, an early application of dominating sets is explored for routing in ad hoc
wireless networks devoid of any central control. The nodes belonging to the
dominating sets are interpreted as “gateways” through which any two nodes in
the network can communicate with minimal delay. This was extended to higher
dimensional wireless networks in zou  and for a survey on the usage of
domination in communications, we refer to du .

Ad hoc networks are especially fragile in terms of linkage in the sense that
the sensors are continually moving around and so links may break or form
randomly. Moreover, due to environmental constraints like shadowing and
fading, it may happen that links between certain nodes are simply not
feasible. In such a situation, it is of natural interest to know whether the
domination property is still retained and this is the topic of study in this
paper. We consider dominating sets in the Bernoulli random graph $G$ and are
interested in obtaining “robust” dominating sets that retain the domination
property even if a small deterministic set of edges are removed. We obtain
sufficient conditions for asymptotic optimality of the robust domination
number in terms of the maximum vertex degree and the number of edges of the
graph that has been removed from $K_{n}.$

The paper is organized as follows: In Section 2, we state and prove our main
result regarding robust domination number in random graphs for the dense
regime. We use the probabilistic method to establish sufficient conditions for
asymptotic optimality. Next, in Section 3, we also discuss our results for the
robust domination in the sparse regime.

##  2 Robust Domination

Let $K_{n}$ be the complete graph on $n$ vertices and let $\\{Z(f)\\}_{f\in
K_{n}}$ be independent random variables indexed by the edge set of $K_{n}$ and
with distribution

$\mathbb{P}(Z(f)=1)=p=1-\mathbb{P}(Z(f)=0)$ (2.1)

where $0<p<1.$ Let $G$ be the random graph formed by the union of all edges
$f$ satisfying $Z(f)=1$ and let $H$ be any _deterministic_ subgraph of $K_{n}$
with $m=m(n)$ edges and a maximum vertex degree of $\Delta=\Delta(n).$

A set ${\cal S}\subset V$ is said to be a _dominating set_ of $G\setminus H$
if each vertex in $V\setminus{\cal S}$ is adjacent to at least one vertex in
${\cal S}$ in the graph $G\setminus H.$ We also say that ${\cal S}$ is a
$H-$_robust_ dominating set or simply a robust dominating set. The $H-$_robust
domination number_ or simply the robust domination number is defined to be the
minimum size of a dominating set in $G\setminus H$ and is denoted by
$\gamma(G\setminus H).$

We seek conditions on $H$ so that the robust domination number
$\Gamma_{n}:=\gamma(G\setminus H)$ and the actual domination number
$\gamma(G)\leq\Gamma_{n}$ are of the same order. Intuitively, if $H$ is
sparse, then we expect $\Gamma_{n}$ and $\gamma(G)$ to be close with high
probability, i.e., with probability converging to one as $n\rightarrow\infty.$
This is illustrated in our first result below that obtains bounds for
$\Gamma_{n}$ in terms of the maximum vertex degree $\Delta$ of the graph $H.$
For $0<x,y<1$ we define $u_{n}(x,y):=\frac{\log(nx)}{|\log(1-y)|}$ and set
$u_{n}:=u_{n}(p,p).$ Moreover, we use the notation $a_{n}=o(b_{n})$ to denote
that $\frac{a_{n}}{b_{n}}\longrightarrow 0,$ as $n\rightarrow\infty.$

###### Lemma 1

The following properties hold:
$(a)$ Let $\lambda_{a}:=np$ and $\lambda_{b}:=n|\log(1-p)|>\lambda_{a}.$ For
every $\theta>2,$ there exists a $\lambda_{0}=\lambda_{0}(\theta)>0$ such that
if $\frac{\lambda_{0}}{n}\leq p\leq 1-\frac{1}{n^{3}},$ then

$\mathbb{P}\left(\Gamma_{n}\geq
u_{n}\left(1-\frac{\theta\log\log{\lambda_{b}}}{\log{\lambda_{a}}}\right)\right)\geq
1-\exp\left(-\frac{3n}{8}\cdot\frac{(\log{\lambda}_{b})^{\theta}}{\lambda_{a}}\right).$
(2.2)

$(b)$ Let $\Delta$ be the maximum vertex degree of $H$ and suppose
$np\longrightarrow\infty$ and
$p\leq p_{0}$ for some constant $0<p_{0}<1.$ For every $\epsilon>0$ and all
$n$ large,

$\mathbb{P}\left(\Gamma_{n}\leq u_{n}(1+\epsilon)+\Delta\right)\geq
1-\frac{1}{\log(np)}.$ (2.3)

Consequently if $\Delta=o(u_{n})$ and $p\leq p_{0}$ is such that
$np\longrightarrow\infty,$ then $\frac{\Gamma_{n}}{u_{n}}\longrightarrow 1$ in
probability as $n\rightarrow\infty.$

The condition $np\longrightarrow\infty$ ensures that $G$ is reasonably dense
in terms of its vertex degrees. In particular if the edge probability $p$ is a
constant, then $u_{n}$ is of the order of $\log{n}$ and moreover both
$\lambda_{a}$ and $\lambda_{b}$ are of the order of $n.$ Setting $\theta=3$ in
(2.2), we then get that $\Gamma_{n}\geq
u_{n}\left(1-O\left(\frac{\log\log{n}}{\log{n}}\right)\right)$ with
probability at leat $1-e^{-C(\log{n})^{3}}$ for some constant $C>0.$
Similarly, the final statement (2.3) implies that if $\Delta=o(\log{n}),$ then
$\Gamma_{n}\leq u_{n}(1+2\epsilon)$ with high probability, for any arbitrary
constant $\epsilon>0.$

Combining the observations of the previous paragraph, we get that
$\Gamma_{n}\sim u_{n}$ with high probability, where we use the notation
$a_{n}\sim b_{n}$ to denote that
$\frac{a_{n}}{b_{n}}\longrightarrow 1$ as $n\rightarrow\infty.$ Thus the
robust domination number satisfies
$\Gamma_{n}\sim u_{n}\sim\gamma(G)$ and is therefore asymptotically equal to
the “ideal” domination number $\gamma(G),$ with high probability.

_Proof of Lemma 1 $(a)$_: Since $\gamma(G\setminus H)\geq\gamma(G),$ it
suffices to lower bound $\gamma(G)$ and for completeness, we give a small
proof using a union bound argument covering all possibilities, as in wieland
glebov . Specifically, letting $\lambda_{a}:=np,\lambda_{b}=n|\log(1-p)|$ and
$t_{n}:=\frac{\log{\lambda_{a}}-\theta\log\log{\lambda_{b}}}{|\log(1-p)|}$
vertices, we show that there exists a dominating set containing $t_{n}$
vertices, with high probability.

We begin with upper and lower bounds for $t_{n}.$ Using $|\log(1-p)|>p,$ we
see that
$t_{n}\leq\frac{\log{\lambda_{a}}}{p}=n\frac{\log{\lambda_{a}}}{\lambda_{a}}<\frac{n}{4}$
if $\lambda_{a}\geq\lambda_{0},$ a sufficiently large absolute constant.
Moreover, we have that $\lambda_{a}>(\log{\lambda_{b}})^{2\theta}$ for all
$n\geq N_{0}=N_{0}(\theta)$ large, provided
$np\geq\lambda_{0}=\lambda_{0}(\theta)$ is large. Indeed if
$p\leq\frac{1}{2},$ then using $|\log(1-p)|<2p,$ we get that
$\lambda_{a}-(\log{\lambda_{b}})^{2\theta}\geq np-(\log(2np))^{2\theta}>0$ if
$np\geq\lambda_{0}=\lambda_{0}(\theta)$ is sufficiently large. On the other
hand if $\frac{1}{2}\leq p\leq 1-\frac{1}{n^{3}},$ then
$\lambda_{a}=np>\frac{n}{2}$ and

$(\log{\lambda_{b}})^{2\theta}=\left(\log
n+\log\log\left(\frac{1}{1-p}\right)\right)^{2\theta}\leq(\log{n}+6\log\log{n})^{2\theta}<\frac{n}{2}$

for all $n\geq N_{0}=N_{0}(\theta)$ large. Summarizing, we get that

$\frac{\log{\lambda_{a}}}{2|\log(1-p)|}<t_{n}<n\frac{\log{\lambda_{a}}}{\lambda_{a}}<\frac{n}{4}$
(2.4)

for all $n$ large.

Let ${\cal S}$ be any set containing $t_{n}$ vertices. For a vertex $v\in{\cal
S}^{c},$ the probability that $v$ is not adjacent to any vertex of ${\cal S}$
is $(1-p)^{t_{n}}=\frac{(\log{\lambda_{b}})^{\theta}}{\lambda_{a}}.$ Thus the
vertex $v$ is adjacent to some vertex of ${\cal S}$ with probability
$1-\frac{(\log{\lambda_{b}})^{\theta}}{\lambda_{a}}$ and so if $E_{dom}({\cal
S})$ is the event that ${\cal S}$ is a dominating set, then using the fact
that the complement set ${\cal S}^{c}$ has $n-t_{n}\geq\frac{3n}{4}$ vertices
(see (2.4)), we get that

$\mathbb{P}\left(E_{dom}\left({\cal
S}\right)\right)\leq\left(1-\frac{(\log{\lambda_{b}})^{\theta}}{\lambda_{a}}\right)^{\frac{3n}{4}}\leq\exp\left(-\frac{3n}{4}\cdot\frac{(\log{\lambda_{b}})^{\theta}}{\lambda_{a}}\right).$

Since there are ${n\choose
t_{n}}\leq\left(\frac{ne}{t_{n}}\right)^{t_{n}}=\exp\left(t_{n}\log\left(\frac{ne}{t_{n}}\right)\right)$
sets of size $t_{n},$ we use the union bound and the bounds in (2.4), to see
that the probability that there exists a dominating set of size at most
$t_{n}$ is bounded above by

$\displaystyle\exp\left(t_{n}\log\left(\frac{ne}{t_{n}}\right)\right)\exp\left(-\frac{3n}{4}\cdot\frac{(\log{\lambda_{b}})^{\theta}}{\lambda_{a}}\right)$
$\displaystyle\;\;\leq\;\;\exp\left(n\frac{\log{\lambda_{a}}}{\lambda_{a}}\log\left(\frac{2ne|\log(1-p)|}{\log{\lambda_{a}}}\right)\right)\exp\left(-\frac{3n}{4}\cdot\frac{(\log{\lambda_{b}})^{\theta}}{\lambda_{a}}\right)$
$\displaystyle\;\;=\;\;\exp\left(n\frac{\log{\lambda_{a}}}{\lambda_{a}}\log\left(\frac{2e\lambda_{b}}{\log{\lambda_{a}}}\right)\right)\exp\left(-\frac{3n}{4}\cdot\frac{(\log{\lambda_{b}})^{\theta}}{\lambda_{a}}\right)$
$\displaystyle\;\;\leq\;\;\exp\left(n\frac{\log{\lambda_{a}}}{\lambda_{a}}\log\left(2e\lambda_{b}\right)\right)\exp\left(-\frac{3n}{4}\cdot\frac{(\log{\lambda_{b}})^{\theta}}{\lambda_{a}}\right)$
$\displaystyle\;\;\leq\;\;\exp\left(n\frac{(\log(2e\lambda_{b}))^{2}}{\lambda_{a}}\right)\exp\left(-\frac{3n}{4}\cdot\frac{(\log{\lambda_{b}})^{\theta}}{\lambda_{a}}\right)$
$\displaystyle\;\;\leq\;\;\exp\left(-\frac{3n}{8}\cdot\frac{(\log{\lambda}_{b})^{\theta}}{\lambda_{a}}\right)$
(2.5)

for all $n\geq N_{0}$ not depending on $\lambda_{a}$ or $\lambda_{b},$ where
the second inequality in (2.5) is true provided
$np=\lambda_{a}\geq\lambda_{0}$ is large and the final inequality in (2.5) is
true if we choose $\theta>2$ strictly.

_Proof of Lemma 1 $(b)$_: Let ${\cal D}$ be any set containing
$(1+\epsilon)u_{n}+\Delta$ vertices. Each vertex $v\notin{\cal D}$ is adjacent
to at least $(1+\epsilon)u_{n}$ vertices of ${\cal D}$ in the graph
$K_{n}\setminus H$ and so the probability that $v$ is _not_ adjacent to any
vertex of ${\cal D}$ in $G\setminus H,$ is at most
$(1-p)^{(1+\epsilon)u_{n}}=\frac{1}{(np)^{1+\epsilon}}.$ Thus if ${\cal B}$ is
the set of all vertices not dominated by ${\cal D}$ in $G\setminus H,$ then
$\mathbb{E}\\#{\cal B}\leq\frac{n}{(np)^{1+\epsilon}}$ and so a direct
application of Markov inequality gives that

$\mathbb{P}\left(\\#{\cal
B}\geq\frac{n\log(np)}{(np)^{1+\epsilon}}\right)\leq\frac{1}{\log(np)}.$ (2.6)

By definition ${\cal D}\cup{\cal B}$ is a dominating set in $G\setminus H$ and
has size

$\\#({\cal D}\cup{\cal
B})\leq(1+\epsilon)u_{n}+\Delta+\frac{n\log(np)}{(np)^{1+\epsilon}}$ (2.7)

with probability at least $1-\frac{1}{\log{np}},$ by (2.6). Also since $p\leq
p_{0}$ a constant, we have that $|\log(1-p)|\leq\sum_{k\geq
1}p^{k}\leq\frac{p}{1-p}\leq\frac{p}{1-p_{0}}$ and so

$\frac{n\log(np)}{(np)^{1+\epsilon}}=\frac{1}{(np)^{\epsilon}}\frac{\log(np)}{p}<\frac{1}{(np)^{\epsilon}}\frac{u_{n}}{1-p_{0}}<\epsilon
u_{n}$

for all $n$ large, since $np\longrightarrow\infty.$ From (2.7), we then the
upper deviation bound in (2.3).

From the discussion following Lemma $1,$ we see that if the edge probability
$p$ is a constant, then $\Delta=o(\log{n})$ is sufficient to ensure the
asymptotic equivalence of the robust and the ideal domination numbers.
However, in this case we also know that with high probability, the vertex
degree in the random graph $G$ in fact grows linearly with $n,$ which is much
larger than $\log{n}.$ Therefore could we, perhaps under additional
assumptions, establish asymptotic equivalence for conflict graphs $H$ that are
sparse _in comparison_ to $G$? Addressing this issue, we have the following
result for random graphs with a convergent edge probability sequence.

###### Theorem 2.1

Suppose $np\longrightarrow\infty,\;\;p\leq 1-\frac{1}{n^{3}}$ and
$p=p(n)\longrightarrow p_{0}$ for some constant $0\leq p_{0}\leq 1.$ As
before, let $H=H(n)$ be any deterministic graph with maximum vertex degree
$\Delta=\Delta(n)$ and containing $m=m(n)$ edges. If either

$\Delta=o(n(1-p))\;\;\;\;\text{ or }\;\;\;\;m=o(nu_{n}(1-p)),$ (2.8)

then $\frac{\Gamma_{n}}{u_{n}}\longrightarrow 1$ in probability as
$n\rightarrow\infty.$

Continuing with constant edge probability example, we see from Theorem 2.1
that if $p$ is a constant, then either $\Delta=o(n)$ or $m=o(n\log{n})$ is
sufficient for $\Gamma_{n}$ and $\gamma(G)$ to be asymptotically equal.

For the case $p_{0}=0$ which is of interest in communication networks, we see
that there are robust dominating sets that asymptotically have the same size
as the ideal dominating sets even if the number of edges removed per vertex is
much larger than the vertex degree itself. This is true because the expected
degree of a vertex in $G$ equals $(n-1)p\approx np$ and so by the standard
deviation estimate (A.1), we can deduce that each vertex has degree at most of
the order of $np$ with high probability. Condition (2.8) ensures that the
robust domination number is asymptotically optimal provided $\Delta=o(n),$
even if $\Delta$ is much larger than $np.$

To prove Theorem 2.1, we perform a case by case analysis of $\Gamma_{n}$ based
on the asymptotic edge probability $p_{0}.$ Recalling the definition of
$u_{n}(x,y)$ and $u_{n}=u_{n}(p,p)$ prior to Lemma 1, we have the following
result.

###### Lemma 2

Suppose that $\Delta\leq r_{0}n-1$ for some constant $0<r_{0}<1.$
$(a)$ For every $\epsilon>0$ there are positive constants
$\lambda_{i}=\lambda_{i}(\epsilon,r_{0}),i=1,2$ such that if
$\frac{\lambda_{1}}{n}\leq
p\leq\min\left(\frac{1}{2},1-\exp\left(-\frac{\epsilon^{2}(1-r_{0})}{16}\right)\right),$
then

$\mathbb{P}\left(\Gamma_{n}\leq\frac{(1+6\epsilon)u_{n}}{1-r_{0}}\right)\geq
1-z_{n},$ (2.9)

where

$z_{n}:=\min\left(\exp\left(-\frac{\lambda_{2}n}{4(np)^{(1+4\epsilon)(1-r_{0})^{-1}}}\right),\frac{1}{(np)^{\epsilon/2}}\right).$

$(b)$ For every $\epsilon>0$ and every constant $0<p<1,$ we have that

$\mathbb{P}\left(\Gamma_{n}\leq(1+\epsilon)u_{n}(p,p(1-\epsilon)-r_{0})\right)\geq
1-\exp\left(-\frac{\epsilon^{2}np}{8}\right).$ (2.10)

$(c)$ For every $\epsilon>0,$ there is a constant $C=C(\epsilon)>0$ such that
if
$q_{1}:=\max\left(1-p,\frac{\Delta}{n}\right)\leq 2^{-2/\epsilon-2}$ then

$\mathbb{P}\left(\Gamma_{n}\leq(1+\epsilon)u_{n}(p,1-q_{1})\right)\geq
1-\frac{C}{n^{\epsilon/2}}.$ (2.11)

Parts $(a),(b)$ and $(c)$ of Lemma 2 essentially obtain deviation upper bounds
for $\Gamma_{n}$ for the cases $p_{0}=0,0<p_{0}<1$ and $p_{0}=1,$
respectively.

We use the probabilistic method to prove Lemma 2 and so we begin with a couple
of common definitions. For integer $t\geq 1$ let ${\cal
X}:=(X_{1},\ldots,X_{t})$ be a random $t-$tuple chosen from $V^{t},$ that is
independent of the graph $G.$ Also let $\mathbb{P}_{X}$ denote the probability
distribution of ${\cal X}.$ In each of the three cases below, we choose the
tuple ${\cal X}$ appropriately so that certain niceness properties are
satisfied and exploit this to estimate the domination number.

_Proof of Lemma 2 $(a)$_: For a constant $0<\zeta<1$ to be determined later,
let $t=\frac{u_{n}}{1-\zeta}.$ Assuming that $X_{i},1\leq i\leq t$ are
independent and chosen uniformly randomly from $V,$ we estimate below the
number of vertices “left out” by the set ${\cal D}:=\\{X_{1},\ldots,X_{t}\\}.$
For a vertex $v,$ the $\mathbb{P}_{X}-$probability that the random variable
$X_{1}$ is equal to $v$ or adjacent to $v$ in $H$ is at most
$\frac{\Delta+1}{n}\leq r_{0}.$ Therefore if $Q(v)$ is the number of indices
$i,1\leq i\leq t$ such that $X_{i}$ is _not_ adjacent to $v$ in the graph $H,$
then $\mathbb{E}_{X}(Q(v))\geq t(1-r_{0})$ and using the standard deviation
estimate (A.1) we get for $\epsilon>0$ that

$\mathbb{P}_{X}\left(Q(v)\geq
t(1-r_{0})(1-\epsilon)\right)\leq\exp\left(-\frac{\epsilon^{2}}{4}t(1-r_{0})\right).$
(2.12)

In the Appendix we show that $u_{n}(x,x)=\frac{\log(nx)}{|\log(1-x)|}$ is
strictly decreasing for all $x>\frac{\lambda_{low}}{n}$ where
$\lambda_{low}>0$ is a sufficiently large absolute constant. Therefore if
$\frac{\lambda_{low}}{n}\leq
p\leq\lambda_{up}:=1-\exp\left(-\frac{\epsilon^{2}(1-r_{0})}{16}\right),$ then
for all $n\geq N_{0}(\epsilon,r_{0})$ large we have that

$t\geq u_{n}(p,p)\geq
u_{n}(\lambda_{up},\lambda_{up})\geq\frac{\log{n}}{2|\log(1-\lambda_{up})|}=\frac{8}{\epsilon^{2}(1-r_{0})}\log{n},$
(2.13)

where the second inequality in (2.13) is true since $\lambda_{up}$ is a
constant and so $\log(n\lambda_{up})\geq\frac{\log{n}}{2}$ for all $n$ large.
Therefore setting

$E_{tot}:=\bigcap_{v\notin{\cal D}}\left\\{Q(v)\geq
t(1-r_{0})(1-\epsilon)\right\\},$

we get from the union bound, (2.12) and (2.13) that

$\mathbb{P}_{X}\left(E_{tot}\right)\geq
1-n\cdot\frac{1}{n^{2}}=1-\frac{1}{n}.$

We assume henceforth that $E_{tot}$ occurs.

Next, we estimate the number of distinct entries in ${\cal X}.$ Since
$|\log(1-p)|>p,$ we get for any constant $\zeta>0$ that
$t=\frac{1}{1-\zeta}\frac{\log(np)}{|\log(1-p)|}<\frac{\log(np)}{p(1-\zeta)}<\frac{\epsilon
n}{2}(1-r_{0}),$ provided
$np\geq\lambda_{low}=\lambda_{low}(\epsilon,\zeta,r_{0})$ is large enough.
Now, for $i\neq j,$ the probability that $X_{i}$ equals $X_{j}$ is
$\frac{1}{n}$ and so the $\mathbb{P}_{X}-$expected number of repeated entries
is at most $\frac{t^{2}}{n}\leq\frac{\epsilon t}{2}(1-r_{0}).$ If $E_{rep}$ is
the event that the number of repeated entries is at most $t\epsilon(1-r_{0})$
then $\mathbb{P}_{X}(E^{c}_{rep})\leq\frac{1}{2},$ by the Markov inequality.
Combining with the estimate for $\mathbb{P}_{X}(E_{tot})$ in the previous
paragraph we then get from the union bound that $E_{tot}\cap E_{rep}$ occurs
with $\mathbb{P}_{X}-$probability at least $\frac{1}{2}-\frac{1}{n}>0.$

We assume henceforth that $E_{tot}\cap E_{rep}$ occurs so that each vertex $v$
is adjacent to least $t(1-\epsilon)(1-r_{0})-t\epsilon(1-r_{0})\geq
t(1-2\epsilon)(1-r_{0})$ and at most $t=\frac{u_{n}}{1-\zeta}$ vertices of
${\cal D},$ in the graph $K_{n}\setminus H.$ Setting
$1-\zeta:=\frac{(1-2\epsilon)(1-r_{0})}{1+\epsilon},$ we then get that the
probability of the event $J_{v}$ that $v$ is not adjacent to any vertex of
${\cal D}$ in the graph $G\setminus H,$ is at most
$(1-p)^{(1+\epsilon)u_{n}}=\frac{1}{(np)^{1+\epsilon}}$ and at least
$(1-p)^{t}=\frac{1}{(np)^{(1-\zeta)^{-1}}}.$ If $L_{tot}:=\sum_{v\notin{\cal
D}}1{1}(J_{v}),$ then $\mathbb{E}L_{tot}\leq\frac{n}{(np)^{1+\epsilon}}$ and a
direct application of the Markov inequality gives us that

$\mathbb{P}\left(L_{tot}\geq\frac{n}{(np)^{1+\epsilon/2}}\right)\leq\frac{1}{(np)^{\epsilon/2}}.$
(2.14)

Similarly $\mathbb{E}L_{tot}\geq\frac{n}{(np)^{(1-\zeta})^{-1}}$ and so using
the standard deviation estimate (A.1) we get that

$\mathbb{P}\left(L_{tot}\geq\frac{2n}{(np)^{1+\epsilon}}\right)\leq\exp\left(-\frac{Cn}{(np)^{(1-\zeta)^{-1}}}\right)\leq\exp\left(-\frac{Cn}{(np)^{(1+4\epsilon)/(1-r_{0})}}\right)$
(2.15)

since
$(1-\zeta)^{-1}=\frac{1+\epsilon}{(1-2\epsilon)(1-r_{0})}\leq\frac{1+4\epsilon}{1-r_{0}}$
provided $\epsilon>0$ is a small enough constant. We fix such an $\epsilon$
henceforth.

If $L_{tot}\leq\frac{n}{(np)^{1+\epsilon/2}},$ then $\Gamma_{n}\leq\\#{\cal
D}+L_{tot}\leq\frac{u_{n}}{1-\zeta}+\frac{n}{(np)^{1+\epsilon/2}}$ and
moreover, using $|\log(1-p)|<2p$ for $p<\frac{1}{2},$ we have for
$np\geq\lambda_{low}$ large enough that
$\frac{n}{(np)^{1+\epsilon/2}}<\epsilon\frac{\log(np)}{p}<2\epsilon u_{n}.$
Thus

$\Gamma_{n}\leq\left(\frac{1}{1-\zeta}+2\epsilon\right)u_{n}\leq\left(\frac{1+4\epsilon}{1-r_{0}}+2\epsilon\right)u_{n}\leq\frac{(1+6\epsilon)u_{n}}{1-r_{0}}$

and together with (2.14) and (2.15), this obtains the desired upper bound in
(2.9).

_Proof of Lemma 2 $(b)$_: We begin with a couple of preliminary calculations.
If $d_{G}(v)$ is the degree of $v$ in $G,$ then $\mathbb{E}d_{G}(v)=(n-1)p.$
Therefore from the deviation estimate (A.1), we get that $d_{G}(v)\geq
np(1-\epsilon)$ with probability at least
$1-\exp\left(-\frac{\epsilon^{2}}{5}np\right).$ Letting
$E_{deg}:=\bigcap_{v}\\{d_{G}(v)\geq np(1-\epsilon)\\},$ we get from the union
bound that

$\mathbb{P}(E_{deg})\geq 1-n\exp\left(-\frac{\epsilon^{2}}{5}np\right)\geq
1-\exp\left(-\frac{\epsilon^{2}}{8}np\right)$ (2.16)

for all $n$ large.

We henceforth assume that $E_{deg}$ occurs and let $X_{j},1\leq j\leq t$ be
independently and uniformly chosen from the vertex set $V$ also independent of
the graph $G.$ Let ${\cal N}(X_{i})$ be the set of all neighbours of $X_{i}$
in the graph $G\setminus H$ and set ${\cal N}[X_{i}]:=\\{X_{i}\\}\cup{\cal
N}(X_{i})$ to be the closed neighbourhood of $X_{i}.$ Setting ${\cal
B}:=\bigcup_{1\leq j\leq t}{\cal N}[X_{j}],$ we see that each vertex in ${\cal
B}$ is adjacent to at least one vertex in $\\{X_{j}\\}_{1\leq j\leq t}$ and so
${\cal D}:=\bigcup\\{X_{j}\\}_{1\leq j\leq t}\bigcup\left(V\setminus{\cal
B}\right)$ is a dominating set for $G\setminus H.$ Letting $\mathbb{P}_{X}$ be
the distribution of $\\{X_{j}\\}_{1\leq j\leq t},$ we see that the
$\mathbb{P}_{X}-$expected size of ${\cal D}$ is

$\mathbb{E}_{X}\\#{\cal D}\leq t+(n-\mathbb{E}_{X}\\#{\cal B})$ (2.17)

and in the rest of the proof below, we use telescoping to bound the expected
size of ${\cal B}.$

Formally, for $1\leq j\leq t$ we let ${\cal B}_{j}:=\bigcup_{1\leq i\leq
j}{\cal N}[X_{i}]$ and estimate the expected increment $\mathbb{E}_{X}\\#{\cal
B}_{j}-\mathbb{E}_{X}\\#{\cal B}_{j-1}.$ Adding these increments would then
give us the desired bound for ${\cal B}={\cal B}_{t}.$ Specifically, we have
by construction that $\\#{\cal B}_{j}=\\#{\cal B}_{j-1}+\\#\left({\cal
N}[X_{j}]\setminus{\cal B}_{j-1}\right)$ and for any set ${\cal S},$

$\displaystyle\\#\left({\cal N}[X_{j}]\cap{\cal S}\right)$ $\displaystyle=$
$\displaystyle\sum_{y\in{\cal S}}1{1}\left(y\in{\cal N}[X_{j}]\right)$
$\displaystyle=$ $\displaystyle\sum_{y\in{\cal
S}}1{1}(y=X_{j})+1{1}\left(y\in{\cal N}(X_{j})\right)$ $\displaystyle=$
$\displaystyle\sum_{y\in{\cal S}}1{1}(y=X_{j})+1{1}\left(X_{j}\in{\cal
N}(y)\right).$

Thus $\mathbb{E}_{X}\\#\left({\cal N}[X_{j}]\cap{\cal
S}\right)=\frac{1}{n}\sum_{y\in{\cal S}}(d(y)+1),$ where $d(y)$ is the degree
of vertex $y$ in $G\setminus H$ and setting ${\cal S}=V\setminus{\cal
B}_{j-1}=:{\cal B}^{c}_{j-1},$ we therefore get that

$\mathbb{E}_{X}\\#{\cal B}_{j}=\mathbb{E}_{X}\\#{\cal
B}_{j-1}+\frac{1}{n}\mathbb{E}\sum_{y\in{\cal B}^{c}_{j-1}}(d(y)+1).$ (2.18)

We recall that $E_{deg}$ occurs and also that the maximum vertex degree of $H$
is $\Delta$ and so $\sum_{y\in{\cal B}^{c}_{j-1}}(d(y)+1)\geq\\#{\cal
B}^{c}_{j-1}(np(1-\epsilon)+1-\Delta).$ Defining
$\beta_{j}:=\frac{\mathbb{E}\\#{\cal B}_{j}}{n},$ we then get that
$\beta_{j}\geq\theta_{1}+\theta_{2}\beta_{j-1},$ where
$\theta_{1}=1-\theta_{2}:=p-p\epsilon-\frac{\Delta-1}{n}.$ Applying recursion
and using the fact that $\beta_{1}>0,$ we get that

$\displaystyle\beta_{t}$ $\displaystyle\geq$
$\displaystyle\theta_{1}\left(1+\theta_{2}+\ldots+\theta_{2}^{t-2}\right)+\theta_{2}^{t-1}\beta_{1}$
(2.19) $\displaystyle\geq$
$\displaystyle\frac{\theta_{1}}{1-\theta_{2}}(1-\theta_{2}^{t-1})$
$\displaystyle=$ $\displaystyle 1-(1-\theta_{1})^{t-1}.$

Substituting (2.19) into (2.17) and using $\frac{\\#{\cal B}}{n}=\beta_{t},$
we finally get that $\mathbb{E}_{X}\\#{\cal D}\leq t+n(1-\theta_{1})^{t-1}.$

Summarizing, if the event $E_{deg}$ occurs, then there exists a dominating set
of size at most $t+n(1-\theta_{1})^{t-1}.$ Setting
$t-1=(1+\epsilon)\frac{\log{(np)}}{|\log(1-\theta_{1})|}$ we get that
$n(1-\theta_{1})^{t-1}=\frac{n}{(np)^{1+\epsilon}}=O\left(\frac{1}{n^{\epsilon}}\right)$
and so the above iteration procedure necessarily terminates after at most $t$
steps to provide the desired dominating set ${\cal D}$ of size at most $t+1.$
By Lemma statement

$\theta_{1}=p(1-\epsilon)-\frac{\Delta-1}{n}\geq p(1-\epsilon)-r_{0}$

for all $n$ large and so ${\cal D}$ has size at most
$(1+\epsilon)u_{n}(p,p(1-\epsilon)-r_{0}).$ From (2.16), we then get (2.10).

_Proof of Lemma 2 $(c)$_: For $t\leq 2\log{n},$ let ${\cal
X}=(X_{1},\ldots,X_{t})$ be a uniformly randomly chosen $t-$tuple from $V^{t}$
with _distinct_ entries. Say that a vertex $v$ is _bad_ if $v$ is not adjacent
to any vertex of ${\cal X}$ in $G\setminus H$ and let $q:=1-p.$ The vertex $v$
is not adjacent to $X_{i}$ in $G\setminus H$ if either $v=X_{i}$ or $v$ is
adjacent to $X_{i}$ in $H$ or the edge $(v,X_{i})$ is not present in $G.$
Therefore if $A_{i}$ denotes the event that $v$ is not adjacent to $X_{i}$ in
$G\setminus H,$ then

$\mathbb{P}(A_{i})=1{1}({\cal Z}_{i})+1{1}({\cal Z}_{i}^{c})q$ (2.20)

where ${\cal Z}_{i}$ is the event that either $v=X_{i}$ or $v$ is adjacent to
$X_{i}$ in $H.$ Moreover, because the entries of ${\cal X}$ are distinct, the
events $A_{i}$ and $A_{j}$ are mutually $\mathbb{P}-$independent, given ${\cal
X}.$

Thus denoting $A_{bad}(v)$ to be the event that $v$ is bad, we see that

$\displaystyle\mathbb{E}_{X}\mathbb{P}(A_{bad}(v))$ $\displaystyle=$
$\displaystyle\mathbb{E}_{X}\mathbb{P}\left(\bigcap_{1\leq j\leq
t}A_{j}\right)$ (2.21) $\displaystyle=$
$\displaystyle\mathbb{E}_{X}\prod_{j=1}^{t}\mathbb{P}(A_{j})$ $\displaystyle=$
$\displaystyle\mathbb{E}_{X}\left(\prod_{j=1}^{t-1}\mathbb{P}(A_{j})\mathbb{E}_{X}\left(\mathbb{P}(A_{t})\mid
X_{1},\ldots,X_{t-1}\right)\right).$

Given $X_{1},\ldots,X_{t-1},$ the random variable $X_{t}$ is equally likely to
be any of the remaining $n-t+1$ vertices from $\\{1,2,\ldots n\\}$ and since
the vertex $v$ is adjacent to at most $\Delta$ vertices in $H,$ the event
${\cal Z}_{i}$ defined prior to (2.20) occurs with conditional probability

$\mathbb{P}_{X}({\cal Z}_{i}\mid
X_{1},\ldots,X_{t-1})\leq\frac{\Delta+1}{n-t+1}.$

Plugging this into (2.20) we obtain

$\mathbb{E}_{X}\left(\mathbb{P}(A_{t})\mid
X_{1},\ldots,X_{t-1}\right)\leq\frac{\Delta+1}{n-t+1}+q\leq\frac{\Delta}{n-2\log{n}}+q\leq
2q_{1}$

for all $n$ large, where $q_{1}:=\max\left(q,\frac{\Delta}{n}\right).$
Continuing iteratively, we see from (2.21) that

$\mathbb{E}_{X}\mathbb{P}(A_{bad}(v))\leq(2q_{1})^{t}\leq\frac{1}{(np)^{1+\epsilon/2}}$
(2.22)

provided we set
$t:=\left(1+\frac{\epsilon}{2}\right)\frac{\log{(np)}}{|\log(2q_{1})|}.$ Using
$p\leq 1$ and $q_{1}\leq 2^{-2/\epsilon-2}$ we see that the required condition
$t\leq 2\log{n}$ is satisfied for all $n$ large.

If $N_{bad}:=\sum_{v}1{1}(A_{bad}(v))$ is the total number of bad vertices,
then from (2.22) we see that

$\mathbb{E}_{X}\mathbb{E}N_{bad}\leq\frac{n}{(np)^{1+\epsilon/2}}$

and so there exists a choice of ${\cal X}$ such that
$\mathbb{E}N_{bad}\leq\frac{n}{(np)^{1+\epsilon/2}}.$ We fix such a ${\cal X}$
henceforth and get from the Markov inequality that

$\mathbb{P}(N_{bad}\geq
1)\leq\frac{n}{(np)^{1+\epsilon/2}}\leq\frac{C}{n^{\epsilon/2}},$

for some constant $C>0$ since $p\geq 1-2^{-2/\epsilon-2}$ (see statement of
the Lemma). In other words, with probability at least
$1-\frac{C}{n^{\epsilon/2}},$ the vertices in ${\cal X}$ form a dominating set
of $G$ and so

$\mathbb{P}\left(\Gamma_{n}\leq\left(1+\frac{\epsilon}{2}\right)\frac{\log{(np)}}{|\log(2q_{1})|}\right)\geq
1-\frac{C}{n^{\epsilon/2}}.$ (2.23)

Again using $q_{1}\leq 2^{-2/\epsilon-2}$ we have that
$\frac{1+\epsilon/2}{|\log(2q_{1})|}\leq\frac{1+\epsilon}{|\log{q_{1}}|}$ and
so (2.23) implies that $\Gamma_{n}\leq(1+\epsilon)u_{n}(p,1-q_{1})$ and this
obtains the desired deviation upper bound in (2.10).

We now use Lemma 2 to prove Theorem 2.1 below.
_Proof of Theorem 2.1_: We consider three separate subcases depending on
whether the asymptotic edge probability $p_{0}=0,1$ or otherwise. For
$p_{0}=0$ and $\Delta=o(n),$ we use the lower deviation bound in part $(a)$ of
Lemma 1 and the upper deviation bound in part $(a)$ of Lemma 2 to get that
$\frac{\Gamma_{n}}{u_{n}}\longrightarrow 1$ in probability. Similarly, the
cases $0<p_{0}<1$ and $p_{0}=1$ are obtained using parts $(b)$ and $(c),$
respectively, of Lemma 2.

For $m=o(nu_{n}(1-p)),$ we include a small “preprocessing” step. First
consider the case $p_{0}=0.$ For $\epsilon>0$ let ${\cal Q}$ be the set of all
vertices with degree at most $\epsilon n.$ In the proof of Lemma 2$(a),$ we
now choose $X_{i},1\leq i\leq t$ uniformly and independently from ${\cal Q}$
and estimate the number of vertices covered by the set ${\cal
D}:=\\{X_{1},\ldots,X_{t}\\}\cup{\cal Q}^{c}.$ For $\epsilon>0$ and a vertex
$v,$ the $\mathbb{P}_{X}-$probability that $X_{1}$ is equal or adjacent to $v$
in $H$ is at most $\frac{\Delta+1}{\\#{\cal
Q}}\leq\frac{\epsilon}{1-\epsilon}<2\epsilon$ since by definition, the set
${\cal Q}^{c}$ has size $o(u_{n})<\epsilon u_{n}<\epsilon n$ for all $n$
large.

If $L_{tot}$ is the number of vertices “left out” by
$\\{X_{1},\ldots,X_{t}\\},$ then arguing as in the proof of Lemma 2$(a)$ we
get that both (2.14) and (2.15) holds and so

$\Gamma_{n}\leq\\#{\cal D}+L_{tot}\leq(1+C_{1}\epsilon)u_{n}+\\#{\cal
Q}^{c}\leq(1+C_{2}\epsilon)u_{n}$

for some constants $C_{1},C_{2}>0.$ Since $\epsilon>0$ is arbitrary, we argue
as in the first paragraph of this proof to then get that
$\mathbb{E}\Gamma_{n}=u_{n}(1+o(1)).$ An analogous analysis holds for the
cases $0<p_{0}<1$ and $p_{0}=1$ as well.

##  3 The Sparse Regime

In this section, we discuss robust domination in the sparse regime when
$np\longrightarrow\lambda<\infty.$ We consider the cases $\lambda=0$ and
$0<\lambda<\infty$ separately and have the following result regarding the
robust domination number.

###### Theorem 3.1

We have:
$(a)$ If $np\longrightarrow 0,n^{2}p\longrightarrow\infty$ and either
$\Delta=o(n)$ or $m=o(n^{3}p),$ then
$\frac{4\Gamma_{n}}{n^{2}p}\longrightarrow 1$ in probability as
$n\rightarrow\infty.$
$(b)$ Suppose $np\longrightarrow\lambda$ for some $0<\lambda<\infty$ and
either $\Delta=o(n)$ or $m=o(n^{2}).$ For every $\epsilon>0,$ we have

$\mathbb{P}\left(a(\lambda)(1-\epsilon)\leq\frac{\gamma(G)}{n}\leq\frac{\Gamma_{n}}{n}\leq
b(\lambda)(1+\epsilon)\right)\longrightarrow 1$ (3.1)

where

$\displaystyle a(\lambda):=\left\\{\begin{array}[]{cc}\lambda
e^{-2\lambda}&\;\;\;\lambda\leq\lambda_{0}\\\ \\\
\frac{\log{\lambda}-3\log\log{\lambda}}{\lambda},&\;\;\;\lambda>\lambda_{0}\end{array}\right.\;\;,\;\;b(\lambda):=\left\\{\begin{array}[]{cc}\frac{\lambda}{4},&\;\;\;\lambda\leq
1\\\ \\\
\frac{\log{\lambda}+1}{\lambda},&\;\;\;\lambda>1\end{array}\right.\;\;,\;\;$
(3.8)

and $\lambda_{0}>0$ is an absolute constant not depending on the choice of
$\lambda$ or $H.$

Essentially, for $\lambda=0$ we see that $\Gamma_{n}$ is of the order of
$n^{2}p$ while for the “intermediate” regime $0<\lambda<\infty,$ the robust
domination number is of the order of $n,$ with high probability.

_Proof of Theorem 3.1$(a)$_: If $Y_{tot}$ and $Z_{tot}$ denote, respectively,
the number of edges and the number of isolated edges of $G\setminus H,$ then
$\frac{Y_{tot}}{2}\leq\Gamma_{n}\leq\frac{Z_{tot}}{2}$ and so it suffices to
bound $Y_{tot}$ and $Z_{tot}.$ The expected number of edges in $G$ is
${n\choose 2}p=\frac{n^{2}p}{2}(1+o(1))$ and so from the deviation estimate
(A.1) in Appendix, we get that

$\mathbb{P}\left(2\Gamma_{n}\geq
Z_{tot}\geq\frac{n^{2}p}{2}(1+\epsilon)\right)\leq\exp\left(-\frac{\epsilon^{2}n^{2}p}{8}\right).$
(3.9)

This provides an upper bound for $\Gamma_{n}.$

We now obtain general lower bounds for $\Gamma_{n}$ assuming that
$np\longrightarrow\lambda$ and $\Delta\leq r_{0}n-1$ for some finite constants
$0<r_{0}<1$ and $0\leq\lambda<\infty.$ As discussed before, it suffices to
obtain a deviation bound for $Y_{tot}$ and we use the second moment method.
For an edge $e\in K_{n}\setminus H,$ let $A_{e}$ be the event that $e$ is
isolated so that $Y_{tot}=\sum_{e\in K_{n}\setminus H}1{1}(A_{e}),$ where
$1{1}(.)$ is the indicator function. Since each vertex has degree at most $n,$
we have that

$\displaystyle\mathbb{P}(A_{e})$ $\displaystyle\geq$ $\displaystyle
p(1-p)^{2n-4}$ (3.10) $\displaystyle=$
$\displaystyle\frac{p}{(1-p)^{4}}(1-p)^{2n}$ $\displaystyle=$
$\displaystyle\frac{p}{(1-p)^{4}}e^{-2\lambda}(1+o(1))$ $\displaystyle=$
$\displaystyle pe^{-2\lambda}(1+o(1))$

and since $\Delta\leq r_{0}n$ we have that the number of edges in $H$ is
$m\leq\frac{1}{2}\Delta n\leq\frac{1}{2}r_{0}n^{2}.$ Therefore from (3.10), we
get that

$\mathbb{E}Y_{tot}\geq\left({n\choose
2}-m\right)pe^{-2\lambda}(1+o(1))\geq\frac{n^{2}p}{2}e^{-2\lambda}(1-r_{0}-\epsilon)$
(3.11)

for all $n$ large.

Next, the minimum vertex degree in $K_{n}\setminus H$ is $n-1-\Delta\geq
n(1-r_{0})$ and so for distinct edges $e_{1}\neq e_{2}$ in $K_{n}\setminus H,$
we argue as in (3.10) to get that

$\mathbb{P}\left(A_{e_{1}}\cap A_{e_{2}}\right)\leq
p^{2}(1-p)^{4(n-r_{0}n-3)}=p^{2}e^{-4\lambda(1-r_{0})}(1+o(1)).$

Thus again using (3.10), we get that $\mathbb{P}\left(A_{e_{1}}\cap
A_{e_{2}}\right)-\mathbb{P}(A_{e_{1}})\mathbb{P}(A_{e_{2}})$ is bounded above
by

$p^{2}e^{-4\lambda}\left(e^{4\lambda
r_{0}}-1\right)(1+o(1))\leq\mathbb{P}(A_{e_{1}})\mathbb{P}(A_{e_{2}})\left(e^{4\lambda
r_{0}}-1\right)(1+o(1))$

and therefore

$\displaystyle var(Y_{tot})$ $\displaystyle=$ $\displaystyle\sum_{e\in
K_{n}\setminus H}\mathbb{P}(A_{e})-\mathbb{P}^{2}(A_{e})+\sum_{e_{1}\neq
e_{2}}\mathbb{P}\left(A_{e_{1}}\cap
A_{e_{2}}\right)-\mathbb{P}(A_{e_{1}})\mathbb{P}(A_{e_{2}})$ (3.12)
$\displaystyle\leq$ $\displaystyle\sum_{e\in K_{n}\setminus
H}\mathbb{P}(A_{e})+\sum_{e_{1}\neq
e_{2}}\mathbb{P}(A_{e_{1}})\mathbb{P}(A_{e_{2}})\left(e^{4\lambda
r_{0}}-1\right)(1+o(1))$ $\displaystyle\leq$
$\displaystyle\mathbb{E}Y_{tot}+\left(\mathbb{E}Y_{tot}\right)^{2}\left(e^{4\lambda
r_{0}}-1\right)(1+o(1)).$

Using (3.12), (3.11) and the Chebychev inequality, we get for $\epsilon>0$
that

$\displaystyle\mathbb{P}\left(Y_{tot}\leq\mathbb{E}Y_{tot}(1-\epsilon)\right)$
$\displaystyle\leq$
$\displaystyle\frac{var(Y_{tot})}{\epsilon^{2}(\mathbb{E}Y_{tot})^{2}}$ (3.13)
$\displaystyle\leq$
$\displaystyle\frac{1}{\mathbb{E}Y_{tot}}+\left(e^{4\lambda
r_{0}}-1\right)(1+o(1))$ $\displaystyle\leq$
$\displaystyle\frac{C}{n^{2}p}+\left(e^{4\lambda r_{0}}-1\right)(1+o(1))$
$\displaystyle\leq$ $\displaystyle\frac{C}{n^{2}p}+2\left(e^{4\lambda
r_{0}}-1\right)$

where $C=C(\lambda,r_{0},\epsilon)>0$ is a constant. Again using (3.11) and
(3.13), we get that

$\mathbb{P}\left(2\Gamma_{n}\geq
Y_{tot}\geq\frac{n^{2}p}{2}e^{-2\lambda}(1-r_{0}-2\epsilon)\right)\geq
1-\frac{C}{n^{2}p}-2\left(e^{4\lambda r_{0}}-1\right).$ (3.14)

If $\Delta=o(n)$ and $\lambda=0,$ then we can set $r_{0}$ arbitrarily small in
the above analysis and get from (3.9) and (3.14) that
$\frac{4\Gamma_{n}}{n^{2}p}\longrightarrow 1$ in probability as
$n\rightarrow\infty.$ If $m=o(n^{3}p),$ then the number of vertices with
degree larger than $\epsilon n$ for $\epsilon>0$ is $o(n^{2}p).$ Performing
the “pre-processing” steps as in the proof of Theorem 2.1, we again get that
$\frac{4\Gamma_{n}}{n^{2}p}\longrightarrow 1$ in probability.

_Proof of Theorem 3.1$(b)$_: We show that there exists a constant $C>0$ such
that for every $\epsilon>0,$

$a(\lambda)(1-\epsilon)\leq\frac{\mathbb{E}\Gamma_{n}}{n}\leq
b(\lambda)(1+\epsilon)\text{ and }var(\Gamma_{n})\leq
Cn(\log{n})^{2}=o(\mathbb{E}\Gamma_{n})^{2}.$ (3.15)

From (3.15) and the Chebychev inequality, we then get (3.1). Also, we only
consider the case $\Delta=o(n)$ and the preprocessing arguments analogous to
the proof of Theorem 3.1$(a)$ holds for the case $m=o(n^{2}).$

For convenience, we assume throughout that $np=\lambda$ and begin with the
lower bounds for $\mathbb{E}\Gamma_{n}.$ Set $\theta=3$ in Lemma 1$(a)$ and
let $\lambda_{0}:=\lambda_{0}(3).$ Since $p=\frac{\lambda}{n},$ we have that

$u_{n}=\frac{\log(np)}{|\log(1-p)|}\sim
n\frac{\log{\lambda}}{\lambda},\lambda_{a}=np=\lambda,\lambda_{b}=n|\log(1-p)|\sim\lambda$

and so for $\epsilon>0$ we have that
$u_{n}\left(1-\frac{3\log\log{\lambda_{b}}}{\log{\lambda_{a}}}\right)\geq
a(\lambda)n(1-\epsilon)$ for all $n$ large. Consequently, for
$\lambda>\lambda_{0},$ we get from (2.2) in Lemma 1 that

$\mathbb{P}\left(\Gamma_{n}\geq a(\lambda)n(1-\epsilon)\right)\geq 1-e^{-Cn}$

and so $\mathbb{E}\Gamma_{n}\geq a(\lambda)n(1-2\epsilon)$ for all $n$ large.
For $\lambda<\lambda_{0},$ we use (3.11) and the fact that $\Delta=o(n)$ to
get that
$\mathbb{E}\Gamma_{n}\geq\frac{n^{2}p}{4}e^{-2\lambda}(1-2\epsilon)=a(\lambda)n(1-2\epsilon)$
for all $n$ large.

Next, for the upper bound for $\mathbb{E}\Gamma_{n}$ for $\lambda\leq 1,$ we
recall from the discussion prior to (3.11) that
$\mathbb{E}\Gamma_{n}\leq\frac{\mathbb{E}Z_{tot}}{2}\leq\frac{n^{2}p}{4}=\frac{\lambda
n}{4}.$ For $\lambda>1,$ we use the alteration method as in the proof of Lemma
1$(b).$ Let ${\cal D}$ be any set of $u_{n}+\Delta$ vertices. Each vertex
$v\notin{\cal D}$ is adjacent to at least $u_{n}$ vertices of ${\cal D}$ and
so $v$ is not adjacent to any vertex of ${\cal D}$ in $G\setminus H$ with
probability at most $(1-p)^{u_{n}}=\frac{1}{np}$ and if ${\cal B}$ is the set
of all “bad” vertices in ${\cal D}^{c}$ not adjacent to any vertex of ${\cal
D},$ then the expected size of ${\cal B}$ is at most
$\frac{1}{p}=\frac{n}{\lambda}.$ Moreover, the asymptotic relation
$|\log(1-p)|\sim p$ and $\Delta=o(n)$ imply that ${\cal D}$ has size
$u_{n}+\Delta\leq\left(\frac{\log{\lambda}}{\lambda}+o(1)\right)n.$ The set
${\cal D}\cup{\cal B}$ is a dominating set of $G\setminus H$ and has an
expected size of at most
$n\left(\frac{\log{\lambda}+1}{\lambda}+o(1)\right)\leq
b(\lambda)n(1+\epsilon)$ for all $n$ large. This completes the proof of the
expectation bounds in (3.15).

Next, to prove the variance bound in (3.15), we use the martingale difference
method. For $1\leq j\leq n,$ let ${\cal
F}_{j}=\sigma\left(\\{Z(f):f=(u,v),1\leq u<v\leq j\\}\right)$ denote the sigma
field generated by the state of the edges in the complete subgraph $K_{j}.$
Defining the martingale difference $R_{j}:=\mathbb{E}(\Gamma_{n}\mid{\cal
F}_{j})-\mathbb{E}(\Gamma_{n}\mid{\cal F}_{j-1}),$ we get that
$\Gamma_{n}-\mathbb{E}\Gamma_{n}=\sum_{j=1}^{n}R_{j}.$ By the martingale
property we then have

$var(\Gamma_{n})=\mathbb{E}\left(\sum_{j=1}^{n}R_{j}\right)^{2}=\sum_{j=1}^{n}\mathbb{E}R_{j}^{2}.$
(3.16)

To evaluate $\mathbb{E}R_{j}^{2},$ we introduce the graph $G^{(j)}$ obtained
by using independent copies for the states of all edges $(u,j),1\leq u<j$ and
retaining the same state as $G$ for the rest of the edges. With this notation,
we rewrite $R_{j}=\mathbb{E}(\Gamma_{n}-\Gamma_{n}^{(j)}\mid{\cal F}_{j}),$
where $\Gamma_{n}^{(j)}$ is the domination number of the graph
$G^{(j)}\setminus H$ and so squaring and taking expectations, we get
$\mathbb{E}R_{j}^{2}\leq\mathbb{E}(\Gamma_{n}-\Gamma_{n}^{(j)})^{2}.$ To
estimate the difference $|\Gamma_{n}-\Gamma_{n}^{(j)}|,$ we let ${\cal D}$ be
any minimum size dominating set of $G\setminus H.$ Adding all vertices
adjacent to the vertex $j$ in the graph $G^{(j)}$ to the set ${\cal D}$ gives
us a dominating set of $G^{(j)}\setminus H$ and so
$\Gamma_{n}\leq\Gamma_{n}^{(j)}+l_{j},$ where $l_{j}$ is the total number of
edges containing $j$ as an endvertex either in $G$ or $G^{(j)}.$ By symmetry,
we therefore get $|\Gamma_{n}-\Gamma^{(j)}_{n}|\leq l_{j}$ and so
$\mathbb{E}R_{j}^{2}\leq\mathbb{E}l^{2}_{j}.$

The expected number of edges in $G$ containing $j$ as an endvertex is
$(n-1)p\leq\lambda$ and so if $E_{up}$ is the event that the vertex $j$ is
adjacent to at most $C_{1}\log{n}$ edges in $G$ then using Chernoff bound we
get for $s>0$ that

$\displaystyle\mathbb{P}(E^{c}_{up})$ $\displaystyle\leq$ $\displaystyle
e^{-sC_{1}\log{n}}(1-p+e^{s}p)^{n-1}$ (3.17) $\displaystyle\leq$
$\displaystyle e^{-sC_{1}\log{n}}\exp\left((e^{s}-1)(n-1)p\right)$
$\displaystyle\leq$ $\displaystyle C_{2}e^{-sC_{1}\log{n}}$

for some constant $C_{2}=C_{2}(\lambda,s)>0.$ Setting $s=1$ and choosing
$C_{1}$ large, we get that $\mathbb{P}(E^{c}_{up})\leq\frac{1}{n^{6}}.$
Defining an analogous event $E_{up}^{(j)}$ for the graph $G^{(j)},$ we get
from the union bound that $F_{up}:=E_{up}\cap E^{(j)}_{up}$ occurs with
probability at least $1-\frac{2}{n^{6}}.$ If $F_{up}$ occurs, then $l_{j}\leq
2C_{1}\log{n}$ and other wise, we use the bound $l_{j}\leq 2n.$ Combining this
with the discussion in the previous paragraph, we get

$\displaystyle\mathbb{E}R_{j}^{2}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}l_{j}^{2}$ $\displaystyle\leq$
$\displaystyle(2C_{1}\log{n})^{2}+4(2n)^{2}\mathbb{P}(F_{up}^{c})$
$\displaystyle\leq$ $\displaystyle(2C_{1}\log{n})^{2}+\frac{2(2n)^{2}}{n^{6}}$
$\displaystyle\leq$ $\displaystyle C_{3}(\log{n})^{2}$

for some constant $C_{3}>0.$ Plugging this into (3.16) gives the variance
bound in (3.15) and therefore completes the proof of Theorem 3.1$(b).$

## Appendix

_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<\eta<\frac{1}{2}$ we have that

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

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

_Montonicity of $u_{n}(x)$_: The function
$u_{n}(x):=\frac{\log(nx)}{|\log(1-x)|}$ has a derivative

$u^{\prime}_{n}(x)=\frac{H(x)-x\log{n}}{x(1-x)|\log(1-x)|^{2}}$

where

$H(x):=-x\cdot\log{x}-(1-x)\cdot\log(1-x)$ (A.2)

is the binary entropy function and logarithms are natural throughout. If
$x>\frac{1}{2},$ then $H(x)-x\log{n}\leq 1-\frac{\log{n}}{2}<0$ for all $n\geq
4.$ The numerator $H(x)-x\log{n}$ has derivative
$\log\left(\frac{1}{x}-1\right)-\log{n}<0$ for all $x>\frac{1}{n+1}.$ Thus for
$\frac{\lambda}{n}<x<\frac{1}{2}$ and $\lambda>1$ we use $(1-x)|\log(1-x)|<x$
to get that $H(x)-x\log{n}$ is bounded above by

$H\left(\frac{\lambda}{n}\right)-\frac{\lambda\log{n}}{n}=\frac{-\lambda\log{\lambda}}{n}-\left(1-\frac{\lambda}{n}\right)\log\left(1-\frac{\lambda}{n}\right)\leq-\frac{\lambda\log{\lambda}}{n}+\frac{\lambda}{n}$

which is strictly less than zero if $\lambda>e.$

### Data Availability

Data sharing not applicable to this article as no datasets were generated or
analysed during the current study.

### Acknowledgement

I thank Professors Rahul Roy, C. R. Subramanian and the referee for crucial
comments that led to an improvement of the paper. I also thank IMSc and IISER
Bhopal for my fellowships.

## References

  * [1] Alon, N. and Spencer, J. (2008). The Probabilistic Method. _Wiley Interscience_ , 2008.
  * [2] Bollobás, B. (2001). Random Graphs. _Cambridge University Press_.
  * [3] Clark, L. and Johnson, D. (2011). The Independent Domination Number of a Random Graph. _Discuss. Math. Graph Theory_ , 31, 129–142.
  * [4] Du, H., Ding, L., Wu, W., Kim, D., Pardalos, P. M. and Willson, J. (2013). Connected Dominating Set in Wireless Networks. In: _Pardalos, P., Du, DZ., Graham, R. (eds) Handbook of Combinatorial Optimization_. Springer, New York.
  * [5] Glebov , R., Liebenau, A. and Szabó, T. (2012). On the Concentration of the Domination Number of the Random Graph. _SIAM Journal on Discrete Mathematics_ , 29, 1186–1206.
  * [6] Wang, B. and Xiang, K. (2009). On $k-$tuple Domination of Random Graphs. _Appl. Math. Lett._ , 22, 1513–1517.
  * [7] Wieland, B. and Godbole, A. P. (2001). On the Domination Number of a Random Graph. _Electronic Journal of Combinatorics_ , 8, $\\#$R37, 1–13.
  * [8] Wu, J. and Li. H. (2000). Domination and its Applications in Ad Hoc Wireless Networks with Unidirectional Links. _IEEE International Conference on Parallel Processing 2000_ , 1–9.
  * [9] Zou, F., Li, X., Kim, D. and Wu, W. (2008). Construction of Minimum Connected Dominating Set in $3-$Dimensional Wireless Network. Wireless Algorithms, Systems and Applications, 5258, 134–140.


# Nanophotonic oscillators for laser conversion beyond an octave

Grant M. Brodnik<EMAIL_ADDRESS>Time and Frequency Division,
National Institute of Standards and Technology, Boulder, CO, USA  Department
of Physics, University of Colorado, Boulder, CO, USA  Haixin Liu  Time and
Frequency Division, National Institute of Standards and Technology, Boulder,
CO, USA  Department of Physics, University of Colorado, Boulder, CO, USA
David R. Carlson  Time and Frequency Division, National Institute of Standards
and Technology, Boulder, CO, USA  Octave Photonics, Louisville, CO, USA
Jennifer A. Black  Time and Frequency Division, National Institute of
Standards and Technology, Boulder, CO, USA  Scott B. Papp  Time and Frequency
Division, National Institute of Standards and Technology, Boulder, CO, USA
Department of Physics, University of Colorado, Boulder, CO, USA

###### Abstract

Many uses of lasers place the highest importance on access to specific
wavelength bands. For example, mobilizing optical-atomic clocks for a leap in
sensing requires compact lasers at frequencies spread across the visible and
near infrared. Integrated photonics enables high-performance, scalable laser
platforms, however, customizing laser-gain media to support wholly new bands
is challenging and often prohibitively mismatched in scalability to early
quantum-based sensing and information systems. Here, we demonstrate a
microresonator optical-parametric oscillator (OPO) that converts a pump laser
to an output wave within a frequency span exceeding an octave. We achieve
phase matching for oscillation by nanopatterning the microresonator to open a
photonic-crystal bandgap on the mode of the pump laser. By adjusting the
nanophotonic pattern and hence the bandgap, the ratio of output OPO wave
frequency span to required pump laser tuning is more than 10,000. We also
demonstrate tuning the oscillator in free-spectral-range steps, more finely
with temperature, and minimal additive frequency noise of the laser-conversion
process. Our work shows that nanophotonics offers control of laser conversion
in microresonators, bridging phase-matching of nonlinear optics and
application requirements for laser designs.

††preprint: APS/123-QED

Sophisticated physical systems with such disparate aims as characterization of
biological samples [1], operation of quantum information protocols [2],
standards and sensors for time based on optical clocks [3], and precision
metrology with optical sources [4] demand versatility in lasers. Especially in
the visible to near infrared, laser-wavelength access is challenging due to
the limited availability and narrow operating ranges of laser-gain materials.
The challenge is solved today by large, tabletop lasers based on solid-state
materials and bulk nonlinear optics that provide exceptional flexibility in
wavelength range, output power, and temporal profile but with substantial
expense and complicated operation that hinders usability in applications.

Semiconductor lasers are less expensive and better engineered to support
applications. However, the recurring effort to customize semiconductor gain
materials is a barrier in expanding their use. Moreover, achieving high
performance in semiconductor lasers requires low-loss components that are
often incompatible with high gain. A theme in recent laser development has
been the combination of gain and photonics materials. Heterogeneous
integration of gain and photonics materials on a common substrate or hybrid
integration of independent laser chips and photonics chips can both overcome
the challenge of semiconductor material loss, but such laser platforms
currently support only select wavelength bands. To date, heterogeneous
integration approaches have demonstrated fabrication of lasers on photonic
platforms in telecommunications bands [5, 6] and more recently below 1 $\mu$m
[7, 8]. Still, a universal laser platform to simultaneously support visible
and near-infrared wavelengths remains elusive. Hybrid integration of
semiconductor lasers with photonic waveguides has demonstrated co-integration
of visible sources with photonics [9], but this approach requires custom
packaging and active alignment of gain material with waveguides.

To open up laser-wavelength access in challenging spectral bands, we propose
an approach bringing together semiconductor laser integration and chip-based
nonlinear laser conversion. Thereby, we leverage advancing laser integration
in select wavelength bands, and we develop nonlinear wavelength converters
with integrated photonics that is directly compatible with laser integration.
This alleviates recursive laser-gain development and provides integration.
Nonlinear phase matching in integrated photonics has been extensively studied,
however now we include the constraint of compatibility with laser integration.
For example, both $\chi^{(2)}$ and $\chi^{(3)}$ nonlinear optical processes
have enabled laser conversion with integrated photonics, including via
harmonic generation [10, 11, 12, 13, 14, 15], difference frequency generation
[16], four-wave mixing [17, 18, 19, 20], and optical-parametric oscillation
(OPO) [21, 22]. Of these processes, $\chi^{(3)}$ microresonator-based
degenerate OPO is particularly appealing because of operation with a single
input laser, generation of OPO output waves across wide spectral ranges, and
implementation with commonly used integrated photonics.

Figure 1: (a) A laser diode (LD) pumps a nanophotonic oscillator with
frequency $\nu_{\textrm{p}}$ for OPO laser conversion to output waves with
frequency $\nu_{\textrm{s}}$ and $\nu_{\textrm{i}}$. (b) Scanning electron
microscope (SEM) images of a nanophotonic oscillator highlighting the
nanophotonic modulation with amplitude $\textit{A}_{\textrm{PhC}}$. (c)
Graphical representation of phase matching which governs resonant OPO
processes in a nanophotonic oscillator. (d) Frequency error, ${\delta}f$, of
Eqn. 1. As we increase $\gamma$, different resonant modes $f(\pm\mu)$ are
brought into phase matching for OPO. (e) Corresponding optical spectra of
nanophotonic oscillation with increasing $\gamma$.

We design microresonator OPOs by group-velocity dispersion (GVD) engineering
with geometry, tailoring microresonator waveguide thickness, radius, and width
[23, 24]. Microresonator OPOs based on GVD engineering provide phase matching
that conserves energy of the pump, signal, and idler waves. Moreover, such
OPOs depend upon high quality factor of the microresonator modes for these
waves [25, 26]. To date, the widest signal-to-idler frequency span in
microresonator OPOs have a design target of near-zero GVD between the three
waves. Indeed, the current limit in OPO frequency span is the required GVD
engineering and challenges in fabricating microresonators with tightly
controlled geometry [21, 23, 24, 27]. Moreover, in operating OPOs with visible
wavelength output, the increasingly normal material GVD limits control of
phase matching through geometry alone.

Recently, OPO designs have augmented GVD engineering by geometry with the
inclusion of a nanostructured periodic modulation inscribed on the inner wall
of a microresonator. These so called photonic-crystal ring resonators (PhCR)
induce coherent backscattering at an optical frequency determined by the
nanostructure periodicity [28, 29]. This opens an optical bandgap, which has
been used to control OPO phase matching with bandgaps at the pump [30, 31], at
the signal wave [32], and in the bandgap-detuned regime [33]. Importantly,
nanostructures and geometry are two independent and direct controls of OPO
phase matching. However, the OPO signal-to-idler wave frequency span of such
nanophotonic OPO has not been explored, nor has operation in the important
near-zero GVD regime.

Here, we report nanophotonic oscillators that convert a pump laser to an
output wave whose frequency is controllable within a span exceeding an octave.
We use geometric GVD engineering to access the near-zero GVD regime between
the OPO waves, and we use a photonic-crystal bandgap to provide phase matching
for broadband OPO. This enables robust laser conversion and access to an
unprecedented OPO wave frequency span in nanostructured microresonators.
Importantly, our approach simplifies the required pump laser tuning range for
a microresonator OPO; in our experiments the pump tuning is 10,000 times less
than the OPO wave frequency span. We realize nanophotonic oscillators on the
tantalum pentoxide (Ta2O5), or tantala, platform, which has high Kerr
nonlinearity, low stress, and high quality factor across the visible and near-
infrared wavelengths [34]. Moreover, tantala supports GVD engineering [35] and
heterogeneous integration [36, 37, 38]. Experimentally, we demonstrate
nanophotonic oscillators, which take a pump laser near 1062 nm and create
output OPO signal and idler waves. We demonstrate a maximum OPO wave frequency
span from 749 nm to 1806 nm that corresponds to >230 THz with pump-laser
tuning <30 GHz. These experiments demonstrate the principle of laser-
wavelength access while requiring minimal pump laser tuning, which is a
critical innovation for laser-wavelength access on a chip. In view of interest
to use the devices for applications, we characterize several aspects of the
output OPO, including thermal fine-frequency tuning and additive frequency
noise of the laser-conversion process.

Nanophotonic wavelength converters
Nanophotonic oscillators enable laser conversion through resonant phase
matching of the pump, signal, and idler waves [39]. We characterize the
frequency error ${\delta}f(\mu)$ for phase matching as

${\delta}f(\mu)=2(f_{0}\pm\gamma/2)-f(\scalebox{0.7}[0.7]{{\hbox{+}}}\mu)-f(\scalebox{0.7}[1.0]{{\hbox{-}}}\mu)$
(1)

where the resonant frequencies of a microresonator are $f(\mu)$ and
$\mu=m-m_{p}$ is the azimuthal mode number, $m$, relative to the pump,
$m_{p}$. The pump mode $f(\mu=0)$ is $f_{0}$, which we split with a photonic-
crystal bandgap of magnitude $\gamma$, thereby shifting its frequency without
affecting the GVD design. The pump mode, $f_{0}\pm\gamma$/2, phase matches to
modes symmetric about the pump, $f(\pm\mu)$, when Eqn. 1 is positive to within
the pump mode Kerr shift [30, 25, 32]. We operate nanophotonic oscillators in
the near-zero GVD regime and use $\gamma$ to control the signal and idler wave
frequencies with minimal pump laser frequency tuning. Figure 1(a) presents the
concept of nanophotonic oscillators where we convert a pump laser with
frequency $\nu_{\textrm{p}}$ to signal and idler waves with frequency
$\nu_{\textrm{s}}$ and $\nu_{\textrm{i}}$. We instill $\gamma$ by inscribing a
nanopattern into the microresonator sidewall with modulation amplitude
$A_{\textrm{PhC}}$ as seen in Fig. 1(b).Graphically, we can understand
nanophotonic oscillator laser conversion through the mode structure depicted
in Fig. 1(c). Operationally, we tune the pump laser to resonance
$\nu_{\textrm{p}}=f_{0}+\gamma/2$ to initiate OPO-based laser conversion to
$\nu_{\textrm{s}}$ and $\nu_{\textrm{s}}$, which abides strict energy
conservation $2\nu_{\textrm{p}}=\nu_{\textrm{s}}+\nu_{\textrm{i}}$ [40].

We realize this method in practice, demonstrating $\gamma$-controlled laser
conversion. To implement nanophotonic oscillators, we use PhCRs, which provide
a broadband and high-finesse microresonator with programmable $\gamma$ to
control OPO phase matching. Figure 1(d) plots ${\delta}f$ of such a
nanophotonic oscillator where we see that varying $\gamma$ enables alignment
of $f_{0}+\gamma/2$ to different pairs of $f(\pm\mu)$, thereby modifying OPO
phase matching to control $\nu_{\textrm{s}}$ and $\nu_{\textrm{i}}$. We
transfer the ${\delta}f$ design of Fig. 1(d) to devices in the tantala
platform (see Methods), demonstrating laser conversion as seen in Fig. 1(e) in
which we plot optical spectra for several $\gamma$ settings with otherwise
identical GVD. The pump $\nu_{\textrm{p}}$ needs tune only several GHz to
track $\gamma$/2 while $\nu_{\textrm{s}}$ and $\nu_{\textrm{i}}$ are tuned
across $\approx$ 20 THz with an OPO wave frequency span exceeding 100 THz.

Device characteristics
In addition to satisfying Eqn. 1 for OPO phase matching, we require a high
quality factor to realize nanophotonic oscillators [23, 25, 41]. To
characterize the quality factor of devices, we measure transmission spectra of
three widely tunable external cavity lasers near the 980 nm, 1064 nm, and 1300
nm wavelength bands. Figure 2(a) presents the loaded, intrinsic, and coupling
quality factors ($Q_{\textrm{L}}$, $Q_{\textrm{i}}$, and $Q_{\textrm{c}}$) as
a function of frequency for a nanophotonic oscillator device. We measure
$Q_{\textrm{i}}$ $\approx$ 0.9 x 106 across the three wavelength bands,
suitable for efficient OPO. Moreover, we measure the wavelength-dependent
$Q_{\textrm{c}}$ to agree with three-dimensional, finite-difference time-
domain modelling within fabrication tolerance (Methods) [42].

Figure 2: (a) Measured $Q_{\textrm{L}}$, $Q_{\textrm{i}}$, and
$Q_{\textrm{c}}$ (colored markers) across three spectral regions and modelled
$Q_{\textrm{c}}$ (blue line). (b) Experimental (colored circles) and modelled
(black circles) $D_{\textrm{int}}$/2$\pi$. (c) OPO spectrum for the device
characterized in (a) and (b). (d) Measured $\gamma$ vs. $A_{\textrm{PhC}}$.
Left inset shows example pump resonance $f_{0}\pm\gamma/2$ and right inset
shows $A_{\textrm{PhC}}$ inner sidewall modulation. (e) $Q_{\textrm{i}}$ vs.
$A_{\textrm{PhC}}$. (f) Measured (circles) and modelled (lines) OPO
frequencies vs. $A_{\textrm{PhC}}$, highlighting nanophotonic control of OPO.

To explore the accuracy of $\gamma$-controlled phase matching in our
nanophotonic oscillators, we measure the GVD and pump the devices above the
OPO threshold power to validate Eqn. 1. We express the resonant angular
frequencies, $\omega$, of a microresonator as a function of $\mu$ using a
Taylor expansion:

$\begin{split}\omega(\mu)&=2\pi f({\mu})={2\pi
f_{0}}+{D_{1}}\mu+\frac{D_{2}\mu^{2}}{2}+\frac{D_{3}\mu^{3}}{6}+...\\\
&={\omega_{0}}+{D_{1}}\mu+D_{\textrm{int}}.\end{split}$ (2)

The integrated dispersion, $D_{\textrm{int}}$, relates the change in resonant
angular frequencies relative to the free spectral range (FSR $=D_{1}/2\pi$) at
the pump [43]. From our measured transmission spectra, we can directly
determine $D_{\textrm{int}}$ and compare with finite element method
simulations of the microresonator eigenfrequencies (see Methods for more).
Figure 2(b) presents measured (colored circles) and modelled (black circles)
$D_{\textrm{int}}/2\pi$ as a function of frequency. We find the nanophotonic
oscillator pump resonance $f_{0}+\gamma/2$ with $m_{\textrm{p}}$ = 511
satisfies Eqn. 1 at modes $m$ = 685 and $m$ = 337 ($\mu=\pm$ 174). In terms of
$D_{\textrm{int}}$, OPO phase matching occurs when we can draw a straight line
through $f_{0}+\gamma/2$ and $f(\pm{\mu})$ as seen in Fig. 2(b) [40]. We
validate this by pumping the nanophotonic oscillator with $D_{\textrm{int}}$
from Fig. 2(b) and recording the output OPO spectrum as seen in Fig. 2(c). We
find that when pumping $f_{0}+\gamma/2$ at $\nu_{\textrm{p}}$ = 282.8 THz, the
nanophotonic oscillator provides laser conversion to output waves with
frequencies $\nu_{\textrm{s}}$ = 365.5 THz and $\nu_{\textrm{i}}$ = 200.1 THz.

Deterministic control of $\gamma$ is of critical importance for laser
conversion with nanophotonic oscillators. Therefore, we characterize $\gamma$
as a function of $A_{\textrm{PhC}}$ and find a linear response with slope
$\approx$ 0.5 GHz/nm up to $A_{\textrm{PhC}}$ = 50 nm as seen in Fig. 2(d).
Remarkably, despite the presence of the nanostructure, we measure little
$Q_{\textrm{i}}$ variation or degradation over the full range of $\gamma$ < 25
GHz as seen in Fig. 2(e). We control the laser conversion process by use of
$A_{\textrm{PhC}}$ as shown in Fig. 2(f). Here, we find that
$A_{\textrm{PhC}}$ < 50 nm results in a large change of OPO phase matching
governed by Eqn. 1, with control of both $\nu_{\textrm{s}}$ and
$\nu_{\textrm{i}}$ across > 50 THz and maximum OPO wave frequency span
exceeding 150 THz of optical bandwidth.

Figure 3:  (a) Measured (points) and modelled (line) $\Delta\nu_{OPO}$ as a
function of $\gamma$ for an otherwise fixed GVD. (b) Measured (points) and
modelled (line) $\nu_{\textrm{output}}$ vs $\nu_{\textrm{design}}$. (c)
Thermal response of OPO wave frequencies in a single nanophotonic oscillator.
(d) Measured frequency noise for an OPO with $\nu_{\textrm{p}}$ = 282.8 THz
(grey) and $\nu_{\textrm{i}}$ = 219.3 THz (red).

Frequency design and control
Leveraging nanophotonic oscillators, we demonstrate wavelength access beyond
an octave through $\gamma$-controlled laser conversion. We measure OPO spectra
of devices pumped above threshold, and we extract $\nu_{\textrm{s}}$ and
$\nu_{\textrm{i}}$ to determine the output OPO signal-to-idler frequency span,
which we denote $\Delta\nu_{\textrm{OPO}}$ = $\nu_{\textrm{s}}$ \-
$\nu_{\textrm{i}}$. Figure 3(a) shows measurements (points) and modelling
(line) of $\Delta\nu_{\textrm{OPO}}$ as a function of $\gamma$, predicted by
the phase-matching condition of Eqn. 1. Figure 3(b) presents a compilation of
measured output OPO wave frequencies, $\nu_{\textrm{s}},\nu_{\textrm{i}}$,
which we denote as the $\nu_{\textrm{output}}$ (points) for various
nanophotonic oscillators and compare with the Eqn. 1 prediction, which we
denote as $\nu_{\textrm{design}}$ (line) of the OPO; see Methods. These data
assess the maximum wave span of the OPO.

Provided the wavelength access of nanophotonic oscillators, we characterize
other important operational details for applications, including thermal
frequency tuning and power-spectral noise density of output waves. Figure 3(c)
shows the variation of OPO wave frequencies in a single device as we vary the
temperature from 10∘C to 70∘ by use of a thermoelectric cooler. At room
temperature, T = 20∘C, $\nu_{\textrm{s}}$ = 365.5 THz and $\nu_{\textrm{i}}$ =
200.1 THz ($\Delta\nu_{\textrm{OPO}}$ = 165.4 THz). We then measure the three
OPO waves as a function of temperature $\nu_{\textrm{s,p,i}}(T)$, and plot the
variation from the room temperature measurement, $\Delta\nu_{\textrm{s,p,i}}$
= $|\nu_{\textrm{s,p,i}}$(20∘C) - $\nu_{s,p,i}(T)|$. During thermal tuning, we
shift $\nu_{\textrm{p}}$ to track the thermo-optic shift of the pump resonance
mode with slope $\approx$ $-$ 1.4 GHz/C, consistent with tantala’s reported
thermo-optic coefficient [34]. However, across the measured temperature range,
$\nu_{\textrm{s}}$ and $\nu_{\textrm{i}}$ tune by $\approx$ 4 THz
discontinuously, which we attribute to thermally sensitive phase matching
[24]. We also measure the optical frequency noise power spectral density,
$S_{\nu}(f)$, for $\nu_{\textrm{p}}$ and $\nu_{\textrm{i}}$ (Fig. 3(d)),
calculating the integral linewidth by use of the 1/$\pi$ and
$\beta$-separation techniques [44, 45]. We find the pump laser
($\nu_{\textrm{p}}$ = 282.8 THz) to have a 1/$\pi$-integrated linewidth of 28
$\pm$ 3 kHz and a $\beta$-separation linewidth of 862 $\pm$ 61 kHz integrated
down to Fourier frequency of 78 Hz. The corresponding free-running
$\nu_{\textrm{i}}$ = 219.3 THz has a 1/$\pi$-integrated linewidth of 89 $\pm$
6 kHz and a $\beta$-separation linewidth of 1.03 $\pm$ 0.07 MHz. We attribute
the additional optical-frequency noise of $\nu_{\textrm{i}}$ to thermo-
refractive noise due to the characteristic bandwidth of the power-spectral
density [46].

Discussion
In summary, we have demonstrated a nanophotonic approach to achieve phase
matching for broadband OPO laser conversion into the visible and near-
infrared. Moreover, thermal fine-frequency tuning and the laser conversion
process contribute minimal additive frequency noise in nanophotonic
oscillators. By leveraging the precise phase-matching control afforded by
nanophotonic oscillators, we realize laser conversion spanning more than an
octave with pump tunability of only tens of gigahertz, a ratio exceeding
10,000. Nanophotonic oscillators enable the broadband, configurable gain
afforded by nonlinear optics to operate in concert with existing integrated
pump lasers, avoiding the necessity to re-customize laser gain materials in
underdeveloped spectral regions. Thereby, nanophotonic oscillators address the
challenge of laser-wavelength access, in particular, reaching across the
short-wave infrared and into the visible.

Methods
Nanophotonic oscillator design
We design nanophotonic oscillator GVD to support OPO by satisfying Eqn. 1. To
determine the GVD of a nanophotonic oscaillator, we first solve for the
ordinary microresonator ($A_{\textrm{PhC}}=0$) eigenfrequencies, using a
finite element method solver. We include the bulk material GVD of the bottom
cladding (silica) and the waveguide layer (tantala [35]) and the waveguide
geometry, including microresonator radius, waveguide width, and thickness. To
target specific OPO output wave frequencies, we use Eqn. 1 to determine the
necessary $\gamma$ for a given ordinary microresonator GVD. We then map the
required $A_{\textrm{PhC}}$ to achieve target $\gamma$ using the results from
Fig. 2(d). We modelled various geometries of tantala waveguides with a
measured thickness 566 $\pm$ 5 nm and an under-etched tantala pedestal height
of 21 $\pm$ 2 nm, within our fabrication variation. As seen in the figures,
these geometric ranges provide good agreement with the measurements. Finally,
to efficiently couple light into the nanophotonic oscillator, we employ a
broadband pulley coupler with a pulley-coupler length of 5 $\mu$m, a bus
waveguide width of 650 nm, and a bus-to-resonator gap of 180 nm [42]. We
employ commercially available software to model the anticipated
$Q_{\textrm{c}}$ using the three-dimensional finite-difference time-domain
method. We find the calculated $Q_{\textrm{c}}$ to be slightly larger than the
measurement (see Fig. 2(a)), suggesting the devices are more over-coupled than
the design, which is in good agreement with our GVD modelling of an under-
etched tantala film.

Experimental testing
Measuring passive characteristics of nanophotonic oscillators requires precise
frequency tracking of our tunable lasers. We employ fibre Mach-Zehnder
interferometers (MZIs) with RF-calibrated free spectral ranges (FSR) as
optical frequency rulers when measuring quality factors, $D_{\textrm{int}}$,
and $\gamma$ vs. $A_{PhC}$ (see Fig. 2a, 2b, and 2d). We split the output of
our tunable lasers into two paths, with one path coupled to the PhCR under
test and the second path passing through the fibre MZI. Simultaneously
recording both the MZI and PhCR transmission while frequency sweeping the
tunable laser enables direct, continuous mapping of relative optical frequency
by unwrapping the sinusoidal output of the MZI. We include fibre dispersion in
the FSR calibration, which is particularly important when measuring GVD. We
use three independent, widely tunable lasers to measure $D_{\textrm{int}}$,
with their corresponding measurements stitched together for the plot in Fig.
2b. Additionally, we use an RF-calibrated MZI as an optical frequency-to-
voltage discriminator for the frequency noise measurements presented in Fig.
3d. For the OPO frequency noise measurement, the idler is optically filtered
using a free space bandpass filter.

Fabrication procedure
Our fabrication process begins with an oxidized silicon wafer with an ion-
beam-sputtered tantala waveguide layer (FiveNine Optics) with target thickness
570 nm. We transfer our designs to the waveguide layer using electron-beam
lithography and a fluorine inductively coupled plasma-reactive ion etch. The
top air clad devices are singulated into chips using UV lithography and a
reactive ion dry etch. Finally, we use an overnight thermal anneal in air at
500∘C to reduce material defects. This 3-inch, wafer-scale process affords
more than 3000 independent PhCR laser converters per fabrication cycle.

Acknowledgments
We thank Lindell Williams and Yan Jin for reviewing the manuscript. This
research has been funded by the DARPA LUMOS program HR0011-20-2-0046, AFOSR
FA9550-20-1-0004 Project Number 19RT1019, NSF Quantum Leap Challenge Institute
Award OMA - 2016244, and NIST. This work is a contribution of the US
Government and is not subject to US copyright. Mention of specific companies
or trade names is for scientific communication only and does not constitute an
endorsement by NIST.

## References

  * Ozcelik  _et al._ [2017] D. Ozcelik, A. Jain, A. Stambaugh, M. A. Stott, J. W. Parks, A. Hawkins, and H. Schmidt, Scalable spatial-spectral multiplexing of single-virus detection using multimode interference waveguides, Scientific Reports 7, 12199 (2017).
  * Pino  _et al._ [2021] J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. Allman, C. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, _et al._ , Demonstration of the trapped-ion quantum CCD computer architecture, Nature 592, 209 (2021).
  * McGrew  _et al._ [2019] W. F. McGrew, X. Zhang, H. Leopardi, R. Fasano, D. Nicolodi, K. Beloy, J. Yao, J. A. Sherman, S. A. Schaeffer, J. Savory, _et al._ , Towards the optical second: verifying optical clocks at the SI limit, Optica 6, 448 (2019).
  * Bothwell  _et al._ [2022] T. Bothwell, C. J. Kennedy, A. Aeppli, D. Kedar, J. M. Robinson, E. Oelker, A. Staron, and J. Ye, Resolving the gravitational redshift across a millimetre-scale atomic sample, Nature 602, 420 (2022).
  * Huang  _et al._ [2019] D. Huang, M. A. Tran, J. Guo, J. Peters, T. Komljenovic, A. Malik, P. A. Morton, and J. E. Bowers, High-power sub-kHz linewidth lasers fully integrated on silicon, Optica 6, 745 (2019).
  * Guo  _et al._ [2023] J. Guo, C. Xiang, T. J. Morin, J. D. Peters, L. Chang, and J. E. Bowers, E-band widely tunable, narrow linewidth heterogeneous laser on silicon, APL Photonics 8, 046114 (2023).
  * Tran  _et al._ [2022] M. A. Tran, C. Zhang, T. J. Morin, L. Chang, S. Barik, Z. Yuan, W. Lee, G. Kim, A. Malik, Z. Zhang, J. Guo, H. Wang, B. Shen, L. Wu, K. Vahala, J. E. Bowers, H. Park, and T. Komljenovic, Extending the spectrum of fully integrated photonics to submicrometre wavelengths, Nature 610, 10.1038/s41586-022-05119-9 (2022).
  * Zhang  _et al._ [2023] Z. Zhang, B. Shen, M. A. Tran, W. Lee, K. Asawa, G. Kim, Y. Shen, T. J. Morin, A. Malik, J. E. Bowers, T. Komljenovic, and C. Zhang, Photonic integration platform for rubidium sensors and beyond, Optica 10, 752 (2023).
  * Corato-Zanarella  _et al._ [2023] M. Corato-Zanarella, A. Gil-Molina, X. Ji, M. C. Shin, A. Mohanty, and M. Lipson, Widely tunable and narrow-linewidth chip-scale lasers from near-ultraviolet to near-infrared wavelengths, Nature Photonics 17, 157 (2023).
  * Carmon and Vahala [2007] T. Carmon and K. J. Vahala, Visible continuous emission from a silica microphotonic device by third-harmonic generation, Nature Physics 3, 430 (2007).
  * Bruch  _et al._ [2019] A. W. Bruch, X. Liu, J. B. Surya, C.-L. Zou, and H. X. Tang, On-chip $\chi$(2) microring optical parametric oscillator, Optica 6, 1361 (2019).
  * Chang  _et al._ [2016] L. Chang, Y. Li, N. Volet, L. Wang, J. Peters, and J. E. Bowers, Thin film wavelength converters for photonic integrated circuits, Optica 3, 531 (2016).
  * Nitiss  _et al._ [2022] E. Nitiss, J. Hu, A. Stroganov, and C.-S. Brès, Optically reconfigurable quasi-phase-matching in silicon nitride microresonators, Nature Photonics 16, 134 (2022).
  * Hickstein  _et al._ [2019] D. D. Hickstein, D. R. Carlson, H. Mundoor, J. B. Khurgin, K. Srinivasan, D. Westly, A. Kowligy, I. I. Smalyukh, S. A. Diddams, and S. B. Papp, Self-organized nonlinear gratings for ultrafast nanophotonics, Nature Photonics 13, 494 (2019).
  * McKenna  _et al._ [2022] T. P. McKenna, H. S. Stokowski, V. Ansari, J. Mishra, M. Jankowski, C. J. Sarabalis, J. F. Herrmann, C. Langrock, M. M. Fejer, and A. H. Safavi-Naeini, Ultra-low-power second-order nonlinear optics on a chip, Nature Communications 13, 4532 (2022).
  * Sahin  _et al._ [2021] E. Sahin, B. Zabelich, O. Yakar, E. Nitiss, J. Liu, R. N. Wang, T. J. Kippenberg, and C.-S. Brès, Difference-frequency generation in optically poled silicon nitride waveguides, Nanophotonics 10, 1923 (2021).
  * Foster  _et al._ [2006] M. A. Foster, A. C. Turner, J. E. Sharping, B. S. Schmidt, M. Lipson, and A. L. Gaeta, Broad-band optical parametric gain on a silicon photonic chip, Nature 441, 960 (2006).
  * Lu  _et al._ [2019a] X. Lu, G. Moille, Q. Li, D. A. Westly, A. Singh, A. Rao, S.-P. Yu, T. C. Briles, S. B. Papp, and K. Srinivasan, Efficient telecom-to-visible spectral translation through ultralow power nonlinear nanophotonics, Nature Photonics 13, 593 (2019a).
  * Ye  _et al._ [2021] Z. Ye, P. Zhao, K. Twayana, M. Karlsson, V. Torres-Company, and P. A. Andrekson, Overcoming the quantum limit of optical amplification in monolithic waveguides, Science Advances 7, eabi8150 (2021).
  * Riemensberger  _et al._ [2022] J. Riemensberger, N. Kuznetsov, J. Liu, J. He, R. N. Wang, and T. J. Kippenberg, A photonic integrated continuous-travelling-wave parametric amplifier, Nature 612, 56 (2022).
  * Sayson  _et al._ [2019] N. L. B. Sayson, T. Bi, V. Ng, H. Pham, L. S. Trainor, H. G. L. Schwefel, S. Coen, M. Erkintalo, and S. G. Murdoch, Octave-spanning tunable parametric oscillation in crystalline kerr microresonators, Nature Photonics 13, 701 (2019).
  * Ledezma  _et al._ [2023] L. Ledezma, A. Roy, L. Costa, R. Sekine, R. Gray, Q. Guo, R. Nehra, R. M. Briggs, and A. Marandi, Octave-spanning tunable infrared parametric oscillators in nanophotonics, Science Advances 9, eadf9711 (2023).
  * Lu  _et al._ [2019b] X. Lu, G. Moille, A. Singh, Q. Li, D. A. Westly, A. Rao, S.-P. Yu, T. C. Briles, S. B. Papp, and K. Srinivasan, Milliwatt-threshold visible–telecom optical parametric oscillation using silicon nanophotonics, Optica 6, 1535 (2019b).
  * Lu  _et al._ [2020] X. Lu, G. Moille, A. Rao, D. A. Westly, and K. Srinivasan, On-chip optical parametric oscillation into the visible: generating red, orange, yellow, and green from a near-infrared pump, Optica 7, 1417 (2020).
  * Stone  _et al._ [2022a] J. R. Stone, G. Moille, X. Lu, and K. Srinivasan, Conversion efficiency in Kerr-microresonator optical parametric oscillators: From three modes to many modes, Physical Review Applied 17, 024038 (2022a).
  * Liu  _et al._ [2024] H. Liu, G. M. Brodnik, J. Zang, D. R. Carlson, J. A. Black, and S. B. Papp, Threshold and laser conversion in nanostructured-resonator parametric oscillators, Physical Review Letters 132, 023801 (2024).
  * Domeneguetti  _et al._ [2021] R. R. Domeneguetti, Y. Zhao, X. Ji, M. Martinelli, M. Lipson, A. L. Gaeta, and P. Nussenzveig, Parametric sideband generation in CMOS-compatible oscillators from visible to telecom wavelengths, Optica 8, 316 (2021).
  * Lu  _et al._ [2014] X. Lu, S. Rogers, W. C. Jiang, and Q. Lin, Selective engineering of cavity resonance for frequency matching in optical parametric processes, Applied Physics Letters 105, 151104 (2014).
  * Yu  _et al._ [2021] S.-P. Yu, D. C. Cole, H. Jung, G. T. Moille, K. Srinivasan, and S. B. Papp, Spontaneous pulse formation in edgeless photonic crystal resonators, Nature Photonics 15, 461 (2021).
  * Black  _et al._ [2022] J. A. Black, G. M. Brodnik, H. Liu, S.-P. Yu, D. R. Carlson, J. Zang, T. C. Briles, and S. B. Papp, Optical-parametric oscillation in photonic-crystal ring resonators, Optica 9, 1183 (2022).
  * Lu  _et al._ [2022] X. Lu, A. Chanana, F. Zhou, M. Davanco, and K. Srinivasan, Kerr optical parametric oscillation in a photonic crystal microring for accessing the infrared, Optics Letters 47, 3331 (2022).
  * Stone  _et al._ [2024] J. R. Stone, X. Lu, G. Moille, D. Westly, T. Rahman, and K. Srinivasan, Wavelength-accurate nonlinear conversion through wavenumber selectivity in photonic crystal resonators, Nature Photonics 18, 192 (2024).
  * Jin  _et al._ [2024] Y. Jin, E. Lucas, J. Zang, T. Briles, I. Dickson, D. Carlson, and S. B. Papp, The bandgap-detuned excitation regime in photonic-crystal resonators (2024), arXiv:2404.11733 [physics].
  * Jung  _et al._ [2021] H. Jung, S.-P. Yu, D. R. Carlson, T. E. Drake, T. C. Briles, and S. B. Papp, Tantala Kerr nonlinear integrated photonics, Optica 8, 811 (2021).
  * Black  _et al._ [2021] J. A. Black, R. Streater, K. F. Lamee, D. R. Carlson, S.-P. Yu, and S. B. Papp, Group-velocity-dispersion engineering of tantala integrated photonics, Optics Letters 46, 817 (2021).
  * Jafari  _et al._ [2022] M. Jafari, T. Fatema, D. R. Carlson, S. B. Papp, and A. Beling, Heterogeneous integration of AlGaAs/GaAs photodiodes on tantala waveguides for visible-light applications, in  _2022 Conference on Lasers and Electro-Optics (CLEO)_ (IEEE, 2022) pp. 1–2.
  * Dorche  _et al._ [2023] A. E. Dorche, N. Nader, E. J. Stanton, S. W. Nam, and R. P. Mirin, Heterogeneously integrated near-infrared DFB laser on tantalum pentoxide, in  _Optical Fiber Communication Conference_ (Optica Publishing Group, 2023) pp. Tu3C–6.
  * Blumenthal [2020] D. J. Blumenthal, Photonic integration for UV to IR applications, APL Photonics 5 (2020).
  * Kippenberg  _et al._ [2004] T. J. Kippenberg, S. M. Spillane, and K. J. Vahala, Kerr-nonlinearity optical parametric oscillation in an ultrahigh-Q toroid microcavity, Physical Review Letters 93, 083904 (2004).
  * Black  _et al._ [2023] J. A. Black, Z. L. Newman, S.-P. Yu, D. R. Carlson, and S. B. Papp, Nonlinear networks for arbitrary optical synthesis, Physical Review X 13, 021027 (2023).
  * Stone  _et al._ [2022b] J. R. Stone, X. Lu, G. Moille, and K. Srinivasan, Efficient chip-based optical parametric oscillators from 590 to 1150 nm, APL Photonics 7 (2022b).
  * Moille  _et al._ [2019] G. Moille, Q. Li, T. C. Briles, S.-P. Yu, T. Drake, X. Lu, A. Rao, D. Westly, S. B. Papp, and K. Srinivasan, Broadband resonator-waveguide coupling for efficient extraction of octave-spanning microcombs, Optics letters 44, 4737 (2019).
  * Fujii and Tanabe [2020] S. Fujii and T. Tanabe, Dispersion engineering and measurement of whispering gallery mode microresonator for Kerr frequency comb generation, Nanophotonics 9, 1087 (2020).
  * Liang  _et al._ [2015] W. Liang, V. Ilchenko, D. Eliyahu, A. Savchenkov, A. Matsko, D. Seidel, and L. Maleki, Ultralow noise miniature external cavity semiconductor laser, Nature communications 6, 7371 (2015).
  * Di Domenico  _et al._ [2010] G. Di Domenico, S. Schilt, and P. Thomann, Simple approach to the relation between laser frequency noise and laser line shape, Applied Optics 49, 4801 (2010).
  * Drake  _et al._ [2020] T. E. Drake, J. R. Stone, T. C. Briles, and S. B. Papp, Thermal decoherence and laser cooling of Kerr microresonator solitons, Nature Photonics 14, 480 (2020).