A Note on Hamiltonian Cycles in Digraphs with Large Degrees

Samvel Kh. Darbinyan

Institute for Informatics and Automation Problems of NAS RA

E-mail<EMAIL_ADDRESS>
Abstract

In this note we prove: Let $D$ be a 2-strong digraph of order $n$ such that
its $n-1$ vertices have degrees at least $n+k$ and the remaining vertex $z$
has degree at least $n-k-4$, where $k$ is a positive integer. If $D$ contains
a cycle of length at least $n-k-2$ passing through $z$, then $D$ is
Hamiltonian.

Keywords: Digraphs, Hamiltonian cycles, degree, 2-strong.

##  1 Introduction

In this paper, we consider finite digraphs (directed graphs) without loops and
multiple arcs. The order of a digraph $D$ is the number of its vertices. We
shall assume that the reader is familiar with the standard terminology on
digraphs. Terminology and notations not described below follow [1]. Every
cycle and path is assumed to be simple and directed. A cycle (path) in a
digraph $D$ is called Hamiltonian (Hamiltonian path) if it includes every
vertex of $D$. A digraph $D$ is Hamiltonian if it contains a Hamiltonian
cycle.

There are numerous sufficient conditions for the existence of a Hamiltonian
cycle in a digraph (see, [1], [2], [3]). The following two sufficient
conditions on the existence of Hamiltonian cycles in digraphs are classical
and famous.

Theorem 1: (Ghouila-Houri [4]). Let $D$ be a strong digraph of order $n\geq
2$. If for every vertex $x\in V(D)$, $d(x)\geq n$, then $D$ is Hamiltonian.

Theorem 2: (Meyniel [5]). Let $D$ be a strong digraph of order $n\geq 2$. If
$d(x)+d(y)\geq 2n-1$ for all pairs of non-adjacent vertices $x$ and $y$ in
$D$, then $D$ is Hamiltonian.

Nash-Williams [6] raised the problem of describing all the extreme digraphs
for Ghouila -Houri’s theorem the strong non-Hamiltonian digraphs of order $n$
and with minimum degree $n-1$. As a solution to this problem, Thomassen [7]
proved a structural theorem on the extremal digraphs. An analogous problem for
the Meyniel theorem (Theorem 2) was considered by the author [8], proving a
structural theorem on the strong non-Hamiltonian digraphs $D$ of order $n$,
with the degree condition that $d(x)+d(y)\geq 2n-2$ for every pair of non-
adjacent distinct vertices $x,y$. This improves the corresponding structural
theorem of Thomassen. Moreover, in [8], it was also proved that if $m$ is the
length of a longest cycle in $D$, then $D$ contains cycles of all lengths
$k=2,3,\ldots,m$.

Goldberg, Levitskaya and Satanovskyi [9] relaxed the conditions of the
Ghouila-Houri theorem. They proved the following theorem.

Theorem 3: (Goldberg et al. [9]). Let $D$ be a strong digraph of order $n\geq
2$. If $n-1$ vertices of $D$ have degrees at least $n$ and the remaining
vertex has degree at least $n-1$, then $D$ is Hamiltonian.

Note that Theorem 3 is the best possible in the sense that for every $n$,
there is a non-Hamiltonian strong digraphs of order $n$ such that its $n-2$
(or $n-1$) vertices have degrees equal to $n+1$ (respectively, $n$) and the
other two remaining vertices (respectively, the remaining vertex) have degrees
equal to $n-1$ (respectively, has degree equal to $n-2$).

It is worth to mention that, Thomassen [7] constructed a strong non-
Hamiltonian digraph of order $n$ with only two vertices of degree $n-1$ and
all other vertices have degree not less than $(3n-5)/2$.

In [10], it was reported that the following theorem holds.

Theorem 4: (Darbinyan [10]). Let $D$ be a 2-strong digraph of order $n\geq 9$
with minimum degree at least $n-4$. If $n-1$ vertices of $D$ have degrees at
least $n$, then $D$ is Hamiltonian.

The proof of the last theorem has never been published. In [11], we presented
the first part of the proof of Theorem 4, by proving the following theorem.

Theorem 5: (Darbinyan [11]). Let $D$ be a 2-strong digraph of order $n$.
Suppose that $n-1$ vertices of $D$ have degrees at least $n$ and the remaining
vertex $z$ has degree at least $n-4$. If $D$ contains a cycle of length $n-2$
through $z$, then $D$ is Hamiltonian.

In [11], we also proposed the following conjecture.

Conjecture 1: Let $D$ be a 2-strong digraph of order $n$ such that its $n-1$
verteices have degrees at least $n+k$ and the remaining vertex $z$ has degree
at least $n-k-4$, where $k$ is a non-negative integer. Then $D$ is
Hamiltonian.

Let us note that Conjecture 1 is an extention Ghouila-Houri’s theorem for
2-strong digraphs and is a generalization of Theorem 4. The truth of
Conjecture 1 in the case $k=0$ follows from Theorem 4. Resently, we settled
Conjecture 1 for any $k\geq 0$. Our goal in this note to present the first
part of the proof of Conjecture 1 for any $k\geq 1$, which we formulate as
Theorem 6.

Theorem 6: Let $D$ be a 2-strong digraph of order $n\geq 3$ such that its
$n-1$ verteices have degrees at least $n+k$ and the remaining vertex $z$ has
degree at least $n-k-4$, where $k\geq 0$ is an integer. If $D$ has a cycle of
length at least $n-k-2$ through $z$, then $D$ is Hamiltonian.

The second part of the proof (i.e., the complete proof) of Conjecture 1 for
any $k\geq 0$ (in particular, the second part of the proof of Theorem 4) we
will present in the forthcoming paper.

##  2  Further Terminology and Notation

For the sake of clarity we repeat the most impotent definition. The vertex set
and the arc set of a digraph $D$ are denoted by $V(D)$ and $A(D)$,
respectively. The arc of a digraph $D$ directed from $x$ to $y$ is denoted by
$xy$ or $x\rightarrow y$ (we also say that $x$ dominates $y$ or $y$ is an out-
neighbour of $x$ and $x$ is an in-neighbour of $y$), and $x\leftrightarrow y$
denotes that $x\rightarrow y$ and $y\rightarrow x$ ($x\leftrightarrow y$ is
called 2-cycle). If $x\rightarrow y$ and $y\rightarrow z$, we write
$x\rightarrow y\rightarrow z$. Let $A$ and $B$ be two disjoint subsets in
$V(D)$. The notation $A\rightarrow B$ means that every vertex of $A$ dominates
every vertex of $B$. We define $A(A\rightarrow B)=\\{xy\in A(D)\,|\,x\in
A,y\in B\\}$. If $x\in V(D)$ and $A=\\{x\\}$ we sometimes write $x$ instead of
$\\{x\\}$. Let $N_{D}^{+}(x)$, $N_{D}^{-}(x)$ denote the set of out-neighbors,
respectively the set of in-neighbors of a vertex $x$ in a digraph $D$. If
$A\subseteq V(D)$, then $N_{D}^{+}(x,A)=A\cap N_{D}^{+}(x)$ and
$N_{D}^{-}(x,A)=A\cap N_{D}^{-}(x)$. The out-degree of $x$ is
$d_{D}^{+}(x)=|N_{D}^{+}(x)|$ and $d_{D}^{-}(x)=|N_{D}^{-}(x)|$ is the in-
degree of $x$. Similarly, $d_{D}^{+}(x,A)=|N_{D}^{+}(x,A)|$ and
$d_{D}^{-}(x,A)=|N_{D}^{-}(x,A)|$. The degree of the vertex $x$ in $D$ is
defined as $d_{D}(x)=d_{D}^{+}(x)+d_{D}^{-}(x)$ (similarly,
$d_{D}(x,A)=d_{D}^{+}(x,A)+d_{D}^{-}(x,A)$). We omit the subscript if the
digraph is clear from the context. The subdigraph of $D$ induced by a subset
$A$ of $V(D)$ is denoted by $D\langle A\rangle$. In particular, $D-A=D\langle
V(D)\setminus A\rangle$. For integers $a$ and $b$, $a\leq b$, by $[a,b]$ we
denote the set $\\{x_{a},x_{a+1},\ldots,x_{b}\\}$. If $j<i$, then
$\\{x_{i},x_{i+1},\ldots,x_{j}\\}=\emptyset$. A path is a digraph with vertex
set $\\{x_{1},x_{2},\ldots,x_{k}\\}$ and arc set
$\\{x_{1}x_{2},x_{2}x_{3},\ldots,x_{k-1}x_{k}\\}$, and is denoted by
$x_{1}x_{2}\cdots x_{k}$. This is also called an $(x_{1},x_{k})$-path or a
path from $x_{1}$ and $x_{k}$. If we add the arc $x_{k}x_{1}$ to the path
above, we obtain a cycle $x_{1}x_{2}\ldots x_{k}x_{1}$. The length of a cycle
or a path is the number of its arcs. If $P$ is a path containing a subpath
from $x$ to $y$, we let $P[x,y]$ denote that subpath. Similarly, if $C$ is a
cycle containing vertices $x$ and $y$, $C[x,y]$ denotes the subpath of $C$
from $x$ to $y$, and an $(x,y)$-path $P$ is a $C$-bypass (or is an
$(x,y)$-bypass) if $|V(P)|\geq 3$ and $V(P)\cap V(C)=\\{x,y\\}$. Let $D$ be a
digraph and $z\in V(D)$. By $C_{m}(z)$ (respectively, $C(z)$) we denote a
cycle in $D$ of length $m$ (respectively, any cycle in $D$), which contains
the vertex $z$. Similarly, we denote by $C_{k}$ a cycle of length $k$. A
digraph $D$ is strong (strongly connected) if, for every pair $x,y$ of
distinct vertices in $D$, there exists an $(x,y)$-path and a $(y,x)$-path. A
digraph $D$ is $k$-strong ($k$-strongly connected) if, $|V(D)|\geq k+1$ and
for any set $A$ of at most $k-1$ vertices $D-A$ is strong. Two distinct
vertices $x$ and $y$ are adjacent if $xy\in$ or $yx\in V(D)$ (or both). The
converse digraph of $D$ is the digraph obtained from $D$ by reversing the
direction of all arcs in $D$. We will use the principle of digraph duality:
Let $D$ be a digraph, then $D$ has a subdigraph $H$ if and only if the
converse digraph of $D$ has the converse of the subdigraph $H$.

##  3 Preliminaries

In our proofs, we will use the following well-known simple lemmas.

Lemma 1: (Häggkvist and Thomassen [12]). Let $D$ be a digraph of order $n\geq
3$ containing a cycle $C_{m}$ of length $m$, $m\in[2,n-1]$. Let $x$ be a
vertex not contained in this cycle. If $d(x,V(C_{m}))\geq m+1$, then for every
$k\in[2,m+1]$, $D$ contains a cycle $C_{k}$ of length $k$ including $x$.

The next lemma is a slight modification of the lemma by Bondy and Thomassen
[13], it is very useful and will be used extensively throughout this paper.

Lemma 2:. Let $D$ be a digraph of order $n\geq 3$ containing a path
$P:=x_{1}x_{2}\ldots x_{m}$, $m\in[2,n-1]$. Let $x$ be a vertex not contained
in this path. If one of the following condition holds:

(i) $d(x,V(P))\geq m+2$,

(ii) $d(x,V(P))\geq m+1$ and $xx_{1}\notin A(D)$ or $x_{m}x\notin A(D)$,

(iii) $d(x,V(P))\geq m$ and $xx_{1}\notin A(D)$ and $x_{m}x\notin A(D)$,

then there is an $i\in[1,m-1]$ such that $x_{i}\rightarrow x\rightarrow
x_{i+1}$, i.e., $D$ contains a path $x_{1}x_{2}\ldots x_{i}xx_{i+1}\ldots
x_{m}$ of length $m$ (we say that $x$ can be inserted into $P$).

In [14], the author proved the following theorem.

Theorem 7: (Darbinyan [14]). Let $D$ be a strong digraph of order $n\geq 3$.
Suppouse that $d(x)+d(y)\geq 2n-1$ for all pairs of non-adjacent vertices
$x,y\in V(D)\setminus\\{z\\}$, where $z$ is an arbitrary vertex in $V(D)$.
Then $D$ is Hamiltonian or contains a cycle of length $n-1$.

Using Theorem 7 and Lemma 1, it is not difficult to show that the following
corollary is true.

Corollary 1: Let $D$ be a strong digraph of order $n\geq 3$. Suppose that
$n-1$ vertices of $D$ have degrees at least $n$. Then $D$ is Hamiltonian or
contains a cycle of length $n-1$ (in fact, $D$ has a cycle that contains all
the vertices of degrees at least $n$).

By the same arguments as the proof Lemma 4 in [11], we can prove the following
lemma.

Lemma 3: Let $D$ be a digraph of order $n\geq 4$. Suppose that $n-1$ vertices
of $D$ have degrees at least $n$ and the remaining vertex $z$ has degree at
most $n-2$. If $D$ contains a cycle $C_{m}(z)=x_{1}x_{2}\ldots x_{m}x_{1}$
that has an $(x_{i},x_{j})$-bypass such that $z\notin
V(C_{m}(z)[x_{i+1},x_{j-1}])$, then $D$ contains a $C(z)$-cycle of length at
least $m+1$.

## The main result

Our proofs are based on the arguments of [11]. We frist will prove the
following lemma.

Lemma 4: Let $D$ be a non-Hamiltonian 2-strong digraph of order $n$ such that
its $n-1$ vertices have degrees at least $n+1$ and the remaining vertex $z$
has degree at most $n-2$. Suppose that $C_{m+1}(z)=x_{1}x_{2}\ldots
x_{m}zx_{1}$ with $m\in[2,n-3]$ is a longest cycle through $z$ in $D$, and
$Y:=V(D)\setminus V(C_{m+1}(z))$ has two distinct mutually reachable vertices
$y_{1}$ and $y_{2}$ such that for each $y_{i}\in\\{y_{1},y_{2}\\}$,
$d(y_{i},\\{x_{1},x_{2},\ldots,x_{m}\\})=m+1$. Then $n\geq 7$ and $d(z)\leq
m-2$.

Proof: By contradiction, suppose that $d(z)\geq m-1$. We denote by $P$ the
path $x_{1}x_{2}\ldots x_{m}$. It is clear that $|Y|=n-m-1$. Since
$C_{m+1}(z)$ is a longest cycle, it follows that every vertex $y\in Y$ cannot
be inserted into $C_{m+1}(z)$. Then by Lemma 1, $d(y,V(C_{m+1}(z)))\leq m+1$
and

$n+1\leq d(y)=d(y,V(C_{m+1}(z)))+d(y,Y)\leq m+1+d(y,Y).$

Hence, $d(y,Y)\geq n-m=|Y|+1$. Therefore by Ghoula-Houri’s theorem, $D\langle
Y\rangle$ contains a Hamiltonian path. Let $H_{1}$, $H_{2},\cdots,H_{f}$ be
the strong components of $D\langle Y\rangle$ labelled in such way that no
vertex of $H_{i}$ dominates a vertex of $H_{j}$ whenever $i>j$. Since
$D\langle Y\rangle$ has a Hamiltonian path, it follows that for each
$i\in[1,f-1]$ thete is an arc from $H_{i}$ to $H_{i+1}$. From
$d(y,Y)\geq|Y|+1$ we obtain that if $u\in V(H_{i})$, then
$d(u,V(H_{i}))\geq|V(H_{i})|+1$. Therefore, $|V(H_{i})|\geq 3$ and by Ghoula-
Houri’s theorem every subdigraph $H_{i}$ is Hamiltonian. Observe that for some
$s\in[1,f]$, the vertices $y_{1}$ and $y_{2}$ are in $V(H_{s})$ since in
$D\langle Y\rangle$ the vertices $y_{1}$ and $y_{2}$ are mutually reachable.
Notice that if $|V(H_{i})|=3$, then $H_{i}$ is a complete digraph and if
$|V(H_{i})|=4$, then is a semicomplete digraph.

Since $D$ is 2-strong and $C_{m+1}(z)$ is a longest cycle, using Lemma 2 and
the fact that $d(y_{i},V(P))=m+1$ it is not difficult to show that there is an
integer $l\in[2,m-1]$ such that

$\\{x_{l},x_{l+1},\ldots,x_{m}\\}\rightarrow\\{y_{1},y_{2}\\}\rightarrow\\{x_{1},x_{2},\ldots,x_{l}\\}.$
$None$

Put $E:=\\{x_{1},x_{2},\ldots,x_{l-1}\\}$ and
$F:=\\{x_{l+1},x_{l+2},\ldots,x_{m}\\}$. Note that $|E|\geq 1$ and $|F|\geq
1$. Since $C_{m+1}(z)$ is a longest cycle, from (1) it follows that

$A(\\{z\\}\cup
E\rightarrow\sum_{i=1}^{s}V(H_{i}))=A(\sum_{i=s}^{f}V(H_{i})\rightarrow\\{z\\}\cup
F)=\emptyset,$ $None$

in particular, $d(z,V(H_{s}))=0$. Note that from $|Y|\geq 3$, $|E|\geq 1$ and
$|F|\geq 1$ it follows that $n\geq 7$. If $u,v\in Y$, then we use $L(u,v)$ to
denote a $(u,v)$-path in $D\langle Y\rangle$. We need to prove Claims 1-2
bellow.

Claim 1.

(i) If $d^{-}(z,E)\geq 1$, then $d^{+}(z,F)=0$. (ii) $A(E\rightarrow
F)\not=\emptyset$.

Proof. (i) By contradiction, suppose that $x_{i}\in E$, $x_{j}\in F$ and
$x_{i}\rightarrow z\rightarrow x_{j}$. Then by (1), $y_{1}\rightarrow x_{i+1}$
and $x_{j-1}\rightarrow y_{2}$. Hence, $C_{m+3}(z)=x_{1}x_{2}\ldots
x_{i}zx_{j}\ldots x_{m}y_{1}x_{i+1}\ldots x_{j-1}y_{2}x_{1}$, a contradiction.

(ii) Suppose, on the contrary, that $A(E\rightarrow F)=\emptyset$. Let us
consider the subdigraph $D-x_{l}$. Then by (2), we have: if $d^{-}(z,E)=0$,
then

$A(E\cup\sum_{i=s}^{f}V(H_{i}))\rightarrow\\{z\\}\cup
F\cup\sum_{i=1}^{s-1}V(H_{i}))=\emptyset,$

and if $d^{-}(z,E)\geq 1$, then $d^{+}(z,F)=0$ (Claim 1(i)) and

$A(\\{z\\}\cup E\cup\sum_{i=s}^{f}V(H_{i})\rightarrow
F\cup\sum_{i=1}^{s-1}V(H_{i}))=\emptyset.$

Thus, we have that, in both cases, $D-x_{l}$ is not strong, which contradicts
that $D$ is 2-strong.

From now on, we assume that $x_{a}x_{b}\in A(E\rightarrow F)$. Note that by
(1), we have

$x_{b-1}\rightarrow\\{y_{1},y_{2}\\}\rightarrow x_{a+1}.$ $None$

From Claim 1(i) it follows that either $x_{a}z\notin A(D)$ or $zx_{b}\notin
A(D)$. Therefore, since $z$ cannot be inserted into $P$, using Lemma 2(ii), we
obtain

$d(z,\\{x_{1},x_{2},\ldots,x_{a}\\})+d(z,\\{x_{b},x_{b+1},\ldots,x_{m}\\})\leq
a+m-b+2.$ $None$

We denote by $R$ a longest path between $y_{1}$ and $y_{2}$ in $D\langle
Y\rangle$. It is clear that $|V(R)|\geq 3$ since $H_{s}$ is Hamiltonian and
$|V(H_{s})|\geq 3$. Using (3), $|V(R)|\geq 3$ and the fact that $C_{m+1}(z)$
is a longest cycle, it is not difficult to check that the following claim is
true.

Claim 2.

(i) If $i\in[a+1,l-1]$, then $x_{i}z\notin A(D)$.

(ii) If $j\in[l+1,b-1]$, then $zx_{j}\notin A(D)$.

(iii) If $i\in[a+1,l]$ and $i-a\leq 3$, then $zx_{i}\notin A(D)$.

(iv) If $j\in[l,b-1]$ and $b-j\leq 3$, then $x_{j}z\notin A(D)$.

Now we will consider the following cases depending on the values of $a$ and
$b$ with respect to $l$.

Case 1. $a\leq l-3$ and $b\geq l+2$.

Then by Claim 2, $d(z,\\{x_{a+1},x_{a+2},x_{b-1}\\})=0$ and $x_{b-2}z\notin
A(D)$. Therefore, since $z$ cannot be inserted into $P$, using (4) and Lemma
2, we obtain

$m-1\leq
d(z,V(P))=d(z,\\{x_{1},x_{2},\ldots,x_{a},x_{b},x_{b+1},\ldots,x_{m}\\})$
$+d(z,\\{x_{a+3},x_{a+4},\ldots,x_{b-2}\\})\leq a+m-b+2+b-2-a-2=m-2,$

which is a contradiction.

Case 2. $a\leq l-3$ and $b=l+1$.

Then by Claim 2, $d(z,\\{x_{a+1},x_{a+2}\\})=0$, $x_{b-1}z\notin A(D)$ and
$zx_{a+3}\notin A(D)$. Again using (4) and Lemma 2, we obtain

$m-1\leq
d(z,\\{x_{1},x_{2},\ldots,x_{a},x_{b},x_{b+1},\ldots,x_{m}\\})+d(z,\\{x_{a+3},x_{a+4},\ldots,x_{b-1}\\})$
$\leq a+m-b+2+b-1-a-3=m-b+l-1=m-2,$

which is a contradiction.

Before consider the Caseses 3 and 4, we claim that if $m\geq b+1=l+2$ and
$d(z,\\{x_{l}\\})=0$, then

$A(\\{x_{1},x_{2},\ldots,x_{l}\\}\rightarrow\\{x_{l+2},x_{l+3},\ldots,x_{m}\\})\not=\emptyset.$
$None$

Asume that this is not the case. Then, since $D-x_{l+1}$ is strong, it follows
that in $D-x_{l+1}$ there is a path from a vertex of
$\\{x_{1},x_{2},\ldots,x_{l}\\}$ to a vertex of
$\\{x_{l+2},x_{l+3},\ldots,x_{m}\\}$. Let $Q$ be such a shortes path. Using
Claim 1(i), (2) and the above assumption, it is not difficult to show that $Q$
is an $(x_{l},x_{j})$-path, where
$x_{j}\in\\{x_{l+2},x_{l+3},\ldots,x_{m}\\}$, whose internal vertices are in
$\sum_{i=1}^{s-1}V(H_{i})$ or in $\\{z\\}\cup\sum_{i=1}^{s-1}V(H_{i})$. This
means that $C_{m+1}(z)$ contains an $(x_{l},x_{j})$\- or $(x_{l},z)$-bypass
such that $z\notin V(C_{m+1}(z)[x_{l+1},x_{j-1}])$ or $z\notin
V(C_{m+1}(z)[x_{l+1},x_{m}])$, respectively. Therefore by Lemma 3, $D$
contains a $C(z)$-cycle of length at least $m+2$, which contradicts the
supposition of Lemma 4 that $C_{m+1}(z)$ is a longest cycle in $D$. Thus, (5)
is true.

Case 3. $a=l-2$.

Taking into account the Cases 1 and 2, we may assume that $b\leq l+2$. Using
Claim 2 and (4), it is not difficult to show that $b=l+1$. Then by Claim 2,
$d(z,\\{x_{l-1},x_{l}\\})=0$, which together with (4) implies that
$d(z,V(P))=m-1$. Taking into account the considered cases, we may assume that

$A(\\{x_{1},x_{2},\ldots,x_{a}\\}\rightarrow\\{x_{b+1},x_{b+2},\ldots,x_{m}\\})=\emptyset.$
$None$

Subcase 3.1. $m\geq b+1=l+2$.

If $x_{i}\rightarrow x_{j}$, with $i\in[l-1,l]$ and $j\in[l+2,m]$, then the
cycle $C(z)=x_{1}x_{2}\ldots x_{a}x_{b}\ldots\\\ x_{j-1}Rx_{i}x_{j}\ldots
x_{m}zx_{1}$ has length greater than $m+2$, a contradiction. Therefore, we may
assume that
$A(\\{x_{l-1},x_{l}\\}\rightarrow\\{x_{l+2},x_{l+3},\ldots,x_{m}\\})=\emptyset$.
This together with (6) implies that

$A(\\{x_{1},x_{2},\ldots,x_{l}\\}\rightarrow\\{x_{l+2},x_{l+3},\ldots,x_{m}\\})=\emptyset,$

a contradiction to (5).

Subcase 3.2. $b=l+1=m$.

Assume first that $a\geq 2$. Taking into account the considered Case 2, we may
assume that $d^{-}(x_{m},\\{x_{1},x_{2},\ldots,x_{a-1}\\})=0$. It is not
difficult to see that
$A(\\{x_{1},x_{2},\ldots,x_{a-1}\\}\rightarrow\\{x_{a+1},x_{a+2}\\})=\emptyset$.
Indeed, if $x_{i}x_{j}\in A(D)$ with $i\in[1,a-1]$ and $j\in[a+1,a+2]$, then
$C(z)=x_{1}x_{2}\ldots x_{i}x_{j}x_{a+2}Rx_{i+1}\ldots x_{a}x_{m}zx_{1}$ is a
cycle of length at least $m+3$, a contradiction.

Thus, we may assume that

$A(\\{x_{1},x_{2},\ldots,x_{a-1}\\}\rightarrow\\{x_{a+1},x_{a+2},x_{a+3}=x_{m}\\})=\emptyset.$
$None$

Since $D-x_{a}$ is strong, it follows that in $D-x_{a}$ there is a path from a
vertex $x_{i}\in\\{x_{1},x_{2},\ldots,x_{a-1}\\}$ to a vertex
$x_{j}\in\\{x_{a+1},x_{a+},x_{a+3}=x_{m}\\}$. Let $Q$ be such a shortest path.
Then, using (2) and (7), it is not difficult to see that
$x_{j}\in\\{x_{a+1},x_{a+2}\\}$ and the internal vertices of $Q$ are in
$\sum_{i=s+1}^{f}V(H_{i})$ or in $\\{z\\}\cup\sum_{i=s+1}^{f}V(H_{i})$. This
means that $C_{m+1}(z)$ contains an $(x_{i},x_{j})$\- or $(z,x_{j})$-bypass
such that $z\notin V(C_{m+1}(z)[x_{i+1},x_{j-1}])$ or $z\notin
V(C_{m+1}(z)[x_{1},x_{j-1}])$, respectively. Therefore by Lemma 3, $D$
contains a $C(z)$-cycle of length at least $m+2$, this contradicts that
$C_{m+1}(z)$ is a longest cycle in $D$.

Assume second that $a=1$. Then $m=4$, and either $x_{1}\rightarrow z$ or
$z\rightarrow x_{m}$ since $d(z,V(P))=m-1=3$ and $d(z,\\{x_{2},x_{3}\\})=0$.
Let $x_{1}\rightarrow z$. Then $zx_{4}\notin A(D)$ (Claim 1(i)), and for some
$u\in\sum_{i=s+1}^{f}V(H_{i})$, $z\rightarrow u$ since $d^{+}(z)\geq 2$ and
$d^{+}(z,\\{x_{2},x_{3},x_{4}\\}\cup\sum_{i=1}^{s}V(H_{i}))=0$, in particular,
$f\geq s+1\geq 2$. Since
$A(V(H_{f})\rightarrow\\{x_{4},z\\}\cup\sum_{i=1}^{f-1}V(H_{i}))=\emptyset$,
there are $v\in V(H_{f})$ and $x_{j}$ with $j\in[1,3]$ such that $v\rightarrow
x_{j}$. Then if $j=1$, then $C(z)=x_{1}x_{2}x_{3}x_{4}zL(u,v)x_{1}$ is a cycle
of length at least 6, and if $j\in[2,3]$, then
$C(z)=x_{1}zL(u,v)x_{j}x_{3}x_{4}Rx_{1}$ is a cycle of length at least 8. So,
in both cases we have a cotradiction. Let now $x_{1}z\notin A(D)$. Then
$z\rightarrow x_{4}$ and for some $u\in\cup\sum_{i=1}^{s-1}V(H_{i}))$,
$u\rightarrow z$. If $x_{3}\rightarrow v$ or $x_{4}\rightarrow v$ with $v\in
V(H_{1})$, then $C(z)=x_{3}L(v,u)zx_{4}Rx_{3}$ is a cycle of length at least
7, or $C(z)=x_{4}L(v,u)zx_{1}x_{2}x_{3}x_{4}$ is a cycle of length at least 6.
So, in both cases we have a cotradiction. Therefore,
$A(\\{x_{1},x_{2},x_{3},x_{4},z\\}\cup\sum_{i=2}^{f}V(H_{i})\rightarrow
V(H_{1}))=\emptyset$. This contracdicts that $D$ is 2-strong. The disussion of
Case 3 is completed.

Case 4. $a=l-1$. Taking into account Cases 2-3 and the digraph duality, we may
assume that $b=l+1$ and

$A(\\{x_{1},x_{2},\ldots,x_{l-2}\\}\rightarrow\\{x_{l+1},x_{l+2},\ldots,x_{m}\\})$
$=A(\\{x_{1},x_{2},\ldots,x_{l-1}\\}\rightarrow\\{x_{l+2},x_{l+3},\ldots,x_{m}\\})=\emptyset.$
$None$

Using (3), it is not difficult see that

$d^{-}(x_{l},\\{x_{1},x_{2},\ldots
x_{l-2})\\})=d^{+}(x_{l},\\{x_{l+2},x_{l+3},\ldots,x_{m})\\})=0.$

Indeed, if $x_{i}\rightarrow x_{l}$ with $i\in[1,l-2]$ or $x_{l}\rightarrow
x_{j}$ with $j\in[l+2,m]$, then $C(z)=x_{1}x_{2}\ldots
x_{i}x_{l}y_{1}x_{i+1}\ldots x_{l-1}x_{l+1}\ldots x_{m}zx_{1}$ or
$C(z)=x_{1}x_{2}\ldots x_{l-1}x_{l+1}\ldots x_{j-1}y_{1}x_{l}x_{j}\ldots
x_{m}\\\ zx_{1}$ is a cycle of length $m+2$, respectively. So, in both cases,
we have a contradiction.

The last equalities together with (8) imply that

$A(\\{x_{1},x_{2},\ldots,x_{l}\\}\rightarrow\\{x_{l+2},x_{l+3},\ldots,x_{m}\\})$
$=A(\\{x_{1},x_{2},\ldots,x_{l-2}\\}\rightarrow\\{x_{l},x_{l+1},\ldots,x_{m}\\})=\emptyset.$
$None$

From (5) and (9) it follows that $m=l+1$. By the digraph duality, we may
assume that $a=l-1=1$. Hence, $b=l+1=m=3$. Let $x_{1}\rightarrow z$. Then
$zx_{3}\notin A(D)$ and for some $u\in\sum_{i=s+1}^{f}V(H_{i})$, $z\rightarrow
u$ since $d^{+}(z)\geq 2$ and
$d^{+}(z,\\{x_{2},x_{3}\\}\cup\sum_{i=1}^{s}V(H_{i}))=0$. Hence it is not
difficult to see that $d^{-}(x_{1},V(H_{f}))=0$. This together with
$A(V(H_{f})\rightarrow\\{z,x_{3}\\}\cup\sum_{i=1}^{f-1}V(H_{i}))=\emptyset$
implies that for some $v\in V(H_{f})$, $v\rightarrow x_{2}$. Therefore,
$C(z)=x_{1}zL(u,v)x_{2}x_{3}y_{1}x_{1}$ has length at least $m+2$, a
contradiction. Let now $x_{1}z\notin A(D)$. Then, since $d^{-}(z)\geq 2$ and
$d^{-}(z,\\{x_{1},x_{2}\\}\cup\sum_{i=s}^{f}V(H_{i}))=0$, for some
$w\in\sum_{i=1}^{s-1}V(H_{i})$, $w\rightarrow z$. It is not difficult to see
that $A(\\{x_{1},x_{3},z\\})\rightarrow V(H_{1}))=\emptyset$. This together
with $A(\sum_{i=2}^{f}V(H_{i})\rightarrow V(H_{1}))=\emptyset$ implies that
$D-x_{2}$ is not strong, a contradiction. The discussion of Case 4 is
completed. Lemma 4 is proved.

Now we are ready to prove the main result.

Proof of Theorem 6: Let $C_{m}(z):=x_{1}x_{2}\ldots x_{m}x_{1}$ be a longest
cycle through $z$ and let $Y=V(D)\setminus V(C_{m}(z))$. Note that $m\geq 3$.
Then by the supposition of the theorem, $m\geq n-k-2$. By Theorem 5, we may
assume that $k\geq 1$. Since $C_{m}(z)$ is a longest cycle in $D$, it follows
that any vertex $u\in Y$ cannot be inserted into $C_{m}(z)$. Then by Lemma 1,
$d(u,V(C_{m}(z))\leq m$ and

$n+k\leq d(u)=d(u,V(C_{m}(z)))+d(u,Y)\leq m+2n-2m-2=2n-m-2.$

Hence, $m\leq n-k-2$ (i.e., $m=n-k-2$), $|Y|=k+2\geq 2$, $d(u,Y)=2k+2$ (i.e.,
$D\langle Y\rangle$ is a complete digraph) and $d(u,V(C_{m}(z)))=n-k-2$. If
some vertex of $Y$ is adjacent to every vertex of $C_{m}(z)$, then $D$ is
Hamiltonian. We may therefore assume that there are vertices $y\in Y$ and
$x_{i}$, say $x_{n-k-2}$, which are not adjacent and $D$ is not Hamiltonian.
Then by Lemma 2, it is easy to see that $x_{n-k-3}\rightarrow y\rightarrow
x_{1}$. Using the facts that $D\langle Y\rangle$ is complete and $C_{m}(z)$ is
a longest cycle, it is not difficult to show that $d(x_{n-k-2},Y)=0$,
$x_{n-k-3}\rightarrow Y\rightarrow x_{1}$ and $z=x_{n-k-2}$. Since for every
vertex $u\in Y$, $d(u,V(C_{n-k-2}(z)))=n-k-2$, it follows that $D$ satisfies
the conditions of Lemma 4. Therefore by Lemma 4,
$d(z)=d(z,\\{x_{1},x_{2},\ldots,x_{n-k-3}\\})\leq n-k-5$, which contradicts
that $d(z)\geq n-k-4$. The theorem is proved.

##  4 Conclusion

For Hamiltonicity of a graph $G$ (undirected graph), there are numerous
sufficient conditions in terms of the connectivity number $k(G)$ of $G$, where
$k(G)\geq 3$ (recall that for a graph $G$ to be Hamiltonian, $k(G)\geq 2$ is a
necessary condition) and the minimum degree $\delta(G)$ or the sum of degrees
of some vertices with certain properties. Results on Hamiltonian graphs can be
found in the survey papers by Gould, e.g. [15]. This is not the case for the
general digraphs. Moreover, in [16], the author proved that: For every pair of
integers $k\geq 2$ and $n\geq 4k+1$ (respectively, $n=4k+1$), there exists a
$k$-strong $(n-1)$-regular (respectively, with minimum degree at least $n-1$
and with minimum semi-degrees at least $2k-1=(n-3)/2$) a non-Hamiltonian
digraph of order $n$. Based on the evidence from Theorem 7, we propose the
following problem.

Problem: Let $D$ be a $s$-strong digraph of order $n$, where $s\geq 2$.
Suppose that $n-1$ vertices of $D$ have degrees at least $n+p$ and the
remaining vertex has degree at least $n-q$. For fixed $s$, find the minimum
value of $p$ and the maximum value of $q$ such that $D$ is Hamiltonian.

## References

  * [1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, 2000.
  * [2] J.-C. Bermond and C. Thomassen, “Cycles in digraphs – A survey”, Journal of Graph Theory vol. 5, no. 1, pp. 1-43, 1981.
  * [3] D. Kühn and D. Osthus, “A survey on Hamilton cycles in directed graphs”, European Journal of Combinatorics, vol. 33, pp. 750-766, 2012.
  * [4] A. Ghouila-Houri, “Une condition suffisante d’existence d’un circuit hamiltonien”, Comptes Rendus de I’Academie des Sciences Paris, ser. A-B 251, pp. 495-497, 1960.
  * [5] M. Meyniel, “Une condition suffisante d’existence d’un circuit hamiltonien dans un graphe oriente”, Journal of Combinatorial Theory, Ser. B, vol. 14, pp. 137-147, 1973.
  * [6] C.St.J.A. Nash-Williams, “Hamilton circuits in graphs and digraphs”, The many facets of graph theory, Springer Verlag Lecture Notes 110, (Springer Verlag) pp. 237-243, 1969.
  * [7] C. Thomassen, “Long cycles in digraphs”, Proceedings of London Mathematical Society, vol. 3(42), pp. 231-251, 1981.
  * [8] S.Kh. Darbinyan, “Cycles of any length in digraph with large semi-degrees”, Aakdemy Nauk Armyan SSR Doklady, vol. 75, no. 4, pp. 147-152, 1982 (arXiv.1911.05998v1).
  * [9] M.K. Goldberg, L.P. Levitskaya and L.M. Satanovskyi, “On one strengthening of the Ghouila-Houri theorem”, Vichislitelnaya Matematika i Vichislitelnaya Teknika, vol. 2, pp. 56-61, 1971.
  * [10] S.Kh. Darbinyan, “A sufficient condition for a digraph to be Hamiltonian”, Aakdemy Nauk Armyan SSR Doklady, vol. 91, no. 2, pp. 57-59, 1990.
  * [11] S.Kh. Darbinyan, “ On an Extension of the Ghouila-Houri Theorem” Mathematical Problems of Computer Science, vol.58, pp. 20-31, 2022.
  * [12] R. Häggkvist and C. Thomassen, “On pancyclic digraphs”, Journal of Combinatorial Theory, Ser. B, vol. 20, no. 1, pp. 20-40, 1976.
  * [13] J.A. Bondy and C. Thomassen, “A short proof of Meyniel’s theorem”, Discrete Mathematics, vol. 19, pp. 195-197, 1977.
  * [14] S.Kh. Darbinyan, “Hamiltonian and strongly Hamilton-Connected digraphs”, Aakdemy Nauk Armyan SSR Doklady, vol. 91, no. 1, pp. 3-6, 1990 (arXiv.1801.05166v1).
  * [15] R.J. Gould, “Resent Advances on the Hamiltonian Problem: Survey III”, Graphs and Combinatorics, vol. 30, pp. 1-46, 2014.
  * [16] S.Kh. Darbinyan, “Disproof of a conjecture of Thomassen ”, Aakdemy Nauk Armyan SSR Doklady, vol. 76, no. 2, pp. 51-54, 1983.


# Determination of lower order perturbations of a polyharmonic operator in two
dimensions

Rajat Bansal  Rajat Bansal
Department of Mathematics, Indian Institute of Science Education and Research,
Pune<EMAIL_ADDRESS>,  Venkateswaran P. Krishnan
Venkateswaran P. Krishnan
Centre for Applicable Mathematics, Tata Institute of Fundamental Research,
Bengaluru<EMAIL_ADDRESS>and  Rahul Raju Pattar  Rahul Raju Pattar
Centre for Applicable Mathematics, Tata Institute of Fundamental Research,
Bengaluru<EMAIL_ADDRESS>
###### Abstract.

We study an inverse boundary value problem for a polyharmonic operator in two
dimensions. We show that the Cauchy data uniquely determine all the
anisotropic perturbations of orders at most $m-1$ and several perturbations of
orders $m$ to $2m-2$ under some restriction. The uniqueness proof relies on
the $\bar{\partial}$-techniques and the method of stationary phase.

###### Key words and phrases:

Inverse boundary value problem; Perturbed two-dimensional polyharmonic
operator; Cauchy data; Uniqueness.

###### 2020 Mathematics Subject Classification:

35R30; 35J40

##  1\. Introduction

Let $\Omega$ be a bounded domain with smooth boundary in $\mathbb{R}^{2}$.
This paper aims to study the inverse boundary value problem in two dimensions
for a polyharmonic operator of the form:

$\mathcal{L}=\partial^{m}\bar{\partial}^{m}+\sum_{j,k=0}^{m-1}{A_{j,k}\partial^{j}\bar{\partial}^{k}},\quad
m\geq 2.$ (1.1)

Note that $x=(x_{1},x_{2})\in\Omega\subset\mathbb{R}^{2}$ is identified with
$z=x_{1}+ix_{2}\in\mathbb{C}$ and
$\partial=\frac{1}{2}\left(\partial_{x_{1}}-i\partial_{x_{2}}\right),$
$\bar{\partial}=\frac{1}{2}\left(\partial_{x_{1}}+i\partial_{x_{2}}\right)$.

In this paper we uniquely determine the coefficients $A_{j,k}$ from the set of
Cauchy data

$\mathcal{C}(\mathcal{L})=\left\\{\left(u|_{\partial\Omega},\partial_{\nu}u|_{\partial\Omega},\partial_{\nu}^{2}u|_{\partial\Omega}\ldots,\partial_{\nu}^{(2m-1)}u|_{\partial\Omega}\right):u\in
H^{2m}(\Omega),\mathcal{L}u=0\right\\},$ (1.2)

where $\nu$ is an outer unit normal to $\operatorname{\partial\Omega}$.

To the best of our knowledge, there are few prior works investigating inverse
problems for lower order perturbation of polyharmonic operator (especially for
$m\geq 3$) in two dimensions compared to higher dimensions. For $m=2$, in
[Ike91] Ikehata proved a local uniqueness of a potential $V\in L^{2}(\Omega)$
associated to the Calderón problem for $(\Delta^{2}+V)u=0$ with
$\|V\|_{L^{2}}$ small. In [Ike93], the same author studied a local uniqueness
theorem for the Calderón problem for a perturbed biharmonic operator related
to Love-Kirchhoff plate theory. In [Ike96], the author studied the
relationship between two D-N maps in the linear theory of elasticity in two
dimensions and the linearized Calderon problem for anisotropic fourth order
equation. In [IY15, LUW15], the authors have studied Navier-Stokes equation in
two dimensions using the biharmonic operator.

In dimensions $n\geq 3,$ Krupchyk, Lassas, and Uhlmann [KLU14] established
that the Cauchy data for a polyharmonic operator uniquely determines first
order perturbations. This work was extended by many authors; see, for
instance, [GK16, BG19, BKS21, BG22]. Till now, the perturbations considered
for the polyharmonic operator are of order at most $m$ in $n\geq 3$. Moreover,
in [SS23], the authors considered the linearized Calderón inverse problem for
polyharmonic operator and recovered several lower order coefficients up to
order $2m-1$ in $n\geq 3$.

In this paper, we establish that the Cauchy data for a polyharmonic operator
in two dimensions uniquely determines all anisotropic perturbations of order
at most $m-1$ and several perturbations of orders $m$ to $2m-2$ with some
restrictions. This restriction is captured in the following representation of
the operator $\mathcal{L}$ as

$(\partial\bar{\partial})^{m}+A_{m-1,m-1}(\partial\bar{\partial})^{m-1}+\sum_{l=1}^{m-2}{\left(\sum_{j+k=m-l-1}{A_{j+l,k+l}\partial^{j}\bar{\partial}^{k}}\right)(\partial\bar{\partial})^{l}}+\sum_{l=0}^{m-1}\sum_{j+k=l}{A_{j,k}\partial^{j}\bar{\partial}^{k}}.$

The constraint on the coefficients of orders $m$ to $2m-2$ is required for the
techniques employed in this paper to work, mainly, to make the equation for
the amplitude of complex geometric optics (CGO) solutions to be independent of
the coefficients.

An early study of inverse boundary value problems for second-order operators
was carried out by Calderón [Cal80]. Sylvester and Uhlmann [SU87] obtained the
first uniqueness result for the Calderón problem. In two dimensions, the
Calderón problem was studied by Nachman [Nac96], Brown-Uhlmann [BU97], and
finally Astala–Päivärinta [AP06]. Nachman required two derivatives to convert
the conductivity equation into the Schrödringer equation. The paper of Astala
and Päivärinta solved Calderón’s problem most generally for $L^{\infty}$
conductivity.

Our approach relies on two main techniques - the $\bar{\partial}$-techniques
and the method of stationary phase. These techniques were first used by
Bukhgeim in his seminal work [Buk08] to recover the zeroth order perturbation
of the Laplacian in two dimensions that has led to many developments in the
study of two-dimensional inverse boundary value problems. However, his proof
only gives uniqueness for potentials in the class $W^{1,p}$, $p>2$ as pointed
out in Blåsten’s licentiate thesis [Blå11]. The corresponding partial data
problem was considered by Imanuvilov, Uhlmann and Yamamoto in [IUY10] and
Guillarmou and Tzou in [GT11a]. The inverse problem for magnetic Schrödinger
equation in $n=2$ using Bukhgeim approach was studied by Lai in [Lai11] and
for partial data by Imanuvilov, Uhlmann and Yamamoto in [IUY12] and by Tzou in
[Tzo17]. We refer the interested reader to the survey article [GT13] for a
detailed overview of results and techniques for inverse problems in two
dimensions.

Now we state the main theorem of this paper.

######  Theorem 1.1.

Let $\Omega$ be a bounded domain with smooth boundary in $\mathbb{R}^{2}$. Let
$\mathcal{L}$ and $\tilde{\mathcal{L}}$ be two operators of the form (1.1)
with coefficients $A_{j,k},\tilde{A}_{j,k}\in W^{j+k+1,p}(\Omega),\ p>2$,
respectively. Assume that

$\partial_{\nu}^{l}{A}_{j,k}=\partial_{\nu}^{l}{\tilde{A}}_{j,k}\text{ and
}{A}_{0,k}=\tilde{A}_{0,k}\text{ on }\partial\Omega,\quad\text{ for }0\leq
l\leq j-1,\ 0\leq j,k\leq m-1.$ (1.3)

Then $\mathcal{C}(\mathcal{L})=\mathcal{C}(\tilde{\mathcal{L}})$ implies that
$A_{j,k}=\tilde{A}_{j,k}$ on $\Omega$ for $0\leq j,k\leq m-1.$

We require the condition (1.3) on the coefficients to make the boundary terms
_zero_ when we apply integration by parts on the integral identity and also to
apply the method of stationary phase as explained in Section 3.

Alternatively, one can consider a Cauchy data set of the form

$\mathcal{N}(\mathcal{L})=\left\\{\left(u|_{\partial\Omega},\ldots,(-\Delta)^{m-1}u|_{\partial\Omega},(\partial_{\nu}u)|_{\partial\Omega},\cdots\partial_{\nu}(-\Delta)^{m-1}u|_{\partial\Omega}\right):u\in
H^{2m}(\Omega),\mathcal{L}u=0\right\\},$

as $\mathcal{C}(\mathcal{L})$ can be obtained from $\mathcal{N}(\mathcal{L})$
by an explicit description for the Laplacian in the boundary normal
coordinates, see [LU89]. We have the following corollary.

######  Corollary 1.2.

With the hypothesis as in Theorem 1.1,
$\mathcal{N}(\mathcal{L})=\mathcal{N}(\tilde{\mathcal{L}})$ implies that
$A_{j,k}=\tilde{A}_{j,k}$ on $\Omega$ for $0\leq j,k\leq m-1.$

To prove Theorem 1.1, we need to construct so-called complex geometric optics
(CGO) solutions. The next theorem gives the existence of such solutions in our
setting. Let us fix some notation before stating the theorem. Let
$\Phi=i(z-z_{0})^{2}$ where $z_{0}\in\Omega$ and $dS$ be the surface measure
on $\operatorname{\partial\Omega}$.

######  Theorem 1.3.

Let $a$ be smooth function such that $\bar{\partial}^{m}a=0$ in $\Omega$. If
$A_{j,k}\in W^{j+k+1,p}(\Omega)$, for some $p>2$, then for all small $h>0$
there exist solutions $u\in H^{2m}(\Omega)$ to

$\mathcal{L}u=\partial^{m}\bar{\partial}^{m}u+\sum_{j,k=0}^{m-1}{A_{j,k}\partial^{j}\bar{\partial}^{k}u}=0,\quad\text{
in }\Omega,$ (1.4)

of the form

$u=e^{\Phi/h}(a+r_{h}),$ (1.5)

where the correction term $r_{h}$ satisfies
$\|r_{h}\|_{H^{m}(\Omega)}=O(h^{\frac{1}{2}+\epsilon})$ for some $\epsilon>0$.

##  2\. CGO Solutions

In this section, we prove Theorem 1.3 as stated in Introduction. We begin by
writing

$\mathcal{L}u=\partial^{m}\bar{\partial}^{m}u+\sum_{j,k=0}^{m-1}{A_{j,k}\partial^{j}\bar{\partial}^{k}u}=0$

in the following form

$\mathcal{L}u=\partial^{m}\bar{\partial}^{m}u+\sum_{j,k=0}^{m-1}{\partial^{j}(A_{j,k}^{\prime}\bar{\partial}^{k}u)}=0,$
(2.1)

where we can define $A^{\prime}_{j,k}\in W^{j+k+1,p}(\Omega)$ uniquely
satisfying

$A_{j,k}=\sum_{l=j}^{m-1}{\binom{l}{j}\partial^{l-j}A^{\prime}_{l,k}}.$ (2.2)

Substituting $u=e^{\Phi/h}f$ in (2.1), we have

$\partial^{m}\left(e^{\Phi/h}\bar{\partial}^{m}f\right)+\sum_{j,k=0}^{m-1}{\partial^{j}\left(e^{\Phi/h}A^{\prime}_{j,k}\bar{\partial}^{k}f\right)}=0.$

Now, we write $G=e^{\Phi/h}\bar{\partial}^{m}f$ and the above expression takes
the form

$\displaystyle\begin{split}\bar{\partial}^{m}f&=e^{-\Phi/h}G\\\
\partial^{m}G&=-\sum_{j,k=0}^{m-1}{\partial^{j}\left(e^{\Phi/h}A^{\prime}_{j,k}\bar{\partial}^{k}f\right)}\end{split}$
(2.3)

The problem here is that $|e^{\pm\Phi/h}|$ grows too fast when $h\to 0$. This
can be solved by choosing $G=e^{\bar{\Phi}/h}g$ to get

$\displaystyle\bar{\partial}^{m}f$ $\displaystyle=e^{(\bar{\Phi}-\Phi)/h}g$
(2.4) $\displaystyle\partial^{m}g$
$\displaystyle=-\sum_{j,k=0}^{m-1}{\partial^{j}\left(e^{(\Phi-\bar{\Phi})/h}A^{\prime}_{j,k}\bar{\partial}^{k}f\right)}$
(2.5)

For (2.4), we take the solution

$f=a+\bar{\partial}^{-m}\left(e^{(\bar{\Phi}-\Phi)/h}g\right),\quad\text{
where }\bar{\partial}^{m}a=0$ (2.6)

and for (2.5) we choose the solution

$g=-\sum_{j,k=0}^{m-1}{\partial^{j-m}\left(e^{(\Phi-\bar{\Phi})/h}A^{\prime}_{j,k}\bar{\partial}^{k}f\right)}.$
(2.7)

By combining these two, we get an integral equation for $g$ of the form

$g+\sum_{j,k=0}^{m-1}{\partial^{j-m}\left(e^{(\Phi-\bar{\Phi})/h}A^{\prime}_{j,k}\bar{\partial}^{k-m}\left(e^{(\bar{\Phi}-\Phi)/h}g\right)\right)}=-\sum_{j,k=0}^{m-1}{\partial^{j-m}\left(e^{(\Phi-\bar{\Phi})/h}A^{\prime}_{j,k}\bar{\partial}^{k}a\right)}.$
(2.8)

The above expression for $g$ can be written in the form

$(I-\mathcal{S}_{h})g=w,$ (2.9)

where

$\displaystyle\begin{split}\mathcal{S}_{h}(v)&=-\sum_{j,k=0}^{m-1}{\partial^{j-m}\left(e^{(\Phi-\bar{\Phi})/h}A^{\prime}_{j,k}\bar{\partial}^{k-m}\left(e^{(\bar{\Phi}-\Phi)/h}v\right)\right)}\\\
w&=-\sum_{j,k=0}^{m-1}{\partial^{j-m}\left(e^{(\Phi-\bar{\Phi})/h}A^{\prime}_{j,k}\bar{\partial}^{k}a\right)}.\end{split}$
(2.10)

The existence of a CGO solution of the form (1.5) to the equation (1.4)
depends on the solvability of (2.9). To this end, we estimate the norm of
$\mathcal{S}_{h}$ for which we need the following crucial operator bound from
[GT11b, Lemma 2.3] and [GT13, Lemma 5.4].

######  Lemma 2.1.

Let $q\in(1,\infty)$ and $p>2$, then there exists $C>0$ independent of $h$
such that for all $\omega\in W^{1,p}(\Omega)$

$\displaystyle\|{\partial}^{-1}(e^{(\Phi-\bar{\Phi})/h}\omega)\|_{L^{q}(\Omega)}$
$\displaystyle\leq Ch^{2/3}\|\omega\|_{W^{1,p}(\Omega)}\quad\text{if }1<q<2,$
$\displaystyle\|{\partial}^{-1}(e^{(\Phi-\bar{\Phi})/h}\omega)\|_{L^{q}(\Omega)}$
$\displaystyle\leq Ch^{1/q}\|\omega\|_{W^{1,p}(\Omega)}\quad\text{if }2\leq
q\leq p.$

There exist $\epsilon>0$ and $C>0$ such that for all $\omega\in
W^{1,p}(\Omega)$

$\|{\partial}^{-1}(e^{(\Phi-\bar{\Phi})/h}\omega)\|_{L^{2}(\Omega)}\leq
Ch^{\frac{1}{2}+\epsilon}\|\omega\|_{W^{1,p}(\Omega)}.$

######  Lemma 2.2.

For any $1<r\leq p$, the operator $\mathcal{S}_{h}$ is bounded on
$L^{r}(\Omega)$ and satisfies $\norm{\mathcal{S}_{h}}_{L^{r}\to
L^{r}}=O(h^{1/r})$ for $r>2$ and $\norm{\mathcal{S}_{h}}_{L^{2}\to
L^{2}}=O(h^{\frac{1}{2}-\epsilon})$ for any $0<\epsilon<1/2$ small.

###### Proof.

Firstly, for $2<r\leq p,$ we obtain

$\displaystyle\|S_{h}(v)\|_{L^{r}(\Omega)}$
$\displaystyle\leq\sum_{j,k=0}^{m-1}\norm{\partial^{j-m}\left(e^{(\Phi-\bar{\Phi})/h}A^{\prime}_{j,k}\bar{\partial}^{k-m}\left(e^{(\bar{\Phi}-\Phi)/h}v\right)\right)}_{L^{r}(\Omega)}$
$\displaystyle\leq
C\sum_{j,k=0}^{m-1}\norm{\partial^{j-m+1}\left(e^{(\Phi-\bar{\Phi})/h}A^{\prime}_{j,k}\bar{\partial}^{k-m}\left(e^{(\bar{\Phi}-\Phi)/h}v\right)\right)}_{L^{r}(\Omega)}$
$\displaystyle\leq
C\sum_{j,k=0}^{m-1}\norm{\partial^{-1}\left(e^{(\Phi-\bar{\Phi})/h}A^{\prime}_{j,k}\bar{\partial}^{k-m}\left(e^{(\bar{\Phi}-\Phi)/h}v\right)\right)}_{L^{r}(\Omega)}$
$\displaystyle\leq
Ch^{\frac{1}{r}}\sum_{j,k=0}^{m-1}\norm{A^{\prime}_{j,k}\bar{\partial}^{k-m}\left(e^{(\bar{\Phi}-\Phi)/h}v\right)}_{W^{1,r}(\Omega)}$
$\displaystyle\leq
Ch^{\frac{1}{r}}\sum_{k=0}^{m-1}\norm{\bar{\partial}^{k-m}\left(e^{(\bar{\Phi}-\Phi)/h}v\right)}_{W^{1,r}(\Omega)}$
$\displaystyle\leq Ch^{\frac{1}{r}}\|v\|_{L^{r}(\Omega)}.$

Further, for $1<r<2,$

$\displaystyle\|S_{h}(v)\|_{L^{r}(\Omega)}$
$\displaystyle\leq\sum_{j,k=0}^{m-1}\norm{\partial^{j-m}\left(e^{(\Phi-\bar{\Phi})/h}A^{\prime}_{j,k}\bar{\partial}^{k-m}\left(e^{(\bar{\Phi}-\Phi)/h}v\right)\right)}_{L^{r}(\Omega)}$
$\displaystyle\leq
C\sum_{j,k=0}^{m-1}\norm{\partial^{-1}\left(e^{(\Phi-\bar{\Phi})/h}A^{\prime}_{j,k}\bar{\partial}^{k-m}\left(e^{(\bar{\Phi}-\Phi)/h}v\right)\right)}_{L^{r}(\Omega)}$
$\displaystyle\leq
C\sum_{j,k=0}^{m-1}\norm{A^{\prime}_{j,k}\bar{\partial}^{k-m}\left(e^{(\bar{\Phi}-\Phi)/h}v\right)}_{L^{r}(\Omega)}$
$\displaystyle\leq
C\sum_{k=0}^{m-1}\norm{\bar{\partial}^{k-m}\left(e^{(\bar{\Phi}-\Phi)/h}v\right)}_{L^{r}(\Omega)}$
$\displaystyle\leq C\|v\|_{L^{r}(\Omega)}.$

For all $\varepsilon>0$ small, interpolating between $r=1+\varepsilon$ and
$r=2+\varepsilon$, gives the desired result for $r=2$. ∎

######  Proposition 2.3.

For all sufficiently small $h>0$, there exist a solution $g\in H^{m}(\Omega)$
to the equation

$(I-\mathcal{S}_{h})g=w,$

where $\mathcal{S}_{h}$ and $w$ defined in (2.10) which satisfies
$\|g\|_{L^{2}}=O(h^{\frac{1}{2}+\epsilon})$.

###### Proof.

In view of Lemma 2.2, equation (2.9) can be solved by using Neumann series by
setting (for small $h>0$)

$g=\sum_{j=0}^{\infty}\mathcal{S}_{h}^{j}w.$

as an element of $L^{2}(\Omega)$. Indeed
$\|w\|_{L^{2}(\Omega)}=O(h^{\frac{1}{2}+\epsilon})$ by Lemma 2.1 and
$\norm{\mathrm{S}_{h}}_{L^{2}\rightarrow L^{2}}=O(h^{\frac{1}{2}-\epsilon})$
by Lemma 2.2 we obtain
$\norm{\mathrm{S}_{h}^{j}w}_{L^{2}}=O\left(h^{(\frac{1}{2}-\epsilon)j}h^{\frac{1}{2}+\epsilon}\right)$
which implies $\norm{g}_{L^{2}(\Omega)}=O(h^{\frac{1}{2}+\epsilon})$.

Now that $g\in L^{2}(\Omega)$ and $A^{\prime}_{j,k}\in W^{j+k+1,p}(\Omega)$,
we use bootstrapping argument on the expression (2.8) to conclude that $g\in
H^{m}(\Omega).$ ∎

Proof of Theorem 1.3. Choose $g$ as in Proposition 2.3 and let

$r_{h}=\bar{\partial}^{-m}\left(e^{(\bar{\Phi}-\Phi)/h}g\right)$

as observed in (2.6). Clearly, $r_{h}\in H^{2m}(\Omega)$ and
$\norm{r_{h}}_{H^{m}(\Omega)}=O(h^{\frac{1}{2}+\varepsilon})$. Then we see
that $u=e^{\Phi/h}(a+r_{h})\in H^{2m}(\Omega)$ where $\bar{\partial}^{m}a=0$
solves $\mathcal{L}u=0.$ This proves Theorem 1.3. ∎

The adjoint operator $\mathcal{L}^{*}$ has a similar form as the operator
$\mathcal{L}.$ Hence, by following similar arguments, we can show that the
adjoint equation has the same type of CGO solutions as given in Theorem 1.3.

######  Remark 2.4.

One can define an integral equation for $f$ instead of $g$ by substituting
(2.7) in (2.6) and following the above procedure one can obtain that
$\norm{r_{h}}_{H^{m}(\Omega)}=O(h^{\frac{1}{2}-\varepsilon}).$

######  Remark 2.5.

From the techniques used in the proof of Theorem 1.3 one can even construct
CGO solutions to the equation

$\mathcal{P}u=\mathcal{L}u+\sum_{j=0}^{m-1}{A_{j,m}\partial^{j}\bar{\partial}^{m}u}=\partial^{m}\bar{\partial}^{m}u+\sum_{j,k=0}^{m-1}{A_{j,k}\partial^{j}\bar{\partial}^{k}u}+\sum_{j=0}^{m-1}{A_{j,m}\partial^{j}\bar{\partial}^{m}u}=0$

of the form (1.5). But the difficulty lies in the construction of CGO
solutions to the adjoint $P^{*}$ as the transport equation defining the
amplitude of the CGO solution to $P^{*}v=0$ will depend on the coefficients
$A_{j,m}.$

##  3\. Proof of uniqueness of coefficients

In this section, we prove Theorem 1.1. We start by deriving an integral
identity. Let $u_{1},v\in H^{2m}(\Omega)$ be such that

$\mathcal{L}u_{1}=0,\quad\tilde{\mathcal{L}}^{*}v=0.$ (3.1)

By assuming $\mathcal{C}(\mathcal{L})=\mathcal{C}(\tilde{\mathcal{L}})$ there
exists $u_{2}\in H^{2m}(\Omega)$ satisfying

$\begin{rcases}\begin{aligned} \tilde{\mathcal{L}}u_{2}&=0\\\
u_{2}|_{\operatorname{\partial\Omega}}&=u_{1}|_{\operatorname{\partial\Omega}},\\\
(\partial_{\nu}u_{2})|_{\operatorname{\partial\Omega}}&=(\partial_{\nu}u_{1})|_{\operatorname{\partial\Omega}},\\\
\vdots\quad\quad&\quad\quad\vdots\\\
(\partial_{\nu}^{(2m-1)}u_{2})|_{\operatorname{\partial\Omega}}&=(\partial_{\nu}^{(2m-1)}u_{1})|_{\operatorname{\partial\Omega}}.\end{aligned}\end{rcases}$
(3.2)

Note that

$\tilde{\mathcal{L}}(u_{1}-u_{2})=\sum_{j,k=0}^{m-1}(\tilde{A}_{j,k}-A_{j,k})\partial^{j}\bar{\partial}^{k}u_{1}.$

Now we use integration by parts and (3.2) to obtain the following integral
identity

$\displaystyle 0$
$\displaystyle=\int_{\Omega}{(u_{1}-u_{2})\overline{\tilde{\mathcal{L}}^{*}v}\,dx}$
$\displaystyle=\int_{\Omega}{\tilde{\mathcal{L}}(u_{1}-u_{2})\bar{v}\,dx}$
$\displaystyle=\int_{\Omega}{\left[\sum_{j,k=0}^{m-1}(\tilde{A}_{j,k}-A_{j,k})\partial^{j}\bar{\partial}^{k}u_{1}\right]\bar{v}\,dx}.$

By our assumption (1.3), we get the following integral identity

$\sum_{j,k=0}^{m-1}\left((-1)^{j}\int_{\Omega}{({\tilde{A}^{\prime}}_{j,k}-{A^{\prime}}_{j,k})\bar{\partial}^{k}u_{1}\partial^{j}\bar{v}\,dx}\right)=0.$
(3.3)

where $\mathcal{L}(u_{1})=0$ and $\tilde{\mathcal{L}}^{*}(v)=0$.

By using Theorem 1.3 we consider $u_{1}$ and $v$ of the form

$\displaystyle\begin{split}u_{1}&=e^{\Phi/h}(a+r_{h}),\text{ where }\
\bar{\partial}^{m}a=0,\\\ v&=e^{-\Phi/h}(b+s_{h}),\text{ where }\
\bar{\partial}^{m}b=0,\end{split}$ (3.4)

with $r_{h}$ and $s_{h}$ satisfy
$\|r_{h}\|_{H^{m}(\Omega)}=O(h^{\frac{1}{2}+\epsilon})$ and
$\|s_{h}\|_{H^{m}(\Omega)}=O(h^{\frac{1}{2}+\epsilon})$ for some $\epsilon>0$.

By using $u_{1}$ and $v$, the integral identity takes the form

$\displaystyle 0$
$\displaystyle=\sum_{j,k=0}^{m-1}(-1)^{j}\int_{\Omega}{\left[e^{(\Phi-\bar{\Phi})/h}(\tilde{A}^{\prime}_{j,k}-A^{\prime}_{j,k})\bar{\partial}^{k}a\partial^{j}\bar{b}\right]}$
$\displaystyle\quad+\sum_{j,k=0}^{m-1}(-1)^{j}\int_{\Omega}{\left[e^{(\Phi-\bar{\Phi})/h}(\tilde{A}^{\prime}_{j,k}-A^{\prime}_{j,k})(\bar{\partial}^{k}a\partial^{j}\bar{s}_{h}+\bar{\partial}^{k}r_{h}\partial^{j}\bar{b}+\bar{\partial}^{k}r_{h}\partial^{j}\bar{s}_{h})\right]}$

By using the assumption (1.3) and the method of stationary phase one can
obtain that

$\sum_{j,k=0}^{m-1}\left((-1)^{j}\int_{\Omega}{{e^{2i\psi/h}(\tilde{A}^{\prime}_{j,k}-A^{\prime}_{j,k})(\bar{\partial}^{k}a)(\partial^{j}\bar{b})}}\right)\\\
=\sum_{j,k=0}^{m-1}{C_{j,k}(z_{0})he^{2i\psi(z_{0})/h}(\tilde{A}^{\prime}_{j,k}(z_{0})-{A}^{\prime}_{j,k}(z_{0}))\bar{\partial}^{k}a(z_{0})\partial^{j}\bar{b}(z_{0})}+o(h).$
(3.5)

where $C_{j,k}(z_{0})\neq 0$ for all $0\leq j,k\leq m-1$.

Next, we use the fact that
$\|r_{h}\|_{H^{m}(\Omega)}=O(h^{\frac{1}{2}+\epsilon})$,
$\|s_{h}\|_{H^{m}(\Omega)}=O(h^{\frac{1}{2}+\epsilon}),$ for some $\epsilon>0$
and obtain the following estimate

$\sum_{j,k=0}^{m-1}(-1)^{j}\int_{\Omega}{\left[e^{(\Phi-\bar{\Phi})/h}(\tilde{A}^{\prime}_{j,k}-A^{\prime}_{j,k})\bar{\partial}^{k}r_{h}\partial^{j}\bar{s_{h}}\right]}=O(h^{1+2\epsilon}).$
(3.6)

Let $\tilde{r}_{h}$ and $\tilde{s}_{h}$ be such that

$\displaystyle r_{h}$
$\displaystyle=\bar{\partial}^{-m}\left(e^{(\bar{\Phi}-\Phi)/h}\tilde{r}_{h}\right),$
$\displaystyle s_{h}$
$\displaystyle=\bar{\partial}^{-m}\left(e^{(\bar{\Phi}-\Phi)/h}\tilde{s}_{h}\right)$

and they satisfy the equation (2.8) in place of $g$. Using this we have the
following estimate

$\displaystyle\sum_{j,k=0}^{m-1}(-1)^{j}\int_{\Omega}{\left[e^{(\Phi-\bar{\Phi})/h}(\tilde{A}^{\prime}_{j,k}-A^{\prime}_{j,k})\bar{\partial}^{k}r_{h}\partial^{j}\bar{b}\right]}$
$\displaystyle\quad=\sum_{j,k=0}^{m-1}(-1)^{j}\int_{\Omega}{\left[e^{(\Phi-\bar{\Phi})/h}(\tilde{A}^{\prime}_{j,k}-A^{\prime}_{j,k})\bar{\partial}^{k-m}\left(e^{(\bar{\Phi}-\Phi)/h}\tilde{r}_{h}\right)\partial^{j}\bar{b}\right]}$
$\displaystyle\quad=\sum_{j,k=0}^{m-1}(-1)^{j}\int_{\Omega}{\left[\bar{\partial}^{k-m}\left(e^{(\Phi-\bar{\Phi})/h}(\tilde{A}^{\prime}_{j,k}-A^{\prime}_{j,k})\partial^{j}\bar{b}\right)e^{(\bar{\Phi}-\Phi)/h}\tilde{r}_{h}\right]}$
$\displaystyle\quad\leq
Ch^{\frac{1}{2}+\epsilon}\sum_{j,k=0}^{m-1}\norm{(\tilde{A}^{\prime}_{j,k}-A^{\prime}_{j,k})\partial^{j}\bar{b}}_{W^{1,p}}\norm{\tilde{r}_{h}}_{L^{2}},$

where we have used Fubini’s theorem in the third equality while the last
inequality is obtained by applying Lemma 2.1. Now, we apply Proposition 2.3 to
obtain

$\sum_{j,k=0}^{m-1}(-1)^{j}\int_{\Omega}{\left[e^{(\Phi-\bar{\Phi})/h}(\tilde{A}^{\prime}_{j,k}-A^{\prime}_{j,k})\bar{\partial}^{k}r_{h}\partial^{j}\bar{b}\right]}=O(h^{1+2\epsilon}).$
(3.7)

Similarly, we obtain

$\sum_{j,k=0}^{m-1}(-1)^{j}\int_{\Omega}{\left[e^{(\Phi-\bar{\Phi})/h}(\tilde{A}^{\prime}_{j,k}-A^{\prime}_{j,k})\bar{\partial}^{k}a\partial^{j}\bar{s}_{h}\right]}=O(h^{1+2\epsilon}).$
(3.8)

Proof of Theorem 1.1. Using the estimates (3.5) - (3.8) and matching the
asymptotics as $h\to 0$, we obtain

$0=\sum_{j,k=0}^{m-1}(-1)^{j}(\tilde{A}^{\prime}_{j,k}(z_{0})-{A}^{\prime}_{j,k}(z_{0}))\bar{\partial}^{k}a(z_{0})\partial^{j}\bar{b}(z_{0}).$
(3.9)

We now show that $A^{\prime}_{0,0}=\tilde{A}^{\prime}_{0,0}$. To this end, let
us choose $a=b=1$. With this choice we obtain

$\tilde{A}^{\prime}_{0,0}(z_{0})={A}^{\prime}_{0,0}(z_{0}).$

Since for any $z_{0}\in\Omega$ we can choose $\Phi$ with a unique critical
point at $z_{0}$, we have

$\tilde{A}^{\prime}_{0,0}={A}^{\prime}_{0,0}\quad\text{in}\ \Omega.$

Next to show that $A^{\prime}_{0,1}=\tilde{A}^{\prime}_{0,1},$ we rewrite
(3.9) by setting the term $\tilde{A}^{\prime}_{0,0}-{A}^{\prime}_{0,0}=0.$
Then, we choose $a=\bar{z},b=1$ to obtain

$A^{\prime}_{0,1}=\tilde{A}^{\prime}_{0,1},\quad\text{in}\ \Omega.$

Similarly, one can show $A^{\prime}_{j,k}=\tilde{A}^{\prime}_{j,k}$ in an
increasing order for $j+k$ by choosing

$a=\frac{\bar{z}^{k}}{k!}\ \text{ and }b=\frac{\bar{z}^{j}}{j!}$

and applying the above procedure to obtain

$\tilde{A}^{\prime}_{j,k}={A}^{\prime}_{j,k}\ \text{in}\ \Omega\quad\text{for
all}\ \ 0\leq j,k\leq m-1.$

From (2.2), we readily obtain that

$\tilde{A}_{j,k}={A}_{j,k}\ \text{in}\ \Omega\quad\text{for all}\ \ 0\leq
j,k\leq m-1.$

This proves Theorem 1.1.

## Acknowledgements

VPK would like to thank the Isaac Newton Institute for Mathematical Sciences,
Cambridge, UK, for support and hospitality during _Rich and Nonlinear
Tomography - a multidisciplinary approach_ in 2023 where part of this work was
done (supported by EPSRC Grant Number EP/R014604/1). The authors thank Manas
Kar for suggesting this problem and Masaru Ikehata for pointing out the
references [Ike91, Ike93, Ike96].

## References

  * [AP06] Kari Astala and Lassi Päivärinta.  Calderón’s inverse conductivity problem in the plane.  Annals of Mathematics, pages 265–299, 2006.
  * [BG19] Sombuddha Bhattacharyya and Tuhin Ghosh.  Inverse boundary value problem of determining up to a second order tensor appear in the lower order perturbation of a polyharmonic operator.  Journal of Fourier Analysis and Applications, 25:661–683, 2019\.
  * [BG22] Sombuddha Bhattacharyya and Tuhin Ghosh.  An inverse problem on determining second order symmetric tensor for perturbed biharmonic operator.  Mathematische Annalen, pages 1–33, 2022.
  * [BKS21] Sombuddha Bhattacharyya, Venkateswaran P Krishnan, and Suman Kumar Sahoo.  Unique determination of anisotropic perturbations of a polyharmonic operator from partial boundary data.  arXiv preprint arXiv:2111.07610, 2021.
  * [Blå11] Eemeli Blåsten.  The inverse problem of the Schrödinger equation in the plane; a dissection of Bukhgeim’s result.  arXiv preprint arXiv:1103.6200, 2011.
  * [BU97] Russell M Brown and Gunther A Uhlmann.  Uniqueness in the inverse conductivity problem for nonsmooth conductivities in two dimensions.  Communications in partial differential equations, 22(5-6):1009–1027, 1997.
  * [Buk08] A. L. Bukhgeim.  Recovering a potential from Cauchy data in the two-dimensional case.  Journal of Inverse and Ill-Posed Problems, 16(1):19–33, 2008.
  * [Cal80] Alberto-P. Calderón.  On an inverse boundary value problem.  In Seminar on Numerical Analysis and its Applications to Continuum Physics, Rio de Janeiro, 1980, pages 65–73. Brazilian Math. Soc., 1980\.
  * [GK16] Tuhin Ghosh and Venkateswaran P Krishnan.  Determination of lower order perturbations of the polyharmonic operator from partial boundary data.  Applicable Analysis, 95(11):2444–2463, 2016.
  * [GT11a] Colin Guillarmou and Leo Tzou.  Calderón inverse problem with partial data on Riemann surfaces.  Duke Mathematical Journal, 158(1):83 – 120, 2011.
  * [GT11b] Colin Guillarmou and Leo Tzou.  Identification of a connection from cauchy data on a Riemann surface with boundary.  Geometric and Functional Analysis, 21(2):393–418, 2011.
  * [GT13] Colin Guillarmou and Leo Tzou.  The Calderón inverse problem in two dimensions.  Inverse problems and applications: Inside Out. II, pages 119–166, 2013.
  * [Ike91] Masaru Ikehata.  A special Green’s function for the biharmonic operator and its application to an inverse boundary value problem.  Computers & Mathematics with Applications, 22(4-5):53–66, 1991\.
  * [Ike93] Masaru Ikehata.  An inverse problem for the plate in the Love–Kirchhoff theory.  SIAM Journal on Applied Mathematics, 53(4):942–970, 1993.
  * [Ike96] Masaru Ikehata.  A relationship between two dirichlet to neumann maps in anisotrpoic elastic plate theory.  Journal of Inverse and Ill-posed Problems, 4(3):233–244, 1996.
  * [IUY10] Oleg Imanuvilov, Gunther Uhlmann, and Masahiro Yamamoto.  The Calderón problem with partial data in two dimensions.  Journal of the American Mathematical Society, 23(3):655–691, 2010\.
  * [IUY12] Oleg Yu Imanuvilov, Gunther Uhlmann, and Masahiro Yamamoto.  Partial cauchy data for general second order elliptic operators in two dimensions.  Publications of the Research Institute for Mathematical Sciences, 48(4):971–1055, 2012.
  * [IY15] O Yu Imanuvilov and M Yamamoto.  Global uniqueness in inverse boundary value problems for the Navier–Stokes equations and Lamé system in two dimensions.  Inverse Problems, 31(3):035004, 2015.
  * [KLU14] Katsiaryna Krupchyk, Matti Lassas, and Gunther Uhlmann.  Inverse boundary value problems for the perturbed polyharmonic operator.  Transactions of the American Mathematical Society, 366(1):95–112, 2014.
  * [Lai11] Ru-Yu Lai.  Global uniqueness for an inverse problem for the magnetic Schrödinger operator.  Inverse Problems and Imaging, 5(1):59–73, 2011.
  * [LU89] John M Lee and Gunther Uhlmann.  Determining anisotropic real-analytic conductivities by boundary measurements.  Communications on Pure and Applied Mathematics, 42(8):1097–1112, 1989.
  * [LUW15] Ru-Yu Lai, Gunther Uhlmann, and Jenn-Nan Wang.  Inverse boundary value problem for the Stokes and the Navier–Stokes equations in the plane.  Archive for Rational Mechanics and Analysis, 215:811–829, 2015\.
  * [Nac96] Adrian I Nachman.  Global uniqueness for a two-dimensional inverse boundary value problem.  Annals of Mathematics, pages 71–96, 1996.
  * [SS23] Suman Kumar Sahoo and Mikko Salo.  The linearized Calderón problem for polyharmonic operators.  Journal of Differential Equations, 360:407–451, 2023.
  * [SU87] John Sylvester and Gunther Uhlmann.  A global uniqueness theorem for an inverse boundary value problem.  Annals of mathematics, pages 153–169, 1987.
  * [Tzo17] Leo Tzou.  The reflection principle and Calderón problems with partial data.  Mathematische Annalen, 369:913–956, 2017.


$\varphi(\mathbf{z}_{1}+\mathbf{z}_{2})=\varphi((z_{1i}+z_{2i})_{i=1}^{n})=(\varphi(z_{1i}+z_{2i}))_{i=1}^{n}=(\varphi(z_{1i})+\varphi(z_{2i}))_{i=1}^{n}=\varphi(\mathbf{z}_{1})+\varphi(\mathbf{z}_{2}),$

and

$\varphi(\mathbf{z}_{1}\odot\mathbf{z}_{2})=\varphi((z_{1i}z_{2i})_{i=1}^{n})=(\varphi(z_{1i}z_{2i}))_{i=1}^{n}=(\varphi(z_{1i})\varphi(z_{2i}))_{i=1}^{n}=\varphi(\mathbf{z}_{1})\odot\varphi(\mathbf{z}_{2}).$

Therefore, the extended $\varphi:\mathbb{C}^{n}\rightarrow\mathbb{R}^{2n\times
2}$ of (3.2) is a ring homomorphism. Using, proposition 5 of section 7.3 of
Dummit and Foote [2004], $\text{Image}(\varphi)$ is a subring of
$\mathbb{R}^{2n\times 2}$, and the kernel of $\varphi$, denoted by
$\text{ker}(\varphi)=\\{\mathbf{z}:\varphi(\mathbf{z})=\mathbf{0}_{2n\times
2}\\}$, is a subring of $\mathbb{C}^{n}$. In this case, $\text{ker}(\varphi)$
consists of all those complex numbers $z$ such that
$\textbf{Re}(\mathbf{z})=0,\ \textbf{Im}(\mathbf{z})=0$, i.e. $\mathbf{z}=0$.
Therefore, $\varphi$ has a trivial kernel and hence it is a one-to-one map. As
a result, $\varphi$ described in (3.2) is a ring isomorphism.

  * (b)

The proof is similar to part (a). The only difference in this case are (i)
$\mathbb{C}^{m\times n}$ and $\mathbb{R}^{2m\times 2n}$ are rings under
addition $+$ and entry-wise multiplication $\odot$ of $m\times n$ dimensional
complex matrices and $2m\times 2n$ dimensional real matrices respectively, and
(ii) $\varphi$ is described in $\eqref{eq:phi-extn-2}$.

  * (c)

Similar to the proof of part (a), $\text{GL}_{n}(\mathbb{C})$ is a field, and
hence a ring. $\text{Image}(\varphi)$ is a subring of $\mathbb{R}^{2n\times
2n}$ and the kernel is trivial, which implies that $\varphi$ described in
(3.3) is a ring isomorphism in this case. In addition, using the homomorphic
properties of $\varphi$ and the field properties of
$\text{GL}_{n}(\mathbb{C})$, it can be shown that $\text{Image}(\varphi)$ is
also a field. Therefore, $\text{Image}(\varphi)$ is a field in this case, and
hence $\varphi$ is a field isomorphism.

For any $A\in GL_{n}(\mathbb{C})$,
$\varphi(A)\varphi(A^{-1})=\varphi(AA^{-1})=\varphi(I_{n})=I_{2n}$. Therefore,
$\varphi(A^{-1})=[\varphi(A)]^{-1}$.

### Proof of Proposition 4.1

By Proposition 3.5 of Sun et al. [2018], for some constants $c,c^{\prime}$ and
any $\eta>0$, we have

$\mathbb{P}\left(\left|\hat{f}_{kl}(\omega_{j})-\mathbb{E}\hat{f}_{kl}(\omega_{j})\right|\geq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\eta\right)\leq
c^{\prime}\exp\\{-c(2m+1)\min\\{\eta,\eta^{2}\\}\\}.$

We choose $\eta=\sqrt{\frac{R\log p}{m}}$. In the asymptotic regime
$m\succsim{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{2}\log
p$, we have $\eta=\sqrt{\frac{R\log p}{m}}\geq\frac{R\log p}{m}=\eta^{2}$.
Therefore, by using a union bound over all $k,l$, we obtain

$\displaystyle\mathbb{P}\left(\max_{k,l}\left|\hat{f}_{kl}(\omega_{j})-\mathbb{E}\hat{f}_{kl}(\omega_{j})\right|\geq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\sqrt{\frac{R\log
p}{m}}\right)$ $\displaystyle\leq p^{2}\cdot
c^{\prime}\exp\left\\{-c(2m+1)\frac{R\log p}{m}\right\\}$ $\displaystyle\leq
p^{2}c^{\prime}\exp\\{-2cR\log p\\}=c^{\prime}p^{-(2cR-2)}.$ (B.1)

Also, from Proposition 3.3 of Sun et al. [2018], the upper bound on the bias
term is

$\left|\mathbb{E}\hat{f}_{kl}(\omega_{j})-f_{kl}(\omega_{j})\right|\leq\frac{m+\frac{1}{2\pi}}{n}\Omega_{n}+\frac{1}{2\pi}L_{n},~{}~{}~{}\mbox{for
all }k,l,$

where $\Omega_{n}$ and $L_{n}$ are defined in (4.1). Therefore,

$\max_{k,l}\left|\mathbb{E}\hat{f}_{kl}(\omega_{j})-f_{kl}(\omega_{j})\right|\leq\frac{m+\frac{1}{2\pi}}{n}\Omega_{n}+\frac{1}{2\pi}L_{n}.$
(B.2)

We have chosen
$\Delta_{f}(m,n,p)={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\sqrt{\frac{R\log
p}{m}}+\frac{m+\frac{1}{2\pi}}{n}\Omega_{n}+\frac{1}{2\pi}L_{n}$. Combining
(B.1) and (B.2), we obtain

$\mathbb{P}\left({\left|\kern-1.07639pt\left|\hat{f}(\omega_{j})-f(\omega_{j})\right|\kern-1.07639pt\right|}_{\max}\geq\Delta_{f}(m,n,p)\right)\leq
c^{\prime}p^{-(cR-2)}.$

$\hfill\square$

### Proof of Theorem 4.1

Our objective is to show that the primal dual witness matrix
$\widetilde{\Theta}$ in (B.4) is equal to the solution of the optimization
problem (2.3) with high probability. For a fixed $j\in[n]$ and Fourier
frequency $\omega_{j}\in[-\pi,\pi]$, we define the event
$\mathcal{E}:=\bigg{\\{}{\left|\kern-1.07639pt\left|\hat{f}(\omega_{j})-f(\omega_{j})\right|\kern-1.07639pt\right|}_{\max}$
$\leq\Delta_{f}(m,n,p)\bigg{\\}}$. As we are in the regime
$m\succeq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{2}\zeta^{2}\log
p$, $m\preceq n/\left[\Omega_{n}\zeta\right]$ and $\zeta\geq 1$, so
$m\succeq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{2}\log
p$, $m\preceq n/\Omega_{n}$. Also, in the definition of $\Delta_{f}(m,n,p)$ in
(4.2), we consider $R>1/c$ i.e. $\tau=cR>2$. Hence, by Proposition 4.1
$\mathbb{P}(\mathcal{E})\geq 1-\frac{c^{\prime}}{p^{\tau-2}}$ for constants
$c^{\prime}>0$ and $\tau>2$. In the following analysis, we condition on the
event $\mathcal{E}$.

Our proof goes on the following route- we first describe a primal-dual witness
approach required for the proof, state a series of claims which are just
restatement of a number of lemmas in Ravikumar et al. [2011] with highlight on
the changes due to incorporating complex regime.

######  Claim B.1.

The penalized log-determinant program 2.3 has a unique solution $\hat{\Theta}$
characterized by the equation

$\hat{f}(\omega_{j})-{\hat{\Theta}}^{-1}+\lambda\hat{\Psi}=0,$ (B.3)

where $\hat{\Psi}$ is an element in the set of subdifferentials of
$\partial\|(\cdot)\|_{\text{1,off}}$ at $\hat{\Theta}$ as characterized in
(3.15).

Proof sketch. The proof of this claim B.1 follows from the Lemma 3 of
Ravikumar et al. [2011]. Claim B.1 is similar to their result with the real
covariance matrix $\hat{\Sigma}$ replaced with the averaged periodogram matrix
$\hat{f}(\omega_{j})$, and $\hat{\Psi}$ replaced with the matrix with entry-
wise signs of $\hat{\Theta}$ (details available in Equation 41 Section 4.1 in
Ravikumar et al. [2011]). The basic idea for the proof is following: the
penalized log-determinant program (2.3) is a strict convex program i.e. the
concerned objective function is a strictly convex function of $\Theta$ since
the $\ell_{1}$ penalty on the off-diagonals is a convex function of $\Theta$
and the log-determinant barrier is also convex (section 3.1.5 of Boyd and
Vandenberghe [2004]). Also for complex positive definite Hermitian matrices,
i.e. $\Theta\in\mathcal{H}^{p}_{++}$, eigen values and diagonal elements of
$\Theta$ are strictly positive. According to the proof of Lemma 3 in Ravikumar
et al. [2011], and Hadamard’s inequality for Hermitian positive definite
matrices (theorem 7.8.1 of Horn and Johnson [2012]), we have
$\log\det\Theta\leq\sum_{k=1}^{p}\log\Theta_{kk}$. Hence,

$\sum_{k=1}^{p}\Theta_{kk}[\hat{f}(\omega_{j})]_{kk}-\log\det\Theta\geq\sum_{k=1}^{p}\left(\Theta_{kk}[\hat{f}(\omega_{j})]_{kk}-\log\Theta_{kk}\right).$

The right-hand side of the above inequality is coercive, i.e. it diverges to
infinity as $\|(\Theta_{11},\cdots,\Theta_{pp})\|\rightarrow\infty$.
Therefore, the objective function is a continuous and coercive function of
$\Theta$. Hence the level sets are compact, and continuity implies that a
minimum is attained. In addition, strict convexity guarantees the uniqueness
of the minimum.

A sufficient condition for $\hat{\Theta}$ to be a solution of (2.3) is that
zero belongs to the subdifferential of the objective function of (2.3)
evaluated at $\hat{\Theta}$, i.e.
$0\in\partial\left(\langle\hat{\Theta},\hat{f}(\omega_{j})\rangle-\log\det\hat{\Theta}+\lambda\|\hat{\Theta}\|_{1,\text{off}}\right)$.
Using theorems 2.9 and 2.10 of Weylandt Jr [2020], the KKT (Karush-Kahn
Tucker) conditions, i.e. the subdifferential equation corresponding to the
optimization problem (2.3) is the same as (B.3). $\hfill\square$

As now we guarantee existence, uniqueness, and a formulation of the optimal
solution of (2.3), we can take a primal dual witness approach to calculate the
solution as well as to recover the correct support set. The primal dual
witness construction is motivated by previous works by Zhao and Yu [2006];
Wainwright [2009]; Ravikumar et al. [2011]; Loh and Wainwright [2017]. The key
idea is to search for a pair of unique primal and dual feasible solutions
satisfying the strict dual feasibility conditions in a setting when the
objective function may not be strictly convex. Next we provide a reiteration
of the primal dual witness construction in Ravikumar et al. [2011] for a
restricted CGLASSO problem.

#### Primal-dual witness construction

We recall from section 4 that $S$ is the augmented edge set, and consider the
restricted log-determinant problem

$\widetilde{\Theta}=\operatorname*{arg\,min}_{\Theta\in\mathcal{H}_{++}^{p}:\
\Theta_{S^{\texttt{c}}}=0}\langle\Theta,\hat{f}(\omega_{j})\rangle-\log\det\Theta+\lambda\|\Theta\|_{1,\text{off}}.$
(B.4)

By this construction, $\widetilde{\Theta}$ is positive-definite Hermitian as
well as $\widetilde{\Theta}_{S^{\texttt{c}}}=0$. Let
$\widetilde{\Psi}\in\partial\|(\cdot)\|_{\text{1,off}}(\widetilde{\Theta})$.
For $(k,l)\in S^{\texttt{c}}$, we replace $(\widetilde{\Psi})_{kl}$ with

$\displaystyle\widetilde{\Psi}_{kl}=\frac{1}{\lambda}\left[-\left(\hat{f}(\omega_{j})\right)_{kl}+\left(\widetilde{\Theta}^{-1}\right)_{kl}\right].$

The pair $(\widetilde{\Theta},\widetilde{\Psi})$ satisfies the equation (B.3)
replacing $(\hat{\Theta},\hat{\Psi})$. Finally we check the strict dual
feasibility condition, i.e.

$|\widetilde{\Psi}_{kl}|<1\text{ for all }(k,l)\in S^{\texttt{c}}.$

This step ensures that $\widetilde{\Psi}$ satisfies the necessary conditions
to belong to the set of subdifferentials.

We define $G=\widetilde{\Theta}-\Theta^{*}$. Also let the remainder term of
the first order Taylor expansion of $(\Theta^{*}+G)^{-1}$ around $\Theta^{*}$
be $R(G)=(\Theta^{*}+G)^{-1}-\Theta^{*}+{\Theta^{*}}^{-1}G{\Theta^{*}}^{-1}$.
We state the following result:

######  Claim B.2.

Suppose that

$\max\left\\{{\left|\kern-1.07639pt\left|\hat{f}(\omega_{j})-f(\omega_{j})\right|\kern-1.07639pt\right|}_{\max},{\left|\kern-1.07639pt\left|R(G)\right|\kern-1.07639pt\right|}_{\max}\right\\}\leq\frac{\alpha}{8}\lambda.$
(B.5)

Then the vector $\widetilde{\Psi}$ constructed in the primal dual witness
construction satisfies $\|\widetilde{\Psi}_{S^{c}}\|_{\max}<1$. Hence strict
duality holds and $\widetilde{\Theta}=\hat{\Theta}$.

Proof sketch. The proof of claim B.2 follows from the proof of Lemma 4 in
Ravikumar et al. [2011] and involves basic linear algebra computation with
complex valued matrices. The only change in notation are that
$W=\hat{\Sigma}-\Sigma$ is replaced by $\hat{f}(\omega_{j})-f(\omega_{j})$ in
our case and $G$ is the difference between the primal dual witness and the
true spectral density instead of the difference $\Delta$ (as per the notation
in Ravikumar et al. [2011], in our literature $\Delta$ is used to denote the
threshold parameter) between the true inverse covariance and its primal dual
witness. Lemma 4 in Ravikumar et al. [2011] shows that under the assumption
$\max\\{{\left|\kern-1.07639pt\left|W\right|\kern-1.07639pt\right|}_{\max},{\left|\kern-1.07639pt\left|R(\Delta)\right|\kern-1.07639pt\right|}_{\max}\\}\leq\alpha\lambda/8$,
the matrix of entry-wise signs for the primal-dual witness problem i.e.
$\widetilde{\Psi}$ satisfies strict dual feasibility condition
$\|\widetilde{\Psi}_{S^{c}}\|_{\max}<1$. The same strict dual feasibility
condition can be concluded under the condition (B.5) if we follow the steps
(51)-(55) in the proof of Lemma 4 (section 4.2.1) in Ravikumar et al. [2011].
And under strict dual feasibility, by construction,
$\widetilde{\Theta}=\hat{\Theta}$ is ensured.$\hfill\square$

Next, we verify that the assumption (B.5) holds. As our choice of
regularization parameter is $\lambda=\frac{8}{\alpha}\Delta_{f}(m,n,p)$, under
the event $\mathcal{E}$ we have
${\left|\kern-1.07639pt\left|\hat{f}(\omega_{j})-f(\omega_{j})\right|\kern-1.07639pt\right|}_{\max}\leq\frac{\alpha}{8}\lambda=\Delta_{f}(m,n,p)$.
In order to show (B.5) it remains to show
${\left|\kern-1.07639pt\left|R(G)\right|\kern-1.07639pt\right|}_{\max}\leq\frac{\alpha}{8}\lambda$.
For that we will require the following two claims.

######  Claim B.3.

Suppose that

$r:=2\kappa_{\Theta^{*}}\left({\left|\kern-1.07639pt\left|\hat{f}(\omega_{j})-f(\omega_{j})\right|\kern-1.07639pt\right|}_{\max}+\lambda\right)\leq\min\left\\{\frac{1}{3\kappa_{f}d},\frac{1}{3\kappa_{f}^{3}\kappa_{\Theta^{*}}d}\right\\}.$

Then
${\left|\kern-1.07639pt\left|G\right|\kern-1.07639pt\right|}_{\max}={\left|\kern-1.07639pt\left|\widetilde{\Theta}-\Theta^{*}\right|\kern-1.07639pt\right|}_{\max}\leq
r$.

Proof sketch. The proof of Claim B.3 is similar to that of Lemma 6 in
Ravikumar et al. [2011] and involves linear algebra of complex matrices. By
claim B.1, the restricted problem (B.4) has a unique solution. Thus, upon
taking partial derivative w.r.t the restricted element, it should vanish at
the unique optimum, that is, $\widetilde{\Theta}_{S}$ satisfies

$H_{1}(\Theta_{S}):=[\hat{f}(\omega_{j})]_{S}-[\Theta^{-1}]_{S}+\lambda\widetilde{\Psi}_{S}=0.$

This restricted zero gradient condition is necessary and sufficient for the
optimal solution, hence the solution is unique. Now we define the map
$H_{2}:\mathbb{R}^{|S|}\rightarrow\mathbb{R}^{|S|}$ as follows

$H_{2}(\overline{G}_{S}):=-(\Upsilon_{SS}^{*})^{-1}\
\overline{H}_{1}(\Theta_{S}^{*}+G_{S})+\overline{G}_{S}.$

From construction, $H_{2}(\overline{G}_{S})=\overline{G}_{S}$, i.e.
$H_{1}(\Theta_{S}^{*}+G_{S})=H_{1}(\widetilde{\Theta}_{S}^{*})=0$. Let
$\mathbb{B}(r)$ be the $\ell_{\infty}$ ball in $\mathbb{R}$, i.e.
$\mathbb{B}(r)=\\{\Theta_{S}:\|\Theta_{S}\|_{\infty}\leq r\\}$ Now, following
the matrix algebraic calculations in equations 72 to 74 of Ravikumar et al.
[2011], it can be easily checked that
$H_{2}(\mathbb{B}(r))\subset\mathbb{B}(r)$. Since $H_{2}$ is a continuous
function on $\mathbb{R}^{|S|}$ and $\mathbb{B}(r)$ is convex and compact in
$\mathbb{R}^{|S|}$, by Brouwere’s fixed point theorem [Kellogg et al., 1976],
existence of a fixed point $\overline{G}_{S}\in\mathbb{B}(r)$ of the function
$H_{2}$ is guaranteed. Also uniqueness of the zero gradient condition (B)
implies the uniqueness of the fixed points of $H_{2}$. Therefore, we can
conclude that $\|\widetilde{\Theta}_{S}-\Theta^{*}_{S}\|_{\infty}\leq r$, and
hence the claim is proved. $\hfill\square$

By our choice of the regularization constant

$2\kappa_{\Theta^{*}}\left({\left|\kern-1.07639pt\left|\hat{f}(\omega_{j})-f(\omega_{j})\right|\kern-1.07639pt\right|}_{\max}+\lambda\right)\leq
2\kappa_{\Theta^{*}}\left(1+\frac{8}{\alpha}\right)\Delta_{f}(m,n,p)=2\kappa_{\Theta^{*}}C_{\alpha}\Delta_{f}(m,n,p).$

From the conditions of Theorem 4.1,
$\Delta_{f}(m,n,p)d\leq[6\kappa_{f}^{3}\kappa_{\Theta^{*}}^{2}C_{\alpha}^{2}]^{-1}$,
and $C_{\alpha}>1$. Therefore, the following two inequalities are satisfied

$r\leq
2\kappa_{\Theta^{*}}C_{\alpha}\Delta_{f}(m,n,p)\leq[3\kappa_{f}^{3}\kappa_{\Theta^{*}}d]^{-1},$
(B.6)

and

$2\kappa_{\Theta^{*}}C_{\alpha}^{2}\Delta_{f}(m,n,p)\leq[3\kappa_{f}^{3}\kappa_{\Theta^{*}}d]^{-1}$
(B.7)

Now we turn to a result in similar spirit as Lemma 5 in Ravikumar et al.
[2011]. The result states the following:

######  Claim B.4.

${\left|\kern-1.07639pt\left|G\right|\kern-1.07639pt\right|}_{\max}\leq\frac{1}{3\kappa_{f}d}$
implies
${\left|\kern-1.07639pt\left|R(G)\right|\kern-1.07639pt\right|}_{\max}\leq\frac{3}{2}d{\left|\kern-1.07639pt\left|G\right|\kern-1.07639pt\right|}_{\max}^{2}\kappa_{f}^{3}$.

The proof follows from Lemma 5 in Ravikumar et al. [2011]. The proof involves
a step where we need to expand the power series of the complex matrix
$(\Theta^{*}+G)^{-1}$ as

$(\Theta^{*}+G)^{-1}=\sum_{k=0}^{\infty}({\Theta^{*}}^{-1}G)^{k}{\Theta^{*}}^{-1}$

The power series expansion can be verified as
${\left|\kern-1.07639pt\left|G\right|\kern-1.07639pt\right|}_{\max}\leq
1/3\kappa_{f}d$ implies
${\left|\kern-1.07639pt\left|{\Theta^{*}}^{-1}G\right|\kern-1.07639pt\right|}_{\max}<1$
(ensures the radius of convergence condition, see equation (68) in Appendix B
of Ravikumar et al. [2011]), and also from the results in holomorphic
functional calculus that involves the general power series expansion of an
operator on a Banach space [Dudley et al., 2011; Haase, 2018]. Rest of the
proof can be imitated as the proof of Lemma 5 in Appendix B of Ravikumar et
al. [2011]

Combining this result with (B.6) we get

$\displaystyle{\left|\kern-1.07639pt\left|R(G)\right|\kern-1.07639pt\right|}_{\max}\leq\frac{3}{2}d{\left|\kern-1.07639pt\left|G\right|\kern-1.07639pt\right|}_{\max}^{2}\kappa_{f}^{3}$
$\displaystyle\leq\frac{3}{2}d\left(2\kappa_{\Theta_{j}^{*}}C_{\alpha}\Delta_{f}(m,n,p)\right)^{2}\kappa_{f}^{3}$
$\displaystyle=6\kappa_{f}^{3}\kappa_{\Theta^{*}}^{2}dC_{\alpha}^{2}\left[\Delta_{f}(m,n,p)\right]^{2}$
$\displaystyle=\left(6\kappa_{f}^{3}\kappa_{\Theta^{*}}^{2}dC_{\alpha}^{2}\left[\Delta_{f}(m,n,p)\right]\right)\frac{\alpha\lambda}{8}$
$\displaystyle\leq\frac{\alpha\lambda}{8}$

where the last inequality follows from (B.7). Therefore, we have shown that
condition (B.5) holds under $\mathcal{E}$ and strict duality allows us to
conclude that $\hat{\Theta}=\widetilde{\Theta}$. Hence, $\hat{\Theta}$
satisfies the bound (B.6) and
$\hat{\Theta}_{S^{c}}=\widetilde{\Theta}_{S^{c}}=0$. Hence
$E(\hat{\Theta})=E(\widetilde{\Theta})$. Also, for $(k,l)\in S$ such that
$\left|\Theta^{*}_{kl}\right|>2C_{\alpha}\kappa_{\Theta^{*}}\Delta_{f}(m,n,p)$

$\displaystyle\left|\hat{\Theta}_{kl}\right|$
$\displaystyle=\left|\hat{\Theta}_{kl}-\Theta^{*}_{kl}+\Theta^{*}_{kl}\right|\geq\left|\Theta^{*}_{kl}\right|-\left|\hat{\Theta}_{kl}-\Theta^{*}_{kl}\right|>0$

Therefore, $E(\hat{\Theta})$ contains all edges $(k,l)$ with
$\left|\hat{\Theta}^{*}_{kl}\right|>2C_{\alpha}\kappa_{\Theta^{*}}\Delta_{f}(m,n,p)$
and hence (b) is proved.

Now we use the idea of Corollary 3 of Ravikumar et al. [2011] and write

$\displaystyle\|\hat{\Theta}-\Theta^{*}\|_{F}$
$\displaystyle\leq\left[\sum_{k=1}^{p}\left|\hat{\Theta}_{kk}-\Theta^{*}_{kk}\right|^{2}+\sum_{(k,l)\in
E(\Theta^{*})}\left|\hat{\Theta}_{kl}-\Theta^{*}_{kl}\right|^{2}\right]^{1/2}$
$\displaystyle\leq
2\kappa_{\Theta^{*}}C_{\alpha}\Delta_{f}(m,n,p)\times\sqrt{s+p}$

And

$\|\hat{\Theta}-\Theta^{*}\|_{2}\leq\|\hat{\Theta}-\Theta^{*}\|_{\infty}\leq
d\times 2\kappa_{\Theta^{*}}C_{\alpha}\Delta_{f}(m,n,p)$

where we use the definition of $\ell_{\infty}$ norm and the fact that
$\hat{\Theta}$ and $\Theta^{*}$ both have $d$ non-zeros in each row. Now we
use the fact that Frobenius norm dominates $\ell_{\infty}$ norm and (c)
follows. $\hfill\square$

##  Appendix C Figures and tables

Figure 7: Plot of diagonals of spectral density across different frequencies for VAR(1) model in 5 for $p=20$. The $k$th line represents $[f(\omega)]_{kk}$ across $\omega\in[-\pi,\pi]$. Figure 8: Plot of diagonals of spectral density across different frequencies for VARMA(2, 2) model in 5 for $p=20$. The $k$th line represents $[f(\omega)]_{kk}$ across $\omega\in[-\pi,\pi]$. Here $1\leq k\leq 5$, since for $p=10$ $f(\omega)$ has two $5\times 5$ blocks. |  |  |  | RMSE |  |
---|---|---|---|---|---|---
Family |  | Inverse periodogram |  | CGLASSO (oracle) |  | CGLASSO (BIC)
White Noise |  |  |  |  |  |
$p=10$ |  |  |  |  |  |
$n=200$ |  | 123.69 (66.17) |  | 11.59 (2.08) |  | 17.34 (2.72)
$n=400$ |  | 50.68 (17.23) |  | 8.11 (1.09) |  | 15.01 (1.49)
$p=20$ |  |  |  |  |  |
$n=200$ |  | 200.23 (783.49) |  | 14.06 (1.52) |  | 21.76 (1.71)
$n=400$ |  | 394.05 (123.59) |  | 10.88 (1.43) |  | 18.69 (1.53)
$p=50$ |  |  |  |  |  |
$n=200$ |  | - |  | 18.16 (1.34) |  | 31.07 (0.77)
$n=400$ |  | - |  | 14.21 (1.07) |  | 25.44 (0.88)
VAR(1) |  |  |  |  |  |
$p=10$ |  |  |  |  |  |
$n=200$ |  | 205.82 (137.47) |  | 17.50 (-) |  | 17.50 (-)
$n=400$ |  | 121.15 (34.07) |  | 17.99 (1.45) |  | 18.06 (1.25)
$p=20$ |  |  |  |  |  |
$n=200$ |  | 1831.27 (666.7) |  | 20.67 (-) |  | 20.67 (-)
$n=400$ |  | 489.32 (140.18) |  | 19.47 (0.81) |  | 19.47 (0.81)
$p=50$ |  |  |  |  |  |
$n=200$ |  | - |  | 20.59 (-) |  | 20.59 (-)
$n=400$ |  | - |  | 19.52 (-) |  | 19.52 (-)
VARMA(2, 2) |  |  |  |  |  |
$p=10$ |  |  |  |  |  |
$n=200$ |  | 117.13 (42.06) |  | 13.72 (2.34) |  | 15.00 (2.32)
$n=400$ |  | 62.96 (14.67) |  | 11.20 (2.03) |  | 11.48 (2.03)
$p=20$ |  |  |  |  |  |
$n=200$ |  | 2359.21 (1101.53) |  | 15.32 (1.73) |  | 20.35 (1.69)
$n=400$ |  | 446.45 (127.16) |  | 12.83 (2.01) |  | 14.80 (1.67)
$p=50$ |  |  |  |  |  |
$n=200$ |  | - |  | 16.77 (0.90) |  | 28.98 (1.28)
$n=400$ |  | - |  | 13.60 (0.86) |  | 18.67 (0.73)
Table 3: RMSE of inverted periodogram and the complex graphical lasso estimator at $\omega_{j}=\pi/2$. The RMSE (oracle) column corresponds to the minimum RMSE (in %) along the regularization path. The RMSE (in %) corresponding to the estimator with minimum BIC along the regularization paths are also reported in RMSE (BIC) column. Results are averaged over 20 independent replicates. Standard deviations (in %) are also reported in parentheses. |  |  |  | RMSE |  |
---|---|---|---|---|---|---
Family |  | Inverse periodogram |  | CGLASSO (oracle) |  | CGLASSO (BIC)
White Noise |  |  |  |  |  |
$p=10$ |  |  |  |  |  |
$n=200$ |  | 148.83 (79.25) |  | 10.31 (2.15) |  | 12.83 (2.21)
$n=400$ |  | 80.58 (52.42) |  | 8.75 (2.38) |  | 11.21 (2.73)
$p=20$ |  |  |  |  |  |
$n=200$ |  | 3620.6 (4038.01) |  | 12.49 (2.07) |  | 18.69 (2.31)
$n=400$ |  | 441.79 (222.01) |  | 9.74 (1.55) |  | 14.96 (1.63)
$p=50$ |  |  |  |  |  |
$n=200$ |  | - |  | 14.96 (1.44) |  | 28.44 (1.16)
$n=400$ |  | - |  | 11.94 (0.93) |  | 23.47 (1.18)
VAR(1) |  |  |  |  |  |
$p=10$ |  |  |  |  |  |
$n=200$ |  | 158.18 (119.3) |  | 9.49 (-) |  | 15.68 (1.65)
$n=400$ |  | 73.09 (37.48) |  | 8.69 (-) |  | 14.17 (2.40)
$p=20$ |  |  |  |  |  |
$n=200$ |  | 4439.06 (3856.06) |  | 13.55 (-) |  | 16.61 (2.15)
$n=400$ |  | 607.81 (324.17) |  | 12.65 (1.14) |  | 14.77 (1.84)
$p=50$ |  |  |  |  |  |
$n=200$ |  | - |  | 16.44 (0.48) |  | 17.30 (1.47)
$n=400$ |  | - |  | 14.74 (-) |  | 15.15 (0.52)
VARMA(2, 2) |  |  |  |  |  |
$p=10$ |  |  |  |  |  |
$n=200$ |  | 162.61 (131.66) |  | 9.64 (0.84) |  | 15.11 (2.36)
$n=400$ |  | 67.55 (23.58) |  | 7.62 (0.87) |  | 9.21 (2.16)
$p=20$ |  |  |  |  |  |
$n=200$ |  | 3174.67 (2912.83) |  | 12.04 (1.39) |  | 21.01 (2.44)
$n=400$ |  | 470.83 (270.81) |  | 9.11 (-) |  | 17.98 (1.56)
$p=50$ |  |  |  |  |  |
$n=200$ |  | - |  | 14.10 (0.83) |  | 19.85 (1.28)
$n=400$ |  | - |  | 11.16 (0.95) |  | 17.52 (0.93)
Table 4: RMSE of inverted periodogram and the complex graphical lasso estimator at $\omega_{j}=\pi$. The RMSE (oracle) column corresponds to the minimum RMSE (in %) along the regularization path. The RMSE (in %) corresponding to the estimator with minimum BIC along the regularization paths are also reported in RMSE (BIC) column. Results are averaged over 20 independent replicates. Standard deviations (in %) are also reported in parentheses. | NWR | CGLASSO |  | CGLASSO |
---|---|---|---|---|---
Family | AUROC | AUROC | Precision | Recall | Accuracy
White Noise |  |  |  |  |
$p=10$ |  |  |  |  |
$n=200$ | 97.27 (2.79) | 99.61 (0.69) | 53.45 (7.93) | 100.00 (0.00) | 81.78 (5.79)
$n=400$ | 99.68 (0.57) | 99.91 (0.28) | 59.37 (9.45) | 100.00 (0.00) | 85.56 (5.07)
$p=20$ |  |  |  |  |
$n=200$ | 96.50 (2.11) | 98.82 (1.64) | 53.04 (5.89) | 98.42 (3.01) | 90.92 (2.08)
$n=400$ | 97.99 (2.18) | 99.78 (0.63) | 51.97 (5.39) | 99.74 (1.18) | 90.55 (2.02)
$p=50$ |  |  |  |  |
$n=200$ | 96.52 (1.55) | 94.81 (2.40) | 68.60 (6.89) | 90.00 (4.72) | 97.90 (0.54)
$n=400$ | 98.18 (1.09) | 99.48 (0.53) | 62.79 (4.86) | 99.08 (1.04) | 97.58 (0.49)
VAR(1) |  |  |  |  |
$p=10$ |  |  |  |  |
$n=200$ | 74.42 (5.93) | 50.00 (-) | - | 0.00 (0.00) | 62.22 (0.00)
$n=400$ | 80.81 (7.04) | 50.25 (0.85) | 100.00 (-) | 0.49 (1.70) | 62.41 (0.64)
$p=20$ |  |  |  |  |
$n=200$ | 72.76 (4.97) | 52.70 (-) | 100.00 (-) | 5.41 (-) | 81.58 (-)
$n=400$ | 79.42 (3.51) | 50.75 (0.71) | 100.00 (0.00) | 1.50 (1.42) | 80.82 (0.28)
$p=50$ |  |  |  |  |
$n=200$ | 68.48 (3.33) | 49.96 (-) | 0.00 (-) | 0.00 (-) | 92.00 (-)
$n=400$ | 75.54 (2.70) | 50.00 (-) | - | 0.00 (-) | 92.08 (-)
VARMA(2, 2) |  |  |  |  |
$p=10$ |  |  |  |  |
$n=200$ | 76.27 (7.25) | 90.20 (6.02) | 75.97 (10.69) | 88.25 (6.34) | 81.56 (8.65)
$n=400$ | 79.62 (4.27) | 93.83 (3.69) | 76.00 (6.82) | 92.25 (6.17) | 83.22 (5.17)
$p=20$ |  |  |  |  |
$n=200$ | 73.37 (4.33) | 85.27 (4.40) | 88.98 (5.73) | 71.62 (8.67) | 92.11 (2.07)
$n=400$ | 77.96 (2.28) | 94.36 (1.65) | 77.53 (6.15) | 90.62 (3.23) | 92.34 (1.87)
$p=50$ |  |  |  |  |
$n=200$ | 77.58 (1.75) | 50.00 (0.00) | - | 0.00 (0.00) | 91.84 (0.00)
$n=400$ | 79.88 (2.10) | 88.29 (2.72) | 88.74 (3.17) | 76.90 (5.42) | 97.31 (0.43)
Table 5: AUROC for nodewise regression(NWR) and CGLASSO, precision, recall, accuracy and F1-score (each in %) of complex graphical lasso for $\omega_{j}=\pi/2$. Results are averaged over 20 replicates. Standard deviations (in %) are also reported in parentheses. | NWR | CGLASSO |  | CGLASSO |
---|---|---|---|---|---
Family | AUROC | AUROC | Precision | Recall | Accuracy
White Noise |  |  |  |  |
$p=10$ |  |  |  |  |
$n=200$ | 93.46 (4.26) | 96.71 (3.77) | 46.73 (6.85) | 97.22 (6.11) | 76.56 (5.61)
$n=400$ | 95.22 (3.86) | 97.93 (2.55) | 48.18 (6.34) | 98.33 (4.07) | 77.78 (5.90)
$p=20$ |  |  |  |  |
$n=200$ | 88.63 (5.41) | 96.01 (3.20) | 39.19 (5.21) | 95.00 (5.53) | 84.37 (3.26)
$n=400$ | 95.36 (3.13) | 98.48 (1.76) | 42.91 (5.01) | 98.42 (3.01) | 86.50 (2.66)
$p=50$ |  |  |  |  |
$n=200$ | 88.68 (3.63) | 91.48 (2.23) | 42.58 (5.63) | 84.69 (4.32) | 94.68 (1.13)
$n=400$ | 92.98 (2.95) | 96.43 (1.63) | 42.77 (4.51) | 93.78 (3.14) | 94.63 (1.02)
VAR(1) |  |  |  |  |
$p=10$ |  |  |  |  |
$n=200$ | 60.63 (8.53) | 53.00 (3.05) | 84.38 (22.90) | 6.95 (6.35) | 64.24 (2.32)
$n=400$ | 64.01 (7.95) | 50.93 (1.71) | 100.00 (0.00) | 1.86 (3.43) | 62.92 (1.29)
$p=20$ |  |  |  |  |
$n=200$ | 58.52 (5.95) | 50.32 (0.78) | 58.33 (49.16) | 0.75 (1.55) | 80.58 (0.36)
$n=400$ | 60.13 (4.20) | 50.92 (1.25) | 81.25 (37.20) | 1.93 (2.47) | 80.83 (0.53)
$p=50$ |  |  |  |  |
$n=200$ | 55.86 (2.28) | 50.00 (0.00) | - | 0.00 (0.00) | 92.08 (0.00)
$n=400$ | 58.41 (2.37) | 50.63 (0.61) | 42.47 (2.52) | 1.44 (1.21) | 92.03 (0.17)
VARMA(2, 2) |  |  |  |  |
$p=10$ |  |  |  |  |
$n=200$ | 65.19 (6.36) | 71.59 (8.46) | 90.88 (7.09) | 46.05 (16.63) | 74.04 (7.56)
$n=400$ | 68.87 (6.78) | 81.12 (6.83) | 74.44 (8.42) | 75.25. (11.75) | 77.22 (7.42)
$p=20$ |  |  |  |  |
$n=200$ | 63.09 (5.02) | 50.00 (0.00) | - | 0.00 (0.00) | 78.95 (0.00)
$n=400$ | 67.26 (4.28) | 50.00 (0.00) | - | 0.00 (0.00) | 78.95 (0.00)
$p=50$ |  |  |  |  |
$n=200$ | 65.10 (2.84) | 50.00 (0.00) | - | 0.00 (0.00) | 91.84 (0.00)
$n=400$ | 66.88 (2.56) | 50.00 (0.00) | - | 0.00 (0.00) | 91.84 (0.00)
Table 6: AUROC for nodewise regression(NWR) and CGLASSO, precision, recall,
accuracy and F1-score (each in %) of complex graphical lasso for
$\omega_{j}=\pi$. Results are averaged over 20 replicates. Standard deviations
(in %) are also reported in parentheses.