# A priori and a posteriori error estimates
for discontinuous Galerkin time-discrete methods
via maximal regularity

Georgios Akrivis  Department of Computer Science and Engineering, University
of Ioannina, 451 10 Ioannina, Greece, and Institute of Applied and
Computational Mathematics, FORTH, 700 13 Heraklion, Crete, Greece  akrivis@
cse.uoi.gr and  Stig Larsson  Department of Mathematical Sciences, Chalmers
University of Technology and University of Göteborg, Göteborg, Sweden  stig@
chalmers.se

###### Abstract.

The maximal regularity property of discontinuous Galerkin methods for linear
parabolic equations is used together with variational techniques to establish
a priori and a posteriori error estimates of optimal order under optimal
regularity assumptions. The analysis is set in the maximal regularity
framework of UMD Banach spaces. Similar results were proved in an earlier
work, based on the consistency analysis of Radau IIA methods. The present
error analysis, which is based on variational techniques, is of independent
interest, but the main motivation is that it extends to nonlinear parabolic
equations; in contrast to the earlier work. Both autonomous and nonautonomous
linear equations are considered.

###### Key words and phrases:

Discontinuous Galerkin methods, maximal regularity, error estimates, parabolic
equations

###### 2020 Mathematics Subject Classification:

65M12, 65M15

S. L. was supported by Vetenskapsrådet (VR) through grant no. 2017-04274.

##  1\. Introduction

We consider the discretization of differential equations satisfying the
maximal parabolic $L^{p}$-regularity property in unconditional martingale
differences (UMD) Banach spaces by discontinuous Galerkin (dG) methods. We
combine the maximal regularity property of the methods with variational
techniques and establish optimal order, optimal regularity, a priori and a
posteriori error estimates.

###  1.1. Maximal parabolic regularity

We consider an initial value problem for a linear parabolic equation,

(1.1) $\left\\{\begin{aligned} &u^{\prime}(t)+Au(t)=f(t),\quad 0<t<T,\\\
&u(0)=u_{0},\end{aligned}\right.$

in a UMD Banach space $X$ with initial value $u_{0}\in X.$ Our structural
assumption is that the closed operator $-A$ is the generator of an analytic
semigroup on $X$ having _maximal $L^{p}$-regularity_. This means that for
vanishing initial value $u_{0}=0$, for any $T\in(0,\infty],$ for some, or, as
it turns out, for all $p\in(1,\infty),$ and for any $f\in L^{p}((0,T);X)$
there exists a unique solution $u$ of (1.1) such that $u^{\prime}\in
L^{p}((0,T);X)$; then we also have $Au\in L^{p}((0,T);X).$ As a consequence of
the closed graph theorem, the solution $u$ of (1.1) with $u_{0}=0$ satisfies
the stability estimate

(1.2) $\|u^{\prime}\|_{L^{p}((0,T);X)}+\|Au\|_{L^{p}((0,T);X)}\leqslant
c_{p,X}\|f\|_{L^{p}((0,T);X)}\quad\forall f\in L^{p}((0,T);X)$

with a constant $c_{p,X}$ independent of $T,$ depending only on $p$ and $X$;
see, e.g., [5] and [8].

Since also
$\|f\|_{L^{p}((0,T);X)}\leqslant\|u^{\prime}\|_{L^{p}((0,T);X)}+\|Au\|_{L^{p}((0,T);X)}$
by the triangle inequality, the norm of the sum
$\|u^{\prime}+Au\|_{L^{p}((0,T);X)}$ and the sum of the norms
$\|u^{\prime}\|_{L^{p}((0,T);X)}+\|Au\|_{L^{p}((0,T);X)}$ are equivalent on
the Banach space

$\big{\\{}v\in W^{1,p}((0,T);X)\cap
L^{p}((0,T);{\mathscr{D}}(A)):v(0)=0\big{\\}}$

with constants independent of $T,$ for $T<\infty$. Here
${\mathscr{D}}(A):=\\{v\in X:Av\in X\\}$ is the domain of the operator $A$.

###  1.2. The numerical methods

We consider the discretization of the initial value problem (1.1) by dG
methods.

Let $N\in{\mathbb{N}},k=T/N$ be the constant time step,
$t_{n}:=nk,n=0,\dotsc,N,$ be a uniform partition of the time interval $[0,T],$
and $J_{n}:=(t_{n},t_{n+1}].$

For $s\in{\mathbb{N}}_{0},$ we denote by ${\mathbb{P}}(s)$ and
${\mathbb{P}}_{X^{\prime}}(s)$ the spaces of polynomials of degree at most $s$
with coefficients in ${\mathscr{D}}(A)$ and in the dual $X^{\prime}$ of $X$,
respectively, i.e., the elements $g$ of ${\mathbb{P}}(s)$ and of
${\mathbb{P}}_{X^{\prime}}(s)$, respectively, are of the form

$g(t)=\sum_{j=0}^{s}t^{j}w_{j},\quad
w_{j}\in{\mathscr{D}}(A)\quad\text{and}\quad w_{j}\in X^{\prime},\quad
j=0,\dotsc,s.$

With this notation, let ${\mathcal{V}}_{k}^{\text{c}}(s)$ and
${\mathcal{V}}_{k}^{\text{d}}(s)$ be the spaces of continuous and possibly
discontinuous piecewise elements of ${\mathbb{P}}(s)$, respectively,

$\displaystyle{\mathcal{V}}_{k}^{\text{c}}(s):=\\{v\in
C\big{(}[0,T];{\mathscr{D}}(A)\big{)}:v|_{J_{n}}\in{\mathbb{P}}(s),\
n=0,\dotsc,N-1\\},$
$\displaystyle{\mathcal{V}}_{k}^{\text{d}}(s):=\\{v:(0,T]\to{\mathscr{D}}(A),\
v|_{J_{n}}\in{\mathbb{P}}(s),\ n=0,\dotsc,N-1\\}.$

The spaces ${\mathcal{X}}_{k}^{\text{c}}(s)$ and
${\mathcal{X}}_{k}^{\text{d}}(s)$ are defined analogously, with coefficients
$w_{j}\in X$. Let us emphasize that we allow the values at $0$ of functions in
${\mathcal{V}}_{k}^{\text{d}}(s)$ to belong to $X.$

We denote by $\langle\cdot,\cdot\rangle$ the duality pairing between $X$ and
$X^{\prime}.$

For $q\in{\mathbb{N}},$ with starting value $U(0)=U_{0}:=u_{0}\in X$ and
source term $f\in L^{p}((0,T);X)$, we consider the discretization of the
initial value problem (1.1) by the _discontinuous Galerkin method_ dG$(q-1)$,
i.e., we seek $U\in{\mathcal{V}}_{k}^{\text{d}}(q-1)$ such that

(1.3)
$\int_{J_{n}}\big{(}{\langle}U^{\prime},v{\rangle}+{\langle}AU,v{\rangle}\big{)}\,{\mathrm{d}}t+{\langle}U_{n}^{+}-U_{n},v_{n}^{+}{\rangle}=\int_{J_{n}}{\langle}f,v{\rangle}\,{\mathrm{d}}t\quad\forall
v\in{\mathbb{P}}_{X^{\prime}}(q-1)$

for $n=0,\dotsc,N-1$. As usual, we use the notation $v_{n}:=v(t_{n}),$
$v_{n}^{+}:=\lim_{s\searrow 0}v(t_{n}+s)$.

####  1.2.1. A reconstruction operator

With $0<c_{1}<\dotsb<c_{q}=1$ the Radau nodes in the interval $[0,1]$, let
$t_{ni}:=t_{n}+c_{i}k,i=1,\dotsc,q,$ be the intermediate nodes; we also use
the notation $t_{n0}:=t_{n}.$ The _reconstruction operator_
${\mathcal{V}}_{k}^{\text{d}}(q-1)\to{\mathcal{X}}_{k}^{\text{c}}(q),w\mapsto\widehat{w},$
defined via extended interpolation at the Radau nodes, cf. [11],

(1.4) $\widehat{w}(t_{nj})=w(t_{nj}),\quad
j=0,\dotsc,q\quad(w(t_{n0})=w_{n}),$

plays a crucial role in our analysis; notice that
$\widehat{w}\in{\mathcal{V}}_{k}^{\text{c}}(q),$ provided
$w(0)\in{\mathscr{D}}(A).$

###  1.3. Main results

We establish the following optimal order, optimal regularity, a priori and a
posteriori error estimates.

######  Theorem 1.1 (A priori error estimates).

Let $p\in(1,\infty)$ and assume that the solution of (1.1) is sufficiently
regular, $u\in W^{q,p}\big{(}(0,T);{\mathscr{D}}(A)\big{)}.$ Then, the dG
approximation $U\in{\mathcal{V}}_{k}^{\text{d}}(q-1)$ satisfies the estimate

(1.5) $\|A(u-U)\|_{L^{p}((0,T);X)}\leqslant
Ck^{q}\|Au^{(q)}\|_{L^{p}((0,T);X)}.$

Furthermore, if $u_{0}\in{\mathscr{D}}(A)$ and $u\in
W^{q+1,p}\big{(}(0,T);X\big{)},$ for the reconstruction
$\widehat{U}\in{\mathcal{V}}_{k}^{\text{c}}(q),$ we have

(1.6)
$\displaystyle\|(u-\widehat{U})^{\prime}\|_{L^{p}((0,T);X)}+\|A(u-\widehat{U})\|_{L^{p}((0,T);X)}$
$\displaystyle\qquad\leqslant
Ck^{q}\big{(}\|u^{(q+1)}\|_{L^{p}((0,T);X)}+\|Au^{(q)}\|_{L^{p}((0,T);X)}\big{)}.$

The constant $C$ depends on $q,p$, and $X$, but it is independent of the
solution $u,$ of $T,$ and of the time step $k.$

######  Theorem 1.2 (A posteriori error estimate).

For initial value $u_{0}\in{\mathscr{D}}(A),$ let
$R(t):=\widehat{U}^{\prime}(t)+A\widehat{U}(t)-f(t)$ be the residual of the
reconstruction $\widehat{U}\in{\mathcal{V}}_{k}^{\text{c}}(q)$ of the dG
approximation $U\in{\mathcal{V}}_{k}^{\text{d}}(q-1).$ Then, the following
maximal regularity a posteriori error estimate holds:

(1.7)
$\|R\|_{L^{p}((0,t);X)}\leqslant\|(u-\widehat{U})^{\prime}\|_{L^{p}((0,t);X)}+\|A(u-\widehat{U})\|_{L^{p}((0,t);X)}\leqslant
c_{p,X}\|R\|_{L^{p}((0,t);X)}$

for all $0<t\leqslant T$ for any $p\in(1,\infty)$ with the constant $c_{p,X}$
from (1.2). Furthermore, the estimator is of optimal asymptotic order of
accuracy,

(1.8) $\|R\|_{L^{p}((0,T);X)}\leqslant
Ck^{q}\big{(}\|u^{(q+1)}\|_{L^{p}((0,T);X)}+\|Au^{(q)}\|_{L^{p}((0,T);X)}\big{)},$

provided that $u\in W^{q,p}\big{(}(0,T);{\mathscr{D}}(A)\big{)}\cap
W^{q+1,p}\big{(}(0,T);X\big{)}.$

Our proofs of Theorems 1.1 and 1.2 rely on the maximal regularity property of
the dG methods from [2] and on variational techniques. The variational
technique is applicable also in the case of nonlinear parabolic equations; see
[1]; this is our main motivation.

Similar error estimates were recently established in [2]. The proofs in [2]
rely on properties of the Radau IIA methods; in particular, the proof of the
optimality of $\|R\|_{L^{p}((0,T);X)}$ in [2] is significantly lengthier and
more involved.

As the proof of Theorem 1.2 is very short, we give it here.

###### Proof.

Our assumption $u_{0}\in{\mathscr{D}}(A)$ ensures that the reconstruction
$\widehat{U}$ of the dG approximation $U$ belongs to
${\mathcal{V}}_{k}^{\text{c}}(q).$ The residual $R,$ the amount by which
$\widehat{U}$ misses being an exact solution of the differential equation in
(1.1), is a computable quantity, depending only on the numerical solution
$\widehat{U}$ and the given forcing term $f.$ Replacing $f$ in the residual by
$u^{\prime}+Au,$ we see that the error $\hat{e}:=u-\widehat{U}$ satisfies the
_error equation_

(1.9) $\hat{e}^{\prime}(t)+A\hat{e}(t)=-R(t),\quad t\in(t_{n},t_{n+1}],\
n=0,\dotsc,N-1;\quad\hat{e}(0)=0.$

Now, the triangle inequality and the maximal $L^{p}$-regularity (1.2) of the
operator $A$ applied to the error equation (1.9) yield (1.7), i.e., the
asserted lower and upper a posteriori error estimators.

In view of the representation (1.9) of $R,$ the optimality (1.8) of the
residual is an immediate consequence of the a priori error estimate (1.6). ∎

We present the a priori error analysis in Section 2. In Section 3 we extend
these results to the case of nonautonomous linear parabolic equations. The
Appendix contains proofs of relevant interpolation error estimates.

##  2\. A priori error estimates

In this section we prove Theorem 1.1.

###  2.1. A discrete $\ell^{p}(X)$-norm and its equivalence to the continuous
$L^{p}(X)$-norm

We introduce the discrete $\ell^{p}(X)$-norm $\|\cdot\|_{\ell^{p}((0,T);X)}$
on
${\mathcal{V}}_{k,0}^{\text{d}}(q-1):=\\{v\in{\mathcal{V}}_{k}^{\text{d}}(q-1):v(0)=0\\}$
and on
${\mathcal{V}}_{k,0}^{\text{c}}(q):=\\{v\in{\mathcal{V}}_{k}^{\text{c}}(q):v(0)=0\\}$
by

(2.1)
$\|v\|_{\ell^{p}((0,T);X)}:=\Big{(}\sum_{\ell=0}^{N-1}\Big{(}k\sum_{i=1}^{q}\|v(t_{\ell
i})\|_{X}^{p}\Big{)}\Big{)}^{1/p}$

and show that it is equivalent to the continuous
$\|\cdot\|_{L^{p}((0,T);X)}$-norm.

Let us focus on the space ${\mathcal{V}}_{k,0}^{\text{d}}(q-1);$ the proof for
the space ${\mathcal{V}}_{k,0}^{\text{c}}(q)$ is completely analogous. First,
it is easily seen that the continuous norm is dominated by the discrete norm,

(2.2)
$\|v\|_{L^{p}((0,T);X)}\leqslant\tilde{c}_{q,p}\|v\|_{\ell^{p}((0,T);X)}\quad\forall
v\in{\mathcal{V}}_{k,0}^{\text{d}}(q-1).$

Indeed, with $\ell_{mi}$ the Lagrange polynomials
$\ell_{i}\in{\mathbb{P}}_{q}$ for the Radau points $c_{1},\dotsc,c_{q},$
shifted to a subinterval $J_{m}$, we have

$\begin{split}\int_{J_{m}}\|v(t)\|_{X}^{p}\,{\mathrm{d}}t&=\int_{J_{m}}\Big{\|}\sum_{i=1}^{q}\ell_{mi}(t)v(t_{mi})\Big{\|}_{X}^{p}\,{\mathrm{d}}t\leqslant
k\Big{(}\sum_{i=1}^{q}\|\ell_{mi}\|_{L^{\infty}(J_{m})}\|v(t_{mi})\|_{X}\Big{)}^{p}\\\
&\leqslant\Big{(}\sum_{i=1}^{q}\|\ell_{mi}\|^{p^{\prime}}_{L^{\infty}(J_{n})}\Big{)}^{p/p^{\prime}}\Big{(}\sum_{i=1}^{q}k\|v(t_{mi})\|_{X}^{p}\Big{)}=c_{q,p}k\sum_{i=1}^{q}\|v(t_{mi})\|_{X}^{p}\end{split}$

with $p^{\prime}$ the dual exponent of $p,\frac{1}{p}+\frac{1}{p^{\prime}}=1,$
and summing over $m,$ we obtain (2.2); cf. [2].

Next, we prove that the discrete norm is dominated by the continuous norm in
the reference element $[0,1]$ for polynomials $v$ of degree at most $q-1$ with
coefficients in $X;$ a scaling argument then shows that this is the case in
arbitrary intervals $(0,T).$111We thank Pedro Morin for a personal
communication regarding this result. We use the Lagrange form of $v,$

$v(t)=\sum_{i=1}^{q}\ell_{i}(t)v(c_{i}),\quad t\in[0,1].$

Let $i$ be such that

(2.3) $\|v(c_{i})\|_{X}=\max_{1\leqslant j\leqslant q}\|v(c_{j})\|_{X}.$

We want to show that

$\|v(c_{i})\|_{X}\leqslant c\|v\|_{L^{p}((0,1);X)}.$

We have,

$\|v\|_{L^{p}((0,1);X)}^{p}\geqslant\int_{c_{i}-\delta}^{c_{i}}\|v(t)\|_{X}^{p}\,{\mathrm{d}}t=\int_{c_{i}-\delta}^{c_{i}}\|\ell_{i}(t)v(c_{i})+\sum_{\begin{subarray}{c}j=1\\\
j\neq i\end{subarray}}^{q}\ell_{j}(t)v(c_{j})\|_{X}^{p}\,{\mathrm{d}}t,$

whence, in view of (2.3),

(2.4)
$\|v\|_{L^{p}((0,1);X)}^{p}\geqslant\|v(c_{i})\|_{X}^{p}\int_{c_{i}-\delta}^{c_{i}}\Big{(}|\ell_{i}(t)|-\sum_{\begin{subarray}{c}j=1\\\
j\neq i\end{subarray}}^{q}|\ell_{j}(t)|\Big{)}^{p}\,{\mathrm{d}}t.$

Now, for any $\varepsilon_{1},\varepsilon_{2}\in(0,1),$ for sufficiently small
$\delta,$ we have

(2.5) $|\ell_{i}(t)|\geqslant
1-\varepsilon_{1},\quad|\ell_{j}(t)|\leqslant\varepsilon_{2},\quad j\neq
i,\quad\forall t\in[c_{i}-\delta,c_{i}],$

and (2.4) yields

(2.6)
$\|v\|_{L^{p}((0,1);X)}^{p}\geqslant\delta\big{(}1-\varepsilon_{1}-(q-1)\varepsilon_{2}\big{)}^{p}\|v(c_{i})\|_{X}^{p}$

and the desired property follows easily.

The proof for the space ${\mathcal{V}}_{k,0}^{\text{c}}(q)$ is completely
analogous. In this case we shift the Lagrange polynomials
$\hat{\ell}_{i}\in{\mathbb{P}}_{q}$ for the points
$c_{0}=0,c_{1},\dotsc,c_{q},$ to a subinterval $J_{m}$, and use the fact that
$t_{n,0}:=t_{n}=t_{n-1,q}.$

Notice that it is obvious from (1.4) that the discrete $\ell^{p}(X)$-norms of
an element $v\in{\mathcal{V}}_{k,0}^{\text{d}}(q-1)$ and of its reconstruction
$\hat{v}\in{\mathcal{V}}_{k,0}^{\text{c}}(q)$ coincide,

(2.7) $\|\hat{v}\|_{\ell^{p}((0,T);X)}=\|v\|_{\ell^{p}((0,T);X)}\quad\forall
v\in{\mathcal{V}}_{k,0}^{\text{d}}(q-1).$

Since the equivalence constants of the discrete
$\|\cdot\|_{\ell^{p}((0,T);X)}$\- and continuous
$\|\cdot\|_{L^{p}((0,T);X)}$-norms are independent of $T,$ the corresponding
discrete $\|\cdot\|_{\ell^{p}((0,t_{n});X)}$\- and continuous
$\|\cdot\|_{L^{p}((0,t_{n});X)}$-seminorms, $n=1,\dotsc,N,$ are also
equivalent with constants independent of $n.$ Of course, the discrete
$\|\cdot\|_{\ell^{p}((0,t_{n});X)}$-seminorm is the term on the right-hand
side of (2.1) with $N$ replaced by $n.$

###  2.2. Maximal parabolic regularity of the dG method

We shall use the notation $\partial_{k}$ for the backward difference operator,

$\partial_{k}v:=\frac{v(\cdot)-v(\cdot-k)}{k},\quad
v\in{\mathcal{V}}_{k,0}^{\text{d}}(q-1)\cup{\mathcal{V}}_{k,0}^{\text{c}}(q)$

with $v=0$ in the interval $[-k,0).$ Obviously, $\partial_{k}$ commutes with
the reconstruction operator,
$\partial_{k}\hat{v}=\widehat{\partial_{k}v},v\in{\mathcal{V}}_{k,0}^{\text{d}}(q-1).$

In the case of vanishing initial value $u_{0}=0,$ for the reconstruction
$\widehat{U}$ and the dG approximation $U$ we have the following maximal
parabolic regularity result

(2.8)
$\begin{split}\|\partial_{k}\widehat{U}\|_{\ell^{p}((0,T);X)}&+\|\widehat{U}^{\prime}\|_{L^{p}((0,T);X)}+\|A\widehat{U}\|_{L^{p}((0,T);X)}\\\
&+\|AU\|_{L^{p}((0,T);X)}\leqslant C_{p,X}\|f\|_{L^{p}((0,T);X)},\end{split}$

with $C_{p,X}$ a method-dependent constant, independent of $N$ and $T.$ The
estimate for the last three terms on the left-hand side of (2.8) is given in
[2, (1.9) and the last line on p. 186]; the proof relies on the interpretation
of dG methods in [2] as modified Radau IIA methods and on the maximal
regularity property of Radau IIA methods from [6]. Notice that
$\widehat{U}\in{\mathcal{V}}_{k}^{\text{c}}(q)$ since
$u_{0}=0\in{\mathscr{D}}(A).$

It remains to prove the estimate for the first term on the left-hand side of
(2.8). Now, the nodal values
$\widehat{U}_{ni}=U_{ni}=U(t_{ni}),n=0,\dotsc,N-1,i=1,\dotsc,q,$ satisfy the
Radau IIA equations with the nodal values $f(t_{ni})$ of the forcing term
replaced by the averages $f_{ni},$

(2.9)
$f_{ni}:=\frac{1}{\int_{J_{n}}\ell_{ni}(s)\,{\mathrm{d}}s}\int_{J_{n}}\ell_{ni}(s)f(s)\,{\mathrm{d}}s,\quad
n=0,\dotsc,N-1,\ i=1,\dotsc,q;$

see [2, Lemma 2.2]. Therefore, according to the maximal regularity result of
the Radau IIA methods in [7, Lemma 3.6], we have

(2.10)
$\sum_{i=1}^{q}\|(\partial\widehat{U}_{ni})_{n=0}^{N-1}\|_{\ell^{p}(X)}^{p}\leqslant
C_{p,r}\sum_{i=1}^{q}\|(f_{ni})_{n=0}^{N-1}\|_{\ell^{p}(X)}^{p};$

here, $\widehat{U}_{-1,1}=\dotsb=\widehat{U}_{-1,q}=0,$ and for a sequence
$(v_{n})_{n\in{\mathbb{N}}_{0}}\subset X,$ we used the notation

$\partial
v_{n}:=\frac{v_{n}-v_{n-1}}{k}\quad\text{and}\quad\|(v_{n})_{n=0}^{N-1}\|_{\ell^{p}(X)}:=\Big{(}k\sum_{n=0}^{N-1}\|v_{n}\|_{X}^{p}\Big{)}^{1/p}$

for the backward difference quotient and for the discrete $\ell^{p}(X)$-norm
$\|\cdot\|_{\ell^{p}(X)}.$

Notice that the term on the left-hand side of (2.10) coincides with the first
term on the left-hand side of (2.8) raised to the power $p.$ Furthermore,

(2.11)
$\sum_{i=1}^{q}\|(f_{ni})_{n=0}^{N-1}\|_{\ell^{p}(X)}^{p}\leqslant\gamma\|f\|_{L^{p}((0,T);X)}^{p}$

with a constant $\gamma$ depending only on $c_{1}\dotsc,c_{q},$ and $p;$ see
[2, (2.12)]. Now, (2.10) and (2.11) yield

$\|\partial_{k}\widehat{U}\|_{\ell^{p}((0,T);X)}\leqslant
C_{p,X}\|f\|_{L^{p}((0,T);X)},$

and the proof of (2.8) is complete.

Obviously, (2.8) is also valid with $T$ replaced by $t_{n},n=1,\dotsc,N.$

Let us note that the estimate for the first term on the left-hand side of
(2.8) is not needed in the error analysis for linear parabolic equations;
however, it plays a key role in the error analysis for nonlinear parabolic
equations; see [1]. The analogous estimate for Radau IIA methods from [7,
Lemma 3.6] was used there in the error analysis for Radau IIA methods for
nonlinear parabolic equations.

Notice also that due to the equivalence of the discrete $\ell^{p}(X)$\- and
the continuous $L^{p}(X)$-norms established in section 2.1,
$\|\partial_{k}\widehat{U}\|_{\ell^{p}((0,T);X)}$ can be replaced by
$\|\partial_{k}\widehat{U}\|_{L^{p}((0,T);X)}$ in the maximal regularity
estimate (2.8).

Logarithmically quasi-maximal parabolic regularity results for dG methods were
earlier established in [9] in general Banach spaces for autonomous equations
and in [10] in Hilbert spaces for nonautonomous equations. These works cover
also the cases of variable time steps as well as the critical exponents
$p=1,\infty.$

###  2.3. An interpolant and its approximation properties

We shall use a standard interpolant
$\tilde{u}\in{\mathcal{V}}_{k}^{\text{d}}(q-1)$ of the solution $u$ such that
$\tilde{u}(t_{n})=u(t_{n}),n=0,\dotsc,N,$ and $u-\tilde{u}$ is in each
subinterval $J_{n}$ orthogonal to polynomials of degree at most $q-2$ (with
the second condition being void for $q=1$); then, $\tilde{u}$ is determined in
$J_{n}$ by the conditions

(2.12) $\left\\{\begin{aligned} &\tilde{u}(t_{n+1})=u(t_{n+1}),\\\
&\int_{J_{n}}\big{(}u(t)-\tilde{u}(t)\big{)}t^{j}\,{\mathrm{d}}t=0,\quad
j=0,\dotsc,q-2;\end{aligned}\right.$

cf., e.g., [13, (12.9)] and [12, §§3.1–3.3] for the case of Hilbert spaces.

The approximation property (valid for $1\leq p\leq\infty$, $q\geq 1$)

(2.13) $\|u-\tilde{u}\|_{L^{p}((0,T);X)}\leqslant
Ck^{q}\|u^{(q)}\|_{L^{p}((0,T);X)}$

will play an important role in our analysis. Furthermore, we will use the
following approximation properties of the reconstruction $\hat{\tilde{u}}$ of
$\tilde{u}$,

(2.14) $\displaystyle\|u-\hat{\tilde{u}}\|_{L^{p}((0,T);X)}$
$\displaystyle\leqslant Ck^{q}\|u^{(q)}\|_{L^{p}((0,T);X)},$ (2.15)
$\displaystyle\|(u-\hat{\tilde{u}})^{\prime}\|_{L^{p}((0,T);X)}$
$\displaystyle\leqslant Ck^{q}\|u^{(q+1)}\|_{L^{p}((0,T);X)}.$

We shall prove existence and uniqueness of $\tilde{u}$ as well as the
approximation properties (2.13), (2.14), and (2.15) in the appendix.

Notice that the orthogonality condition in (2.12) can be equivalently written
in the form

(2.16)
$\int_{J_{n}}{\langle}u(t)-\tilde{u}(t),v(t){\rangle}\,{\mathrm{d}}t=0\quad\forall
v\in{\mathbb{P}}_{X^{\prime}}(q-2).$

###  2.4. A priori error estimates

Using the interpolant $\tilde{u},$ we decompose the error $e=u-U$ in the form

$e=\rho+\vartheta\quad\text{with}\quad\rho:=u-\tilde{u}\quad\text{and}\quad\vartheta:=\tilde{u}-U\in{\mathcal{V}}_{k}^{\text{d}}(q-1).$

The desired estimate for the interpolation error $\rho,$

(2.17) $\|A\rho\|_{L^{p}((0,T);X)}\leqslant
Ck^{q}\|Au^{(q)}\|_{L^{p}((0,T);X)},$

is obtained by replacing $u$ by $Au$ in (2.13). Therefore, to prove (1.5), it
remains to bound $\vartheta.$

Since $\rho=u-\tilde{u}$ is orthogonal to $v^{\prime}$ in $J_{n}$ for any
$v\in{\mathbb{P}}_{X^{\prime}}(q-1)$, cf. (2.16), and vanishes at the nodes
$t_{n},$ integration by parts shows that it has the following crucial
property,

(2.18)
$\int_{J_{n}}{\langle}\rho^{\prime},v{\rangle}\,{\mathrm{d}}t+{\langle}\rho_{n}^{+}-\rho_{n},v_{n}^{+}{\rangle}=0\quad\forall
v\in{\mathbb{P}}_{X^{\prime}}(q-1);$

cf. [13, (12.13)].

Subtracting the dG method (1.3) from the corresponding relation for the exact
solution, and using the splitting $e=\rho+\vartheta$ as well as relation
(2.18) for $\rho,$ we obtain the following equation for $\vartheta,$

(2.19)
$\int_{J_{n}}\big{(}{\langle}\vartheta^{\prime},v{\rangle}+{\langle}A\vartheta,v{\rangle}\big{)}\,{\mathrm{d}}t+{\langle}\vartheta_{n}^{+}-\vartheta_{n},v_{n}^{+}{\rangle}=\int_{J_{n}}{\langle}A\rho,v{\rangle}\,{\mathrm{d}}t\quad\forall
v\in{\mathbb{P}}_{X^{\prime}}(q-1)$

for $n=0,\dotsc,N-1$. Notice that the reconstruction
$\hat{\vartheta}=\hat{\tilde{u}}-\widehat{U}$ of $\vartheta$ belongs to
${\mathcal{V}}_{k}^{\text{c}}(q)$ since $\vartheta(0)=0\in{\mathscr{D}}(A);$
in contrast, $\hat{\tilde{u}}$ and $\widehat{U}$ belong only to
${\mathcal{X}}_{k}^{\text{c}}(q)$ for $u_{0}\in X.$

Since $\vartheta(0)=0,$ the maximal regularity property (2.8) of the dG method
applied to the error equation (2.19) yields

$\|\hat{\vartheta}^{\prime}\|_{L^{p}((0,T);X)}+\|A\hat{\vartheta}\|_{L^{p}((0,T);X)}+\|A\vartheta\|_{L^{p}((0,T);X)}\leqslant
C_{p,X}\|A\rho\|_{L^{p}((0,T);X)},$

and thus, in view of (2.17),

(2.20)
$\|\hat{\vartheta}^{\prime}\|_{L^{p}((0,T);X)}+\|A\hat{\vartheta}\|_{L^{p}((0,T);X)}+\|A\vartheta\|_{L^{p}((0,T);X)}\leqslant
Ck^{q}\|Au^{(q)}\|_{L^{p}((0,T);X)}.$

Now, (1.5) follows immediately from (2.17) and (2.20). To prove (1.6), we
write

$\hat{e}=u-\widehat{U}=(u-\hat{\tilde{u}})+(\hat{\tilde{u}}-\widehat{U})=\hat{\rho}+\hat{\vartheta}$

and combine (2.20) with the estimates for $\hat{\rho}:=u-\hat{\tilde{u}}$ and
$\hat{\rho}^{\prime}$ from (2.14) and (2.15), namely

$\displaystyle\|A\hat{\rho}\|_{L^{p}((0,T);X)}\leqslant
Ck^{q}\|Au^{(q)}\|_{L^{p}((0,T);X)},\quad\|\hat{\rho}^{\prime}\|_{L^{p}((0,T);X)}\leqslant
Ck^{q}\|u^{(q+1)}\|_{L^{p}((0,T);X)}.$

##  3\. Extension to nonautonomous equations

In this section, we extend the maximal parabolic regularity stability
estimates for dG methods to nonautonomous parabolic equations by a
perturbation argument. For similar ideas and results, we refer to [10] and [7,
§3.6], [3] for the dG method with piecewise constant elements and for Radau
IIA methods, respectively. Furthermore, we establish optimal order a priori
and a posteriori error estimates.

We consider an initial value problem for a nonautonomous linear parabolic
equation,

(3.1) $\left\\{\begin{aligned} &u^{\prime}(t)+A(t)u(t)=f(t),\quad 0<t<T,\\\
&u(0)=u_{0},\end{aligned}\right.$

in a UMD Banach space $X.$

Our structural assumptions on $A(t)$ are that all operators $A(t),t\in[0,T],$
share the same domain ${\mathscr{D}}(A),$ $A(t)$ is the generator of an
analytic semigroup on $X$ having maximal $L^{p}$-regularity, for every
$t\in[0,T],$ $A(t)$ induce equivalent norms on ${\mathscr{D}}(A),$

(3.2) $\|A(t)v\|_{X}\leqslant c\|A(\tilde{t})v\|_{X}\quad\forall
t,\tilde{t}\in[0,T]\ \forall v\in{\mathscr{D}}(A),$

and $A(t)\colon{\mathscr{D}}(A)\to X$ satisfies the Lipschitz condition with
respect to $t,$

(3.3) $\|\big{(}A(t)-A(\tilde{t})\big{)}v\|_{X}\leqslant
L|t-\tilde{t}|\|A(s)v\|_{X}\quad\forall t,\tilde{t}\in[0,T]\ \forall
v\in{\mathscr{D}}(A),$

for all $s\in[0,T].$

With starting value $U(0)=U_{0}:=u_{0}\in X$ and source term $f\in
L^{p}((0,T);X)$, we consider the discretization of the initial value problem
(3.1) by the dG method dG$(q-1)$, i.e., we seek
$U\in{\mathcal{V}}_{k}^{\text{d}}(q-1)$ such that

(3.4)
$\int_{J_{n}}\big{(}{\langle}U^{\prime},v{\rangle}+{\langle}A(t)U,v{\rangle}\big{)}\,{\mathrm{d}}t+{\langle}U_{n}^{+}-U_{n},v_{n}^{+}{\rangle}=\int_{J_{n}}{\langle}f,v{\rangle}\,{\mathrm{d}}t\quad\forall
v\in{\mathbb{P}}_{X^{\prime}}(q-1)$

for $n=0,\dotsc,N-1$; cf. (1.3).

###  3.1. Maximal parabolic regularity

Here, for vanishing starting value $U_{0},$ we establish maximal parabolic
regularity of dG methods for the nonautonomous parabolic equation (3.1) via a
perturbation argument.

For a fixed $t_{m},m\in\\{1,\dotsc,N\\},$ we write (3.4) in the form

(3.5) $\displaystyle\int_{J_{n}}{\langle}U^{\prime},v{\rangle}\,{\mathrm{d}}t$
$\displaystyle+\int_{J_{n}}{\langle}A(t_{m})U,v{\rangle}\,{\mathrm{d}}t+{\langle}U_{n}^{+}-U_{n},v_{n}^{+}{\rangle}$
$\displaystyle=\int_{J_{n}}{\langle}(A(t_{m})-A(t))U,v{\rangle}\,{\mathrm{d}}t+\int_{J_{n}}{\langle}f,v{\rangle}\,{\mathrm{d}}t\quad\forall
v\in{\mathbb{P}}_{X^{\prime}}(q-1),$

$n=0,\dotsc,m-1.$ Since the time $t$ is frozen at $t_{m}$ on the left-hand
side of (3.5), we can apply the maximal parabolic regularity estimate (2.8)
for dG methods for autonomous equations and obtain

(3.6)
$\begin{split}\|\partial_{k}\widehat{U}\|_{\ell^{p}((0,t_{\ell});X)}&+\|\widehat{U}^{\prime}\|_{L^{p}((0,t_{\ell});X)}+\|A(t_{m})\widehat{U}\|_{L^{p}((0,t_{\ell});X)}+E_{\ell}\\\
&\leqslant
C_{p,X}\big{(}G_{\ell}+\|f\|_{L^{p}((0,t_{\ell});X)}\big{)},\quad\ell=1,\dotsc,m,\end{split}$

with

$G_{\ell}:=\|(A(t_{m})-A(\cdot))U\|_{L^{p}((0,t_{\ell});X)},\
E_{\ell}:=\|A(t_{m})U\|_{L^{p}((0,t_{\ell});X)},\ \ell=1,\dotsc,m,$

and $E_{0}:=0.$

Now, according to (3.6),

(3.7) $E_{m}^{p}\leqslant
C\big{(}G_{m}^{p}+\|f\|_{L^{p}((0,t_{m});X)}^{p}\big{)}.$

Furthermore,

$G_{m}^{p}=\|(A(t_{m})-A(\cdot))U\|_{L^{p}((0,t_{m});X)}^{p}=\sum_{\ell=0}^{m-1}\|(A(t_{m})-A(\cdot))U\|_{L^{p}(J_{\ell};X)}^{p},$

and thus, in view of the Lipschitz condition (3.3),

$G_{m}^{p}\leqslant
L^{p}\sum_{\ell=0}^{m-1}(t_{m}-t_{\ell})^{p}\|A(t_{m})U\|_{L^{p}(J_{\ell};X)}^{p}=L^{p}\sum_{\ell=0}^{m-1}(t_{m}-t_{\ell})^{p}(E_{\ell+1}^{p}-E_{\ell}^{p}).$

Hence, by summation by parts, we have

(3.8) $G_{m}^{p}\leqslant
L^{p}\sum_{\ell=1}^{m}a_{\ell}E_{\ell}^{p}=L^{p}\sum_{\ell=1}^{m-1}a_{\ell}E_{\ell}^{p}+L^{p}k^{p}E_{m}^{p},$

with $a_{\ell}:=(t_{m}-t_{\ell-1})^{p}-(t_{m}-t_{\ell})^{p},$ and (3.7) yields

(3.9) $E_{m}^{p}\leqslant
C\|f\|_{L^{p}((0,t_{m});X)}^{p}+C\sum_{\ell=1}^{m-1}a_{\ell}E_{\ell}^{p}+Ck^{p}E_{m}^{p}$

and hence, for $Ck^{p}\leqslant 1/2$,

$E_{m}^{p}\leqslant
C\|f\|_{L^{p}((0,t_{m});X)}^{p}+C\sum_{\ell=1}^{m-1}a_{\ell}E_{\ell}^{p}.$

Since the sum $\sum_{\ell=1}^{m}a_{\ell}$ is uniformly bounded,

$\sum_{\ell=1}^{m}a_{\ell}=\big{(}t_{m}-t_{0})^{p}\leqslant T^{p},$

a discrete Gronwall-type argument applied to (3.9) leads to

(3.10) $E_{m}^{p}\leqslant C\|f\|_{L^{p}((0,t_{m});X)}^{p}.$

Combining (3.10) with (3.8) and (3.6), we obtain, for sufficiently small $k$,
the desired maximal parabolic regularity stability estimate

(3.11)
$\begin{split}\|\partial_{k}\widehat{U}\|_{\ell^{p}((0,t_{m});X)}&+\|\widehat{U}^{\prime}\|_{L^{p}((0,t_{m});X)}+\|A(t_{m})\widehat{U}\|_{L^{p}((0,t_{m});X)}+\|A(t_{m})U\|_{L^{p}((0,t_{m});X)}\\\
&\leqslant C_{p,X,T}\|f\|_{L^{p}((0,t_{m});X)},\quad m=1,\dotsc,N,\end{split}$

with a constant $C_{p,X,T}$ independent of $k.$ Notice that, due to the
equivalence of norms (3.2), $A(t_{m})$ can be replaced by $A(s)$ on the left-
hand side of (3.11), for arbitrary $s\in[0,T].$

###  3.2. A priori error estimates

Here, we establish the analogue of Theorem 1.1 in the nonautonomous case.

######  Theorem 3.1 (A priori error estimates).

Assume that the solution of (3.1) is sufficiently regular, $u\in
W^{q,p}\big{(}(0,T);{\mathscr{D}}(A)\big{)}.$ Then, for sufficiently small
$k$, the dG approximation $U\in{\mathcal{V}}_{k}^{\text{d}}(q-1)$ of (3.4)
satisfies the estimate

(3.12) $\|A(s)(u-U)\|_{L^{p}((0,T);X)}\leqslant
Ck^{q}\|A(s)u^{(q)}\|_{L^{p}((0,T);X)}$

for any $s\in[0,T].$ Furthermore, if $u_{0}\in{\mathscr{D}}(A)$ and $u\in
W^{q+1,p}\big{(}(0,T);X\big{)},$ for the reconstruction
$\widehat{U}\in{\mathcal{V}}_{k}^{\text{c}}(q)$ of $U,$ we have

(3.13)
$\displaystyle\|(u-\widehat{U})^{\prime}\|_{L^{p}((0,T);X)}+\|A(s)(u-\widehat{U})\|_{L^{p}((0,T);X)}$
$\displaystyle\qquad\leqslant
Ck^{q}\big{(}\|u^{(q+1)}\|_{L^{p}((0,T);X)}+\|A(s)u^{(q)}\|_{L^{p}((0,T);X)}\big{)}.$

The constant $C$ depends on $q$, $p$, $L$, $X$, and $T$, but it is independent
of the solution $u$ and of the time step $k.$

###### Proof.

We proceed as in the proof of Theorem 1.1. In particular, we decompose the
error $e=u-U$ in the form

$e=\rho+\vartheta\quad\text{with}\quad\rho:=u-\tilde{u}\quad\text{and}\quad\vartheta:=\tilde{u}-U\in{\mathcal{V}}_{k}^{\text{d}}(q-1).$

The error $\rho$ can be estimated as in Section 2.4; for instance, the
analogue of (2.17) reads

(3.14) $\|A(s)(u-\tilde{u})\|_{L^{p}((0,T);X)}\leqslant
ck^{q}\|A(s)u^{(q)}\|_{L^{p}((0,T);X)},$

for any $s\in[0,T].$

Furthermore, subtracting the dG method (3.4) from the corresponding equation
for the exact solution $u$ of (3.1) and using the identity (2.18) for $\rho,$
we obtain the following equation for $\vartheta,$

(3.15)
$\int_{J_{n}}\big{(}{\langle}\vartheta^{\prime},v{\rangle}+{\langle}A(t)\vartheta,v{\rangle}\big{)}\,{\mathrm{d}}t+{\langle}\vartheta_{n}^{+}-\vartheta_{n},v_{n}^{+}{\rangle}=\int_{J_{n}}{\langle}A(t)\rho,v{\rangle}\,{\mathrm{d}}t\quad\forall
v\in{\mathbb{P}}_{X^{\prime}}(q-1)$

for $n=0,\dotsc,N-1$.

Since $\vartheta(0)=0,$ the maximal regularity property of the dG method for
nonautonomous equations (see (3.11)) applied to the error equation (3.15)
yields

$\|\hat{\vartheta}^{\prime}\|_{L^{p}((0,T);X)}+\|A(s)\hat{\vartheta}\|_{L^{p}((0,T);X)}+\|A(s)\vartheta\|_{L^{p}((0,T);X)}\leqslant
C_{p,X}\|A(\cdot)\rho\|_{L^{p}((0,T);X)},$

for any $s\in[0,T],$ and thus, in view of (3.14),

(3.16)
$\|\hat{\vartheta}^{\prime}\|_{L^{p}((0,T);X)}+\|A(s)\hat{\vartheta}\|_{L^{p}((0,T);X)}+\|A(s)\vartheta\|_{L^{p}((0,T);X)}\leqslant
Ck^{q}\|A(s)u^{(q)}\|_{L^{p}((0,T);X)}.$

The proof can now be completed as in the case of Theorem 1.1. ∎

###  3.3. A posteriori error estimates

Let $R$ be the _residual_ of the reconstruction $\widehat{U},$

$R(t):=\widehat{U}^{\prime}(t)+A(t)\widehat{U}(t)-f(t),\quad
t\in(t_{n},t_{n+1}],\quad n=0,\dotsc,N-1.$

Then, the error $\hat{e}:=u-\widehat{U}$ satisfies the _error equation_

(3.17) $\hat{e}^{\prime}(t)+A(t)\hat{e}(t)=-R(t),\quad t\in(t_{n},t_{n+1}],\
n=0,\dotsc,N-1;\quad\hat{e}(0)=0.$

Let us now fix an $s\in(0,T].$ To apply the _maximal $L^{p}$-regularity_ of
the operator $A(s),$ frozen at time $s,$ we rewrite (3.17) in the form

$\hat{e}^{\prime}(t)+A(s)\hat{e}(t)=[A(s)-A(t)]\hat{e}(t)-R(t),\quad
t\in(0,s].$

Proceeding as in the proof of the maximal regularity property for
nonautonomous parabolic equations in the continuous case, cf., e.g., [3, §4.2]
for the derivation a posteriori estimates for Radau IIA methods, we obtain the
desired a posteriori error estimate

$\|\hat{e}^{\prime}\|_{L^{p}((0,s);X)}+\|A(s)\hat{e}\|_{L^{p}((0,s);X)}\leqslant
C\|R\|_{L^{p}((0,s);X)},\quad 0<s\leqslant T,$

for any $p\in(1,\infty),$ with a constant $C$ depending on $p,X,L,$ and $T,$
but independent of $s.$

Furthermore, the triangle inequality applied to (3.17) yields a lower a
posteriori error estimator,

$\|R\|_{L^{p}((0,s);X)}\leqslant\|\hat{e}^{\prime}\|_{L^{p}((0,s);X)}+\|A(\cdot)\hat{e}\|_{L^{p}((0,s);X)},\quad
0<s\leqslant T.$

As in the autonomous case, we see that the a posteriori error estimator is of
optimal order as an immediate consequence of the a priori error estimate
(3.13).

##  Appendix A Interpolation error estimates

We prove error estimates for $\tilde{v}$ and $\hat{\tilde{v}}$. We shall use a
standard argument based on the Bramble–Hilbert lemma; cf. [4, (4.4.4)]. The
key ingredients are reproduction of polynomials and boundedness with respect
to a relevant Sobolev norm.

###  A.1. Existence and uniqueness of $\bm{\tilde{v}}$

The interpolant $\tilde{v}$ of a function $v\in C([0,T];X)$ can be expressed
in terms of the value $v(t_{n+1})$ of $v$ at $t_{n+1}$ and the Legendre
coefficients $v_{0},\dotsc,v_{q-2}\in X$ of $v,$

(A.1)
$v_{i}:=\frac{1}{\|L_{ni}\|_{L^{2}(J_{n})}^{2}}\int_{J_{n}}L_{ni}(t)v(t)\,{\mathrm{d}}t.$

More precisely, for $t\in J_{n}$,

(A.2)
$\tilde{v}(t)=(P_{q-2}v)(t)+L_{n,q-1}(t)\Big{[}v(t_{n+1})-\sum_{i=0}^{q-2}v_{i}\Big{]},\quad
P_{q-2}v=\sum_{i=0}^{q-2}L_{ni}v_{i},$

with $P_{q-2}$ the piecewise $L^{2}$-projection onto
${\mathcal{X}}_{k}^{\text{d}}(q-1)$; here, $L_{ni}$ are the Legendre
polynomials $L_{i}$ of degree $i$ shifted to the interval $J_{n},$

$L_{ni}\big{(}\tfrac{1}{2}(t_{n}+t_{n+1}+ks)\big{)}=L_{i}(s),\quad
s\in[-1,1];$

see [12, (3.2)]. Indeed, the part $P_{q-2}v$ of $\tilde{v}$ on the right-hand
side of (A.2) is due to the orthogonality of $v-\tilde{v}$ to the orthogonal
polynomials $L_{ni},i=0,\dotsc,q-2.$ The coefficient of $L_{n,q-1}$ is
determined by the interpolation condition $\tilde{v}(t_{n+1})=v(t_{n+1})$ and
the property $L_{ni}(t_{n+1})=1$ of the Legendre polynomials, which yields
$(P_{q-2}v)(t_{n+1})=v_{0}+\dotsb+v_{q-2}.$ In particular, $\tilde{v}=v$ for
$v\in{\mathcal{X}}_{k}^{\text{d}}(q-1).$

###  A.2. Proof of the approximation property (2.13)

We first consider interpolation of functions on the unit interval $(0,1)$.
Here we assume $1\leq p\leq\infty$ and $q\geq 1$ and hence Sobolev’s embedding
${W^{q,p}((0,1);X)}\subset C([0,1];X)$ holds. From (A.1) and (A.2) it is clear
that the interpolation operator
$C([0,1];X)\to{W^{q,p}((0,1);X)},v\mapsto\tilde{v},$ is bounded, so that by
Sobolev’s inequality,

(A.3) $\|\tilde{v}\|_{W^{q,p}((0,1);X)}\leqslant C\|v\|_{C([0,1];X)}\leqslant
C\|v\|_{W^{q,p}((0,1);X)}.$

Moreover,

(A.4) $\tilde{v}=v\quad\forall v\in{\mathbb{P}}_{X}(q-1).$

Hence, by a standard argument based on the Bramble–Hilbert lemma, we have

(A.5) $\|v-\tilde{v}\|_{W^{q,p}((0,1);X)}\leqslant C|v|_{W^{q,p}((0,1);X)}.$

Here $|v|_{W^{q,p}((0,1);X)}=\|v^{(q)}\|_{L^{p}((0,1);X)}$ denotes the
seminorm.

In fact, by the Bramble–Hilbert lemma there is a Taylor polynomial
$\bar{v}\in{\mathbb{P}}_{X}(q-1)$ such that

(A.6) $\|v-\bar{v}\|_{W^{q,p}((0,1);X)}\leqslant C|v|_{W^{q,p}((0,1);X)}.$

Hence, since by (A.4) $\tilde{\bar{v}}=\bar{v}$, and by (A.3), (A.6),

$\displaystyle\|v-\tilde{v}\|_{W^{q,p}((0,1);X)}$
$\displaystyle\leqslant\|v-\bar{v}\|_{W^{q,p}((0,1);X)}+\|\bar{v}-\tilde{v}\|_{W^{q,p}((0,1);X)}$
$\displaystyle=\|v-\bar{v}\|_{W^{q,p}((0,1);X)}+\|(\bar{v}-{v})^{\tilde{}}\,\|_{W^{q,p}((0,1);X)}$
$\displaystyle\leqslant C\|v-\bar{v}\|_{W^{q,p}((0,1);X)}\leqslant
C|v|_{W^{q,p}((0,1);X)},$

which is (A.5).

Since $|v|_{W^{j,p}((0,1);X)}\leqslant\|v\|_{W^{q,p}((0,1);X)}$ and
$|v|_{L^{\infty}((0,1);X)}\leqslant C\|v\|_{W^{q,p}((0,1);X)}$, from (A.5) we
now conclude

$\displaystyle|v-\tilde{v}|_{W^{j,p}((0,1);X)}$ $\displaystyle\leqslant
C|v|_{W^{q,p}((0,1);X)},\quad j=0,\dotsc,q,$
$\displaystyle\|v-\tilde{v}\|_{L^{\infty}((0,1);X)}$ $\displaystyle\leqslant
C|v|_{W^{q,p}((0,1);X)}.$

Finally, by a change of variables and with a slight abuse of notation, we have

$\displaystyle|v|_{W^{j,p}((0,1);X)}$
$\displaystyle=k^{j-1/p}|v|_{W^{j,p}(J_{n};X)},$
$\displaystyle\|v\|_{L^{\infty}((0,1);X)}$
$\displaystyle=\|v-\tilde{v}\|_{L^{\infty}(J_{n};X)}.$

This proves

(A.7) $\displaystyle|v-\tilde{v}|_{W^{j,p}(J_{n};X)}$ $\displaystyle\leqslant
Ck^{q-j}|v|_{W^{q,p}(J_{n};X)},\quad j=0,\dotsc,q,$ (A.8)
$\displaystyle\|v-\tilde{v}\|_{L^{\infty}(J_{n};X)}$ $\displaystyle\leqslant
Ck^{q-1/p}|v|_{W^{q,p}(J_{n};X)}.$

As a consequence of (A.7) with $j=0$ (or of (A.8)) we have (2.13). This is the
only case that we need in the present work; the other cases are included for
the sake of completeness.

The approximation property (A.8) for general $p$ and for Banach spaces is an
analogue of [13, (12.10)] for $p=2$ and for Hilbert spaces.

###  A.3. Proof of the approximation properties (2.14) and (2.15)

We begin by proving that the operator $v\mapsto\hat{\tilde{v}}$ reproduces
polynomials of degree at most $q$. Again we assume $1\leq p\leq\infty$.

######  Lemma A.1 (Reproduction property).

Assume that $v\in{\mathcal{X}}_{k}^{\text{c}}(q).$ Then, the following
reproduction property holds:

(A.9) $\hat{\tilde{v}}=v.$

In particular, if $v\in{\mathcal{X}}_{k}^{\text{c}}(q-1)$, then
$\hat{\tilde{v}}=\tilde{v}=v$.

###### Proof.

Let us consider the Lagrange interpolant
$w\in{\mathcal{X}}_{k}^{\text{d}}(q-1),$ with $w(0)=v(0),$ of $v$ at the Radau
nodes,

(A.10) $w(t_{nj})=v(t_{nj}),\quad j=1,\dotsc,q,$

for $n=0,\dotsc,N-1.$ Then, it follows immediately from the definition (1.4)
that $v\in{\mathcal{X}}_{k}^{\text{c}}(q)$ is the reconstruction of
$w\in{\mathcal{X}}_{k}^{\text{d}}(q-1)$, that is, $v=\widehat{w}$.

It remains to show that $\tilde{v}=w,$ that is, that $w$ satisfies the
orthogonality condition

$\int_{t_{n}}^{t_{n+1}}\big{(}v(t)-w(t)\big{)}t^{j}\,{\mathrm{d}}t=0,\quad
j=0,\dotsc,q-2.$

This can be easily seen by using the Lagrange form of the interpolation error
$v(t)-w(t)=(v_{n}-w_{n}^{+})\ell_{n0}(t),$ with $\ell_{n0}$ the polynomial of
degree $q$ vanishing at the nodes $t_{n1},\dotsc,t_{nq}$ and taking the value
$1$ at the node $t_{n0},$ and the orthogonality of $\ell_{n0}$ to polynomials
of degree at most $q-2$ or, equivalently, by the exactness of the Radau
quadrature rule for polynomials of degree $2q-2$.

For $v\in{\mathcal{X}}_{k}^{\text{c}}(q-1)$, we obviously have $w=v$ by
(A.10), i.e., $\tilde{v}=v.$ ∎

We next consider the boundedness of $v\mapsto\hat{\tilde{v}}$. Let $v\in
C([0,T];X)$. The hat operator interpolates $\tilde{v}$ at the node values
$\hat{\tilde{v}}(t_{nj})=\tilde{v}(t_{nj})$, $j=0,\dotsc,q$, where
$\tilde{v}(t_{n0})=\tilde{v}(t_{n})=v(t_{n})$ and
$\tilde{v}(t_{nq})=\tilde{v}(t_{n+1})=v(t_{n+1})$. Thus, in view of (A.1) and
(A.2), $\hat{\tilde{v}}|_{J_{n}}$ depends only on the values of $v$ in
$[t_{n},t_{n+1}]$. More precisely, after a transformation to the unit
interval, we have

$\|\hat{\tilde{v}}\|_{W^{q+1,p}((0,1);X)}\leqslant
C\|v\|_{C([0,1];X)}\leqslant C\|v\|_{W^{q+1,p}((0,1);X)}.$

Moreover, according to (A.9),

$\hat{\tilde{v}}=v\quad\forall v\in{\mathbb{P}}_{X}(q).$

By the same argument as in Subsection A.2, we conclude

$\displaystyle|v-\hat{\tilde{v}}|_{W^{j,p}((0,1);X)}$ $\displaystyle\leqslant
C|v|_{W^{q+1,p}((0,1);X)},\quad j=0,\dotsc,q+1,$
$\displaystyle\|v-\hat{\tilde{v}}\|_{L^{\infty}((0,1);X)}$
$\displaystyle\leqslant C|v|_{W^{q+1,p}((0,1);X)},$

which proves

$\displaystyle|v-\hat{\tilde{v}}|_{W^{j,p}(J_{n};X)}$ $\displaystyle\leqslant
Ck^{q+1-j}|v|_{W^{q+1,p}(J_{n};X)},\quad j=0,\dotsc,q+1,$
$\displaystyle\|v-\hat{\tilde{v}}\|_{L^{\infty}(J_{n};X)}$
$\displaystyle\leqslant Ck^{q+1-1/p}|v|_{W^{q+1,p}(J_{n};X)}.$

In particular, for $j=1$, we obtain (2.15).

Since $v\mapsto\hat{\tilde{v}}$ also reproduces polynomials of degree at most
$q-1$, the same argument shows

(A.11) $\displaystyle|v-\hat{\tilde{v}}|_{W^{j,p}(J_{n};X)}$
$\displaystyle\leqslant Ck^{q-j}|v|_{W^{q,p}(J_{n};X)},\quad j=0,\dotsc,q,$
(A.12) $\displaystyle\|v-\hat{\tilde{v}}\|_{L^{\infty}(J_{n};X)}$
$\displaystyle\leqslant Ck^{q-1/p}|v|_{W^{q,p}(J_{n};X)}.$

From (A.11) for $j=0$ (or from (A.12)), we obtain (2.14).

## References

  * [1] G. Akrivis and S. Larsson,  _Discontinuous Galerkin time-stepping methods for nonlinear parabolic equations_ ,  in preparation.
  * [2] G. Akrivis and Ch. Makridakis,  _On maximal regularity estimates for discontinuous Galerkin time-discrete methods_ ,  SIAM J. Numer. Anal. 60 (2022) 180–194. DOI 10.1137/20M1383781. MR4368992
  * [3] G. Akrivis and Ch. G. Makridakis,  _A posteriori error estimates for Radau IIA methods via maximal regularity_ ,  Numer. Math. 150 (2022) 691–717. DOI 10.1007/s00211-022-01271-6. MR4393999
  * [4] S. C. Brenner and L. R. Scott,  _The Mathematical Theory of Finite Element Methods_ ,  Third ed., Texts in Applied Mathematics, vol. 15, Springer, New York, 2008. DOI 10.1007/978-0-387-75934-0 MR2373954
  * [5] R. Denk, M. Hieber, and J. Prüss,  _${\mathcal{R}}$ -boundedness, Fourier multipliers and problems of elliptic and parabolic type_,  Mem. Amer. Math. Soc. 166 (2003), no. 788, 114p. DOI 10.1090/memo/0788. MR2006641
  * [6] B. Kovács, B. Li, and C. Lubich,  _A-stable time discretizations preserve maximal parabolic regularity_ ,  SIAM J. Numer. Anal. 54 (2016) 3600–3624. DOI 10.1137/15M1040918. MR3582825
  * [7] P. C. Kunstmann, B. Li, and C. Lubich,  _Runge–Kutta time discretization of nonlinear parabolic equations studied via discrete maximal parabolic regularity_ ,  Found. Comput. Math. 18 (2018) 1109–1130. DOI 10.1007/s10208-017-9364-x. MR3857906
  * [8] P. C. Kunstmann and L. Weis,  _Maximal $L_{p}$-regularity for Parabolic Equations, Fourier Multiplier Theorems and $H^{\infty}$-functional Calculus_, in Functional Analytic Methods for Evolution Equations,  Lecture Notes in Mathematics 1855 (2004) 65–311. DOI 10.1007/978-3-540-44653-8_2. MR2108959
  * [9] D. Leykekhman and B. Vexler,  _Discrete maximal parabolic regularity for Galerkin finite element methods_ ,  Numer. Math. 135 (2017) 923–952. DOI 10.1007/s00211-006-0821-2. MR3606467
  * [10] D. Leykekhman and B. Vexler,  _Discrete maximal parabolic regularity for Galerkin finite element methods for nonautonomous parabolic problems_ ,  SIAM J. Numer. Anal. 56 (2018) 2178–2202. DOI 10.1137/17M114100X. MR3829516
  * [11] Ch. Makridakis and R. H. Nochetto,  _A posteriori error analysis for higher order dissipative methods for evolution problems_ ,  Numer. Math. 104 (2006) 489–514. DOI 10.1007/s00211-006-0013-6. MR2249675
  * [12] D. Schötzau and C. Schwab,  _Time discretization of parabolic problems by the hp-version of the discontinuous Galerkin finite element method_ ,  SIAM J. Numer. Anal. 38 (2000) 837–875. DOI 10.1137/S0036142999352394. MR1781206
  * [13] V. Thomée,  _Galerkin Finite Element Methods for Parabolic Problems_ , 2${}^{\text{nd}}$ ed.,  Springer–Verlag, Berlin, 2006. DOI 10.1007/3-540-33122-0. MR2249024


# The large deviation principle for inhomogeneous Erdős-Rényi random graphs

Maarten Markering  Mathematical Institute, Leiden University

###### Abstract

Consider the inhomogeneous Erdős-Rényi random graph (ERRG) on $n$ vertices for
which each pair $i,j\in\\{1,\ldots,n\\}$, $i\neq j$ is connected independently
by an edge with probability $r_{n}(\frac{i-1}{n},\frac{j-1}{n})$, where
$(r_{n})_{n\in\mathbb{N}}$ is a sequence of graphons converging to a reference
graphon $r$. As a generalization of the celebrated large deviation principle
(LDP) for ERRGs by Chatterjee and Varadhan [6], Dhara and Sen [7] proved an
LDP for a sequence of such graphs under the assumption that $r$ is bounded
away from 0 and 1, and with a rate function in the form of a lower semi-
continuous envelope. We further extend the results by Dhara and Sen. We relax
the conditions on the reference graphon to $\log r,\log(1-r)\in
L^{1}([0,1]^{2})$. We also show that, under this condition, their rate
function equals a different, more tractable rate function. We then apply these
results to the large deviation principle for the largest eigenvalue of
inhomogeneous ERRGs and weaken the conditions for part of the analysis of the
rate function by Chakrabarty, Hazra, Den Hollander and Sfragara [2].

††footnotetext: Date: ††footnotetext: Email:
<EMAIL_ADDRESS>2010 Mathematics Subject
Classification: 05C80, 60F10, 60B20††footnotetext: Key words: inhomogeneous
Erdős-Rényi random graph, large deviations, rate function, graphons, largest
eigenvalue††footnotetext: Data sharing not applicable to this article as no
datasets were generated or analysed during the current study.

##  1 Introduction

###  1.1 Motivation and outline

The large deviation principle (LDP) for the Erdős-Rényi random graph (ERRG)
was introduced and proved by Chatterjee and Varadhan in their seminal paper
[6]. They viewed the sequence of ERRGs as graphons and obtained the LDP in the
space of graphons with the cut topology. With this LDP, Chatterjee and
Varadhan completely solved a long-standing open problem regarding upper tails
for large deviations of triangle counts in ERRGs. This spurred many further
developments in the area of large deviations for random graphs. We refer to
[4] for an overview.

In this paper, we study the inhomogeneous Erdős-Rényi random graph, which is a
generalization of the ERRG in that different edges do not necessarily occur
with the same probability. This probability is controlled by a reference
graphon. Recently, Dhara and Sen [7, Proposition 3.1] proved the LDP for the
inhomogeneous ERRG model under the assumption that the reference graphon $r$
is bounded away from 0 and 1, i.e., there exists $\eta>0$ such that $\eta\leq
r(x,y)\leq 1-\eta$ for all $(x,y)\in[0,1]^{2}$. The rate function
$J^{\prime}_{r}$ for their LDP has the form of a lower semi-continuous
envelope of another rate function $I_{r}$, which complicates its analysis.

We extend their proof to reference graphons that satisfy the mild
integrability condition $\log r,\log(1-r)\in L^{1}([0,1]^{2})$. Furthemore, we
show that $J^{\prime}_{r}$ is also the lower semi-continuous envelope of
another, more tractable rate function $J_{r}$ that is already semi-continuous,
which implies that $J^{\prime}_{r}$ actually equals $J_{r}$. The relaxation of
the conditions broadens the scope of applications, and the simplification of
the rate function makes the LDP more suitable to such applications. As an
example application, we consider the LDP for the largest eigenvalue of an
inhomogeneous ERRG. We show that the conditions for the analysis by
Chakrabarty, Hazra, Den Hollander and Sfragara [2] can partially be weakened.

Random graphs with inhomogeneities and constraints have many applications in
complex networks, physics and statistics. As a consequence, recent interest in
large deviations for inhomogeneous random graphs has grown considerably. The
LDP for ERRGs was applied by Chatterjee and Diaconis [5] to the exponential
random graph, Dhara and Sen [7] applied the LDP for inhomogeneous ERRGs to
random graphs with fixed degrees, and recently, Borgs et al. [1] proved an LDP
for block models. This paper is part of a general effort to better understand
large deviations for inhomogeneous random graphs.

#### Outline.

In Section 1.2, we briefly introduce the necessary concepts and definitions
from graph limit theory. The LDP for inhomogeneous ERRGs is stated in Section
1.3, and the rate function is introduced. In Section 1.4, we introduce large
deviations for the largest eigenvalue of the inhomogeneous ERRG. The proof
that the rate function is well-defined, lower semi-continuous, and equal to
the rate function of Dhara and Sen [7] is given in Section 2. We generalize
Dhara and Sen’s proof of the LDP upper bound in Section 3. In Section 4, we
finish by showing that the results from this paper can be used to weaken the
conditions of the analysis of the rate function for the largest eigenvalue by
Chakrabarty et al. [2].

###  1.2 Graphons

A graphon is a Borel measurable function $h\colon[0,1]^{2}\to[0,1]$ such that
$h(x,y)=h(y,x)$ for all $(x,y)\in[0,1]^{2}$. We denote the set of graphons by
$\mathcal{W}$. Every finite simple graph $G=(V(G),E(G))$ with
$V(G)=[n]:=\\{1,\ldots,n\\}$ can be represented as the graphon $h^{G}$ defined
as

$h^{G}(x,y)=\begin{cases}1,&(i,j)\in E(G),\,(x,y)\in B(i,j,n),\\\
0,&\text{otherwise,}\end{cases}$ (1.1)

with $B(i,j,n):=[\frac{i-1}{n},\frac{i}{n})\times[\frac{j-1}{n},\frac{j}{n})$.
We call $h^{G}$ the empirical graphon of $G$. Let $\mathcal{M}$ denote the set
of Lebesgue measure-preserving bijections $\phi\colon[0,1]\to[0,1]$. The cut
distance on $\mathcal{W}$ is defined as

$d_{\square}(h_{1},h_{2}):=\sup_{S,T\subset[0,1]}\left|\int_{[0,1]^{2}}(h_{1}(x,y)-h_{2}(x,y))\,dx\,dy\right|$
(1.2)

and the cut metric is defined as

$\delta_{\square}(h_{1},h_{2}):=\inf_{\phi\in\mathcal{M}}d_{\square}(h^{\phi}_{1},h_{2}),$
(1.3)

where $h^{\phi}(x,y):=h(\phi(x),\phi(y))$. See [9, Theorem 8.13] for several
equivalent definitions for $\delta_{\square}$. The cut metric induces an
equivalence relation $\sim$ on $\mathcal{W}$ where $h_{1}\sim h_{2}$ if
$\delta_{\square}(h_{1},h_{2})=0$. Define
$\widetilde{\mathcal{W}}:=\mathcal{W}/{\sim}$ and denote the equivalence class
of $h\in\mathcal{W}$ by $\widetilde{h}$. The space
$(\widetilde{\mathcal{W}},\delta_{\square})$ is a compact metric space [9,
Theorem 9.23].

###  1.3 Main theorem

For some $h\in\mathcal{W}$, define the random graph $G_{n}$ with vertex set
$[n]$ by connecting every pair of vertices $i,j\in[n]$ with probability
$h(\frac{i-1}{n},\frac{j-1}{n})$. Denote the law of the empirical graphon
$h^{G_{n}}$ of $G_{n}$ on $\mathcal{W}$ by $\mathbb{P}_{n,h}$ and the law of
$\widetilde{h}^{G_{n}}$ on $\widetilde{\mathcal{W}}$ by
$\widetilde{\mathbb{P}}_{n,h}$.

We define a sequence of random graphs as follows. Fix a graphon
$r\in\mathcal{W}$ called the reference graphon and let
$(r_{n})_{n\in\mathbb{N}}$ be a sequence of block graphons of the form

$r_{n}=\begin{cases}r_{n,ij},&(x,y)\in B(i,j,n),\,1\leq i,j\leq n,\,i\neq
j,\\\ 0,&\text{otherwise},\end{cases}$ (1.4)

such that $0<r<1$ and $r_{n}\rightarrow r$ Lebesgue-almost everywhere and in
$L^{1}$-norm as $n\rightarrow\infty$. Further assume that

$\log r,\log(1-r)\in L^{1}([0,1]^{2})$ (1.5)

and

$\|\log r_{n}-\log r\|_{L^{1}},\|\log(1-r_{n})-\log(1-r)\|_{L^{1}}\rightarrow
0$ (1.6)

as $n\rightarrow\infty$.

We show that $(\widetilde{\mathbb{P}}_{n,r_{n}})_{n\in\mathbb{N}}$ satisfies
an LDP. First, we define a suitable rate function. For $a\in[0,1]$ and
$b\in(0,1)$, let

$\begin{split}\mathcal{R}(a\mid
b)&:=a\log\frac{a}{b}+(1-a)\log\frac{1-a}{1-b},\end{split}$ (1.7)

where we use the convention $0\log 0=0$. For $h,r\in\mathcal{W}$ such that
$0<r<1$ Lebesgue-almost everywhere, this map can be extended to a map $I_{r}$
on $\mathcal{W}$ by defining

$I_{r}(h)=\int_{[0,1]^{2}}\mathcal{R}(h(x,y)\mid r(x,y))\,dx\,dy.$ (1.8)

In the case $r\equiv p$, $I_{r}$ is invariant under measure-preserving
bijections. Hence, $I_{r}$ can be extended to $\widetilde{\mathcal{W}}$ as
$J_{r}(\widetilde{h}):=I_{r}(h)$ [4, Proposition 5.1]. For inhomogeneous
reference graphons, this is no longer the case. To solve this problem, Dhara
and Sen extend the function to its lower semi-continuous envelope, i.e.,

$J_{r}^{\prime}(\widetilde{h}):=\sup_{\eta>0}\inf_{g\in
B(\widetilde{h},\eta)}I_{r}(g),$ (1.9)

where
$B(\widetilde{h},\eta):=\\{g\in\mathcal{W}\mid\delta_{\square}(\widetilde{h},\widetilde{g})\leq\eta\\}$.
This extension is well-defined and lower semi-continuous [7, Lemma 2.1], but
analytic manipulation can be somewhat difficult. Instead, we propose the
following more tractable rate function:

$J_{r}(\widetilde{h}):=\inf_{\phi\in\mathcal{M}}I_{r}(h^{\phi}).$ (1.10)

A priori, it is not clear whether $J_{r}$ a good rate function on
$\widetilde{\mathcal{W}}$ or even well-defined. In Section 2, we show that it
is, and that $J_{r}$ in fact equals $J^{\prime}_{r}$ under the condition
(1.5). This is one of the main results of this paper.

We are now ready to state the main theorem.

######  Theorem 1.1.

Subject to (1.5) and (1.6), the sequence
$(\widetilde{\mathbb{P}}_{n,r_{n}})_{n\in\mathbb{N}}$ satisfies the large
deviation principle on $(\widetilde{\mathcal{W}},\delta_{\square})$ with rate
$\frac{n^{2}}{2}$ and rate function $J_{r}$, i.e., for all closed sets
$\widetilde{F}\subset\widetilde{\mathcal{W}}$ and open sets
$\widetilde{U}\subset\widetilde{\mathcal{W}}$,

$\begin{split}\limsup_{n\rightarrow\infty}\frac{2}{n^{2}}\log\widetilde{\mathbb{P}}_{n,r_{n}}(\widetilde{F})\leq-\inf_{\widetilde{h}\in\widetilde{F}}J_{r}(\widetilde{h}),\\\
\liminf_{n\rightarrow\infty}\frac{2}{n^{2}}\log\widetilde{\mathbb{P}}_{n,r_{n}}(\widetilde{U})\geq-\inf_{\widetilde{h}\in\widetilde{U}}J_{r}(\widetilde{h}).\end{split}$
(1.11)

This theorem was proved by Dhara and Sen [7, Proposition 3.1] under the
condition that there exists an $\eta>0$ such that $\eta\leq r(x,y)\leq 1-\eta$
and $\eta\leq r_{n,ij}(x,y)\leq 1-\eta$ for all $(x,y)\in[0,1]^{2}$,
$n\in\mathbb{N}$ and $i\neq j$. The novelty in this paper lies in weakening
the conditions and showing that $J_{r}=J^{\prime}_{r}$.

The proof of the lower bound requires only minor adjustments of the proof in
[4]. Therefore, we only prove the upper bound in this paper. For a detailed
proof of the lower bound, we refer to [10, Section 6]. Throughout the rest of
the paper, we implicitly assume that (1.5) and (1.6) hold and no longer
mention it in the statement of our results.

###  1.4 Large deviations for the largest eigenvalue

Let $\lambda_{n}$ be the largest eigenvalue of the adjacency matrix of
$G_{n}$. Then $\frac{\lambda_{n}}{n}$ also satisfies an LDP. Chakrabarty et
al. [2] studied the rate function $\psi_{r}$ under the conditions that $r$ is
bounded away from 0 and 1 and of rank 1, i.e. $r(x,y)=\nu(x)\nu(y)$ for some
$\nu\colon[0,1]\to[0,1]$. They analysed the scaling of the rate function and
identified the form of the minimisers near the rate function’s minimum and
near the boundaries 0 and 1.

The requirement that $r$ is bounded away from 0 and 1 stems in part from the
fact that the results from [2] are obtained using the LDP by Dhara and Sen
[7]. They posed the question whether the boundedness condition could be
weakened to some form of integrability condition. In this paper, we show that
the condition can partially be relaxed to (1.5). In particular, we extend
their analysis of the rate function near its minimum.

From the LDP for inhomogeneous ERRGs, Chakrabarty et al. [2] derive the
following LDP for the largest eigenvalue. Note that for this theorem, we do
not yet require $r$ to be of rank 1.

######  Theorem 1.2.

Let $\mathbb{P}^{*}_{n}$ denote the law of $\lambda_{n}/n$. Subject to (1.5)
and (1.6), the sequence $(\mathbb{P}^{*}_{n})_{n}\in\mathbb{N}$ satisfies the
LDP on $\mathbb{R}$ with rate $n^{2}/2$ and with rate function

$\begin{split}\psi_{r}(\beta)=\inf_{\begin{subarray}{c}\widetilde{h}\in\widetilde{\mathcal{W}}\\\
\|T_{h}\|=\beta\end{subarray}}J_{r}(\widetilde{h})=\inf_{\begin{subarray}{c}h\in\mathcal{W}\\\
\|T_{h}\|=\beta\end{subarray}}I_{r}(h),\quad\beta\in\mathbb{R},\end{split}$
(1.12)

with $T_{h}$ the operator on $L^{2}([0,1]^{2})$ defined as

$\begin{split}T_{h}(u)(x)=\int_{[0,1]}h(x,y)u(y)\,dy\end{split}$ (1.13)

for $h\in\mathcal{W}$, $u\in L^{2}([0,1]^{2})$ and $x\in[0,1]$, and where
$\|T_{h}\|$ is the operator norm of $T_{h}$ with respect to the $L^{2}$-norm
on $L^{2}([0,1]^{2})$.

###### Proof.

The proof is standard and follows from Theorem 1.1, combined with the
observation that $\lambda_{n}/n=\|T_{h^{G^{n}}}\|$. See [2, Theorem 1.4]. ∎

Note that Chakrabarty et al. [2] already use the rate function $J_{r}$, so
their result is already an application of the results from this paper.

Put $C_{r}=\|T_{r}\|$. Then Chakrabarty et al. [2] show that the rate function
$\psi_{r}$ is continuous and unimodal on $[0,1]$, with a unique zero at
$C_{r}$, and that it is strictly decreasing and strictly increasing on
$[0,C_{r}]$ and $[C_{r},1]$ respectively. Furthermore, for every
$\beta\in[0,1]$, the set of minimisers of the variational formula for
$\psi_{r}(\beta)$ in (1.12) is non-empty and compact in
$\widetilde{\mathcal{W}}$. For $\beta\not\in[0,1]$, $\psi_{r}(\beta)=+\infty$.
These results do not require boundedness away from 0 and 1 of the reference
graphon.

One of the main results by Chakrabarty et al. [2] is the scaling of the rate
function and the minimisers near $\beta=C_{r}$ under the condition that $r$ is
bounded away from 0 and 1. We generalize it to the following theorem, which we
prove in Section 4.

######  Theorem 1.3.

Assume there exists $\nu\colon[0,1]\to[0,1]$ such that $r(x,y)=\nu(x)\nu(y)$.
Then, subject to (1.5),

$\psi_{r}(\beta)=(1+o(1))K_{r}(\beta-C_{r})^{2},\quad\beta\rightarrow C_{r},$
(1.14)

with

$K_{r}=\frac{C_{r}^{2}}{2B_{r}},$ (1.15)

where

$B_{r}=\int_{[0,1]^{2}}r(x,y)^{3}(1-r(x,y))\,dx\,dy.$ (1.16)

Furthermore, let $h_{\beta}\in\mathcal{W}$ be any minimiser of the second
infimum in (1.12). Then

$\lim_{\beta\rightarrow C_{r}}(\beta-C_{r})^{-1}\|h_{\beta}-r-(\beta-
C_{r})\Delta\|_{L^{2}}=0,$ (1.17)

with

$\Delta=\frac{C_{r}}{B_{r}}r^{2}(1-r).$ (1.18)

###  1.5 Discussion

#### Conditions on the reference graphon.

In [1], Borgs et al. proved an LDP for a block model in which the reference
graphon consists of rational-length blocks. This result was later strengthened
to include blocks of arbitrary length by Grebík and Pikhurko [8]. In their
model, the reference graphon may take on the values 0 or 1. It would be
interesting to generalise both LDPs to a single LDP for graphons that are
partly block graphons (that can attain the values 0 and 1), and partly satisfy
the integrability condition of this paper. Since the condition $\log
r,\log(1-r)\in L^{1}([0,1]^{2})$ pervades almost every step of the proof of
Theorem 1.1, it appears to be difficult to obtain an LDP for _arbitrary_
reference graphons. It might be the case that the inhomogeneous ERRG model
does not satisfy an LDP for certain reference graphons.

#### Non-dense random graphs.

Graph limit theory provides the right framework for studying sequences of
dense graphs, since non-dense graphs converge to the zero graphon. A similar
framework for non-dense graphs is still in development, so not much is known
yet for large deviations of non-dense random graphs. We refer to the
bibliographical notes in [4, Chapter 6] and [3, Section 3] for a short review
of recent results in sparse graph limit theory and sparse large deviations.
Although this paper also considers dense random graphs, the reference graphon
is allowed to approach 0. Such reference graphons can induce dense random
graphs with non-dense subgraphs. This is in contrast to the setting of Dhara
and Sen [7], where every subgraph is also dense.

#### Rate function for the LDP for block models.

Like Dhara and Sen [7], Borgs et al. [1] use a lower semi-continuous envelope
as their rate function. The rate function from this paper can also be used in
[1]. The authors also derive an LDP for homomorphism densities and define a
symmetric and symmetry breaking regime. The existence of a symmetry breaking
regime is only established for specific block models, in part due to the
intractable nature of the rate function. The precise boundary between the
symmetric and non-symmetric regimes was also only identified for bipartite
ERRGs, again due to the intractability of the rate function. The results from
this paper might aid in resolving the general cases.

#### Acknowledgements

This work was initiated as a Bachelor thesis at Leiden University under the
supervision of Frank den Hollander [10]. The author thanks him for his
continued guidance and support the past year. The author is very grateful for
the many mathematical discussions, as well as his thorough feedback on the
thesis and help with this paper.

The author also thanks an anonymous referee for their careful review.

##  2 The rate function

We show that the candidate rate function is a good rate function, i.e., does
not equal infinity everywhere and has compact level sets. Since the first
requirement is clear and $\widetilde{\mathcal{W}}$ is compact, it suffices to
show that $J_{r}$ is lower semi-continuous. First, we need to check that
$J_{r}$ is well-defined on the quotient space $\widetilde{\mathcal{W}}$. As a
consequence of lower semi-continuity, we prove that $J_{r}$ equals the rate
function $J^{\prime}_{r}$ as defined by Dhara and Sen [7] (see (1.9)).

######  Lemma 2.1.

The function $I_{r}$ is continuous in the $L^{2}$-topology on $\mathcal{W}$.

###### Proof.

Let $(f_{n})_{n\in\mathbb{N}}\subset\mathcal{W}$ and $f\in\mathcal{W}$ such
that $(f_{n})_{n\in\mathbb{N}}$ converges to $f$ in $L^{2}([0,1]^{2})$. Note
that for all $h\in\mathcal{W}$,

$\begin{split}\left|\mathcal{R}(h(x,y)\mid r(x,y))\right|\leq&|h(x,y)\log
h(x,y)|+|h(x,y)\log r(x,y)|\\\
&+|(1-h(x,y))\log(1-h(x,y))|+|(1-h(x,y))\log(1-r(x,y))|\\\
\leq&\frac{2}{e}+|\log r(x,y)|+|\log(1-r(x,y))|\end{split}$ (2.1)

for all $(x,y)\in[0,1]^{2}$, where we use that $x\mapsto x\log x$ has a
minimum $-\frac{1}{e}$ on $[0,1]$. Because $\log r,\log(1-r)\in
L^{1}([0,1]^{2})$, the bound above is integrable.

Let $(n_{k})_{k\in\mathbb{N}}$ be a sequence of integers tending to infinity.
Since $f_{n}\rightarrow f$ as $n\rightarrow\infty$ in $L^{2}([0,1]^{2})$,
there exists a subsequence $(n_{k_{l}})_{l\in\mathbb{N}}$ such that
$f_{n_{k_{l}}}\rightarrow f$ as $l\rightarrow\infty$ Lebesgue-almost
everywhere. By continuity, $\mathcal{R}(f_{n_{k_{l}}}(x,y)\mid
r(x,y))\rightarrow\mathcal{R}(f(x,y)\mid r(x,y))$ Lebesgue-almost everywhere.
By the dominated convergence theorem, using the bound from (2.1), we have
$I_{r}(f_{n_{k_{l}}})\rightarrow I_{r}(f)$ as $l\rightarrow\infty$. Thus, for
every sequence $(n_{k})_{k\in\mathbb{N}}$ there exists a subsequence
$(n_{k_{l}})_{l\in\mathbb{N}}$ such that $I_{r}(f_{n_{k_{l}}})\rightarrow
I_{r}(f)$ as $l\rightarrow\infty$. Hence, $I_{r}(f_{n})\rightarrow I_{r}(f)$
as $n\rightarrow\infty$. ∎

######  Lemma 2.2.

Let $f,g\in\mathcal{W}$ be such that $\delta_{\square}(f,g)=0$. Then
$\inf_{\phi\in\mathcal{M}}I_{r}(f^{\phi})=\inf_{\phi\in\mathcal{M}}I_{r}(g^{\phi})$.

###### Proof.

Note that by [9, Corollary 8.14], $\delta_{\square}(f,g)=0$ if and only if
there exists a sequence $(\phi_{n})_{n\in\mathbb{N}}\subset\mathcal{M}$ such
that $\|f^{\phi_{n}}-g\|_{L^{2}}\rightarrow 0$ as $n\rightarrow\infty$. Since
$\|h_{1}^{\phi}-h_{2}^{\phi}\|_{L^{2}}=\|h_{1}-h_{2}\|_{L^{2}}$ for all
$h_{1},h_{2}\in\mathcal{W}$ and $\phi\in\mathcal{M}$, we find that
$\|(f^{\phi_{n}})^{\phi}-g^{\phi}\|_{L^{2}}\rightarrow 0$ for all
$\phi\in\mathcal{M}$. Thus, by Lemma 2.1,
$I_{r}((f^{\phi_{n}})^{\phi})\rightarrow I_{r}(g^{\phi})$ as
$n\rightarrow\infty$. Because this holds for all $\phi\in\mathcal{M}$, we
obtain

$\begin{split}\inf_{\phi\in\mathcal{M}}I_{r}(g^{\phi})&=\inf_{\phi\in\mathcal{M}}\lim_{n\rightarrow\infty}I_{r}((f^{\phi_{n}})^{\phi})\geq\inf_{\phi\in\mathcal{M}}I_{r}(f^{\phi}).\end{split}$
(2.2)

By symmetry, the reverse inequality also holds. ∎

By Lemma 2.2, $J_{r}$ can also be expressed as

$J_{r}(\widetilde{f})=\inf_{g\in B(\widetilde{f},0)}I_{r}(g),$ (2.3)

so

$J_{r}^{\prime}(\widetilde{f})=\sup_{\eta>0}\inf_{g\in
B(\widetilde{f},\eta)}I_{r}(g)=\sup_{\eta>0}\inf_{\widetilde{g}\in\widetilde{B}(\widetilde{f},\eta)}J_{r}(\widetilde{g}).$
(2.4)

Since $J_{r}\geq J_{r}^{\prime}$, we have $J_{r}=J_{r}^{\prime}$ if $J_{r}$ is
lower semi-continuous on $\widetilde{\mathcal{W}}$.

######  Theorem 2.3.

Subject to (1.5) and (1.6), the function $J_{r}$ is lower semi-continuous on
$\widetilde{\mathcal{W}}$.

###### Proof.

Let $\widetilde{f}\in\widetilde{\mathcal{W}}$ and
$(\widetilde{f}_{n})_{n\in\mathbb{N}}\subset\widetilde{\mathcal{W}}$ such that
$\widetilde{f}_{n}\rightarrow\widetilde{f}$ in $\delta_{\square}$. Without
loss of generality, we may assume that $f_{n}\rightarrow f$ in $d_{\square}$.
Let $\Delta_{n}:=f_{n}-f\in\mathcal{W}_{1}:=\\{f-g\mid f,g\in\mathcal{W}\\}$.
Then $\Delta_{n}\rightarrow 0$ in $d_{\square}$ and by an easy computation,

$I_{r}(f^{\phi}+\Delta_{n}^{\phi})=I_{p}(f^{\phi}+\Delta^{\phi}_{n})+I_{r}(f^{\phi})-I_{p}(f^{\phi})+\int_{[0,1]^{2}}\Delta^{\phi}_{n}(x,y)\log\left(\frac{1-r(x,y)}{r(x,y)}\frac{p}{1-p}\right)\,dx\,dy$
(2.5)

for every $n\in\mathbb{N}$, $\phi\in\mathcal{M}$ and $p\in(0,1)$. Thus,

$\begin{split}&\liminf_{n\rightarrow\infty}J_{r}(\widetilde{f}_{n})=\liminf_{n\rightarrow\infty}J_{r}(\widetilde{f+\Delta}_{n})=\liminf_{n\rightarrow\infty}\inf_{\phi\in\mathcal{M}}I_{r}(f^{\phi}+\Delta_{n}^{\phi})\\\
=&\liminf_{n\rightarrow\infty}\inf_{\phi\in\mathcal{M}}\Bigg{(}I_{p}(f^{\phi}+\Delta_{n}^{\phi})+I_{r}(f^{\phi})-I_{p}(f^{\phi})\\\
&\left.+\int_{[0,1]^{2}}\Delta_{n}^{\phi}(x,y)\log\left(\frac{1-r(x,y)}{r(x,y)}\frac{p}{1-p}\right)\,dx\,dy\right)\\\
\geq&\liminf_{n\rightarrow\infty}\left(I_{p}(f+\Delta_{n})-I_{p}(f)+J_{r}(\widetilde{f})+\inf_{\phi\in\mathcal{M}}\int_{[0,1]^{2}}\Delta_{n}^{\phi}(x,y)\log\left(\frac{1-r(x,y)}{r(x,y)}\frac{p}{1-p}\right)\,dx\,dy\right)\\\
\geq&J_{r}(\widetilde{f})+\liminf_{n\rightarrow\infty}\inf_{\phi\in\mathcal{M}}\int_{[0,1]^{2}}\Delta_{n}^{\phi}(x,y)\log\left(\frac{1-r(x,y)}{r(x,y)}\frac{p}{1-p}\right)\,dx\,dy\\\
\geq&J_{r}(\widetilde{f})+\liminf_{n\rightarrow\infty}\int_{[0,1]^{2}}\Delta_{n}^{\phi_{n}}(x,y)\log\left(\frac{1-r(x,y)}{r(x,y)}\frac{p}{1-p}\right)\,dx\,dy-\varepsilon=J_{r}(\widetilde{f})-\varepsilon\end{split}$
(2.6)

for some $p\in(0,1)$, arbitrary $\varepsilon>0$ and some sequence
$(\phi_{n})_{n\in\mathbb{N}}\subset\mathcal{M}$. The second inequality follows
from the lower semi-continuity of $I_{p}$ on $\mathcal{W}$. The last
inequality is obtained by noting that $\Delta_{n}^{\phi_{n}}\rightarrow 0$ in
$d_{\square}$ and $\log r,\log(1-r)\in L^{1}([0,1]^{2})$ and applying [9,
Lemma 8.22]. Because $\varepsilon>0$ is arbitrary, the proof is complete. ∎

######  Corollary 2.4.

For all $\widetilde{f}\in\mathcal{W}$,
$J_{r}(\widetilde{f})=J_{r}^{\prime}(\widetilde{f})$.

##  3 The upper bound

The proof of the upper bound is an adaptation of the proof by Dhara and Sen
[7, Proposition 3.1]. It suffices to prove the following result.

######  Theorem 3.1.

Let $\varepsilon>0$ and $\widetilde{f}\in\widetilde{\mathcal{W}}$. Then there
exists an $\eta(\varepsilon)>0$ such that, for all
$\eta\in(0,\eta(\varepsilon))$,

$\limsup_{n\rightarrow\infty}\log\widetilde{\mathbb{P}}_{n,r_{n}}(\widetilde{B}(\widetilde{f},\eta))\leq-\inf_{g\in
B(\widetilde{f},4\varepsilon)}I_{r}(g)+\varepsilon,$ (3.1)

with
$\widetilde{B}(\widetilde{f},\eta)=\\{\widetilde{g}\in\widetilde{\mathcal{W}}\mid\delta_{\square}(\widetilde{f},\widetilde{g})\leq\eta\\}$
and
$B(\widetilde{f},4\varepsilon)=\\{g\in\mathcal{W}\mid\delta_{\square}(\widetilde{f},\widetilde{g})\leq
4\varepsilon\\}$.

The proof is done via the level-$n$ approximants
$(\overline{r}_{n})_{n\in\mathbb{N}}$ of $r$, which are of the form (1.4),
with

$\overline{r}_{n,ij}:=n^{2}\int_{B(i,j,n)}r(x,y)\,dx\,dy.$ (3.2)

Dhara and Sen show that the distributions
$\frac{1}{n^{2}}\log\mathbb{P}_{n,r_{n}}$ are well-approximated by
$\frac{1}{n^{2}}\mathbb{P}_{n,\overline{r}_{k}}$ for $n$ large enough and some
fixed $k$ and that the rate function $I_{r}$ is well-approximated by
$I_{\overline{r}_{k}}$ for $k$ large enough. In the case that $r$ is bounded
away from 0 and 1, Dhara and Sen use Lipschitz continuity of the logarithm on
a closed interval. If $r$ tends to 0, $\log\mathbb{P}_{n,r_{n}}$ and
$\log\mathbb{P}_{n,\overline{r}_{k}}$ might differ by large amounts as
$n\rightarrow\infty$. Thus, we require more control over the approximation in
this paper. We obtain this by precisely counting the points in the unit square
where $\log r_{n}$ and $\log\overline{r}_{k}$ are far apart and showing that
this area tends to 0 sufficiently fast. The proof is given in Section 3.2. In
Section 3.1, we show that the rate function induced by the level-$n$
approximants approximates the rate function induced by $r$ well. In Section
3.3, we finish the proof of Theorem 3.1. This part of the proof does not
require $r$ to be bounded away from 0 and 1. Hence, this section does not
contain any original content, but we still include it for the sake of
completeness.

###  3.1 Block graphon approximants

By [4, Proposition 2.6], the level-$n$ approximants converge to $r$ in
$L^{1}$-norm, and convergence almost everywhere follows from the Lebesgue
differentiation theorem for sets of bounded eccentricity [11, Chapter 3,
Corollary 1.7]. The following lemma shows that the level-$n$ approximants
satisfy (1.6). The second lemma is a generalization of [7, Lemma 2.3].

######  Lemma 3.2.

$\|\log\overline{r}_{n}-\log r\|_{L^{1}}\rightarrow 0$ and
$\|\log(1-\overline{r}_{n})-\log(1-r)\|_{L^{1}}\rightarrow 0$ as
$n\rightarrow\infty$.

###### Proof.

First, note that, for $(x,y)\in B(i,j,n)$,

$\begin{split}|\log\overline{r}_{n}(x,y)|=&-\log
n^{2}\int_{B(i,j,n)}r(u,v)\,du\,dv\leq n^{2}\int_{B(i,j,n)}-\log
r(u,v)\,du\,dv.\end{split}$ (3.3)

The equality follows from the fact that $0\leq r\leq 1$, and the inequality
follows from Jensen’s inequality. This upper bound is integrable, since

$\begin{split}\sum_{1\leq i,j\leq n}n^{2}\int_{B(i,j,n)}-\log
r(u,v)\,du\,dv=\|\log r\|_{L^{1}}<\infty.\end{split}$ (3.4)

By the dominated convergence theorem and the fact that $\overline{r}_{n}$
converges to $r$ almost everywhere, $\|\log\overline{r}_{n}-\log
r\|_{L^{1}}\rightarrow 0$. The proof that
$\|\log(1-\overline{r}_{n})-\log(1-r)\|_{L^{1}}\rightarrow 0$ is completely
analogous. ∎

######  Lemma 3.3.

Let $r\in\mathcal{W}$ and $(r_{n})_{n\in\mathbb{N}}\subset\mathcal{W}$ that
satisfy (1.5) and (1.6). Then $I_{r_{n}}(\widetilde{f})\rightarrow
I_{r}(\widetilde{f})$ uniformly over $f\in\mathcal{W}$ as
$n\rightarrow\infty$.

###### Proof.

First note that $\|\log r_{n}-\log r\|_{L^{1}}\rightarrow 0$ and
$\|\log(1-r_{n})-\log(1-r)\|_{L^{1}}\rightarrow 0$ by Lemma 3.2. Furthermore,
for all $f\in\mathcal{W}$,

$\begin{split}|I_{r_{n}}(f)-I_{r}(f)|&=\left|\int_{[0,1]^{2}}\left(f(x,y)\log\frac{r_{n}(x,y)}{r(x,y)}+(1-f(x,y))\log\frac{1-r_{n}(x,y)}{1-r(x,y)}\right)\,dx\,dy\right|\\\
&\leq\|\log r_{n}-\log
r\|_{L^{1}}+\|\log(1-r_{n})-\log(1-r)\|_{L^{1}}.\end{split}$ (3.5)

Hence, by the definition of the rate function on $\widetilde{\mathcal{W}}$,

$\begin{split}\left|J_{r_{n}}(\widetilde{f})-J_{r}(\widetilde{f})\right|&=\left|\inf_{\phi\in\mathcal{M}}I_{r_{n}}(f^{\phi})-\inf_{\phi\in\mathcal{M}}I_{r}(f^{\phi})\right|\leq\sup_{\phi\in\mathcal{M}}\left|I_{r_{n}}(f^{\phi})-I_{r}(f^{\phi})\right|\\\
&\leq\|\log r_{n}-\log
r\|_{L^{1}}+\|\log(1-r_{n})-\log(1-r)\|_{L^{1}}.\end{split}$ (3.6)

Since the bound is uniform over all $\widetilde{f}\in\widetilde{\mathcal{W}}$,
we obtain the desired result. ∎

###  3.2 Approximation by a fixed block graphon

The following lemma is a generalization of [7, Lemma 3.2].

######  Lemma 3.4.

Let $r\in\mathcal{W}$ and $(r_{n})_{n\in\mathbb{N}}\subset\mathcal{W}$ that
satisfy (1.5) and (1.6). For all $\varepsilon>0$ sufficiently small there
exist $N_{0}=N_{0}(\varepsilon)$ and $N_{1}=N_{1}(\varepsilon)$ such that for
all $n\geq N_{1}\geq k\geq N_{0}$, $f\in\mathcal{W}$ and $\eta>0$,

$\left|\frac{1}{n^{2}}\log\mathbb{P}_{n,r_{n}}(B(\widetilde{f},\eta))-\frac{1}{n^{2}}\log\mathbb{P}_{n,\overline{r}_{k}}(B(\widetilde{f},\eta))\right|<\varepsilon,$
(3.7)

where $\overline{r}_{k}$ is the level-$k$ approximant of $r$ as defined in
Section 3.1.

###### Proof.

Let $\varepsilon>0$. Since $\|\log r_{n}-\log
r\|_{L^{1}},\|\log\overline{r}_{n}-\log r\|_{L^{1}}\rightarrow 0$ and
$\|\log(1-r_{n})-\log(1-r)\|_{L^{1}},\|\log(1-\overline{r}_{n})-\log(1-r)\|_{L^{1}}\rightarrow
0$ by Lemma 3.2, there exists an $N_{0}\in\mathbb{N}$ such that $\|\log
r_{n}-\log\overline{r}_{k}\|_{L^{1}}<\varepsilon/4$ and
$\|\log(1-r_{n})-\log(1-\overline{r}_{k})\|_{L^{1}}<\varepsilon/4$ for all
$n\geq k\geq N_{0}$.

Note that

$\begin{split}\mathbb{P}_{n,r_{n}}(B(\widetilde{f},\eta))=\int_{B(\widetilde{f},\eta)}\exp\left(\log\frac{d\mathbb{P}_{n,r_{n}}}{d\mathbb{P}_{n,\overline{r}_{k}}}\right)\,d\mathbb{P}_{n,\overline{r}_{k}}.\end{split}$
(3.8)

Fix $n\geq k\geq N_{0}$, and let $g\in\mathcal{W}$ be of the form (1.4).
Denote by $r_{n,uv}$ and $g_{uv}$ the values of $r_{n}$ and $g$ in $B(u,v,n)$
respectively. Then

$\begin{split}&\frac{1}{n^{2}}\left|\log\frac{d\mathbb{P}_{n,r_{n}}}{d\mathbb{P}_{n,\overline{r}_{k}}}(g)\right|=\frac{1}{n^{2}}\left|\sum_{1\leq
i\leq j\leq k}\sum_{\begin{subarray}{c}u<v\\\
\left(\frac{u-1}{n},\frac{v-1}{n}\right)\in
B(i,j,k)\end{subarray}}\left(g_{uv}\log\frac{r_{n,uv}}{\overline{r}_{k,ij}}+(1-g_{uv})\log\frac{1-r_{n,uv}}{1-\overline{r}_{k,ij}}\right)\right|\\\
\leq&\frac{1}{n^{2}}\sum_{1\leq i\leq j\leq k}\sum_{\begin{subarray}{c}u<v\\\
\left(\frac{u-1}{n},\frac{v-1}{n}\right)\in
B(i,j,k)\end{subarray}}\left(\left|\log\frac{r_{n,uv}}{\overline{r}_{k,ij}}\right|+\left|\log\frac{1-r_{n,uv}}{1-\overline{r}_{k,ij}}\right|\right)\\\
\leq&\frac{1}{n^{2}}\sum_{1\leq i,j\leq k}\sum_{\begin{subarray}{c}1\leq
u,v\leq n\\\ \left(\frac{u-1}{n},\frac{v-1}{n}\right)\in
B(i,j,k)\end{subarray}}\left(\left|\log\frac{r_{n,uv}}{\overline{r}_{k,ij}}\right|+\left|\log\frac{1-r_{n,uv}}{1-\overline{r}_{k,ij}}\right|\right)\end{split}$
(3.9)

The quantity above closely resembles $\|\log
r_{n}-\log\overline{r}_{k}\|_{L^{1}}+\|\log(1-r_{n})-\log(1-\overline{r}_{k})\|_{L^{1}}$,
except that it ‘over-counts’ part of $[0,1]^{2}$ and ignores other parts. We
will make this precise.

For points $(\frac{u-1}{n},\frac{v-1}{n})\in[0,1]^{2}$ such that
$B(u,v,n)\subset B(i,j,k)$ for $i,j$ with
$\left(\frac{u-1}{n},\frac{v-1}{n}\right)\in B(i,j,k)$, we have

$\begin{split}\frac{1}{n^{2}}\left|\log\frac{r_{n,uv}}{\overline{r}_{k,ij}}\right|=\|\log
r_{n}-\log\overline{r}_{k}\|_{L^{1}(B(u,v,n))}.\end{split}$ (3.10)

Now define

$\begin{split}C_{i,j,k}:=\left\\{(u,v)\in[0,1]^{2}\left|\,\left(\frac{u-1}{n},\frac{v-1}{n}\right)\in
B(i,j,k),\,B(u,v,n)\not\subset B(i,j,k)\right\\}\right.,\end{split}$ (3.11)

and

$\begin{split}A_{n}:=\bigcup_{1\leq i,j\leq k}\bigcup_{(u,v)\in
C_{i,j,k}}(B(u,v,n)\cap B(i,j,k)).\end{split}$ (3.12)

The set $C_{i,j,k}$ consists of the right-most and top-most points in the
square $B(i,j,k)$, and the set $A_{n}$ is the part of $[0,1]^{2}$ which is
over-counted in (3.9). For $(u,v)\in C_{i,j,k}$,

$\begin{split}\frac{1}{n^{2}}\left|\log\frac{r_{n,uv}}{\overline{r}_{k,ij}}\right|=&\frac{1}{n^{2}\lambda(B(u,v,n)\cap
B(i,j,k))}\|\log r_{n}-\log\overline{r}_{k}\|_{L^{1}(B(u,v,n)\cap
B(i,j,k))}\\\ \leq&k^{2}\|\log
r_{n}-\log\overline{r}_{k}\|_{L^{1}(B(u,v,n)\cap B(i,j,k))},\end{split}$
(3.13)

where we use that $\lambda(B(u,v,n)\cap
B(i,j,k))=(\frac{i}{k}-\frac{u-1}{n})(\frac{j}{k}-\frac{v-1}{n})\geq\frac{1}{k^{2}n^{2}}$.
Hence,

$\begin{split}&\frac{1}{n^{2}}\sum_{1\leq i\leq j\leq
k}\sum_{\begin{subarray}{c}u<v\\\ \left(\frac{u-1}{n},\frac{v-1}{n}\right)\in
B(i,j,k)\end{subarray}}\left|\log\frac{r_{n,uv}}{\overline{r}_{k,ij}}\right|\\\
=&\frac{1}{n^{2}}\sum_{1\leq i\leq j\leq k}\sum_{\begin{subarray}{c}u<v\\\
\left(\frac{u-1}{n},\frac{v-1}{n}\right)\not\in
C_{i,j,k}\end{subarray}}\left|\log\frac{r_{n,uv}}{\overline{r}_{k,ij}}\right|+\frac{1}{n^{2}}\sum_{1\leq
i\leq j\leq k}\sum_{\begin{subarray}{c}u<v\\\
\left(\frac{u-1}{n},\frac{v-1}{n}\right)\in
C_{i,j,k}\end{subarray}}\left|\log\frac{r_{n,uv}}{\overline{r}_{k,ij}}\right|\\\
\leq&\|\log r_{n}-\log\overline{r}_{k}\|_{L^{1}([0,1]^{2}\setminus
A_{n})}+k^{2}\|\log r_{n}-\log\overline{r}_{k}\|_{L^{1}(A_{n})}.\end{split}$
(3.14)

Since the second part tends to 0 as $n\rightarrow\infty$, there exists an
$N_{1}=N_{1}(\varepsilon)\geq k$ such that $k^{2}\|\log
r_{n}-\log\overline{r}_{k}\|_{L^{1}(A_{n})}<\varepsilon/4$ for all $n\geq
N_{1}$. The argument for the terms
$\left|\log\frac{1-r_{n,uv}}{1-\overline{r}_{k,ij}}\right|$ is completely
analogous. Then

$\begin{split}\frac{1}{n^{2}}\left|\log\frac{d\mathbb{P}_{n,r_{n}}}{d\mathbb{P}_{n,\overline{r}_{k}}}(g)\right|<\varepsilon\end{split}$
(3.15)

for all $n\geq N_{1}\geq k\geq N_{0}$. Substituting this inequality into
(3.8), we obtain

$\begin{split}\left|\frac{1}{n^{2}}\log\mathbb{P}_{n,r_{n}}(B(\widetilde{f},\eta))-\frac{1}{n^{2}}\log\mathbb{P}_{n,\overline{r}_{k}}(B(\widetilde{f},\eta))\right|<\varepsilon.\end{split}$
(3.16)

∎

###  3.3 Proof of the upper bound

The rest of the proof now follows as in [7]. For the sake of completeness, we
repeat their argument in this section using the notation introduced in this
paper.

Let $\mathcal{M}_{n}$ be the set of permutations of $n$ objects, and let
$G^{\phi_{n}}_{n}$ be the graph obtained by relabelling the vertices of
$G_{n}$ with the permutation $\phi_{n}\in\mathcal{M}_{n}$. The following lemma
shows that there exists a finite subset $\mathcal{T}\subset\mathcal{M}$ such
that, for all $n$ large enough, the distribution of $h^{G_{n}^{\phi_{n}}}$ can
be approximated by $h^{G_{n},\tau}$ for some $\tau\in\mathcal{T}$.

######  Lemma 3.5.

Let $r_{k},f\in\mathcal{W}$ be of the form (1.4) with $k\geq 1$. Then, for any
$\varepsilon>0$, there exists $n_{0}=n_{0}(k,\varepsilon)$ and a finite set
$\mathcal{T}=\mathcal{T}(k,\varepsilon)$ such that for all $n\geq n_{0}$ and
$\phi_{n}\in\mathcal{M}_{n}$, there exists $\tau\in\mathcal{T}$ satisfying

$\mathbb{P}_{n,r_{k}}(d_{\square}(h^{G_{n}^{\phi_{n}}},f)\leq\varepsilon)\leq\mathbb{P}_{n,r_{k}}(d_{\square}(h^{G_{n},\tau},f)\leq
2\varepsilon)$ (3.17)

###### Proof.

See [7, Lemma 3.3] ∎

We are now ready to prove Theorem 3.1.

###### Proof of Theorem 3.1.

Fix $\varepsilon>0$ and $\widetilde{f}\in\widetilde{\mathcal{W}}$. Recall the
setup of Theorem 3.1. Because of Lemma 3.4, it suffices to prove that there
exists an $\eta(\varepsilon)>0$ such that, for all $0<\eta<\eta(\varepsilon)$,

$\limsup_{n\rightarrow\infty}\frac{2}{n^{2}}\log\widetilde{\mathbb{P}}_{n,\overline{r}_{k}}(\widetilde{B}(\widetilde{f},\eta))=\limsup_{n\rightarrow\infty}\frac{2}{n^{2}}\log\mathbb{P}_{n,\overline{r}_{k}}(B(\widetilde{f},\eta))\leq-\inf_{g\in
B(\widetilde{f},4\varepsilon)}I_{r}(g),$ (3.18)

where $k$ is chosen to be sufficiently large according to Lemma 3.4. Next, we
apply a version of Szeméredi’s regularity lemma, as formulated in [4, Theorem
3.1]. This states that, for every $\varepsilon>0$, there exists a finite set
$\mathcal{W}(\varepsilon)\subset\mathcal{W}$ such that, for every finite
simple graph $G_{n}$ on $n$ vertices, there exist $\phi_{n}\in\mathcal{M}_{n}$
and $h\in\mathcal{W}(\varepsilon)$ such that $h^{G^{\phi_{n}}_{n}}\in
B(h,\varepsilon)$.

Let $G_{n}$ be a graph drawn according to $\mathbb{P}_{n,\overline{r}_{k}}$.
Define

$B(\mathcal{W}(\varepsilon),\varepsilon):=\\{g\in\mathcal{W}\colon\min_{h\in\mathcal{W}(\varepsilon)}d_{\square}(g,h)\leq\varepsilon\\}.$
(3.19)

Then, by the result above,

$\begin{split}\\{h^{G_{n}}\in B(\widetilde{f},\eta)\\}&=\\{h^{G_{n}}\in
B(\widetilde{f},\eta)\\}\bigcap\left(\bigcup_{\phi_{n}\in\mathcal{M}_{n}}\\{h^{G^{\phi_{n}}_{n}}\in
B(\mathcal{W}(\varepsilon),\varepsilon)\\}\right)\\\
&=\bigcup_{h\in\mathcal{W}(\varepsilon)}\bigcup_{\phi_{n}\in\mathcal{M}_{n}}\\{h^{G_{n}}\in
B(\widetilde{f},\varepsilon)\\}\cap\\{h^{G^{\phi_{n}}_{n}}\in
B(h,\varepsilon)\\}.\end{split}$ (3.20)

Since $\mathcal{W}(\varepsilon)$ is a finite set, it suffices to show that

$\limsup_{n\rightarrow\infty}\frac{2}{n^{2}}\log\mathbb{P}_{n,\overline{r}_{k}}\left(\bigcup_{\phi_{n}\in\mathcal{M}_{n}}\\{h^{G_{n}}\in
B(\widetilde{f},\eta)\\}\cap\\{h^{G^{\phi_{n}}_{n}}\in
B(h,\varepsilon)\\}\right)\leq-\inf_{g\in
B(\widetilde{f},4\varepsilon)}I_{r}(g)$ (3.21)

for all $h\in\mathcal{W}(\varepsilon)$ and $\eta<\varepsilon$. Lemma 3.5
yields that the left-hand side of (3.21) is at most

$\begin{split}&\limsup_{n\rightarrow\infty}\frac{2}{n^{2}}\log\mathbb{P}_{n,\overline{r}_{k}}\left(\bigcup_{\phi_{n}\in\mathcal{M}_{n}}\\{h^{G_{n}^{\phi_{n}}}\in
B(h,\varepsilon)\\}\right)\\\
&\leq\limsup_{n\rightarrow\infty}\frac{2}{n^{2}}\max_{\phi_{n}\in\mathcal{M}_{n}}\log
n!\,\mathbb{P}_{n,\overline{r}_{k}}\left(h^{G_{n}^{\phi_{n}}}\in
B(h,\varepsilon)\right)\\\
&\leq\limsup_{n\rightarrow\infty}\frac{2}{n^{2}}\max_{\tau\in\mathcal{T}}\log\mathbb{P}_{n,\overline{r}_{k}}\left(h^{G_{n}^{\phi_{n}}}\in
B(h,2\varepsilon)\right),\end{split}$ (3.22)

where we use that $|\mathcal{M}_{n}|=n!$ and $\log n!=o(n^{2})$. Since
$\mathcal{T}$ is a finite set, it is enough to show that for each
$\tau\in\mathcal{T}$,

$\begin{split}\limsup_{n\rightarrow\infty}\frac{2}{n^{2}}\log\mathbb{P}^{\prime}_{n,\overline{r}_{k}}\left(h^{G_{n},\tau}\in
B(h,2\varepsilon)\right)&=\limsup_{n\rightarrow\infty}\frac{2}{n^{2}}\log\mathbb{P}_{n,\overline{r}_{k}}\left(h^{G_{n}}\in
B(h^{\tau^{-1}},2\varepsilon)\right)\\\ &\leq-\inf_{g\in
B(\widetilde{f},4\varepsilon)}I_{r}(g).\end{split}$ (3.23)

By [4, Lemma 5.4], $B(h_{\tau^{-1}},2\varepsilon)$ is closed in the weak
topology. Hence, we can apply the LDP upper bound in the weak topology, stated
in [4, Theorem 5.1]. Although that the upper bound in the weak topology was
proved only for the homogeneous ERRG, the argument generalises to the
inhomogeneous ERRG model from this paper. We refer to [10, Section 4] for more
detail. Thus,

$\begin{split}\limsup_{n\rightarrow\infty}\frac{2}{n^{2}}\log\mathbb{P}^{\prime}_{n,\overline{r}_{k}}\left(h^{G_{n}}\in
B(h^{\tau^{-1}},2\varepsilon)\right)\leq-\inf_{g\in
B(h^{\tau^{-1}},2\varepsilon)}I_{\overline{r}_{k}}(g)\leq-\inf_{g\in
B(\widetilde{h},2\varepsilon)}I_{\overline{r}_{k}}(g).\end{split}$ (3.24)

If the event in (3.21) is empty, then the bound is trivial. In order for the
event to be non-empty, we must have that
$d_{\square}(\widetilde{h^{G_{n}}},\widetilde{f})\leq\eta<\varepsilon$ and
$d_{\square}(\widetilde{h^{G_{n}}},\widetilde{h})\leq\varepsilon$, so that
$d_{\square}(\widetilde{f},\widetilde{h})\leq 2\varepsilon$. Hence,
$B(\widetilde{h},2\varepsilon)\subset B(\widetilde{f},4\varepsilon)$ and we
obtain (3.21). The proof is finished by letting $k\rightarrow\infty$ and
applying Lemma 3.3. ∎

##  4 The rate function for the largest eigenvalue

We sketch the proof of Theorem 1.3 as given by Chakrabarty et al. [2]. We only
give details for the Lemmas 4.1 and 4.2, which are generalizations of results
in [2].

Note that when $\beta=C_{r}$, the infimum in (1.12) is attained at $h=r$ and
$\psi_{r}(C_{r})=0$. Take $\beta=C_{r}+\varepsilon$ with $\varepsilon>0$
small, and assume that the infimum is attained by a graphon of the form
$h=r+\Delta_{\varepsilon}$, where
$\Delta_{\varepsilon}\colon[0,1]^{2}\to\mathbb{R}$ represents a perturbation
of the graphon $r$.

The proof of Theorem 1.3 consists of showing that it suffices to consider
$\Delta_{\varepsilon}$ of the form $\varepsilon\Delta$, identifying the
optimal $\Delta$ and calculating $\psi_{r}$. Chakrabarty et al. [2] first
prove that $I_{r}(r+\Delta_{\varepsilon})\geq 2\varepsilon^{2}$ for any
perturbation $\Delta_{\varepsilon}$. The following lemma is an adaptation of
[2, Lemma 3.1 and Lemma 3.2] and shows that $I_{r}(r+\Delta_{\varepsilon})$ is
of order $\varepsilon^{2}$ in the case
$\Delta_{\varepsilon}=\varepsilon\Delta$.

######  Lemma 4.1.

If $\Delta_{\varepsilon}=\varepsilon^{\alpha}\Delta$ on some measurable set
$B\subset[0,1]^{2}$, with $\varepsilon,\alpha>0$ and
$\Delta\colon[0,1]^{2}\to\mathbb{R}$, then the contribution of $B$ to the cost
$I_{r}(r+\Delta_{\varepsilon})$ is

$\int_{B}\mathcal{R}(r(x,y)+\varepsilon^{\alpha}\Delta(x,y)\mid
r(x,y))=(1+o(1))\frac{1}{2}\varepsilon^{2\alpha}\int_{[0,1]^{2}}\frac{\Delta^{2}}{r(1-r)}.$
(4.1)

###### Proof.

Because $\chi(a):=\mathcal{R}(a\mid b)$ is analytic for every $a\in[0,1]$ and
$b\in(0,1)$, we have

$\begin{split}\int_{B}\mathcal{R}(r(x,y)+\varepsilon^{\alpha}\Delta(x,y)\mid
r(x,y))=&\int_{B}\sum_{n=0}^{\infty}\frac{1}{n!}\chi^{(n)}(r)\varepsilon^{\alpha
n}\Delta^{n}=\sum_{n=0}^{\infty}\frac{\varepsilon^{\alpha
n}}{n!}\int_{B}\chi^{(n)}(r)\Delta^{n},\end{split}$ (4.2)

where we can swap the integral and sum due to the fact that
$\int_{[0,1]^{2}}|\mathcal{R}(f(x,y)\mid r(x,y))|\,dx\,dy$ is uniformly
bounded over all $f\in\mathcal{W}$, since $\log r,\log(1-r)\in
L^{1}([0,1]^{2})$. Furthermore, $\chi(b)=\chi^{\prime}(b)=0$ and
$\chi^{\prime\prime}(b)=\frac{1}{b(1-b)}$. Hence,

$\begin{split}\int_{B}\mathcal{R}(r(x,y)+\varepsilon^{\alpha}\Delta(x,y)\mid
r(x,y))=&\frac{1}{2}\varepsilon^{2\alpha}\int_{B}\frac{\Delta^{2}}{r(1-r)}+O(\varepsilon^{3\alpha})=(1+o(1))\frac{1}{2}\varepsilon^{2\alpha}\int_{B}\frac{\Delta^{2}}{r(1-r)}.\end{split}$
(4.3)

∎

From the proof of Lemma 4.1 and [2, Lemma 3.1], it follows that optimal
perturbations with $\Delta_{\varepsilon}$ must satisfy
$\|\Delta_{\varepsilon}\|_{L^{2}}\asymp\varepsilon$, and hence it is desirable
to have $\Delta_{\varepsilon}=\varepsilon\Delta$. Chakrabarty et al. [2] argue
through block graphon approximants that this is indeed the case. For this
argument, we need the following lemma, which shows that block graphons
approximate the rate function well.

######  Lemma 4.2.

Let $\overline{r}_{n}$ and $\overline{f}_{n}$ be the level-$n$ approximants of
$r$ and $f\in\mathcal{W}$, as defined in Section 3.1. Then
$\lim_{n\rightarrow\infty}I_{\overline{r}_{n}}(\overline{f}_{n})=I_{r}(f)$.

###### Proof.

Let $\varepsilon>0$. By Lemma 3.3, $I_{r_{N}}(f)\rightarrow I_{r}(f)$
uniformly over all $f\in\mathcal{W}$. Hence, there exists
$M_{1}=M_{1}(\varepsilon)$ such that for all $N\geq M_{1}$,
$|I_{r_{N}}(f_{N})-I_{r}(f_{N})|<\varepsilon/2$. Furthermore,
$f_{N}\rightarrow f$ in $L^{2}$ and $I_{r}$ is continuous in the
$L^{2}$-topology in $\mathcal{W}$ by Lemma 2.1. Thus, there exists
$M_{2}=M_{2}(\varepsilon)$ such that $|I_{r}(f_{N})-I_{r}(f)|<\varepsilon/2$
for all $N\geq M_{2}$. Choosing $M:=\max\\{M_{1},M_{2}\\}$ completes the
proof. ∎

The remainder of the proof now follows as in [2]. We give a brief summary.
Using Lemma 4.1 and exploiting the property that $r$ is of rank 1, Chakrabarty
et al. [2] show that, in the case $\Delta_{\varepsilon}=\varepsilon\Delta$,

$\psi_{r}(C_{r}+\varepsilon)=(1+o(1))K_{r}\varepsilon^{2},$ (4.4)

with

$K_{r}=\inf_{\begin{subarray}{c}\Delta\colon[0,1]^{2}\to\mathbb{R}\\\
\int_{[0,1]^{2}}r\Delta=C_{r}\end{subarray}}\int_{[0,1]^{2}}\frac{\Delta^{2}}{2r(1-r)}.$
(4.5)

Note that the integral in the expression above may be infinite, so the infimum
is minimized for some $\Delta$ that counteracts the expression
$\frac{1}{r(1-r)}$. Using Lagrange multipliers, we obtain that the infimum is
minimized for

$\Delta=\frac{C_{r}}{B_{r}}r^{2}(1-r)$ (4.6)

and

$K_{r}=\frac{C_{r}^{2}}{2B_{r}},$ (4.7)

with $B_{r}$ as defined in (1.16). Chakrabarty et al. [2] conclude the proof
by showing that perturbations $\Delta_{\varepsilon}$ that are not of the form
$\Delta_{\varepsilon}=\varepsilon\Delta$ are asymptotically worse as
$\varepsilon\rightarrow 0$. They do this via block graphons, and use Lemma
4.2.

## References

  * [1] C. Borgs, J. Chayes, J. Gaudio, S. Petti, and S. Sen.  A large deviation principle for block models.  2020\.  arXiv:2007.14508.
  * [2] A. Chakrabarty, R.S. Hazra, F. den Hollander, and M. Sfragara.  Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs.  2020\.  arXiv:2008.08367.
  * [3] S. Chatterjee.  An introduction to large deviations for random graphs.  Bull. Am. Math. Soc., 53(4):617–642, 2016.
  * [4] S. Chatterjee.  Large Deviations for Random Graphs.  Springer International Publishing, 1st edition, 2017.
  * [5] S. Chatterjee and P. Diaconis.  Estimating and understanding exponential random graph models.  Ann. Statist., 41(5):2428–2461, 2013.
  * [6] S. Chatterjee and S.R.S. Varadhan.  The large deviation principle for the Erdős-Rényi random graph.  Eur. J. Comb., 32(7):1000–1017, 2011.  Homomorphisms and Limits.
  * [7] S. Dhara and S. Sen.  Large deviation for uniform graphs with given degrees.  2020\.  arXiv:1904.07666.
  * [8] J. Grebík and O. Pikhurko.  Large deviation principles for block and step graphon random graph models.  2021\.  arXiv:2101.07025.
  * [9] L. Lovász.  Large Networks and Graph Limits.  American Mathematical Society, 1st edition, 2012.
  * [10] M.J.R. Markering.  The large deviation principle for inhomogeneous Erdős-Rényi random graphs.  Bachelor thesis, Leiden University, May 2020.
  * [11] E.M. Stein and R. Shakarchi.  Real Analysis: Measure Theory, Integration & Hilbert Spaces.  Princeton Lectures in Analysis, III. Princeton University Press, 2005\.