vol. 25:220231310.46298/dmtcs.99572022-08-24; 2022-08-24; 2023-08-082023-08-11

# Homomorphically Full Oriented Graphs

Thomas Bellitto1 This work was initiated while the author was a postdocoral
fellow at Department of Mathematics and Computer Science, University of
Southern Denmark (Odense, Denmark) and supported by the Independent Research
Fund Denmark under grant number DFF 7014-00037B Christopher Duffy2  Gary
MacGillivray3  LIP6, CNRS, Sorbonne Université, Paris, France
School of Mathematics and Statistics, University of Melbourne, Melbourne,
Australia
Department of Mathematics and Statistics, University of Victoria, Victoria,
Canada

###### Abstract

Homomorphically full graphs are those for which every homomorphic image is
isomorphic to a subgraph. We extend the definition of homomorphically full to
oriented graphs in two different ways. For the first of these, we show that
homomorphically full oriented graphs arise as quasi-transitive orientations of
homomorphically full graphs. This in turn yields an efficient recognition and
construction algorithms for these homomorphically full oriented graphs. For
the second one, we show that the related recognition problem is GI-hard, and
that the problem of deciding if a graph admits a homomorphically full
orientation is NP-complete. In doing so we show the problem of deciding if two
given oriented cliques are isomorphic is GI-complete.

###### keywords:

directed graph homomorphism, complexity

##  1 Introduction and Background

Oriented graphs can be considered to arise in one of two ways: as a special
class of digraphs defined by a restriction on the existence of directed
2-cycles, or from simple graphs by assigning a direction to each edge. The
distinction between these perspectives has consequences in the study of
homomorphisms of oriented graphs. For example, each leads to a different
definition of vertex colouring of oriented graphs (see the work of Feder et
al. (2003) and Sopena (2016)). We use the term _antisymmetric digraph_ to
specifically refer to digraphs with the restriction that there are no directed
2-cycles, and the term _oriented graph_ otherwise, including when the
distinction between perspectives is unimportant.

For standard graph theoretic notation we refer the reader to the seminal text
by Bondy and Murty (2008). We generally use Greek capital letters to refer to
graphs and Latin capital letters to refer to antisymmetric digraphs and
oriented graphs.

A _homomorphism_ of a graph $\Gamma$ to a graph $\Lambda$ is a function
$\phi:V(\Gamma)\to V(\Lambda)$ such that $xy\in E(\Gamma)$ implies
$\phi(x)\phi(y)\in E(\Lambda)$. When $\phi$ is a homomorphism of $\Gamma$ to
$\Lambda$ we write $\phi:\Gamma\to\Lambda$. When the existence of a
homomorphism (rather than a particular homomorphism) is of interest we write
$\Gamma\to\Lambda$. The definition of a homomorphism of a digraph $G$ to a
digraph $H$ is identical.

A homomorphism of $\Gamma$ to $\Lambda$ induces a mapping of $A(\Gamma)$ to
$A(\Lambda)$. A homomorphism $\phi:\Gamma\to\Lambda$ is called _complete_ when
both $\phi$ and the induced mapping of $A(\Gamma)$ to $A(\Lambda)$ are
surjective. If there is a complete homomorphism of $\Gamma$ to $\Lambda$, then
$\Lambda$ is called a _homomorphic image_ of $\Gamma$. The corresponding
definitions are the same for digraphs.

If $\Lambda$ is a subgraph of $\Gamma$, then a homomorphism $\phi$ of $\Gamma$
to $\Lambda$ is called a _retraction_ when $\phi(h)=h$ for every vertex $h\in
V(\Lambda)$. If there is a retraction of $\Gamma$ to $\Lambda$, then $\Lambda$
is called a _retract_ of $\Gamma$. A retract of $\Gamma$ is necessarily an
induced subgraph of $\Gamma$, but the converse is false. The corresponding
definitions for digraphs are identical.

Vertices $x$ and $y$ of a graph $G$ are called _neighbourhood comparable_ when
$N(x)\subseteq N(y)$ or $N(y)\subseteq N(x)$. Notice that if $N(x)\subseteq
N(y)$, then there is a retraction of $G$ to $G-x$. A graph $\Gamma$ is called
_homomorphically full_ when every homomorphic image of $\Gamma$ is isomorphic
to a subgraph of $\Gamma$. The homomorphically full graphs were first
characterized by Brewster and MacGillivray (1996).

###### Theorem 1.1

Brewster and MacGillivray (1996) Let $\Gamma$ be a graph. The following
statements are equivalent:

  1. (a)

$\Gamma$ is homomorphically full.

  2. (b)

If $x$ and $y$ are non-adjacent vertices of $\Gamma$, then $x$ and $y$ are
neighbourhood comparable

  3. (c)

Every homomorphic image of $\Gamma$ is isomorphic to a retract of $\Gamma$.

  4. (d)

Every homomorphic image of $\Gamma$ is isomorphic to an induced subgraph of
$\Gamma$.

  5. (e)

$\Gamma$ contains neither $2K_{2}$ nor $P_{4}$ as an induced subgraph.

  6. (f)

$\overline{\Gamma}$ is the comparability graph of an up-branching.

Homomorphic images of simple graphs are implicitly understood to be simple
graphs. If a homomorphic image of a simple graph could be a graph with loops,
then there would be no homomorphically full simple graphs: a single vertex
with a loop would be a homomorphic image of every graph.

Analogous to the definition of graphs, we say an oriented graph or
antisymmetric digraph $G$ is _homomorphically full_ when every homomorphic
image of $G$ is isomorphic to a subgraph of $G$. The two perspectives on how
an oriented graph $G$ arises are germane in understanding its homomorphic
images and the meaning of this definition. When $G$ is an antisymmetric
digraph, a _homomorphic image_ of $G$ is a digraph $H$ (which may have
directed 2-cycles) for which there is a complete homomorphism $G\to H$. When
$G$ is an oriented graph, a _homomorphic image_ of $G$ is an oriented graph
$H$ for which there is a complete homomorphism $G\to H$. In this case, two
vertices joined by a directed path of length 2 (a _$2$ -dipath_) must map to
different vertices of $H$.

For a graph $\Gamma$ and non-adjacent vertices $u,v\in V(\Gamma)$, let
$\Gamma_{uv}$ denote the graph produced by identifying $u$ and $v$ into a
single vertex named $u_{v}$. The homomorphism $\phi:\Gamma\to\Gamma_{uv}$ that
sends $u$ and $v$ to $u_{v}$ and fixes all other vertices is a complete
homomorphism. As such, $\Gamma_{uv}$ is a homomorphic image of $\Gamma$. We
call such a homomorphism _elementary_. Every homomorphism can be expressed as
a composition of elementary homomorphisms. These statements remain true when
considered for oriented graphs and antisymmetric digraphs. However for
oriented graphs we are restricted to considering pairs of vertices that are
neither adjacent nor the ends of a $2$-dipath. In any case, to check whether a
graph, oriented graph, or antisymmetric digraph is homomorphically full it is
enough to check that the target of each elementary homomorphism is isomorphic
to a subgraph.

Let $H$ be the directed path on three vertices. With Theorem 1.1 one can
verify that the underlying graph (i.e., the path on three vertices) is
homomorphically full. Interpreting $H$ as an antisymmetric digraph, there is
an elementary homomorphism that identifies the two ends of the directed path.
The resulting homomorphic image, the directed $2$-cycle, is not isomorphic to
any subgraph of $H$ and so $H$ is not homomorphically full. On the other hand,
interpreting $H$ as an oriented graph, the vertices at the end of the path
cannot be identified by an elementary homomorphism. In this case the only
homomorphic image of $H$ is $H$ itself. And so we conclude $H$ is
homomorphically full.

Let $G$ be a directed graph. We say that an ordered pair of non-adjacent
vertices, $u,v\in V(G)$ are _neighbourhood comparable_ when $N^{+}(u)\subseteq
N^{+}(v)$ and $N^{-}(u)\subseteq N^{-}(v)$ or $N^{+}(v)\subseteq N^{+}(u)$ and
$N^{-}(v)\subseteq N^{-}(u)$. As with graphs, we observe that if $u$ and $v$
are neighbourhood comparable, then, we have $G-u\cong G_{uv}$, presuming
$N^{+}(u)\subseteq N^{+}(v)$ and $N^{-}(u)\subseteq N^{-}(v)$. The implied
isomorphism here is, in some sense, trivial. Each vertex other than $v$ maps
to itself and $v$ maps to $u_{v}$. This occurs as there is a retraction $G\to
G_{uv}$ where $u_{v}$ in $G_{uv}$ is relabelled as $v$.

An oriented graph or antisymmetric digraph $G$ is homomorphically full if and
only if for all $u$ and $v$ that can be identified by an elementary
homomorphism we have that $G_{uv}$ is isomorphic to a subgraph of $G$. And so,
similar to the case for graphs, if for an oriented graph or antisymmetric
digraph $G$ every pair of vertices that can be identified by an elementary
homomorphism is neighbourhood comparable, then $G$ is necessarily
homomorphically full. We will see that the converse of this statement holds
for homomorphically full antisymmetric digraphs but not for homomorphically
full oriented graphs.

Our remaining work proceeds as follows. In Section 2 we fully classify
homomorphically full antisymmetric digraphs as those that are quasi-transitive
and whose underlying graph is homomorphically full. In doing so we provide a
theorem for homomorphically full antisymmetric digraphs analogous to Theorem
1.1. These results imply that homomorphically full antisymmetric digraphs can
be identified in polynomial time. And also that one may decide in polynomial
time if a graph is an underlying graph of a homomorphically full antisymmetric
digraph. In Section 3 we show for oriented graphs that neighbourhood
comparability does not fully characterize homomorphic fullness. This work
leads us to study, in Section 4, the problem of deciding if an oriented graph
is homomorphically full. Though the analogous problems for graphs and
antisymmetric digraphs are Polynomial, we show the problem to be GI-hard for
oriented graphs. We continue studying the complexity of problems related to
homomorphic fullness of oriented graphs in Section 5. We find that deciding if
a graph admits a homomorphically full orientation is NP-complete. We conclude
in Section 6 with discussion and further remarks.

Since the presence or absence of multiple edges in $\Gamma$ or $\Lambda$ does
not matter in the definition of a homomorphism of $\Gamma$ to $\Lambda$, we
consider only graphs in which there are no multiple edges. By contrast, the
presence of loops matters. A homomorphism of a graph can map adjacent vertices
to a vertex with a loop. These statements remain true when we replace graphs
with oriented graphs (under either interpretation). To simplify matters,
herein we assume that all graphs and oriented graphs are irreflexive. We
comment more on the nature of this problem for graphs that may have loops as
part of our further remarks in Section 6.

##  2 Homomorphically Full Antisymmetric Digraphs

We begin our study of homomorphically full antisymmetric digraphs by examining
their underlying graphs.

###### Lemma 2.1

If $G$ is a homomorphically full antisymmetric digraph, then its underlying
graph $U(G)$ is homomorphically full.

######  Proof 2.2.

Let $G$ be a homomorphically full antisymmetric digraph. Notice that each of
$G$ and $U(G)$ have the same set of elementary homomorphisms. For $uv\notin
A(G)$, if $G_{uv}$ is isomorphic to a subgraph of $G$ then $U(G_{uv})$ is
necessarily isomorphic to a subgraph of $U(G)$. As $G$ is homomorphically
full, for each $uv\notin A(G)$ we have that $G_{uv}$ is isomorphic to a
subgraph of $G$. Therefore for each $uv\notin E(U(G))$ the graph $U(G)_{uv}$
is isomorphic to a subgraph of $U(G)$. Thus $U(G)$ is homomorphically full.

We note that the converse of this lemma is false. As discussed in our
introductory remarks, an undirected path on three vertices is homomorphically
full, but the directed path on three vertices is not a homomorphically full
antisymmetric digraph.

Recall that a directed graph is _quasi-transitive_ when for each vertex $w$,
there is complete adjacency between the in-neighbours and the out-neighbours
of $w$. Quasi-transitive directed graphs were first studied and subsequently
fully classified by Ghouila-Houri (1962). A graph is an underlying graph of a
quasi-transitive digraph if and only if it is a comparability graph. Further,
every comparability graph is the underlying graph of some quasi-transitive
digraph.

######  Theorem 2.3.

An antisymmetric digraph is homomorphically full if and only if it is quasi-
transitive and its underlying graph is homomorphically full. Further, every
homomorphically full graph is the underlying graph of a homomorphically full
antisymmetric digraph

######  Proof 2.4.

Let $G$ be an antisymmetric directed graph whose underlying graph is
homomorphically full.

If $G$ is not quasi-transitive, then there exists a vertex $w$ such that there
is not complete adjacency between the in-neighbours and the out-neighbours of
$w$. That is, there exists $u,v\in V(G)$ such that $uwv$ is an directed path
of length $2$ (a $2$-dipath). The elementary homomorphism that identifies $u$
and $v$ is complete. As such $G_{uv}$ is a homomorphic image of $G$. However
$G_{uv}$ is not isomorphic to any subgraph of $G$; it contains a directed
$2$-cycle. Therefore $G$ is not a homomorphically full antisymmetric digraph.

Assume now that $G$ is quasi-transitive. Consider a pair of non-adjacent
vertices $u,v\in V(G)$. Since $U(G)$ is homomorphically full, we have, without
loss of generality, that $N(u)\subseteq N(v)$. Since $G$ is quasi-transitive,
it follows that $N^{+}(u)\subseteq N^{+}(v)$ and $N^{-}(u)\subseteq N^{-}(v)$.
Therefore $G_{uv}\cong G-u$. That is, $G_{uv}$ is isomorphic to a subgraph of
$G$. Therefore $G$ is a homomorphically full antisymmetric digraph.

Let $\Gamma$ be a homomorphically full graph. By Theorem 1.1, $\Gamma$ has no
induced $P_{4}$, and hence is a cograph. Every cograph is a comparability
graph. As proven by Ghouila-Houri (1962), every comparability graph is the
underlying graph of a quasi-transitive digraph.

As with graphs, homomorphically full antisymmetric digraphs can be classified
using neighbourhood comparability, homomorphic images and retracts. We note,
however, that such a classification does not exist for oriented graphs. We
explore this further in Section 3.

######  Theorem 2.5.

Let $G$ be an antisymmetric digraph. The following statements are equivalent:

  1. (a)

$G$ is a homomorphically full antisymmetric digraph.

  2. (b)

$G$ is quasi-transitive and its underlying graph is homomorphically full.

  3. (c)

Every pair of non-adjacent vertices of $G$ are neighbourhood comparable.

  4. (d)

Every homomorphic image of $G$ is isomorphic to a retract of $G$.

  5. (e)

Every homomorphic image of $G$ is isomorphic to an induced subgraph of $G$.

######  Proof 2.6.

Let $G$ be a homomorphically full antisymmetric digraph.

Assume $G$ is a homomorphically full antisymmetric digraph. By Lemma 2.1, we
have that $U(G)$ is homomorphically full. By Theorem 2.3 it follows that $G$
is quasi-transitive. That is, $(a)\Rightarrow(b)$.

Assume $G$ is quasi-transitive and its underlying graph is homomorphically
full. By Theorem 1.1 it follows that every pair of non-adjacent vertices of
$U(G)$ is neighbourhood comparable. Since $G$ is quasi-transitive, it follows
that $G$ has no induced $2$-dipath. Therefore every pair of non-adjacent
vertices of $G$ are neighbourhood comparable. That is, $(b)\Rightarrow(c)$.

Assume every pair of non-adjacent vertices of $G$ are neighbourhood
comparable. Let $H$ be a homomorphic image of $G$. Let $\phi:G\to H$ be a
complete homomorphism. Since $\phi$ is complete it suffices to assume it is an
elementary homomorphism. Since $\phi$ is an elementary homomorphism we have
that $H\cong G_{uv}$ for some pair of non-adjacent vertices $u$ and $v$. Since
$u$ and $v$ are neighbourhood comparable, it follows without loss of
generality that $G_{uv}\cong G-u$. Thus there exists a retraction $G\to G-u$.
And so it follows that every homomorphic image of $G$ is isomorphic to a
retract of $G$. That is, $(c)\Rightarrow(d)$. By definition, every retract of
$G$ is isomorphic to an induced subgraph of $G$. Thus $(d)\Rightarrow(e)$.

Finally, assume every homomorphic image of $G$ is isomorphic to an induced
subgraph of $G$. From the definition of homomorphically full, it follows that
$G$ is homomorphically full. That is, $(e)\Rightarrow(a)$. This completes the
proof.

Let $G$ be a homomorphically full antisymmetric digraph and let $u$ and $v$ be
a pair of non-adjacent vertices. By Theorem 2.5 we can assume, without loss of
generality, that $G_{uv}\cong G-u$. In some sense, this isomorphism is trivial
– vertices other than $u$ and $v$ may be mapped to themselves. Vertex $u_{v}$
may be mapped to $v$. By changing the label of $u_{v}$ to $v$ we arrive at a
homomorphic image that is a subgraph of $G$. The statement of Theorem 2.5
suggests that for antisymmetric digraphs we may remove the word _isomorphic_
from within the definition of homomorphically full. The same observation holds
for homomorphically full graphs. And in fact, the word _isomorphism_ does not
appear in the original definition of homomorphically full given by Brewster
and MacGillivray (1996). In the following section, we will see that the
existence of these trivial isomorphisms is not guaranteed for homomorphically
full oriented graphs.

##  3 Homomorphically Full Oriented Graphs

We turn now to the interpretation of oriented graphs as arising from simple
graphs and the subsequent definition of homomorphically full. Consider the
oriented graphs in Figure 1. Since $v$ and $v^{\prime}$ are neighbourhood
comparable we have $G-v^{\prime}\cong G_{vv^{\prime}}$. Though $u$ and
$u^{\prime}$ are not neighbourhood comparable, one can observe
$G-v^{\prime}-xu^{\prime}\cong G_{uu^{\prime}}$. One can construct such an
isomorphism by first noting that the sole vertex of degree $2$ in
$G-v^{\prime}-xu^{\prime}$ must map to the sole vertex of degree $2$ in
$G_{uu^{\prime}}$. As these are the only elementary homomorphisms of $G$, we
conclude $G$ is homomorphically full. The example shows that a theorem for
homomorphically full oriented graphs akin to Theorems 1.1 and 2.5 is not
possible. That is, this example shows that the property of homomorphic
fullness is not necessarily related to neighbourhood comparability, nor is it
necessarily related to the existence of retracts or homomorphisms to induced
subgraphs.

Figure 1: A homomorphically full oriented graph with a pair of vertices that
are not neighbourhood comparable

Recall that an _oriented clique_ is an oriented graph in which any two non-
adjacent vertices are at directed distance $2$. The name oriented clique
arises from the fact an oriented colouring (i.e., a homomorphism) of such a
graph assigns a different colour (i.e., image) for each vertex. Observe that
oriented cliques have no elementary homomorphisms. From this observation the
following two facts follow.

######  Theorem 3.1.

Every oriented clique is a homomorphically full oriented graph.

######  Theorem 3.2.

Let $G$ be a homomorphically full oriented graph. The core of $G$ is an
oriented clique.

######  Proof 3.3.

Let $G$ be a homomorphically full oriented graph and let $H$ be the oriented
graph with the fewest vertices such that there is a homomorphism $\phi:G\to H$
that is onto with respect to $A(H)$. Observe that $H$ is necessarily an
oriented clique as if otherwise, $H$ has a pair of vertices $u$ and $v$ such
that $G\to H_{uv}$. By the definition of homomorphically full, $H$ is
isomorphic to a subgraph of $G$. Therefore $H$ is isomorphic to the core of
$G$.

Let $G$ be an homomorphically full oriented graph. As our definition of
homomorphically full oriented graph restricts homomorphism to targets that are
oriented graphs, an elementary homomorphism of $G$ necessarily identifies a
pair of non-adjacent vertices that are not the ends of a $2$-dipath. That is,
an elementary homomorphism necessarily identifies vertices that are not at
directed distance either $1$ or $2$. We define the _undirected closure of
$G$_, denoted $cl(G)$, to be the graph formed from $G$ by adding an edge
between any pair of vertices at the end of $2$-dipath and then considering all
arcs as edges. That is, we have $uv\in E(cl(G))$ when $u$ and $v$ are at
directed distance at most $2$ in $G$. Note that for any $u,v\in V(G)$ we have
that there exists an elementary homomorphism $G\to G_{uv}$ if and only if
there exists an elementary homomorphism $cl(G)\to cl(G)_{uv}$.

######  Lemma 3.4.

Let $G$ be an oriented graph and let $u$ and $v$ be a pair of vertices that
are neither adjacent nor at directed distance $2$. We have
$cl(G)_{uv}\subseteq cl(G_{uv})$.

######  Proof 3.5.

Let $G$ be an oriented graph. Let $u_{v}$ denote the vertex in both
$cl(G_{uv})$ and $cl(G)_{uv}$ formed by identifying $u$ and $v$. As
$cl(G_{uv})$ and $cl(G)_{uv}$ have the same vertex set, to show
$cl(G)_{uv}\subseteq cl(G_{uv})$ it suffices to show that for all $xy\in
E(cl(G)_{uv})$ we have $xy\in E(cl(G_{uv}))$.

Consider first an arc $xy\in E(cl(G)_{uv})$ such that $x,y\neq u_{v}$. Since
$xy\in E(cl(G)_{uv})$ and $x,y\neq u_{v}$, we have that $x$ and $y$ are
adjacent in $U(G)$ or there is a $2$-dipath from $x$ to $y$ in $G$. Therefore
$x$ and $y$ are adjacent in $cl(G)$ and so $xy\in E(cl(G_{uv}))$.

Assume without loss of generality that $x=u_{v}$. If one of $uy$ or $vy$ is an
arc in $G$, then $u_{v}y$ is an arc in $G_{uv}$. Thus $xy$ is an edge in
$cl(G_{uv}$. Otherwise, neither of $uy$ or $vy$ is an arc in $G$. Thus $xy$ as
an edge in $cl(G)_{uv}$ could only have arisen from an edge of the form $uy$
or $vy$ in $cl(G)$. Therefore, there is a $2$-dipath in $G$ with one end at
$y$ and the other at one of $u$ or $v$. Since $u$ and $v$ are not adjacent,
this $2$-dipath exists in $G_{uv}$. Therefore $xy$ is an edge in $cl(G_{uv})$.

Using Lemma 3.4 we find a connection between homomorphically full graphs and
homomorphically full oriented graphs.

######  Theorem 3.6.

If $G$ is a homomorphically full oriented graph, then $cl(G)$ is
homomorphically full.

######  Proof 3.7.

Let $G$ be an homomorphically full oriented graph. Consider $cl(G)$ and
$u,v\in V(G)$ such that $u$ and $v$ are not adjacent in $cl(G)$. Since $G$ is
homomorphically full, it follows that $G_{uv}$ isomorphic to a subgraph of
$G$. That is, there exists a subgraph $H$ of $G$ such that $G_{uv}\cong H$.
Since $H$ is a subgraph of $G$, it follows that $cl(H)$ is a subgraph of
$cl(G)$. And so by Lemma 3.4 we have

$cl(G)_{uv}\subseteq cl(G_{uv})\cong cl(H)\subseteq cl(G).$

Thus, $cl(G)_{uv}$ is isomorphic to a subgraph of $cl(G)$. Therefore $cl(G)$
is homomorphically full.

######  Corollary 3.8.

A homomorphically full oriented graph has at most one nontrivial component.

######  Proof 3.9.

Let $G$ be a homomorphically full oriented graph. Notice that $U(G)$ and
$cl(G)$ have the same number of nontrivial components. The result now follows
from Theorems 1.1 and 3.6.

Statement (e) in Theorem 1.1 implies that homomorphically full graphs admit a
forbidden subgraph characterization. Similarly, statement (b) in Theorem 2.5
implies that homomorphically full antisymmetric digraphs admit a forbidden
subgraph characterization. We find this to not be the case for homomorphically
full oriented graphs.

######  Theorem 3.10.

Every oriented graph is an induced subgraph of an homomorphically full
oriented graph.

######  Proof 3.11.

By Lemma 3.1, it suffices to show that every oriented graph appears as an
induced subgraph of some oriented clique. Let $G$ be an oriented graph with
$n$ vertices.

Let $B_{n}$ be the oriented complete bipartite graph with bipartition
$(\\{a_{1},a_{2},\ldots,$ $a_{n}\\},$ $\\{b_{1},b_{2},\ldots,b_{n}\\})$
obtained by orienting the edge $a_{i}b_{j}$ from $a_{i}$ to $b_{j}$ if $i\leq
j$ and from $b_{j}$ to $a_{i}$ if $i>j$. One can verify that $B_{n}$ is an
oriented clique.

Denote by $B^{\prime}_{n}$ the oriented clique obtained from the oriented
clique $B_{n}$ by adding arcs such that the subgraph induced by
$\\{a_{1},a_{2},\ldots,a_{n}\\}$ is isomorphic to $G$.

By construction, the oriented graph $G$ is an induced subgraph of
$B^{\prime}_{n}$. The result now follows by our previous remarks.

As homomorphically full oriented graphs do not admit a forbidden subgraph
orientation, one can wonder if there is an efficient recognition algorithm for
homomorphically full oriented graphs. We study this problem in the following
section.

##  4 Deciding if $G$ is Homomorphically Full

We consider the problem of deciding if an oriented graph is in fact
homomorphically full. The corresponding decision problem for graphs and
antisymmetric digraphs are Polynomial – it is enough to compare the
neighbourhoods of pairs of non-adjacent vertices. However the example in
Figure 2 shows that such a procedure does not suffice for homomorphically full
oriented graphs. We see that $u$ and $u^{\prime}$ are not neighbourhood
comparable, yet $G_{uu^{\prime}}\cong G-v$. We use the example in Figure 2 to
show that the problem of deciding if an oriented graph is homomorphically full
is GI-hard.

Figure 2: A homomorphically full oriented graph with a pair of vertices that
are not neighbourhood comparable

We do this by first showing that the problem of deciding if a pair of oriented
cliques are isomorphic is GI-complete. For these ends we define the following
decision problems.

HOMFULL
_Instance:_ An oriented graph $G$.
_Question:_ Is $G$ homomorphically full?

OCLIQUEISO
_Instance:_ A pair of oriented cliques $G$ and $H$.
_Question:_ Is $G\cong H$?

DAGISO
_Instance:_ A pair of directed acyclic graphs $G$ and $H$
_Question:_ Is $G\cong H$?

We begin by showing OCLIQUEISO is GI-complete. For our reduction, we require
the following result from Zemlyachenko et al.

######  Theorem 4.1.

Zemlyachenko et al. (1985) DAGISO is GI-complete.

Given an instance $G,H$ of DAGISO we construct oriented cliques $G^{\star}$
and $H^{\star}$ such that $G\cong H$ if and only if $G^{\star}\cong
H^{\star}$.

We construct $G^{\star}$ using a pair of disjoint copies of $G$, say $G^{L}$
and $G^{R}$, and a fixed regular tournament $T$ with $2n+1$ vertices. Let
$V(G^{L})=\\{u^{L}_{1},u^{L}_{2},\dots,u^{L}_{n}\\}$ and
$V(G^{R})=\\{u^{R}_{1},u^{R}_{2},\dots,u^{R}_{n}\\}$. Construct $G^{\star}$ by
adding the following arcs to the oriented graph formed from the disjoint union
of $G^{L}$, $G^{R}$ and $T$:

  * •

$u_{i}^{L}u_{i}^{R}$ for all $1\leq i\leq n$;

  * •

$u_{j}^{R}u_{k}^{L}$ for all $1\leq j,k,\leq n,j\neq k$;

  * •

$u^{L}_{i}t$ for all $t\in V(T)$ and all $1\leq i\leq n$; and

  * •

$tu^{R}_{i}$ for all $t\in V(T)$ and all $1\leq i\leq n$.

######  Lemma 4.2.

Let $G$ and $H$ be directed acyclic graphs. We have $G\cong H$ if and only if
$G^{\star}\cong H^{\star}$.

######  Proof 4.3.

Let $G$ and $H$ be directed acyclic graphs with $n$ vertices. Let
$V(G)=\\{u_{1},u_{2},\dots\,u_{n}\\}$ and $V(H)=\\{v_{1},v_{2},\dots,v_{n}\\}$
Let $\phi:G\to H$ be an isomorphism. Using $\phi$ we construct an isomorphism
$\phi^{\star}:G^{\star}\to H^{\star}$ as follows:

  * •

$\phi^{\star}(t)=t$ for all $t\in V(T)$;

  * •

$\phi^{\star}(u_{i}^{L})=\phi(u_{i})^{L}$ for all $1\leq i\leq n$; and

  * •

$\phi^{\star}(u_{i}^{R})=\phi(u_{i})^{R}$ for all $1\leq i\leq n$.

Assume now that $\beta^{\star}:G^{\star}\to H^{\star}$ is an isomorphism. It
suffices to show that for all $u^{L}\in G^{L}$ we have
$\beta^{\star}(u^{L})\in V(H^{L})$. By observation $d^{+}(u^{L})\geq 2n+2$.
Therefore $d^{+}(\beta^{\star}(u^{L}))\geq 2n+2$. In $H^{\star}$ for every
$t\in V(T)$ we have $d^{+}(t)=2n$. Further we have $d^{+}(v^{R})\leq 2n-2$.
Therefore $\beta^{\star}(u^{L})\notin V(T)\cup V(H^{R})$. It then follows that
$\beta^{\star}(u^{L})\in H_{L}$. Thus restricting $\beta^{\star}$ to
$V(G^{L})$ gives an isomorphism $G^{L}\to H^{L}$. Therefore $G\cong H$.

######  Theorem 4.4.

OCLIQUEISO is GI-complete.

######  Proof 4.5.

The reduction is from DAGISO. Given an instance $G,H$ of DAGISO construct the
instance $G^{\star},H^{\star}$ of OCLIQUEISO. Such a construction can be
carried out in polynomial time. The result follows from Lemma 4.2 and Theorem
4.1.

Using Theorem 4.4, we show HOMFULL is GI-hard. Given an instance $G_{1},G_{2}$
of OCLIQUEISO we construct an instance $\hat{G}$ of HOMFULL such that
$G_{1}\cong G_{2}$ if and only if $\hat{G}$ is homomorphically full. We
construct $\hat{G}$ from a copy of $J$ (as labelled as in Figure 2), a copy of
$G_{1}$ and two copies of $G_{2}$, say $G_{2}$ and $G_{2}^{\prime}$, by adding
a new vertex $q$ and the following arcs:

  * •

$qx$ for all $x\in V(J)$; and arcs $yq$ for $y\in V(G_{1})\cup V(G_{2})\cup
V(G_{2}^{\prime})$

  * •

$y_{1}y_{2}$, $y_{2}y_{2}^{\prime}$ and $y_{2}y_{1}$ for all $y_{1}\in
V(G_{1})$, $y_{2}\in V(G_{2})$ and $y_{2}^{\prime}\in V(G_{2}^{\prime})$.

  * •

$wy_{1}$ for all $y_{1}\in V(G_{1})$.

  * •

$vy_{2}$ for all $y_{2}\in V(G_{2})$.

  * •

$uy_{2}^{\prime}$ for all $y_{2}^{\prime}\in V(G_{2}^{\prime})$.

######  Lemma 4.6.

Let $G_{1}$ and $G_{2}$ be oriented cliques. We have $G_{1}\cong G_{2}$ if and
only if $\hat{G}$ is homomorphically full.

######  Proof 4.7.

Let $G_{1}$ and $G_{2}$ be oriented cliques. By construction $\hat{G}$ has two
elementary homomorphisms: $G\to G_{uu^{\prime}}$ and $G\to G_{vv^{\prime}}$.
As $v$ and $v^{\prime}$ are neighbourhood comparable, we have
$G_{vv^{\prime}}\cong G-v^{\prime}$. Thus $\hat{G}$ is homomorphically full if
and only if $\hat{G}_{uu^{\prime}}$ is isomorphic to some subgraph of
$\hat{G}$.

Let $\phi:G_{2}\to G_{1}$ be an isomorphism We extend $\phi$ as follows such
that $\phi^{\star}:\hat{G}_{uu^{\prime}}\to\hat{G}-v^{\prime}$ is an
isomorphism. Let

  * •

$\phi^{\star}(uu^{\prime})=w$;

  * •

$\phi^{\star}(v)=u$;

  * •

$\phi^{\star}(w)=v$;

  * •

$\phi^{\star}(v^{\prime})=u^{\prime}$;

  * •

$\phi^{\star}(y_{2})=\phi(y_{2})$ for all $y_{2}\in V(G_{2})$;

  * •

$\phi^{\star}(y_{1})=\phi^{-1}(y_{1}^{\prime})$ for all $y_{1}\in V(G_{1})$;
and

  * •

$\phi^{\star}(y_{2}^{\prime})=y_{2}$ for all $y_{2}^{\prime}$ in
$V(G_{2}^{\prime})$.

Assume now $\hat{G}$ is homomorphically full. Consider $\hat{C}$, the core of
$\hat{G}$. By Theorem 3.2, $\hat{C}$ is an oriented clique. By observation we
produce a copy of $\hat{C}$ by removing $v^{\prime}$ and $u^{\prime}$ from
$\hat{G}$. We see then that $\hat{C}$ is an oriented clique with
$|V(G_{1})|+2|V(G_{2})|+4$ vertices. We also observe that neither $u^{\prime}$
nor $v^{\prime}$ are contained within a copy of $\hat{C}$. Consider now
$\hat{G}r_{uu^{\prime}}$. Identifying a pair of vertices if $\hat{G}$ cannot
change the core of $\hat{G}$ and so $\hat{C}$ is the core of
$\hat{G}_{uu^{\prime}}$. This implies that $\hat{G}_{uu^{\prime}}$ has as a
subgraph an oriented clique with $|V(G_{1})|+2|V(G_{2})|+4$ vertices.

As $\hat{G}$ is homomorphically full, $\hat{G}_{uu^{\prime}}$ is isomorphic to
some subgraph of $\hat{G}-s$ for some vertex $s\in V(\hat{G})$. Since
$\hat{G}-u^{\prime}$ has a vertex of degree $2$ (and $\hat{G}_{uu^{\prime}}$
does not), it cannot be that $s=u^{\prime}$. If $s\in V(G_{1})\cup
V(G_{2})\cup V(G_{2}^{\prime})\cup\\{q\\}$, then $\hat{G}-s$ does not contain
a copy of $\hat{C}$. Therefore $s=v^{\prime}$. Notice that
$\hat{G}-v^{\prime}$ and $\hat{G}_{uu^{\prime}}$ have the same number of arcs
and the same number of vertices. And so there is an isomorphism
$\beta:\hat{G}_{uu^{\prime}}\to\hat{G}-v^{\prime}$.

Each of $\hat{G}_{uu^{\prime}}$ and $\hat{G}-v^{\prime}$ has a single vertex
of degree three. Therefore $\beta(v^{\prime})=u^{\prime}$. In
$\hat{G}_{uu^{\prime}}$, the vertex $v^{\prime}$ has a single out-neighbour:
$w$. Therefore $\beta(w)=v$, as $v$ is the lone out-neighbour of the image of
$v^{\prime}$ under $\beta$. In $\hat{G}_{uu^{\prime}}$, the vertex
$v^{\prime}$ has a pair of in-neighbours: $q$ and $uu^{\prime}$. By
considering the direction of the arc between $q$ and $uu^{\prime}$ we see
$\beta(q)=q$ and $\beta(uu^{\prime})=w$. Since $\beta(q)=q$ and $q$ has only
four out-neighbours (three of which we have already considered), it follows
that $\beta(v)=u$. Since $\beta$ is an isomorphism, and all other vertices are
accounted for, it must be that $\beta(t)\in V(G_{1})\cup V(G_{2})\cup
V(G_{2}^{\prime})$ for all $t\in V(G_{1})\cup V(G_{2})\cup V(G_{2}^{\prime})$.
As $\beta(w)=v$ it must be that $\beta(y)\in V(G_{2})$ for all $y\in
V(G_{1})$. And so restricting $\beta$ to $V(G_{1})$ gives an isomorphism
$G_{1}\to G_{2}$.

######  Theorem 4.8.

HOMFULL is GI-hard.

######  Proof 4.9.

The reduction is from OCLIQUEISO. Given an instance $G_{1},G_{2}$ of
OCLIQUEISO construct the instance $\hat{G}$ of HOMFULL. Such a construction
can be carried out in polynomial time. The result follows from Lemma 4.6 and
Theorem 4.4

##  5 Orientations of Homomorphically Full Graphs

Theorem 2.5 implies that one may decide in polynomial time if a graph is an
underlying graph of some homomorphically full antisymmetric digraph. In this
section we consider the related problem for homomorphically full oriented
graphs. We begin by noticing a relationship between homomorphically full
graphs and homomorphically full oriented graphs.

######  Theorem 5.1.

Every orientation of a homomorphically full graph is a homomorphically full
oriented graph.

######  Proof 5.2.

Let $G$ be an orientation of a homomorphically full graph. We proceed by
verifying that any pair of vertices that can be identified by an elementary
homomorphism are neighbourhood comparable. Consider $u$ and $v$ such that $u$
and $v$ are either non-adjacent nor the ends of a $2$-dipath. If no such pair
exists, then $G$ is an oriented clique, By Theorem 3.1, $G$ is homomorphically
full. As $U(G)$ is homomorphically full, Theorem 1.1 implies, without loss of
generality, $N(u)\subseteq N(v)$. Since $u$ and $v$ are not the ends of a
$2$-dipath we have

$N^{+}(u)\cap N^{-}(v)=N^{+}(v)\cap N^{-}(u)=\emptyset.$

Therefore $N^{+}(u)\subseteq N^{+}(v)$ and $N^{-}(u)\subseteq N^{-}(v)$. That
is, $u$ and $v$ are neighbourhood comparable. This completes the proof.

Recall from Theorem 2.3 that the underlying graph of a homomorphically full
antisymmetric graph is a homomorphically full graph. From this we obtain the
following corollary to Theorem 5.1.

######  Corollary 5.3.

Every homomorphically full antisymmetric graph is a homomorphically full
oriented graph.

The converse to Theorem 5.1 is false – every oriented clique is
homomorphically full. The oriented clique given in Figure 3 has an underlying
graph that is not homomorphically full — there exist pairs of non-adjacent
vertices that are not neighbourhood comparable (see Theorem 1.1). However, the
statement of Theorem 3.6 implies that every homomorphically full oriented
graph arises as a subgraph induced by the arc set of a mixed graph whose
underlying graph is homomorphically full. In the case of the oriented graph in
Figure 3, this mixed graph is a partial orientation of a complete graph.

Figure 3: An oriented clique on $7$ vertices.

We turn now to considering the problem of deciding if an undirected graph
admits a homomorphically full orientation.

FULLORIENT
_Instance:_ A graph $\Gamma$.
_Question:_ Does $\Gamma$ admit an orientation that is homomorphically full?

We show FULLORIENT is NP-complete by way of reduction to the problem of
deciding if a graph admits an orientation as an oriented clique.

OCLIQUE
_Instance:_ A simple graph $\Gamma$.
_Question:_ Does $\Gamma$ admit an orientation as an oriented clique?

For our reduction, we require the following result of Kirgizov et al.

######  Theorem 5.4.

Kirgizov et al. (2016) OCLIQUE is NP-complete.

Given an instance $\Gamma$, of OCLIQUE we construct an instance
$\tilde{\Gamma}$ of FULLORIENT such that $\Gamma$ admits an orientation as an
oriented clique if and only if $\tilde{\Gamma}$ admits an orientation that is
homomorphically full. Let $V(\Gamma)=\\{v_{1},v_{2},\ldots,v_{n}\\}$. Let
$\Lambda$ be a complete graph on $n+2$ vertices with vertex set
$V(\Lambda)=\\{v_{1}^{\prime},v_{2}^{\prime},\ldots,v_{n}^{\prime},s,t\\}$. We
construct $\tilde{\Gamma}$ from the disjoint union of $\Gamma$ and a complete
graph by adding the following edges

  * •

$v_{i}v_{i}^{\prime}$, for all $1\leq i\leq n$, and

  * •

$tv_{i}$ for each $1\leq i\leq n$.

######  Lemma 5.5.

Let $\Gamma$ be a graph. The graph $\Gamma$ admits an orientation as an
oriented clique if and only if $\tilde{\Gamma}$ admits an orientation that is
homomorphically full.

######  Proof 5.6.

Let $\Gamma$ be a graph. Notice that no two vertices of $\tilde{\Gamma}$ are
neighbourhood comparable. Therefore $\tilde{\Gamma}$ has an orientation that
is a homomorphically full oriented graph if and only if it has an orientation
that is an oriented clique.

Suppose $\Gamma$ has an orientation as an oriented clique, $G$. Extend this
orientation to $\tilde{\Gamma}$ by orienting the edge between $v_{i}$ and
$v_{i}^{\prime}$ from $v_{i}$ to $v_{i}^{\prime}$, $1\leq i\leq n$; orienting
$\Lambda$ to be a transitive tournament, $H$, in which $s$ has in-degree 0 and
$t$ has out-degree $0$; and orienting the edges between $t$ and
$v_{1},v_{2},\ldots,v_{n}$ from $t$ to $v_{i}$, $1\leq i\leq n$.

Since $G$ and $H$ are oriented cliques, it remains to verify that there is a
directed path of length at most 2 between each vertex of $G$ and each vertex
of $H-t$. For $x\in V(H)-\\{t\\}$ and $1\leq i\leq n$ there is a $2$-dipath
$x,t,v_{i}$. Thus this orientation of $\tilde{\Gamma}$ is an oriented clique,
and hence is a homomorphically full oriented graph.

Now suppose $\tilde{\Gamma}$ has an orientation $\tilde{G}$ that is a
homomorphically full oriented graph. As noted above, this orientation
$\tilde{G}$ is an oriented clique. Let $G$ and $H$ respectively be the
subgraphs of $\tilde{G}$ induced by the vertex sets of $\Gamma$ and $\Lambda$.
Since there is no path of length 2 in $\tilde{\Gamma}$ joining a vertex of
$\Gamma$ and a vertex of $\Lambda$, no $2$-dipath joining vertices of $G$
contains a vertex of $H$. Therefore $G$ is an oriented clique. And so $\Gamma$
admits an orientation as an oriented clique.

######  Theorem 5.7.

FULLORIENT is NP-complete.

######  Proof 5.8.

The transformation is from OCLIQUE. Given an instance $\Gamma$ of OCLIQUE
construct the instance $\tilde{\Gamma}$ of FULLORIENT. Such a construction can
be carried out in polynomial time. The result follows from Lemma 5.5 and
Theorem 5.4

##  6 Further Remarks and Future Work

The study of homomorphisms oriented graphs often goes hand-in-hand with that
of $2$-edge-coloured graphs. The literature is brimming of examples where
similar looking results and methods appear for these objects. For example, see
results for homomorphisms of oriented and $2$-edge coloured planar graphs by
Alon and Marshall (1998) and by Raspaud and Sopena (1994).

Emulating the results in Section 2 for $2$-edge-coloured graphs would require
extending the notion of quasi-transitivity to $2$-edge-coloured graphs. As
shown by Duffy and Mullen (2023), the classification of those graphs that
admit a $2$-edge-colouring with a property analogous to quasi-transitivity
results in a classification that is much less natural than that for oriented
graphs. As such we expect discovering the analogous results for $2$-edge-
coloured graphs to require significant work. Similarly, emulating the results
in Section 5 for $2$-edge-coloured graphs will require significant work. It it
unknown if a result analogous to Theorem 5.4 holds for a $2$-edge-coloured
version of the problem.

The result of Theorem 1.1 assumes that both the input graph and the target
graph of the homomorphism are irreflexive. As shown by Huang and MacGillivray
(2013), statements in this theorem corresponding to (a) through (d) are also
equivalent for reflexive graphs, but not for reflexive digraphs. Note that the
definition of neighbourhood comparability differs slightly to account for the
loops, as there is no assumption that adjacent vertices must have the
different images under a homomorphism. In the case of reflexive graphs,
statements (e) and (f) respectively become “$G$ has none of $C_{4}$, $P_{4}$,
$2K_{2}$ as an induced subgraph, i.e., $G$ is a threshold graph” and
“$\overline{G}$ is the comparability graph of a threshold order”. The
homomorphically full reflexive semi-complete digraphs are characterized in the
same paper. The complete characterization of homomorphically full reflexive
and irreflexive digraphs remains open.

## References

  * Alon and Marshall (1998) N. Alon and T. Marshall.  Homomorphisms of edge-colored graphs and coxeter groups.  _Journal of Algebraic Combinatorics_ , 8(1):5–13, 1998.
  * Bondy and Murty (2008) J. Bondy and U. Murty.  Graph Theory, 2008.
  * Brewster and MacGillivray (1996) R. Brewster and G. MacGillivray.  Homomorphically full graphs.  _Discrete Applied Mathematics_ , 66(1):23–31, 1996.
  * Duffy and Mullen (2023) C. Duffy and T. Mullen.  An analogue of quasi-transitivity for edge-coloured graphs.  _Discussiones Mathematicae Graph Theory_ , 2023.  to appear.
  * Feder et al. (2003) T. Feder, P. Hell, and B. Mohar.  Acyclic homomorphisms and circular colorings of digraphs.  _SIAM J. Discrete Math._ , 17(1):161–169, 2003\.
  * Ghouila-Houri (1962) A. Ghouila-Houri.  Caractérisation des graphes non orientés dont on peut orienter les arětes de manière à obtenir le graphe d’une relation d’ordre.  _C. R. Acad. Sci. Paris_ , 254:1370–1371, 1962.
  * Huang and MacGillivray (2013) J. Huang and G. MacGillivray.  Homomorphically full reflexive graphs and digraphs.  _Journal of Canadian Computing and Combinatorial Mathematics_ , 85(4):49–64, 2013.
  * Kirgizov et al. (2016) S. Kirgizov, R. Duvignau, and J. Bensmail.  The complexity of deciding whether a graph admits an orientation with fixed weak diameter.  _Discrete Mathematics & Theoretical Computer Science_, 17, 2016\.
  * Raspaud and Sopena (1994) A. Raspaud and É. Sopena.  Good and semi-strong colorings of oriented graphs.  _Inform. Process. Lett_ , 51:171–174, 1994.
  * Sopena (2016) É. Sopena.  Homomorphisms and colourings of oriented graphs: An updated survey.  _Discrete Mathematics_ , 339(7):1993–2005, 2016\.
  * Zemlyachenko et al. (1985) V. N. Zemlyachenko, N. M. Korneenko, and R. I. Tyshkevich.  Graph isomorphism problem.  _Journal of Soviet Mathematics_ , 29(4):1426–1481, 1985.


# Non-Hermitian band theory in all dimensions: uniform spectra and skin effect

Haiping Hu1, 2<EMAIL_ADDRESS>1Beijing National Laboratory for Condensed
Matter Physics, Institute of Physics, Chinese Academy of Sciences, Beijing
100190, China  2School of Physical Sciences, University of Chinese Academy of
Sciences, Beijing 100049, China

###### Abstract

The non-Hermitian skin effect is an iconic phenomenon, characterized by the
aggregation of eigenstates near the system boundaries in non-Hermitian
systems. While extensively studied in one dimension, understanding the skin
effect and extending the non-Bloch band theory to higher dimensions poses a
formidable challenge, primarily due to infinite lattice geometries or open
boundary conditions. This work adopts a point-gap perspective and presents a
unified non-Hermitian band theory that governs skin effects across all spatial
dimensions. We introduce the concept of uniform spectra and reveal that
regardless of lattice geometry, their energy spectra are uniformly given by
the uniform spectra, even though their manifestations of skin modes may
differ. Building on the uniform spectra, we demonstrate how to account for the
skin effect in generic lattice cuts and establish the connections of skin
modes across different geometric shapes via momentum-basis transformations.
Our findings highlight the pivotal roles played by point gaps, offering a
unified understanding of the non-Hermitian skin effect in all dimensions.

Introduction.—Non-Hermitian systems have emerged as a captivating realm of
exploration in recent years [1, 2, 3, 4, 5, 6], encompassing a wide range of
classical wave systems such as lossy photonic crystals [7, 8, 9, 10, 11, 12,
13] or acoustic cavities [14, 15, 18, 16, 17], ultracold atoms [19, 20, 21],
and electronic systems hosting quasiparticles of finite lifetimes [22, 23,
24]. The breaking of Hermiticity enables the appearance of complex
eigenenergies, giving rise to intrinsic phenomena that lack analogues in
Hermitian systems. A prototypical example is the non-Hermitian skin effect
(NHSE) [25, 27, 26, 28, 29, 30, 31, 33, 34, 35, 32], which exhibits distinct
energy spectra under different boundary conditions and the localization of a
large number of eigenmodes at the boundaries. Experimental observations of the
NHSE have been reported in various platforms [36, 37, 38, 39], and potential
applications, such as unidirectional amplifiers [40], optical funnels [41],
high-efficiency energy harvesting [42], and enhanced sensors [43, 44, 45],
have been explored.

The complex energy spectra bring novel notions to non-Hermitian systems such
as point gap [46, 47, 48, 49, 50]. In Hermitian Hamiltonians, all
eigenenergies are real, and only line gaps are allowed. However, in the non-
Hermitian case, the eigenenergies may exhibit diverse patterns [51, 28, 29] on
the complex plane, deviating from a specific reference point, i.e., a point
gap. At the heart of the NHSE lies the point gap. It dictates the
supersensitivity of the complex energy spectrum to the imposed boundary
condition or threading an imaginary flux [29, 33, 52], challenging the
conventional Bloch band theory. A synopsis of one-dimensional (1D) non-
Hermitian band theory involves replacing the Bloch wave vector $k\rightarrow
k+i\kappa$ to account for the presence of skin modes. With the localization
properties of these skin modes encoded in $\kappa$, this analytical
continuation bridges the non-Hermitian band structures under different
boundary conditions, reinstating the usual bulk-edge correspondence.

Figure 1: Sketch of lattice cuts and open boundary conditions (OBC). (a) 1D
case: OBC is achieved by cutting off the lattice across a single bond. (b) 2D
case: Open boundary can be oriented in any direction, leading to diverse
geometric shapes (in different colors) defined by the lattice cut.

Extending the non-Bloch band theory to higher dimensions, however, presents
formidable challenges. Higher-dimensional systems introduce complexities due
to the vast diversity of lattice geometries and open boundary conditions (OBC)
[See Fig. 1]. The lattice cuts may influence the presence and localizations of
skin modes [53]. Moreover, the vexing numerical errors [54, 55, 56] seem
unavoidable, especially when the system size is large. Previous investigations
of higher-dimensional non-Hermitian systems [57, 58, 59] have mostly been
conducted on a case-by-case basis. Recent advancements have shed light on the
understanding of NHSE in higher dimensions. For instance, a global criterion
has been proposed that relates the occurrence of NHSE to the spectral area
[53]. An elegant formulation [60] connects the spectral density to the
mathematical object Amoeba. Additionally, a dynamical degeneracy splitting has
been introduced to characterize the anisotropic decay behaviors [61, 62].
Despite these developments, fundamental questions regarding NHSE in higher
dimensions remain elusive: What is the topological origin of NHSE in higher
dimensions? How are skin effects with distinct lattice cuts interrelated, and
how can we account for the energy spectra and skin effects across various
lattice geometries in a unified way?

In this paper, we tackle these problems by presenting a unified non-Hermitian
band theory that applies to all spatial dimensions. Drawing insights from the
1D case with point gaps, we introduce the key notion of uniform spectra
($\sigma_{U}$) from the perspective of inserting imaginary flux. We illustrate
that the uniform spectra are lattice-cut independent and precisely describe
the energy spectra for any lattice geometries. Based on the uniform spectra,
we reveal that the skin modes on different lattice geometries can be treated
as different “projections” of the same entity, which are further related
through momentum-basis transformations.

Analytical continuation.—Let us first revisit the well-established non-Bloch
band theory in 1D. The Hamiltonian on a 1D lattice is expressed as:

$\displaystyle H=\sum_{i,j=1}^{L}t_{i-j}c_{i}^{{\dagger}}c_{j},$ (1)

where $c_{i}$ represents the annihilation operator on the $i$-th site. In the
case of a multi-band system, the internal degrees of freedom (e.g., spin,
sublattice) can be incorporated into the annihilation/creation operators.
Through Fourier transformation into momentum space, the Hamiltonian takes the
Bloch form:

$\displaystyle H(k)=\sum_{m=-p}^{q}t_{m}e^{imk}.$ (2)

Here $p\geq 0$ and $q\geq 0$ represent the hopping range to the left and right
side, respectively. The energy spectra under periodic boundary condition
(PBC), are given by $\sigma_{PBC}=\\{H(k),~{}|e^{ik}|=1\\}.$ The eigenmodes
manifest as Bloch waves that extend throughout the entire lattice.

To describe the skin modes under OBC, the non-Bloch band theory comes into
play by replacing the Bloch wave vector $k\rightarrow k+i\kappa$ to
incorporate the localization of the skin modes. The Bloch Hamiltonian is
analytically continued to $H(\beta)$ with $\beta=e^{ik}\in\mathbb{C}$. The
energy spectra under OBC are extracted from the characteristic polynomial
(ChP):

$\displaystyle f(E,\beta)=\det(H(\beta)-E)=\sum_{m=-p}^{q}\beta^{m}-E,$ (3)

which is a Laurent series of two complex variables $(E,\beta)$. For a given
$E$, one can find $p+q$ solutions of $\beta$. Sorting them by the absolute
value, $|\beta_{1}(E)|\leq|\beta_{2}(E)|\leq\ldots\leq|\beta_{p+q}(E)|$, it
turns out that OBC energy spectra are given by the condition [25, 26]:

$\displaystyle\sigma_{OBC}=\\{E,~{}|\beta_{p}(E)|=|\beta_{p+1}(E)|\\}.$ (4)

The solutions $(\beta_{p}(E),\beta_{p+1}(E))$ satisfying
$|\beta_{p}(E)|=|\beta_{p+1}(E)|$ define the generalized Brillouin zone, with
their absolute values determining the localization lengths of the skin modes.

Now, let us examine the $d$D with Bloch Hamiltonian
$H(\bm{k})=H(k_{1},k_{2},...,k_{d})$. The first complexity we encounter is the
selection of boundary cuts. There are infinitely many lattice geometries, as
depicted in Fig. 1(b). There is no guarantee that different geometric shapes
will yield the same OBC spectra, nor is there a prior rule to connect skin
modes on different lattice geometries [53]. Furthermore, it is not clear how
to handle irregular shapes, such as the pentagon shown in Fig. 1(b). So, how
should we address these diverse situations within the unique Bloch Hamiltonian
$H(\bm{k})$? The second difficulty arises from the algebraic aspects. Let us
formally replace the Bloch wave vector with its non-Bloch form for each
lattice momentum: $k_{j}\rightarrow k_{j}+i\kappa_{j}$. Denoting
$\beta_{j}=e^{ik_{j}}$ and analytically continuing it to the entire complex
plane with Hamiltonian $H(\beta_{1},\beta_{2},...,\beta_{d})$, the
eigenspectra of the system are determined by the ChP:

$\displaystyle
f(E,\beta_{1},\beta_{2},...,\beta_{d})=\det(H(\beta_{1},\beta_{2},...,\beta_{d})-E).$
(5)

The ChP is an algebraic equation with $1+d$ complex variables. Note that, as a
Laurent series for each individual $\beta_{j}$, its maximum order may differ
(unlike $p,q$ in the 1D case). For a given $E$, there exist infinitely many
solutions of $(\beta_{1},\beta_{2},...,\beta_{d})$, and it seems hard to
generalize the condition $|\beta_{p}(E)|=|\beta_{p+1}(E)|$ [60].

Point gap and uniform spectra.—Our strategy is to adopt a point-gap
perspective and examine the spectral evolution by introducing an imaginary
flux. In the context of 1D NHSE, the PBC spectra form closed loops on the
complex energy plane. The OBC spectra are entirely contained within these
spectral loops, as shown in Fig. 2(a). By introducing an imaginary flux, the
PBC spectral loop undergoes deformation through a minimal coupling
$k\rightarrow k-ir$. It corresponds to an imaginary gauge transformation on
the system: $H(k)\rightarrow H(k-ir)$. This transformation does not alter the
OBC spectra, as it is implemented as a similarity transformation at the matrix
level. Remarkably, the OBC spectra $\sigma_{OBC}$ remain enclosed within the
deformed spectral loops for all possible flux strengths [29]:

$\displaystyle\sigma_{OBC}\subseteq\mathop{\bigcap}\limits_{|\beta|\in(0,\infty)}Sp(|\beta|).$
(6)

Here, $Sp(|\beta|)$ denotes the region enclosed by the deformed spectral loop
(including the loop itself). The term “enclosed” refers to a non-zero spectral
winding number with respect to the fixed $|\beta|$:

$\displaystyle w(E)=\frac{1}{2\pi i}\oint_{0}^{2\pi}\partial_{\theta}\log
f(E,|\beta|e^{i\theta}).$ (7)

Physically, the spectral region $Sp(|\beta|=1)$ corresponds to the energy
spectra under half-infinite boundary conditions and is bounded by
$\sigma_{PBC}$ [29]. It is evident that the 1D NHSE originates from the
existence of point gap: the point gap with a nonzero $w(E)$ within the PBC
spectra ($|\beta|=1$) would eventually be intersected by some deformed loops
corresponding to some flux strengths. By taking the intersections in Eq. (6),
the OBC spectra must differ from the PBC spectra.

Figure 2: Different types of energy spectra. (a) The 1D case with model
$H(\beta)=\beta+\beta^{-1}+\frac{2}{5}\beta^{-2}$. It displays the PBC spectra
$\sigma_{PBC}$ (blue loop), OBC spectra $\sigma_{OBC}$ (red arcs), and the
rescaled spectra $Sp(0.8)$ (green region), $Sp(1)$ (blue region), $Sp(2)$
(orange region). (b) The 2D case with model
$H(\beta_{1},\beta_{2})=\beta_{1}+\frac{1}{2}\beta_{1}^{-1}+\beta_{2}+\frac{1}{2}\beta_{2}^{-1}+2\beta_{1}\beta_{2}$.
It displays the PBC spectra $\sigma_{PBC}$ (blue region), rescaled spectra
$Sp(1,1)$ (blue region and shading region) and $Sp(0.8,0.8)$ (green region),
and the uniform spectra $\sigma_{U}$ (red region).

This perspective can be readily extended to higher dimensions. By inserting
$d$ imaginary fluxes along each direction, we define:

$\displaystyle
Sp(|\beta_{1}|,|\beta_{2}|,...,|\beta_{d}|):=\\{E,~{}\sum_{j=1}^{d}|w_{j}(E)|\neq
0\\},$ (8) $\displaystyle\textrm{with}~{}w_{j}(E)=\frac{1}{2\pi
i}\oint_{0}^{2\pi}\partial_{\theta_{j}}\log
f(E,\beta_{1},\beta_{2},...,\beta_{d}).$ (9)

Here, $w_{j}(E)$ is the winding number along the $j$-th direction. The
condition $\sum_{j=1}^{d}|w_{j}|\neq 0$ captures the intuitive notion that the
NHSE can arise from a point gap in any direction. For a fixed set of rescaling
factors $(|\beta_{1}|,|\beta_{2}|,...,|\beta_{d}|)$,
$Sp(|\beta_{1}|,|\beta_{2}|,...,|\beta_{d}|)$ describes the spectral region
where at least one of the $d$ directions has nonzero spectral winding or point
gap. Similar to the 1D case, $Sp(|\beta_{1}|,|\beta_{2}|,...,|\beta_{d}|)$ has
a geometric interpretation, encompassing both the rescaled Bloch spectra and
the enclosed region. To visualize this, let us consider a 2D model with
Hamiltonian
$H(\beta_{1},\beta_{2})=\beta_{1}+\frac{1}{2}\beta_{1}^{-1}+\beta_{2}+\frac{1}{2}\beta_{2}^{-1}+2\beta_{1}\beta_{2}$.
As shown in Fig. 2(b), $Sp(1,1)$ contains both the PBC spectra
$\sigma_{PBC}=H(|\beta_{1}|=|\beta_{2}|=1)$ (in blue) and the smaller shaded
region inside with nonzero winding numbers $w_{1}=w_{2}=1$. For another
rescaling $|\beta_{1}|=|\beta_{2}|=0.8$, we can see the OBC spectra are also
inside $Sp(0.8,0.8)$. With varying the rescaling factors, we define the
uniform spectra $\sigma_{U}$ as the intersection of all $Sp$’s:

$\displaystyle\sigma_{U}=\mathop{\bigcap}\limits_{|\beta_{j}|\in(0,\infty),i=1,2,...,d}Sp(|\beta_{1}|,|\beta_{2}|,...,|\beta_{d}|).$
(10)

Geometry-independence.—We aim to relate the uniform spectra $\sigma_{U}$ with
various lattice geometries. So far, we have not yet specified any particular
lattice geometry. To facilitate our discussion, we define regular lattice cuts
as geometric shapes in $d$D that can be labeled by $d$ independent lattice
momenta. Regular cuts correspond to parallelograms in 2D and parallelepipeds
in 3D. Otherwise, we refer to shapes that do not meet this criterion as
irregular lattice cuts.

Theorem: The OBC spectra for any regular lattice geometry are given by uniform
spectra:

$\displaystyle\sigma_{U}=\sigma_{OBC}~{}\textrm{for any regular lattice cut}.$
(11)

The proof consists of three steps. First, any lattice cut yields the same
uniform spectra $\sigma_{U}$. It should be noted that in our analysis, the
representation of the ChP $f(E,\beta_{1},\beta_{2},...,\beta_{d})$ using
analytical continuation $\beta_{j}=e^{ik_{d}}$ has prescribed a momentum basis
$(\hat{k}_{1},\hat{k}_{2},...,\hat{k}_{d})$, which is associated with a
particular lattice cut. Specifically, the choice of momenta
$(k_{x},k_{y},k_{z})$ corresponds to the standard cubic cut along the
$(\hat{x},\hat{y},\hat{z})$ directions. The lattice momenta associated with
two different regular shapes are related via a transformation:
$\bm{k}^{\prime}=S\bm{k}$. For instance, in 2D, a square-shaped lattice and a
diamond-shaped lattice, as depicted in Fig. 1(b), are related through the
transformation:

$\displaystyle(k_{1}^{\prime},k_{2}^{\prime})^{T}=\frac{1}{\sqrt{2}}\left(\begin{array}[]{cc}1&1\\\
1&-1\\\ \end{array}\right)(k_{1},k_{2})^{T}.$

Importantly, $\sigma_{U}$ does not depend on such transformations. A
transformation $S$ would induce a shift in the rescaling factors. For
instance, a 2D Hamiltonian $\beta_{1}+2\beta_{2}$ transforms into
$\beta_{1}^{\prime}\beta_{2}^{\prime}+2\beta_{1}^{\prime}(\beta_{2}^{\prime})^{-1}$
with the aforementioned transformation. However, our definition of
$\sigma_{U}$ in Eq. (10) contains all possible rescaling factors
$(|\beta_{1}|,|\beta_{2}|,...,|\beta_{d}|)$. It is evident that sweeping all
the rescalings $(|\beta_{1}|,|\beta_{2}|)$ is equivalent to sweeping all the
rescalings $(|\beta_{1}^{\prime}|,|\beta_{2}^{\prime}|)$. Additionally, the
transformation is nonsingular $\det S\neq 0$ and preserves the condition
$\sum_{j}|w_{j}(E)|\neq 0$. By taking the intersections in Eq. (10),
$\sigma_{U}$ remains unchanged.

The second step involves a known connection [60] that relates the OBC spectra
to another spectra $\sigma_{\textrm{Amoeba}}$ based on the mathematical
concept Amoeba. With a prescribed basis, such as
$\bm{k}=(k_{1},k_{2},...,k_{d})$, it can be shown that
$\sigma_{\textrm{Amoeba}}=\sigma_{OBC}$ [60] through Szegö’s strong limit
theorem [63, 64, 65, 66, 67] and logarithmic potential theory [68]. The
specific basis chosen corresponds to a definite regular lattice cut in our
definition. The third step is to demonstrate that under the same momentum
basis, $\sigma_{U}=\sigma_{\textrm{Amoeba}}$. The details [69] can be found in
the Supplementary Materials, and the key is to establish the connection
between the central hole in the Amoeba and the point gap in Eq. (8). By
combining all three steps, we conclude that $\sigma_{U}$ is the OBC spectra
under any regular lattice cut. It is obvious that the relation Eq. (6) can be
strengthened to an identity as a special case of the theorem.

NHSE on generic lattice geometries.—We now shift our focus to generic lattice
shapes and establish a connection between NHSE on different geometries.
Drawing insights from the theorem that the spectra on any lattice cuts
uniformly tend to $\sigma_{U}$, the skin modes on seemingly distinct lattices
can be regarded as different “projections” of the same entity. This
observation elucidates why skin modes exhibit varying degrees of localization
on different lattice shapes. Formally, let us denote the lattice momenta
associated with two different cuts as $\bm{k}=(k_{1},k_{2},...,k_{d})$ and
$\bm{k}^{\prime}=(k^{\prime}_{1},k^{\prime}_{2},...,k^{\prime}_{d})$, related
through
$(k^{\prime}_{1},k^{\prime}_{2},...,k^{\prime}_{d})=S(k_{1},k_{2},...,k_{d})$.
Considering the equal status of the inverse localization length (ILL) and
lattice momentum in the analytical continuation
$\beta_{j}=|\beta_{j}|e^{ik_{j}}=e^{ik_{j}+\log|\beta_{j}|}$, we obtain that
the ILL obeys the same transformation:

$\displaystyle\log|\bm{\beta}^{\prime}|=S\log|\bm{\beta}|,$ (13)

with $\log|\bm{\beta}|=(\log|\beta_{1}|,\log|\beta_{2}|,...,|\log\beta_{d}|)$
and
$\log|\bm{\beta}^{\prime}|=(\log|\beta^{\prime}_{1}|,\log|\beta^{\prime}_{2}|,...,|\log\beta^{\prime}_{d}|)$.

For arbitrary lattice shapes, the strategy is to adopt a local perspective and
decompose complex shapes, such as irregular polygons (2D) and polyhedra (3D),
into manageable components. For example in 2D, an $N$-polygon has $N$
boundaries and each edge is associated with a specific cut direction denoted
as $\hat{k}^{(1)},\hat{k}^{(2)},...,\hat{k}^{(N)}$, as sketched in Fig. 3(a).
The corners where two neighboring boundaries meet are identified by pairs of
cut directions ($d$ cut directions in $d$D), namely
$(\hat{k}^{(j)},\hat{k}^{(j+1)}),(j=1,2,...,N)$ with
$\hat{k}^{(N+1)}=\hat{k}^{(1)}$. To explore the skin modes on such complex
shapes, we need to consider $N$ regular shapes, i.e., parallelograms. Taking
the thermodynamic limit smears out the finite-size effects, and the skin modes
on a generic geometry arise from the projections onto the parallelogram at
each corner.

Figure 3: Analysis of skin modes on generic lattice geometries. (a) Sketch of
the decomposition of an $N$-polygon into $N$ simple parallelograms at the
corners. Each parallelogram is formed by two neighboring cuts of the
$N$-polygon. (b) Density distributions of the eigenstates for the 2D Hatano-
Nelson model. The lattice cut is along the $(\hat{x}+2\hat{y})$ direction. The
parameters $(t_{1},t_{-1},r_{1},r_{-1})$ for ①②③④ are
$(1,2,2,1);(1,2,2,\sqrt{2});(1,2,2,3);(1,1/2,2,5/3)$, respectively.

We illustrate the local perspective and relations of skin modes in the 2D
Hatano-Nelson model with Hamiltonian
$H(k_{x},k_{y})=t_{1}e^{ik_{x}}+t_{-1}e^{-ik_{x}}+r_{1}e^{ik_{y}}+r_{-1}e^{-ik_{y}}$.
It has non-reciprocal hoppings along both $x$ and $y$ directions. With a cut
along the $(1,2)$ direction as depicted in Fig. 3(b), the seven corners are
grouped into three types: corners 2, 3, 6; corners 1, 4, 5; and corner 7. The
associated basis transformations are

$\displaystyle S_{1,4,5}=\left(\begin{array}[]{cc}1&0\\\
\frac{1}{\sqrt{5}}&\frac{2}{\sqrt{5}}\end{array}\right);~{}~{}~{}S_{7}=\left(\begin{array}[]{cc}\frac{1}{\sqrt{5}}&\frac{2}{\sqrt{5}}\\\
0&1\end{array}\right).$

With the chosen parameters, the ILL relevant for corner 2, 3, 6 are $①:(-\log
2,\log 2)$, $②:(-\log 2,\frac{\log 2}{2})$, $③:(-\log 2,\log\frac{2}{3})$, and
$④:(\log 2,\log\frac{6}{5})$ for the four panels in Fig. 3. The sign inside
the brackets indicates the localization direction, determining the emergence
of skin modes at corner 6 in ①②) and corner 3 in ④. Similarly, for corner 1,
4, 5, the transformed ILL in ①②③④ are $(-\log 2,\frac{1}{\sqrt{5}}\log 2)$,
$(-\log 2,0)$, $(-\log 2,-\frac{1}{\sqrt{5}}\log
2+\frac{2}{\sqrt{5}}\log\frac{2}{3})$, and $(\log 2,\frac{1}{\sqrt{5}}\log
2+\frac{2}{\sqrt{5}}\log\frac{6}{5})$, indicating the presence of skin modes
at corner 4 in ①, corner 1 in ③, and corner 5 in ④. Notably in ②, the skin
modes extend along the cut due to the vanishing of the second component in the
ILL. One can also check corner 7 with the transformation $S_{7}$ to verify the
presence of skin modes in ③.

Conclusion and discussion.—In conclusion, we present a comprehensive non-
Hermitian band theory across all dimensions, expanding upon the point-gap
perspective of 1D NHSE. We demonstrate that the OBC spectra for any lattice
geometry are given by the uniform spectra $\sigma_{U}$. We further reveal that
the skin modes associated with different lattice cuts are related through
basis transformations and provide insights into handling arbitrary lattice
geometries from a local viewpoint.

Our work indicates that NHSE in all dimensions originates from the inherent
point-gap topology. It provides guidelines for manipulating skin modes via the
appropriate tailoring of lattices in band engineering. We note that our
formulation only addresses the macroscopic “skin” modes, with their number
scaling as $O(L^{d})$. Other types of skin modes, e.g., higher-order skin
modes [70, 71] and hybrid skin modes [72, 74, 75, 76, 77, 73], which have a
band-topology origin and scale as $O(L^{j})$ with $j<d$, fall outside the
scope of this paper. Additionally, we acknowledge the unresolved issue of the
geometry-dependent skin effect [53]. Different lattice cuts exhibit varying
densities of states. And with fine-tuned boundaries, the skin modes may
completely vanish, thereby violating the transformation relation Eq. (13). A
pertinent question is: Can we establish a generic classification of NHSE based
on such geometry dependence? Exploring these special cases remains an
intriguing topic for future study.

###### Acknowledgements.

This work is supported by the National Key Research and Development Program of
China (Grant No. 2022YFA1405800) and the start-up grant of IOP-CAS.

## References

  * [1] C. M. Bender, Making sense of non-Hermitian Hamiltonians, Rep. Prog. Phys. 70, 947 (2007).
  * [2] R. El-Ganainy, K. G. Makris, M. Khajavikhan, Z. H. Musslimani, S. Rotter, and D. N. Christodoulides, Non-Hermitian physics and PT symmetry, Nat. Phys. 14, 11 (2018).
  * [3] N. Moiseyev, Non-Hermitian Quantum Mechanics (Cambridge University Press, New York, 2011).
  * [4] Y. Ashida, Z. Gong, and Masahito Ueda, Non-Hermitian Physics, arXiv:2006.01837.
  * [5] E. J. Bergholtz, J. C. Budich, and F. K. Kunst, Exceptional topology of non-Hermitian systems, Rev. Mod. Phys. 93, 015005 (2021).
  * [6] K. Ding, C. Fang, and G. Ma, Non-Hermitian Topology and Exceptional-Point Geometries, arXiv: 2204.11601.
  * [7] T. Ozawa et al., Topological photonics, Rev. Mod. Phys. 91, 015006 (2019).
  * [8] L. Feng, R. El-Ganainy, and L. Ge, Non-Hermitian photonics based on parity–time symmetry, Nature Photonics 11, 752 (2017).
  * [9] A. Regensburger, C. Bersch, M.-A. Miri, G. Onishchukov, D. N. Christodoulides, and U. Peschel, Parity-time synthetic photonic lattices, Nature (London) 488, 167 (2012).
  * [10] L. Feng, Z. J. Wong, R.-M. Ma, Y. Wang, and X. Zhang, Single-mode laser by parity-time symmetry breaking, Science 346, 972 (2014).
  * [11] B. Zhen, C. W. Hsu, Y. Igarashi, L. Lu, I. Kaminer, A. Pick, S.-L. Chua, J. D. Joannopoulos, and M. Soljačić, Spawning rings of exceptional points out of Dirac cones, Nature (London) 525, 354 (2015).
  * [12] H. Zhou, C. Peng, Y. Yoon, C. W. Hsu, K. A. Nelson, L. Fu, J. D. Joannopoulos, M. Soljačić, and B. Zhen, Observation of bulk Fermi arc and polarization half charge from paired exceptional points, Science 359, 1009 (2018).
  * [13] M. A. Bandres, S. Wittek, G. Harari, M. Parto, J. Ren, M. Segev, D. N. Christodoulides, and M. Khajavikhan, Topological insulator laser: Experiments, Science 359, eaar4005 (2018).
  * [14] K. Ding, G. Ma, M. Xiao, Z. Q. Zhang, and C. T. Chan, Emergence, Coalescence, and Topological Properties of Multiple Exceptional Points and Their Experimental Realization, Phys. Rev. X 6, 021007 (2016).
  * [15] W. Tang, X. Jiang, K. Ding, Y.-X. Xiao, Z.-Q. Zhang, C. T. Chan, G. Ma, Exceptional nexus with a hybrid topological invariant, Science 370, 1077-1080 (2020).
  * [16] K. Ding, G. Ma, Z. Q. Zhang, and C. T. Chan, Experimental Demonstration of an Anisotropic Exceptional Point, Phys. Rev. Lett. 121, 085702 (2018).
  * [17] Q. Zhang, Y. Li, H. Sun, X. Liu, L. Zhao, X. Feng, X. Fan, and C. Qiu, Observation of Acoustic Non-Hermitian Bloch Braids and Associated Topological Phase Transitions, Phys. Rev. Lett. 130, 017201 (2023).
  * [18] W. Tang, K. Ding, and G. Ma, Experimental Realization of Non-Abelian Permutations in a Three-State Non-Hermitian System, Natl. Sci. Rev. nwac010 (2022).
  * [19] Q. Liang, D. Xie, Z. Dong, H. Li, H. Li, B. Gadway, W. Yi, and B. Yan, Dynamic Signatures of Non-Hermitian Skin Effect and Topology in Ultracold Atoms, Phys. Rev. Lett. 29, 070401 (2022).
  * [20] Z. Ren, D. Liu, E. Zhao, C. He, K. K. Pak, J. Li, and G.-B. Jo, Chiral control of quantum states in non-Hermitian spin-orbit-coupled fermions, Nat. Phys. 18, 385-389 (2022).
  * [21] R. Rosa-Medina, F. Ferri, F. Finger, N. Dogra, K. Kroeger, R. Lin, R. Chitra, T. Donner, and T. Esslinger, Observing Dynamical Currents in a Non-Hermitian Momentum Lattice, Phys. Rev. Lett. 128, 143602 (2022).
  * [22] V. Kozii and L. Fu, Non-Hermitian Topological Theory of Finite-Lifetime Quasiparticles: Prediction of Bulk Fermi Arc due to Exceptional Point, arXiv:1708.05841.
  * [23] H. Shen and L. Fu, Quantum Oscillation from In-Gap States and Non-Hermitian Landau Level Problem, Phys. Rev. Lett. 121, 026403 (2018).
  * [24] T. Yoshida, R. Peters, and N. Kawakami, Non-Hermitian perspective of the band structure in heavy-fermion systems, Phys. Rev. B 98, 035141 (2018).
  * [25] S. Yao and Z. Wang, Edge states and topological invariants of Non-Hermitian systems, Phys. Rev. Lett. 121, 086803 (2018).
  * [26] K. Yokomizo and S. Murakami, Non-Bloch band theory of Non-Hermitian systems, Phys. Rev. Lett. 123, 066404 (2019).
  * [27] F. K. Kunst, E. Edvardsson, J. C. Budich, and E. J. Bergholtz, Biorthogonal bulk-boundary correspondence in Non-Hermitian systems, Phys. Rev. Lett. 121, 026808 (2018).
  * [28] K. Zhang, Z. Yang, and C. Fang, Correspondence between winding numbers and skin modes in Non-Hermitian systems, Phys. Rev. Lett. 125, 126402 (2020).
  * [29] N. Okuma, K. Kawabata, K. Shiozaki, and M. Sato, Topological origin of Non-Hermitian skin effects, Phys. Rev. Lett. 124, 086801 (2020).
  * [30] Z. Yang, K. Zhang, C. Fang, and J. Hu, Non-Hermitian bulk-boundary correspondence and auxiliary generalized Brillouin zone theory, Phys. Rev. Lett. 125, 226402 (2020).
  * [31] V. M. Martinez Alvarez, J. E. Barrios Vargas, and L. E. F. Foa Torres, Non-Hermitian robust edge states in one dimension: Anomalous localization and eigenspace condensation at exceptional points, Phys. Rev. B 97, 121401(R) (2018).
  * [32] D. S. Borgnia, A. J. Kruchkov, and R.-J. Slager, Non-Hermitian Boundary Modes and Topology, Phys. Rev. Lett. 124, 056802 (2020).
  * [33] C. H. Lee and R. Thomale, Anatomy of skin modes and topology in nonHermitian systems, Phys. Rev. B 99, 201103(R) (2019).
  * [34] Y. Yi and Z. Yang, Non-Hermitian Skin Modes Induced by On-Site Dissipations and Chiral Tunneling Effect, Phys. Rev. Lett. 125, 186802 (2020).
  * [35] A review on non-Hermitian skin effect, Advances in Physics X 7, 2109431 (2022).
  * [36] A. Ghatak, M. Brandenbourger, J. van Wezel, and C. Coulais, Observation of non-Hermitian topology and its bulk-edge correspondence, arXiv:1907.11619.
  * [37] T. Helbig, T. Hofmann, S. Imhof, M. Abdelghany, T. Kiessling, L. W. Molenkamp, C. H. Lee, A. Szameit, M. Greiter, and R. Thomale, Generalized bulk–boundary correspondence in non-Hermitian topolectrical circuits, Nat. Phys. (2020).
  * [38] L. Xiao, T. Deng, K. Wang, G. Zhu, Z. Wang, W. Yi, and P. Xue, Observation of non-hermitian bulk-boundary correspondence in quantum dynamics, Nat. Phys. (2020).
  * [39] T. Hofmann et al., Reciprocal skin effect and its realization in a topolectrical circuit, Phys. Rev. Research 2, 023265 (2020).
  * [40] A. McDonald and A. A. Clerk, Exponentially-enhanced quantum sensing with non-Hermitian lattice dynamics, Nat. Commun. 11, 5382 (2020).
  * [41] S. Weidemann, M. Kremer, T. Helbig, T. Hofmann, A. Stegmaier, M. Greiter, R. Thomale and A. Szameit, Topological funneling of light, Science 368, 311 (2020).
  * [42] W.-T. Xue, Y.-M. Hu, F. Song, and Z. Wang, Non-Hermitian Edge Burst, Phys. Rev. Lett. 128, 120401 (2022).
  * [43] C.-H. Lee and S. Longhi, Ultrafast and anharmonic Rabi oscillations between non-Bloch bands, Commun Phys. 3, 147 (2020).
  * [44] J. C. Budich and E. J. Bergholtz, Non-Hermitian topological sensors, Phys Rev Lett. 125, 180403. (2020).
  * [45] H. Yuan, W. Zhang, Z. Zhou, W. Wang, N. Pan, Y. Feng, H. Sun, and X. Zhang, Non-Hermitian Topolectrical Circuit Sensor with High Sensitivity, Adv. Sci. 2023, 2301128 (2023).
  * [46] K. Kawabata, K. Shiozaki, M. Ueda, and M. Sato, Symmetry and Topology in Non-Hermitian Physics, Phys. Rev. X 9, 041015 (2019).
  * [47] Z. Gong, Y. Ashida, K. Kawabata, K. Takasan, S. Higashikawa, and M. Ueda, Topological Phases of Non-Hermitian Systems, Phys. Rev. X 8, 031079 (2018).
  * [48] H. Zhou and J. Y. Lee, Periodic table for topological bands with non-Hermitian symmetries, Phys. Rev. B 99, 235112 (2019).
  * [49] C.-H. Liu and S. Chen, Topological classification of defects in non-Hermitian systems, Phys. Rev. B 100, 144106 (2019).
  * [50] C.-H. Liu, H. Jiang, and S. Chen, Topological classification of non-Hermitian systems with reflection symmetry, Phys. Rev. B 99, 125103 (2019).
  * [51] H. Hu and E. Zhao, Knots and Non-Hermitian Bloch Bands, Phys. Rev. Lett. 126, 010401 (2021).
  * [52] C. H. Lee, L. Li, R. Thomale, and J. Gong, Unraveling non-Hermitian pumping: Emergent spectral singularities and anomalous responses, Phys. Rev. B 102, 085151 (2020).
  * [53] K. Zhang, Z. Yang, and C. Fang, Universal non-Hermitian skin effect in two and higher dimensions, Nat. Commun. 13, 2496 (2022).
  * [54] M. J. Colbrook, B. Roman, and A. C. Hansen, Phys. Rev. Lett. 122, 250201 (2019).
  * [55] A. Böttcher and S. M. Grudsky, Spectral Properties of Banded Toeplitz Matrices (Siam, Philadelphia, 2005).
  * [56] L. Reichel and L. N. Trefethen, Linear Algebra Appl. 162, 153 (1992).
  * [57] S. Yao, F. Song, and Z. Wang, Non-Hermitian chern bands, Phys. Rev. Lett. 121, 136802 (2018).
  * [58] J. Bartlett and E. Zhao, Unravelling the edge spectra of non-Hermitian Chern insulators, Phys. Rev. B 107, 035101 (2023).
  * [59] T. Li, Y.-S. Zhang, and W. Yi, Two-Dimensional Quantum Walk with Non-Hermitian Skin Effects, Chin. Phys. Lett. 38, 030301 (2021).
  * [60] H.-Y. Wang, F. Song, Z. Wang, Amoeba formulation of the non-Hermitian skin effect in higher dimensions, arXiv: 2212.11743
  * [61] K. Zhang, C. Fang, and Z. Yang, Dynamical Degeneracy Splitting and Directional Invisibility in Non-Hermitian Systems, arXiv: 2211.07783
  * [62] T. Wan, K. Zhang, J. Li, Z. Yang, and Z. Yang, Observation of dynamical degeneracy splitting for the non-Hermitian skin effect, arXiv:2303.11109
  * [63] G. Szegö, Ein Grenzwertsatz über die toeplitzschen Determinanten einer reellen positiven Funktion, Mathematische Annalen 76, 490 (1915).
  * [64] Harold Widom, Asymptotic behavior of block Toeplitz matrices and determinants, Advances in Mathematics 13, 284 (1974).
  * [65] Harold Widom, Asymptotic behavior of block Toeplitz matrices and determinants. II, Advances in Mathematics 21, 1 (1976).
  * [66] Harold Widom, Szego’s limit theorem: The higher-dimensional matrix case, Journal of Functional Analysis, 39, 182 (1980).
  * [67] R. Ya. Doktorskii, Generalization of G. Szegö’s limit theorem to the multidimensional case, Siberian Mathematical Journal 25, 701 (1984).
  * [68] Edward B. Saff , Vilmos Totik, Logarithmic Potentials with External Fields, Grundlehren der mathematischen Wissenschaften, 316, 1997th Edition.
  * [69] See supplementary material for the proof of the theorem (the third step) with an introduction to Amoeba.
  * [70] K. Kawabata, M. Sato, and K. Shiozaki, Higher-order non-Hermitian skin effect, Phys. Rev. B 102, 205118 (2020).
  * [71] X. Zhang, Y. Tian, J.-H. Jiang, M.-H. Lu, and Y.-F. Chen, Observation of higher-order non-Hermitian skin effect, Nat. Commun. 12, 5377 (2021).
  * [72] C.-H. Lee, L. Li, and J. Gong, Hybrid Higher-Order Skin-Topological Modes in Nonreciprocal Systems, Phys. Rev. Lett. 123, 016805 (2019).
  * [73] D. Zou, T. Chen, W. He, J. Bao, C. H. Lee, H. Sun, and X. Zhang, Observation of hybrid higher-order skin-topological effect in non-Hermitian topolectrical circuits, Nat. Commun. 12, 7201 (2021).
  * [74] T. Liu, Y.-R. Zhang, Q. Ai, Z. Gong, K. Kawabata, M. Ueda, and F. Nori, Second-order topological phases in non-hermitian systems, Phys. Rev. Lett. 122, 076801 (2019).
  * [75] H. Hu, E. Zhao, W. V. Liu, Dynamical signatures of point-gap Weyl semimetal, Phys. Rev. B 106, 094305 (2022).
  * [76] Y. Fu, J. Hu, and S. Wan, Non-Hermitian second-order skin and topological modes, Phys. Rev. B 103, 045420 (2021).
  * [77] Y. Song, W. Liu, L. Zheng, Y. Zhang, B. Wang, and P. Lu, Two-dimensional non-Hermitian Skin Effect in a Synthetic Photonic Lattice, Phys. Rev. Applied 14, 064076 (2020).
  * [78] Israel M. Gelfand, Mikhail M. Kapranov, and Andrei V. Zelevinsky, Discriminants, Resultants, and Multidimensional Determinants (Birkhäuser Boston, 1994).

Supplemental material

In this supplemental material, we prove the third step of the theorem
($\sigma_{U}=\sigma_{\text{Amoeba}}$) presented in the main text. Here,
$\sigma_{U}$ refers to the uniform spectra defined in Eq. (10). To begin, we
delve into the algebraic aspects of the characteristic polynomial (ChP). The
ChP is expressed as:

$\displaystyle
f(E,\beta_{1},\beta_{2},...,\beta_{d})=\det(H(\beta_{1},\beta_{2},...,\beta_{d})-E),$
(15)

which involves $1+d$ complex variables. For a given energy $E$, there exist
infinite solutions for $(|\beta_{1}|,|\beta_{2}|,...,|\beta_{d}|)$. These
solutions can be plotted on a $d$-dimensional ($d$D) coordinate system,
forming a shape known as Amoeba [78]. In 1D, it is well-known that when the
reference energy $E$ belongs to $\sigma_{OBC}$, the two “middle” roots have
the same modulus, i.e., $|\beta_{p}|=|\beta_{p+1}|$. To illustrate the concept
of Amoeba, let us consider the 2D example mentioned in the main text [see Fig.
2(b)]. The corresponding Hamiltonian is given by
$H(\beta_{1},\beta_{2})=\beta_{1}+\frac{1}{2}\beta_{1}^{-1}+\beta_{2}+\frac{1}{2}\beta_{2}^{-1}+2\beta_{1}\beta_{2}$.
We consider two reference energies: $E_{1}=-2+2i$ (outside the OBC spectra
region) and $E_{2}=2+0.2i$ (inside the OBC spectra). The corresponding Amoeba
are depicted in Fig. S1(a) and (b), respectively. It is evident that there is
a central hole on the $(\log|\beta_{1}|,\log|\beta_{2}|)$ plane for the
former; whereas e, there is no such central hole for the latter.

Figure S1: Amoeba for the 2D model
$H(\beta_{1},\beta_{2})=\beta_{1}+\frac{1}{2}\beta_{1}^{-1}+\beta_{2}+\frac{1}{2}\beta_{2}^{-1}+2\beta_{1}\beta_{2}$
with reference energy chosen as (a) $E_{1}=-2+2i$ (outside the OBC spectra
region); and (b) $E_{2}=2+0.2i$ (inside the OBC spectra region).

In the example above, the existence of a central hole in the Amoeba appears to
be related to the OBC spectra. Interestingly, based on the shape of the
Amoeba, a type of spectra is defined [60], dubbed Amoeba spectra. Here, we
reinstate this definition:

$\displaystyle\sigma_{\text{Amoeba}}:=\\{\textrm{Any}~{}E~{}\textrm{without a
central hole}.\\}$ (16)

In this context, a central hole refers to a region where the winding numbers
along all directions become zero when the rescaling factors are taken inside
that hole. The winding numbers are those defined in Eq. (9) of the main text.
Now we are ready to prove the third step of the theorem:
$\sigma_{U}=\sigma_{\text{Amoeba}}$.

Proof: We start with the 1D case, where the Amoeba spectra are given by Eq.
(4). (1) First, let us consider $E\notin\sigma_{\text{Amoeba}}$, which means
$|\beta_{p}(E)|\neq|\beta_{p+1}(E)|$. In this case, we can choose an
intermediate value: $|\beta_{p}|<\xi<|\beta_{p+1}|$. Consequently, there are
exactly $p$ zeros of the ChP inside the circle of radius $\xi$. From the
complex analysis, the winding number for the reference energy $E$ with the
rescaling factor $\xi$ is equal to the difference between the number of zeros
and poles (which is $p$) inside the circle of radius $\xi$:
$w=n_{\text{zeros}}-p$. Thus, we have $w=0$. According to our definition of
$\sigma_{U}$ in Eq. (10), $E\notin\sigma_{U}$, because $\sigma_{U}$ represents
the intersection of all $Sp(|\beta|)$’s. Therefore,
$\sigma_{U}\subseteq\sigma_{\text{Amoeba}}$. (2) Second, let us consider
$E\notin\sigma_{U}$, meaning that there exists some $\xi$ such that $E\notin
Sp(\xi)$, or in other words, $w=0=n_{\text{zeros}}-p$ or $n_{\text{zeros}}=p$.
That is there are exactly $p$ zeros inside the circle of radius $\xi$.
Consequently, $|\beta_{p}(E)|\neq|\beta_{p+1}(E)|$, implying
$E\notin\sigma_{\text{Amoeba}}$. Hence,
$\sigma_{\text{Amoeba}}\subseteq\sigma_{U}$. Combining (1) and (2), we can
conclude that $\sigma_{U}=\sigma_{\text{Amoeba}}$ in 1D.

Now, let us extend the proof to higher dimensions. (1) First, consider
$E\notin\sigma_{\text{Amoeba}}$. In this case, there exists a central hole,
and one can find $(\xi_{1},\xi_{2},...,\xi_{d})$ with
$w_{1}=w_{2}=...=w_{d}=0$. According to our definition, $E\notin
Sp(|xi_{1},\xi_{2},...,\xi_{d})\subseteq\sigma_{U}$. Hence,
$\sigma_{U}\subseteq\sigma_{\text{Amoeba}}$. (2) Second, let us take an
$E\notin\sigma_{U}$, that is, there exist some $(\xi_{1},\xi_{2},...,\xi_{d})$
such that $E\notin Sp(\xi_{1},\xi_{2},...,\xi_{d})$; As $Sp$ contains any $E$
with nonzero windings, or put in another way,
$w_{1}(E)=w_{2}(E)=...=w_{d}(E)=0$. Thus $(\xi_{1},\xi_{2},...,\xi_{d})$ forms
a central hole of Amoeba and according to the definition Eq. (16),
$E\notin\sigma_{\textrm{Amoeba}}$. Combining (1) and (2) and the 1D case, we
have $\sigma_{U}=\sigma_{\textrm{Amoeba}}$ for all dimensions. ∎