2010585-596Nancy, France 585

George B. Mertzios

Ignasi Sau

Shmuel Zaks

# The Recognition of Tolerance
and Bounded Tolerance Graphs

G.B. Mertzios  Department of Computer Science, RWTH Aachen University, Aachen,
Germany<EMAIL_ADDRESS>,  I. Sau  Department of Computer Science,
Technion, Haifa, Israel<EMAIL_ADDRESS>and  S. Zaks  Department of
Computer Science, Technion, Haifa, Israel<EMAIL_ADDRESS>
###### Abstract.

Tolerance graphs model interval relations in such a way that intervals can
tolerate a certain degree of overlap without being in conflict. This subclass
of perfect graphs has been extensively studied, due to both its interesting
structure and its numerous applications. Several efficient algorithms for
optimization problems that are NP-hard on general graphs have been designed
for tolerance graphs. In spite of this, the recognition of tolerance graphs –
namely, the problem of deciding whether a given graph is a tolerance graph –
as well as the recognition of their main subclass of bounded tolerance graphs,
have been the most fundamental open problems on this class of graphs (cf. the
book on tolerance graphs [14]) since their introduction in 1982 [11]. In this
article we prove that both recognition problems are NP-complete, even in the
case where the input graph is a trapezoid graph. The presented results are
surprising because, on the one hand, most subclasses of perfect graphs admit
polynomial recognition algorithms and, on the other hand, bounded tolerance
graphs were believed to be efficiently recognizable as they are a natural
special case of trapezoid graphs (which can be recognized in polynomial time)
and share a very similar structure with them. For our reduction we extend the
notion of an _acyclic orientation_ of permutation and trapezoid graphs. Our
main tool is a new algorithm that uses _vertex splitting_ to transform a given
trapezoid graph into a permutation graph, while preserving this new acyclic
orientation property. This method of vertex splitting is of independent
interest; very recently, it has been proved a powerful tool also in the design
of efficient recognition algorithms for other classes of graphs [21].

###### Key words and phrases:

Tolerance graphs, bounded tolerance graphs, recognition, vertex splitting, NP-
complete, trapezoid graphs, permutation graphs

###### 1991 Mathematics Subject Classification:

F.2.2 Computations on discrete structures, G.2.2 Graph algorithms

##  1\. Introduction

###  1.1. Tolerance graphs and related graph classes

A simple undirected graph ${G=(V,E)}$ on $n$ vertices is a _tolerance_ graph
if there exists a collection ${I=\\{I_{i}\ |\ i=1,2,\ldots,n\\}}$ of closed
intervals on the real line and a set ${t=\\{t_{i}\ |\ i=1,2,\ldots,n\\}}$ of
positive numbers, such that for any two vertices ${v_{i},v_{j}\in V}$,
${v_{i}v_{j}\in E}$ if and only if ${|I_{i}\cap
I_{j}|\geq\min\\{t_{i},t_{j}\\}}$. The pair ${\langle I,t\rangle}$ is called a
_tolerance representation_ of $G$. If $G$ has a tolerance representation
${\langle I,t\rangle}$, such that ${t_{i}\leq|I_{i}|}$ for every
$i=1,2,\ldots,n$, then $G$ is called a _bounded tolerance_ graph and ${\langle
I,t\rangle}$ a _bounded tolerance representation_ of $G$.

Tolerance graphs were introduced in [11], in order to generalize some of the
well known applications of interval graphs. The main motivation was in the
context of resource allocation and scheduling problems, in which resources,
such as rooms and vehicles, can tolerate sharing among users [14]. If we
replace in the definition of tolerance graphs the operator _min_ by the
operator _max_ , we obtain the class of _max-tolerance_ graphs. Both tolerance
and $\max$-tolerance graphs find in a natural way applications in biology and
bioinformatics, as in the comparison of DNA sequences from different organisms
or individuals [17], by making use of a software tool like BLAST [1].
Tolerance graphs find numerous other applications in constrained-based
temporal reasoning, data transmission through networks to efficiently
scheduling aircraft and crews, as well as contributing to genetic analysis and
studies of the brain [13, 14]. This class of graphs has attracted many
research efforts [14, 12, 13, 15, 8, 4, 18, 2, 24, 22], as it generalizes in a
natural way both interval graphs (when all tolerances are equal) and
permutation graphs (when $t_{i}=|I_{i}|$ for every $i=1,2,\ldots,n$) [11]. For
a detailed survey on tolerance graphs we refer to [14].

A _comparability_ graph is a graph which can be transitively oriented. A _co-
comparability_ graph is a graph whose complement is a comparability graph. A
_trapezoid_ (resp.  _parallelogram_ and _permutation_) graph is the
intersection graph of trapezoids (resp. parallelograms and line segments)
between two parallel lines $L_{1}$ and $L_{2}$ [10]. Such a representation
with trapezoids (resp. parallelograms and line segments) is called a
_trapezoid_ (resp.  _parallelogram_ and _permutation_) _representation_ of
this graph. A graph is bounded tolerance if and only if it is a parallelogram
graph [19, 2]. Permutation graphs are a strict subset of parallelogram graphs
[3]. Furthermore, parallelogram graphs are a strict subset of trapezoid graphs
[25], and both are subsets of co-comparability graphs [14, 10]. On the
contrary, tolerance graphs are not even co-comparability graphs [14, 10].
Recently, we have presented in [22] a natural intersection model for general
tolerance graphs, given by parallelepipeds in the three-dimensional space.
This representation generalizes the parallelogram representation of bounded
tolerance graphs, and has been used to improve the time complexity of minimum
coloring, maximum clique, and weighted independent set algorithms on tolerance
graphs [22].

Although tolerance and bounded tolerance graphs have been studied extensively,
the recognition problems for both these classes have been the most fundamental
open problems since their introduction in 1982 [14, 10, 5]. Therefore, all
existing algorithms assume that, along with the input tolerance graph, a
tolerance representation of it is given. The only result about the complexity
of recognizing tolerance and bounded tolerance graphs is that they have a
(non-trivial) polynomial sized tolerance representation, hence the problems of
recognizing tolerance and bounded tolerance graphs are in the class NP [15].
Recently, a linear time recognition algorithm for the subclass of _bipartite
tolerance_ graphs has been presented in [5]. Furthermore, the class of
trapezoid graphs (which strictly contains parallelogram, i.e. bounded
tolerance, graphs [25]) can be also recognized in polynomial time [20, 26,
21]. On the other hand, the recognition of $\max$-tolerance graphs is known to
be NP-hard [17]. Unfortunately, the structure of $\max$-tolerance graphs
differs significantly from that of tolerance graphs ($\max$-tolerance graphs
are not even perfect, as they can contain induced $C_{5}$’s [17]), so the
technique used in [17] does not carry over to tolerance graphs.

Since very few subclasses of perfect graphs are known to be NP-hard to
recognize, it was believed that the recognition of tolerance graphs was in P.
Furthermore, as bounded tolerance graphs are equivalent to parallelogram
graphs [19, 2], which constitute a natural subclass of trapezoid graphs and
have a very similar structure, it was plausible that their recognition was
also in P.

###  1.2. Our contribution

In this article, we establish the complexity of recognizing tolerance and
bounded tolerance graphs. Namely, we prove that both problems are surprisingly
NP-complete, by providing a reduction from the monotone-Not-All-Equal-3-SAT
(monotone-NAE-3-SAT) problem. Consider a boolean formula $\phi$ in conjunctive
normal form with three literals in every clause (3-CNF), which is monotone,
i.e. no variable is negated. The formula $\phi$ is called NAE-satisfiable if
there exists a truth assignment of the variables of $\phi$, such that every
clause has at least one true variable and one false variable. Given a monotone
3-CNF formula $\phi$, we construct a trapezoid graph $H_{\phi}$, which is
parallelogram, i.e. bounded tolerance, if and only if $\phi$ is NAE-
satisfiable. Moreover, we prove that the constructed graph $H_{\phi}$ is
tolerance if and only if it is bounded tolerance. Thus, since the recognition
of tolerance and of bounded tolerance graphs are in the class NP [15], it
follows that these problems are both NP-complete. Actually, our results imply
that the recognition problems remain NP-complete even if the given graph is
trapezoid, since the constructed graph $H_{\phi}$ is trapezoid.

For our reduction we extend the notion of an _acyclic orientation_ of
permutation and trapezoid graphs. Our main tool is a new algorithm that
transforms a given trapezoid graph into a permutation graph by _splitting_
some specific vertices, while preserving this new acyclic orientation
property. One of the main advantages of this algorithm is its robustness, in
the sense that the constructed permutation graph does not depend on any
particular trapezoid representation of the input graph $G$. Moreover, besides
its use in the present paper, this approach based on splitting vertices has
been recently proved a powerful tool also in the design of efficient
recognition algorithms for other classes of graphs [21].

Organization of the paper. We first present in Section 2 several properties of
permutation and trapezoid graphs, as well as the algorithm Split-$U$, which
constructs a permutation graph from a trapezoid graph. In Section 3 we present
the reduction of the monotone-NAE-3-SAT problem to the recognition of bounded
tolerance graphs. In Section 4 we prove that this reduction can be extended to
the recognition of general tolerance graphs. Finally, we discuss the presented
results and further research directions in Section 5. Some proofs have been
omitted due to space limitations; a full version can be found in [23].

##  2\. Trapezoid graphs and representations

In this section we first introduce (in Section 2.1) the notion of an _acyclic
representation_ of permutation and of trapezoid graphs. This is followed (in
Section 2.2) by some structural properties of trapezoid graphs, which will be
used in the sequel for the splitting algorithm Split-$U$. Given a trapezoid
graph $G$ and a vertex subset $U$ of $G$ with certain properties, this
algorithm constructs a permutation graph $G^{\\#}(U)$ with $2|U|$ vertices,
which is independent on any particular trapezoid representation of the input
graph $G$.

Notation. We consider in this article simple undirected and directed graphs
with no loops or multiple edges. In an undirected graph $G$, the edge between
vertices $u$ and $v$ is denoted by $uv$, and in this case $u$ and $v$ are said
to be _adjacent_ in $G$. If the graph $G$ is directed, we denote by $uv$ the
arc from $u$ to $v$. Given a graph ${G=(V,E)}$ and a subset ${S\subseteq V}$,
$G[S]$ denotes the induced subgraph of $G$ on the vertices in $S$, and we use
$E[S]$ to denote $E(G[S])$. Whenever we deal with a trapezoid (resp.
permutation and bounded tolerance, i.e. parallelogram) graph, we will consider
w.l.o.g. a trapezoid (resp. permutation and parallelogram) representation, in
which all endpoints of the trapezoids (resp. line segments and parallelograms)
are distinct [9, 14, 16]. Given a permutation graph $P$ along with a
permutation representation $R$, we may not distinguish in the following
between a vertex of $P$ and the corresponding line segment in $R$, whenever it
is clear from the context. Furthermore, with a slight abuse of notation, we
will refer to the line segments of a permutation representation just as
_lines_.

###  2.1. Acyclic permutation and trapezoid representations

Let $P=(V,E)$ be a permutation graph and $R$ be a permutation representation
of $P$. For a vertex $u\in V$, denote by $\theta_{R}(u)$ the angle of the line
of $u$ with $L_{2}$ in $R$. The class of permutation graphs is the
intersection of comparability and co-comparability graphs [10]. Thus, given a
permutation representation $R$ of $P$, we can define two partial orders
$(V,<_{R})$ and $(V,\ll_{R})$ on the vertices of $P$ [10]. Namely, for two
vertices $u$ and $v$ of $G$, $u<_{R}v$ if and only if $uv\in E$ and
$\theta_{R}(u)<\theta_{R}(v)$, while $u\ll_{R}v$ if and only if $uv\notin E$
and $u$ lies to the left of $v$ in $R$. The partial order $(V,<_{R})$ implies
a transitive orientation $\Phi_{R}$ of $P$, such that $uv\in\Phi_{R}$ whenever
$u<_{R}v$.

Let $G=(V,E)$ be a trapezoid graph, and $R$ be a trapezoid representation of
$G$, where for any vertex $u\in V$, the trapezoid corresponding to $u$ in $R$
is denoted by $T_{u}$. Since trapezoid graphs are also co-comparability graphs
[10], we can similarly define the partial order $(V,\ll_{R})$ on the vertices
of $G$, such that $u\ll_{R}v$ if and only if $uv\notin E$ and $T_{u}$ lies
completely to the left of $T_{v}$ in $R$. In this case, we may denote also
$T_{u}\ll_{R}T_{v}$.

In a given trapezoid representation $R$ of a trapezoid graph $G$, we denote by
$l(T_{u})$ and $r(T_{u})$ the left and the right line of $T_{u}$ in $R$,
respectively. Similarly to the case of permutation graphs, we use the relation
$\ll_{R}$ for the lines $l(T_{u})$ and $r(T_{u})$, e.g.
${l(T_{u})\ll_{R}r(T_{v})}$ means that the line $l(T_{u})$ lies to the left of
the line $r(T_{v})$ in $R$. Moreover, if the trapezoids of all vertices of a
subset $S\subseteq V$ lie completely to the left (resp. right) of the
trapezoid $T_{u}$ in $R$, we write $R(S)\ll_{R}T_{u}$ (resp.
$T_{u}\ll_{R}R(S)$). Note that there are several trapezoid representations of
a particular trapezoid graph $G$. Given one such representation $R$, we can
obtain another one $R^{\prime}$ by _vertical axis flipping_ of $R$, i.e.
$R^{\prime}$ is the mirror image of $R$ along an imaginary line perpendicular
to $L_{1}$ and $L_{2}$. Moreover, we can obtain another representation
$R^{\prime\prime}$ of $G$ by _horizontal axis flipping_ of $R$, i.e.
$R^{\prime\prime}$ is the mirror image of $R$ along an imaginary line parallel
to $L_{1}$ and $L_{2}$. We will extensively use these two operations
throughout the article.

######  Definition 2.1.

Let $P$ be a permutation graph with $2n$ vertices
$\\{u_{1}^{1},u_{1}^{2},u_{2}^{1},u_{2}^{2},\ldots,u_{n}^{1},u_{n}^{2}\\}$.
Let $R$ be a permutation representation and $\Phi_{R}$ be the corresponding
transitive orientation of $P$. The simple directed graph $F_{R}$ is obtained
by merging $u_{i}^{1}$ and $u_{i}^{2}$ into a single vertex $u_{i}$, for every
$i=1,2,\ldots,n$, where the arc directions of $F_{R}$ are implied by the
corresponding directions in $\Phi_{R}$. Then,

  1. (1)

$R$ is an _acyclic permutation representation with respect to_
$\\{u_{i}^{1},u_{i}^{2}\\}_{i=1}^{n}$***To simplify the presentation, we use
throughout the paper $\\{u_{i}^{1},u_{i}^{2}\\}_{i=1}^{n}$ to denote the set
of $n$ unordered pairs
$\\{u_{1}^{1},u_{1}^{2}\\},\\{u_{2}^{1},u_{2}^{2}\\},\ldots,\\{u_{n}^{1},u_{n}^{2}\\}$.
, if $F_{R}$ has no directed cycle,

  2. (2)

$P$ is an _acyclic permutation graph with respect to_
$\\{u_{i}^{1},u_{i}^{2}\\}_{i=1}^{n}$, if $P$ has an acyclic representation
$R$ with respect to $\\{u_{i}^{1},u_{i}^{2}\\}_{i=1}^{n}$.

######  Definition 2.2.

Let $G$ be a trapezoid graph with $n$ vertices and $R$ be a trapezoid
representation of $G$. Let $P$ be the permutation graph with $2n$ vertices
corresponding to the left and right lines of the trapezoids in $R$, $R_{P}$ be
the permutation representation of $P$ induced by $R$, and
$\\{u_{i}^{1},u_{i}^{2}\\}$ be the vertices of $P$ that correspond to the same
vertex $u_{i}$ of $G$, $i=1,2,\ldots,n$. Then,

  1. (1)

$R$ is an _acyclic trapezoid representation_ , if $R_{P}$ is an acyclic
permutation representation with respect to
$\\{u_{i}^{1},u_{i}^{2}\\}_{i=1}^{n}$,

  2. (2)

$G$ is an _acyclic trapezoid graph_ , if it has an acyclic representation $R$.

The following lemma follows easily from Definitions 2.1 and 2.2.

######  Lemma 2.3.

Any parallelogram graph is an acyclic trapezoid graph.

###  2.2. Structural properties of trapezoid graphs

In the following, we state some definitions concerning an arbitrary simple
undirected graph ${G=(V,E)}$, which are useful for our analysis. Although
these definitions apply to any graph, we will use them only for trapezoid
graphs. Similar definitions, for the restricted case where the graph $G$ is
connected, were studied in [6]. For $u\in V$ and $U\subseteq V$, $N(u)=\\{v\in
V\ |\ uv\in E\\}$ is the set of adjacent vertices of $u$ in $G$,
${N[u]=N(u)\cup\\{u\\}}$, and ${N(U)=\bigcup_{u\in U}N(u)\setminus U}$. If
${N(U)\subseteq N(W)}$ for two vertex subsets $U$ and $W$, then $U$ is said to
be _neighborhood dominated_ by $W$. Clearly, the relationship of neighborhood
domination is transitive.

Let ${C_{1},C_{2},\ldots,C_{\omega},\ \omega\geq 1,}$ be the connected
components of ${G\setminus N[u]}$ and ${V_{i}=V(C_{i})}$,
${i=1,2,\ldots,\omega}$. For simplicity of the presentation, we will identify
in the sequel the component $C_{i}$ and its vertex set $V_{i}$,
${i=1,2,\ldots,\omega}$. For ${i=1,2,\ldots,\omega}$, the _neighborhood
domination closure_ of $V_{i}$ with respect to $u$ is the set
${D_{u}(V_{i})=\\{V_{p}\ |\ N(V_{p})\subseteq N(V_{i}),\
p=1,2,\ldots,\omega\\}}$ of connected components of ${G\setminus N[u]}$. A
component $V_{i}$ is called a _master component_ of $u$ if
${|D_{u}(V_{i})|\geq|D_{u}(V_{j})|}$ for all ${j=1,2,\ldots,\omega}$. The
_closure complement_ of the neighborhood domination closure ${D_{u}(V_{i})}$
is the set ${D_{u}^{\ast}(V_{i})=\\{V_{1},V_{2},\ldots,V_{\omega}\\}\setminus
D_{u}(V_{i})}$. Finally, for a subset
${S\subseteq\\{V_{1},V_{2},\ldots,V_{\omega}\\}}$, a component $V_{j}\in S$ is
called _maximal_ if there is no component $V_{k}\in S$ such that
${N(V_{j})\subsetneqq N(V_{k})}$.

For example, consider the trapezoid graph $G$ with vertex set
$\\{u,u_{1},u_{2},u_{3},v_{1},v_{2},v_{3},v_{4}\\}$, which is given by the
trapezoid representation $R$ of Figure 1. The connected components of
${G\setminus N[u]=\\{v_{1},v_{2},v_{3},v_{4}\\}}$ are ${V_{1}=\\{v_{1}\\}}$,
${V_{2}=\\{v_{2}\\}}$, ${V_{3}=\\{v_{3}\\}}$, and ${V_{4}=\\{v_{4}\\}}$. Then,
${N(V_{1})=\\{u_{1}\\}}$, ${N(V_{2})=\\{u_{1},u_{3}\\}}$,
${N(V_{3})=\\{u_{2},u_{3}\\}}$, and ${N(V_{4})=\\{u_{3}\\}}$. Hence,
${D_{u}(V_{1})=\\{V_{1}\\}}$, ${D_{u}(V_{2})=\\{V_{1},V_{2},V_{4}\\}}$,
${D_{u}(V_{3})=\\{V_{3},V_{4}\\}}$, and ${D_{u}(V_{4})=\\{V_{4}\\}}$; thus,
$V_{2}$ is the only master component of $u$. Furthermore,
${D_{u}^{\ast}(V_{1})=\\{V_{2},V_{3},V_{4}\\}}$,
${D_{u}^{\ast}(V_{2})=\\{V_{3}\\}}$,
${D_{u}^{\ast}(V_{3})=\\{V_{1},V_{2}\\}}$, and
${D_{u}^{\ast}(V_{4})=\\{V_{1},V_{2},V_{3}\\}}$.

Figure 1. A trapezoid representation $R$ of a trapezoid graph $G$.

######  Lemma 2.4.

Let $G$ be a simple graph, $u$ be a vertex of $G$, and let
$V_{1},V_{2},\ldots,V_{\omega},\ \omega\geq 1$, be the connected components of
${G\setminus N[u]}$. If $V_{i}$ is a master component of $u$, such that
${D_{u}^{\ast}(V_{i})\neq\emptyset}$, then
${D_{u}^{\ast}(V_{j})\neq\emptyset}$ for every component $V_{j}$ of
$G\setminus N[u]$.

In the following we investigate several properties of trapezoid graphs, in
order to derive the vertex-splitting algorithm Split-$U$ in Section 2.3.

######  Remark 2.5.

Similar properties of trapezoid graphs have been studied in [6], leading to
another vertex-splitting algorithm, called Split-All. However, the algorithm
proposed in [6] is incorrect, since it is based on an incorrect property†††In
Observation 3.1(5) of [6], it is claimed that for an arbitrary trapezoid
representation $R$ of a connected trapezoid graph $G$, where $V_{i}$ is a
master component of $u$ such that ${D_{u}^{\ast}(V_{i})\neq\emptyset}$ and
${R(V_{i})\ll_{R}T_{u}}$, it holds
${R(D_{u}(V_{i}))\ll_{R}T_{u}\ll_{R}R(D_{u}^{\ast}(V_{i}))}$. However, the
first part of the latter inequality is not true. For instance, in the
trapezoid graph $G$ of Figure 1, ${V_{2}=\\{v_{2}\\}}$ is a master component
of $u$, where
$D_{u}^{\ast}(V_{2})=\\{V_{3}\\}=\\{\\{v_{3}\\}\\}{\neq\emptyset}$ and
${R(V_{2})\ll_{R}T_{u}}$. However, $V_{4}=\\{v_{4}\\}\in D_{u}(V_{2})$ and
${T_{u}\ll_{R}}T_{v_{4}}$, and thus, ${R(D_{u}(V_{2}))\not\ll_{R}T}_{u}$. , as
was also verified by [7]. In the sequel of this section, we present new
definitions and properties. In the cases where a similarity arises with those
of [6], we refer to it specifically.

######  Lemma 2.6.

Let $R$ be a trapezoid representation of a trapezoid graph $G$, and $V_{i}$ be
a master component of a vertex $u$ of $G$, such that
$R(V_{i}){\ll}_{R}{T_{u}}$. Then, $T_{u}{\ll}_{R}R(V_{j})$ for every component
$V_{j}\in D_{u}^{\ast}(V_{i})$.

######  Definition 2.7.

Let $G$ be a trapezoid graph, $u$ be a vertex of $G$, and $V_{i}$ be an
arbitrarily chosen master component of $u$. Then, $\delta_{u}=V_{i}$ and

  1. (1)

if $D_{u}^{\ast}(V_{i})=\emptyset$, then $\delta_{u}^{\ast}=\emptyset$.

  2. (2)

if $D_{u}^{\ast}(V_{i})\neq\emptyset$, then $\delta_{u}^{\ast}={V_{j}}$, for
an arbitrarily chosen maximal component $V_{j}\in{D_{u}^{\ast}(V_{i})}$.

Actually, as we will show in Lemma 2.10, the arbitrary choice of the
components $V_{i}$ and $V_{j}$ in Definition 2.7 does not affect essentially
the structural properties of $G$ that we will investigate in the sequel. From
now on, whenever we speak about $\delta_{u}$ and $\delta_{u}^{\ast}$, we
assume that these arbitrary choices of $V_{i}$ and $V_{j}$ have been already
made.

######  Definition 2.8.

Let $G$ be a trapezoid graph and $u$ be a vertex of $G$. The vertices of
$N(u)$ are partitioned into four possibly empty sets:

  1. (1)

$N_{0}(u)$: vertices not adjacent to either ${\delta_{u}}$ or
${\delta_{u}^{\ast}}$.

  2. (2)

$N_{1}(u)$: vertices adjacent to ${\delta_{u}}$ but not to
${\delta_{u}^{\ast}}$.

  3. (3)

$N_{2}(u)$: vertices adjacent to ${\delta_{u}^{\ast}}$ but not to
${\delta_{u}}$.

  4. (4)

$N_{12}(u)$: vertices adjacent to both ${\delta_{u}}$ and
${\delta_{u}^{\ast}}$.

In the following definition we partition the neighbors of a vertex of a
trapezoid graph $G$ into four possibly empty sets. Note that these sets depend
on a given trapezoid representation $R$ of $G$, in contrast to the four sets
of Definition 2.8 that depend only on the graph $G$ itself.

######  Definition 2.9.

Let $G$ be a trapezoid graph, $R$ be a representation of $G$, and $u$ be a
vertex of $G$. Denote by $D_{1}(u,R)$ and $D_{2}(u,R)$ the sets of trapezoids
of $R$ that lie completely to the left and to the right of $T_{u}$ in $R$,
respectively. Then, the vertices of $N(u)$ are partitioned into four possibly
empty sets:

  1. (1)

$N_{0}(u,R)$: vertices not adjacent to either $D_{1}(u,R)$ or $D_{2}(u,R)$.

  2. (2)

$N_{1}(u,R)$: vertices adjacent to $D_{1}(u,R)$ but not to $D_{2}(u,R)$.

  3. (3)

$N_{2}(u,R)$: vertices adjacent to $D_{2}(u,R)$ but not to $D_{1}(u,R)$.

  4. (4)

$N_{12}(u,R)$: vertices adjacent to both $D_{1}(u,R)$ and $D_{2}(u,R)$.

Suppose now that $\delta_{u}^{\ast}\neq\emptyset$, and let $V_{i}$ be the
master component of $u$ that corresponds to $\delta_{u}$, cf. Definition 2.7.
Then, given any trapezoid representation $R$ of $G$, we may assume w.l.o.g.
that $R(V_{i}){\ll}_{R}{T_{u}}$, by possibly performing a vertical axis
flipping of $R$. The following lemma connects Definitions 2.8 and 2.9; in
particular, it states that, if $R(V_{i})\ll_{R}T_{u}$, then the partitions of
the set $N(u)$ defined in these definitions coincide. This lemma will enable
us to use in the vertex splitting (cf. Definition 2.11) the partition of the
set $N(u)$ defined in Definition 2.8, independently of any trapezoid
representation $R$ of $G$, and regardless of any particular connected
components $V_{i}$ and $V_{j}$ of $G\setminus N[u]$.

######  Lemma 2.10.

Let $G$ be a trapezoid graph, $R$ be a representation of $G$, and $u$ be a
vertex of $G$ with ${\delta_{u}^{\ast}\neq\emptyset}$. Let $V_{i}$ be the
master component of $u$ that corresponds to $\delta_{u}$. If
${R(V_{i}){\ll}_{R}{T_{u}}}$, then ${N_{X}(u)=N_{X}(u,R)}$ for every
$X\in\\{0,1,2,12\\}$.

###  2.3. A splitting algorithm

We define now the splitting of a vertex $u$ of a trapezoid graph $G$, where
${\delta_{u}^{\ast}\neq\emptyset}$. Note that this splitting operation does
not depend on any trapezoid representation of $G$. Intuitively, if the graph
$G$ was given along with a specific trapezoid representation $R$, this would
have meant that we replace the trapezoid $T_{u}$ in $R$ by its two lines
$l(T_{u})$ and $r(T_{u})$.

######  Definition 2.11.

Let $G$ be a trapezoid graph and $u$ be a vertex of $G$, where
${\delta_{u}^{\ast}\neq\emptyset}$. The graph $G^{\\#}(u)$ obtained by the
_vertex splitting_ of $u$ is defined as follows:

  1. (1)

$V(G^{\\#}(u))=V(G)\setminus\\{u\\}\cup\\{u_{1},u_{2}\\}$, where $u_{1}$ and
$u_{2}$ are the two new vertices.

  2. (2)

$E(G^{\\#}(u))=E[V(G)\setminus\\{u\\}]\cup\\{u_{1}x\ |\ x\in
N_{1}(u)\\}\cup\\{u_{2}x\ |\ x\in N_{2}(u)\\}\cup\\{u_{1}x,u_{2}x\ |\ x\in
N_{12}(u)\\}$.

The vertices $u_{1}$ and $u_{2}$ are the _derivatives_ of vertex $u$.

We state now the notion of a standard trapezoid representation with respect to
a particular vertex.

######  Definition 2.12.

Let $G$ be a trapezoid graph and $u$ be a vertex of $G$, where
${\delta_{u}^{\ast}\neq\emptyset}$. A trapezoid representation $R$ of $G$ is
_standard with respect to_ $u$, if the following properties are satisfied:

  1. (1)

$l(T_{u})\ll_{R}R(N_{0}(u)\cup N_{2}(u))$.

  2. (2)

$R(N_{0}(u)\cup N_{1}(u))\ll_{R}r(T_{u})$.

Now, given a trapezoid graph $G$ and a vertex subset
$U=\\{u_{1},u_{2},\ldots,u_{k}\\}$, such that
$\delta_{u_{i}}^{\ast}\neq\emptyset$ for every $i=1,2,\ldots,k$, Algorithm
Split-$U$ returns a graph $G^{\\#}(U)$ by splitting every vertex of $U$
exactly once. At every step, Algorithm Split-$U$ splits a vertex of $U$, and
finally, it removes all vertices of the set $V(G)\setminus U$, which have not
been split.

Algorithm 1 Split-$U$

0: A trapezoid graph $G$ and a vertex subset
$U=\\{u_{1},u_{2},\ldots,u_{k}\\}$, such that
$\delta_{u_{i}}^{*}\neq\emptyset$ for all $i=1,2,\ldots,k$

0: The permutation graph $G^{\\#}(U)$

$\overline{U}\leftarrow V(G)\setminus U$; $H_{0}\leftarrow G$

for $i=1$ to $k$ do

$H_{i}\leftarrow H_{i-1}^{\\#}(u_{i})$ {$H_{i}$ is obtained by the vertex
splitting of $u_{i}$ in $H_{i-1}$}

$G^{\\#}(U)\leftarrow H_{k}[V(H_{k})\setminus\overline{U}]$ {remove from
$H_{k}$ all unsplitted vertices}

return $G^{\\#}(U)$

######  Remark 2.13.

As mentioned in Remark 2.5, a similar algorithm, called Split-All, was
presented in [6]. We would like to emphasize here the following four
differences between the two algorithms. First, that Split-All gets as input a
sibling-free graph $G$ (two vertices $u,v$ of a graph $G$ are called
_siblings_ , if $N[u]=N[v]$; $G$ is called _sibling-free_ if $G$ has no pair
of sibling vertices), while our Algorithm Split-$U$ gets as an input any graph
(though, we will use it only for trapezoid graphs), which may contain also
pairs of sibling vertices. Second, Split-All splits all the vertices of the
input graph, while Split-$U$ splits only a subset of them, which satisfy a
special property. Third, the order of vertices that are split by Split-All
depends on a certain property (inclusion-minimal neighbor set), while
Split-$U$ splits the vertices in an arbitrary order. Last, the main difference
between these two algorithms is that they perform a different vertex splitting
operation at every step, since Definitions 2.7 and 2.8 do not comply with the
corresponding Definitions 4.1 and 4.2 of [6].

######  Theorem 2.14.

Let $G$ be a trapezoid graph and $U=\\{u_{1},u_{2},\ldots,u_{k}\\}$ be a
vertex subset of $G$, such that $\delta_{u_{i}}^{\ast}\neq\emptyset$ for every
$i=1,2,\ldots,k$. Then, the graph $G^{\\#}(U)$ obtained by Algorithm
Split-$U$, is a permutation graph with $2k$ vertices. Furthermore, if $G$ is
acyclic, then $G^{\\#}(U)$ is acyclic with respect to
$\\{u_{i}^{1},u_{i}^{2}\\}_{i=1}^{k}$, where $u_{i}^{1}$ and $u_{i}^{2}$ are
the derivatives of $u_{i}$, $i=1,2,\ldots,k$.

##  3\. The recognition of bounded tolerance graphs

In this section we provide a reduction from the _monotone-Not-All-Equal-3-SAT
(monotone-NAE-3-SAT)_ problem to the problem of recognizing whether a given
graph is a bounded tolerance graph. The problem of deciding whether a given
monotone 3-CNF formula $\phi$ is NAE-satisfiable is known to be NP-complete.
We can assume w.l.o.g. that each clause has three distinct literals, i.e.
variables. Given a monotone 3-CNF formula $\phi$, we construct in polynomial
time a trapezoid graph $H_{\phi}$, such that $H_{\phi}$ is a bounded tolerance
graph if and only if $\phi$ is NAE-satisfiable. To this end, we construct
first a permutation graph $P_{\phi}$ and a trapezoid graph $G_{\phi}$.

###  3.1. The permutation graph $P_{\phi}$

Consider a monotone 3-CNF formula
${\phi=\alpha_{1}\wedge\alpha_{2}\wedge\ldots\wedge\alpha_{k}}$ with $k$
clauses and $n$ boolean variables ${x_{1},x_{2},\ldots,x_{n}}$, such that
${\alpha_{i}=(x_{r_{i,1}}\vee x_{r_{i,2}}\vee x_{r_{i,3}})}$ for
${i=1,2,\ldots,k}$, where ${1\leq r_{i,1}<r_{i,2}<r_{i,3}\leq n}$. We
construct the permutation graph $P_{\phi}$, along with a permutation
representation $R_{P}$ of $P_{\phi}$, as follows. Let $L_{1}$ and $L_{2}$ be
two parallel lines and let $\theta(\ell)$ denote the angle of the line $\ell$
with $L_{2}$ in $R_{P}$. For every clause $\alpha_{i}$, ${i=1,2,\ldots,k}$, we
correspond to each of the literals, i.e. variables, $x_{r_{i,1}}$,
$x_{r_{i,2}}$, and $x_{r_{i,3}}$ a pair of intersecting lines with endpoints
on $L_{1}$ and $L_{2}$. Namely, we correspond to the variable $x_{r_{i,1}}$
the pair $\\{{a_{i},c_{i}\\}}$, to $x_{r_{i,2}}$ the pair
$\\{{e_{i},b_{i}\\}}$ and to $x_{r_{i,3}}$ the pair $\\{{d_{i},f_{i}\\}}$,
respectively, such that ${\theta(a_{i})>\theta(c_{i})}$,
${\theta(e_{i})>\theta(b_{i})}$, ${\theta(d_{i})>\theta(f_{i})}$, and such
that the lines ${a_{i},c_{i}}$ lie completely to the left of ${e_{i},b_{i}}$
in $R_{P}$, and ${e_{i},b_{i}}$ lie completely to the left of ${d_{i},f_{i}}$
in $R_{P}$, as it is illustrated in Figure 2. Denote the lines that correspond
to the variable $x_{r_{i,j}}$, $j=1,2,3$, by $\ell_{i,j}^{1}$ and
$\ell_{i,j}^{2}$, respectively, such that
${\theta(\ell_{i,j}^{1})>\theta(\ell_{i,j}^{2})}$. That is,
$(\ell_{i,1}^{1},\ell_{i,1}^{2})=(a_{i},c_{i})$,
$(\ell_{i,2}^{1},\ell_{i,2}^{2})=(e_{i},b_{i})$, and
$(\ell_{i,3}^{1},\ell_{i,3}^{2})=(d_{i},f_{i})$. Note that no line of a pair
$\\{\ell_{i,j}^{1},\ell_{i,j}^{2}\\}$ intersects with a line of another pair
$\\{\ell_{i^{\prime},j^{\prime}}^{1},\ell_{i^{\prime},j^{\prime}}^{2}\\}$.

Figure 2. The six lines of the permutation graph $P_{\phi}$, which correspond
to the clause ${\alpha_{i}=(x_{r_{i,1}}\vee x_{r_{i,2}}\vee x_{r_{i,3}})}$ of
the boolean formula $\phi$.

Denote by $S_{p}$, $p=1,2,\ldots,n$, the set of pairs
$\\{\ell_{i,j}^{1},\ell_{i,j}^{2}\\}$ that correspond to the variable $x_{p}$,
i.e. $r_{i,j}=p$. We order the pairs $\\{\ell_{i,j}^{1},\ell_{i,j}^{2}\\}$
such that any pair of $S_{p_{1}}$ lies completely to the left of any pair of
$S_{p_{2}}$, whenever $p_{1}<p_{2}$, while the pairs that belong to the same
set $S_{p}$ are ordered arbitrarily. For two consecutive pairs
$\\{\ell_{i,j}^{1},\ell_{i,j}^{2}\\}$ and
$\\{\ell_{i^{\prime},j^{\prime}}^{1},\ell_{i^{\prime},j^{\prime}}^{2}\\}$ in
$S_{p}$, where $\\{\ell_{i,j}^{1},\ell_{i,j}^{2}\\}$ lies to the left of
$\\{\ell_{i^{\prime},j^{\prime}}^{1},\ell_{i^{\prime},j^{\prime}}^{2}\\}$, we
add a pair
$\\{u_{i,j}^{i^{\prime},j^{\prime}},v_{i,j}^{i^{\prime},j^{\prime}}\\}$ of
parallel lines that intersect both $\ell_{i,j}^{1}$ and
$\ell_{i^{\prime},j^{\prime}}^{1}$, but no other line. Note that
$\theta(\ell_{i,j}^{1})>\theta(u_{i,j}^{i^{\prime},j^{\prime}})$ and
$\theta(\ell_{i^{\prime},j^{\prime}}^{1})>\theta(u_{i,j}^{i^{\prime},j^{\prime}})$,
while
$\theta(u_{i,j}^{i^{\prime},j^{\prime}})=\theta(v_{i,j}^{i^{\prime},j^{\prime}})$.
This completes the construction. Denote the resulting permutation graph by
$P_{\phi}$, and the corresponding permutation representation of $P_{\phi}$ by
$R_{P}$. Observe that $P_{\phi}$ has $n$ connected components, which are
called _blocks_ , one for each variable $x_{1},x_{2},\ldots,x_{n}$.

An example of the construction of $P_{\phi}$ and $R_{P}$ from $\phi$ with
$k=3$ clauses and $n=4$ variables is illustrated in Figure 3. In this figure,
the lines $u_{i,j}^{i^{\prime},j^{\prime}}$ and
$v_{i,j}^{i^{\prime},j^{\prime}}$ are drawn in bold.

The formula $\phi$ has $3k$ literals, and thus the permutation graph
$P_{\phi}$ has $6k$ lines $\ell_{i,j}^{1},\ell_{i,j}^{2}$ in $R_{P}$, one pair
for each literal. Furthermore, two lines
$u_{i,j}^{i^{\prime},j^{\prime}},v_{i,j}^{i^{\prime},j^{\prime}}$ correspond
to each pair of consecutive pairs $\\{\ell_{i,j}^{1},\ell_{i,j}^{2}\\}$ and
$\\{\ell_{i^{\prime},j^{\prime}}^{1},\ell_{i^{\prime},j^{\prime}}^{2}\\}$ in
$R_{P}$, except for the case where these pairs of lines belong to different
variables, i.e. when $r_{i,j}\neq r_{i^{\prime},j^{\prime}}$. Therefore, since
$\phi$ has $n$ variables, there are $2(3k-n)=6k-2n$ lines
$u_{i,j}^{i^{\prime},j^{\prime}},v_{i,j}^{i^{\prime},j^{\prime}}$ in $R_{P}$.
Thus, $R_{P}$ has in total $12k-2n$ lines, i.e. $P_{\phi}$ has $12k-2n$
vertices. In the example of Figure 3, $k=3$, $n=4$, and thus, $P_{\phi}$ has
$28$ vertices.

Figure 3. The permutation representation $R_{P}$ of the permutation graph
$P_{\phi}$ for $\phi=\alpha_{1}\wedge\alpha_{2}\wedge\alpha_{3}=(x_{1}\vee
x_{2}\vee x_{3})\wedge(x_{2}\vee x_{3}\vee x_{4})\wedge(x_{1}\vee x_{2}\vee
x_{4})$.

Let $m=6k-n$, where $2m$ is the number of vertices in $P_{\phi}$. We group the
lines of $R_{P}$, i.e. the vertices of $P_{\phi}$, into pairs
$\\{u_{i}^{1},u_{i}^{2}\\}_{i=1}^{m}$, as follows. For every clause
$\alpha_{i}$, $i=1,2,\ldots,k$, we group the lines
$a_{i},b_{i},c_{i},d_{i},e_{i},f_{i}$ into the three pairs
$\\{a_{i},b_{i}\\}$, $\\{c_{i},d_{i}\\}$, and $\\{e_{i},f_{i}\\}$. The
remaining lines are grouped naturally according to the construction; namely,
every two lines
$\\{u_{i,j}^{i^{\prime},j^{\prime}},v_{i,j}^{i^{\prime},j^{\prime}}\\}$
constitute a pair.

######  Lemma 3.1.

If the permutation graph $P_{\phi}$ is acyclic with respect to
$\\{u_{i}^{1},u_{i}^{2}\\}_{i=1}^{m}$ then the formula $\phi$ is NAE-
satisfiable.

The truth assignment $(x_{1},x_{2},x_{3},x_{4})=(1,1,0,0)$ is NAE-satisfying
for the formula $\phi$ of Figure 3. The acyclic permutation representation
$R_{0}$ of $P_{\phi}$ with respect to $\\{u_{i}^{1},u_{i}^{2}\\}_{i=1}^{m}$,
which corresponds to this assignment, can be obtained from $R_{P}$ by
performing a horizontal axis flipping of the two blocks that correspond to the
variables $x_{3}$ and $x_{4}$, respectively.

###  3.2. The trapezoid graphs $G_{\phi}$ and $H_{\phi}$

Let $\\{u_{i}^{1},u_{i}^{2}\\}_{i=1}^{m}$ be the pairs of vertices in the
permutation graph $P_{\phi}$ and $R_{P}$ be its permutation representation. We
construct now from $P_{\phi}$ the trapezoid graph $G_{\phi}$ with $m$ vertices
$\\{u_{1},u_{2},\ldots,u_{m}\\}$, as follows. We replace in the permutation
representation $R_{P}$ for every $i=1,2,\ldots,m$ the lines $u_{i}^{1}$ and
$u_{i}^{2}$ by the trapezoid $T_{u_{i}}$, which has $u_{i}^{1}$ and
$u_{i}^{2}$ as its left and right lines, respectively. Let $R_{G}$ be the
resulting trapezoid representation of $G_{\phi}$.

Finally, we construct from $G_{\phi}$ the trapezoid graph $H_{\phi}$ with $7m$
vertices, by adding to every trapezoid $T_{u_{i}}$, $i=1,2,\ldots,m$, six
parallelograms $T_{u_{i,1}},T_{u_{i,2}},\ldots,T_{u_{i,6}}$ in the trapezoid
representation $R_{G}$, as follows. Let $\varepsilon$ be the smallest distance
in $R_{G}$ between two different endpoints on $L_{1}$, or on $L_{2}$. The
right (resp. left) line of $T_{u_{1,1}}$ lies to the right (resp. left) of
$u_{1}^{1}$, and it is parallel to it at distance $\frac{\varepsilon}{2}$. The
right (resp. left) line of $T_{u_{1,2}}$ lies to the left of $u_{1}^{1}$, and
it is parallel to it at distance $\frac{\varepsilon}{4}$ (resp.
$\frac{3\varepsilon}{4}$). Moreover, the right (resp. left) line of
$T_{u_{1,3}}$ lies to the left of $u_{1}^{1}$, and it is parallel to it at
distance $\frac{3\varepsilon}{8}$ (resp. $\frac{7\varepsilon}{8}$). Similarly,
the left (resp. right) line of $T_{u_{1,4}}$ lies to the left (resp. right) of
$u_{1}^{2}$, and it is parallel to it at distance $\frac{\varepsilon}{2}$. The
left (resp. right) line of $T_{u_{1,5}}$ lies to the right of $u_{1}^{2}$, and
it is parallel to it at distance $\frac{\varepsilon}{4}$ (resp.
$\frac{3\varepsilon}{4}$). Finally, the right (resp. left) line of
$T_{u_{1,6}}$ lies to the right of $u_{1}^{2}$, and it is parallel to it at
distance $\frac{3\varepsilon}{8}$ (resp. $\frac{7\varepsilon}{8}$), as
illustrated in Figure 4.

After adding the parallelograms $T_{u_{1,1}},T_{u_{1,2}},\ldots,T_{u_{1,6}}$
to a trapezoid $T_{u_{1}}$, we update the smallest distance $\varepsilon$
between two different endpoints on $L_{1}$, or on $L_{2}$ in the resulting
representation, and we continue the construction iteratively for all
$i=2,\ldots,m$. Denote by $H_{\phi}$ the resulting trapezoid graph with $7m$
vertices, and by $R_{H}$ the corresponding trapezoid representation. Note that
in $R_{H}$, between the endpoints of the parallelograms $T_{u_{i,1}}$,
$T_{u_{i,2}}$, and $T_{u_{i,3}}$ (resp. $T_{u_{i,4}}$, $T_{u_{i,5}}$, and
$T_{u_{i,6}}$) on $L_{1}$ and $L_{2}$, there are no other endpoints of
$H_{\phi}$, except those of $u_{i}^{1}$ (resp. $u_{i}^{2}$), for every
$i=1,2,\ldots,m$. Furthermore, note that $R_{H}$ is standard with respect to
$u_{i}$, for every $i=1,2,\ldots,m$.

Figure 4. The addition of the six parallelograms
$T_{u_{i,1}},T_{u_{i,2}},\ldots,T_{u_{i,6}}$ to the trapezoid $T_{u_{i}}$,
${i=1,2,\ldots,m}$, in the construction of the trapezoid graph $H_{\phi}$ from
$G_{\phi}$.

######  Theorem 3.2.

The formula $\phi$ is NAE-satisfiable if and only if the trapezoid graph
$H_{\phi}$ is a bounded tolerance graph.

For the sufficiency part of the proof of Theorem 3.2, the algorithm Split-All
plays a crucial role. Namely, given the parallelogram graph $H_{\phi}$ (which
is acyclic trapezoid by Lemma 2.3), we construct with this algorithm the
acyclic permutation graph $P_{\phi}$ and then a NAE-satisfying assignment of
the formula $\phi$. Since monotone-NAE-3-SAT is NP-complete, the problem of
recognizing bounded tolerance graphs is NP-hard by Theorem 3.2. Moreover,
since this problem lies in NP [15], we summarize our results as follows.

######  Theorem 3.3.

Given a graph $G$, it is NP-complete to decide whether it is a bounded
tolerance graph.

##  4\. The recognition of tolerance graphs

In this section we show that the reduction from the monotone-NAE-3-SAT problem
to the problem of recognizing bounded tolerance graphs presented in Section 3,
can be extended to the problem of recognizing general tolerance graphs. In
particular, we prove that the constructed trapezoid graph $H_{\phi}$ is a
tolerance graph if and only if it is a bounded tolerance graph. Then, the main
result of this section follows.

######  Theorem 4.1.

Given a graph $G$, it is NP-complete to decide whether it is a tolerance
graph. The problem remains NP-complete even if the given graph $G$ is known to
be a trapezoid graph.

##  5\. Concluding remarks

In this article we proved that both tolerance and bounded tolerance graph
recognition problems are NP-complete, by providing a reduction from the
monotone-NAE-3-SAT problem, thus answering a longstanding open question. The
recognition of unit and of proper tolerance graphs, as well as of any other
subclass of tolerance graphs, except bounded tolerance and bipartite tolerance
graphs [5], remain interesting open problems [14].

## References

  * [1] S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman.  Basic local alignment search tool.  Journal of molecular biology, 215(3):403–410, 1990.
  * [2] K. P. Bogart, P. C. Fishburn, G. Isaak, and L. Langley.  Proper and unit tolerance graphs.  Discrete Applied Mathematics, 60(1-3):99–117, 1995.
  * [3] A. Brandstädt, V. B. Le, and J. P. Spinrad.  Graph classes: a survey.  SIAM Monographs on Discrete Mathematics and Applications, 1999.
  * [4] A. H. Busch.  A characterization of triangle-free tolerance graphs.  Discrete Applied Mathematics, 154(3):471–477, 2006.
  * [5] A. H. Busch and G. Isaak.  Recognizing bipartite tolerance graphs in linear time.  In Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pages 12–20, 2007.
  * [6] F. Cheah and D. G. Corneil.  On the structure of trapezoid graphs.  Discrete Applied Mathematics, 66(2):109–133, 1996.
  * [7] F. Cheah and D. G. Corneil, 2009.  Personal communication.
  * [8] S. Felsner.  Tolerance graphs and orders.  Journal of Graph Theory, 28:129–140, 1998.
  * [9] P. C. Fishburn and W. Trotter.  Split semiorders.  Discrete Mathematics, 195:111–126, 1999.
  * [10] M. C. Golumbic.  Algorithmic graph theory and perfect graphs (Annals of Discrete Mathematics, Vol. 57).  North-Holland Publishing Co., 2nd edition, 2004.
  * [11] M. C. Golumbic and C. L. Monma.  A generalization of interval graphs with tolerances.  In Proceedings of the 13th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium 35, pages 321–331, 1982.
  * [12] M. C. Golumbic, C. L. Monma, and W. T. Trotter.  Tolerance graphs.  Discrete Applied Mathematics, 9(2):157–170, 1984.
  * [13] M. C. Golumbic and A. Siani.  Coloring algorithms for tolerance graphs: reasoning and scheduling with interval constraints.  In Proceedings of the Joint International Conferences on Artificial Intelligence, Automated Reasoning, and Symbolic Computation (AISC/Calculemus), pages 196–207, 2002.
  * [14] M. C. Golumbic and A. N. Trenk.  Tolerance graphs.  Cambridge Studies in Advanced Mathematics, 2004.
  * [15] R. B. Hayward and R. Shamir.  A note on tolerance graph recognition.  Discrete Applied Mathematics, 143(1-3):307–311, 2004.
  * [16] G. Isaak, K. L. Nyman, and A. N. Trenk.  A hierarchy of classes of bounded bitolerance orders.  Ars Combinatoria, 69, 2003.
  * [17] M. Kaufmann, J. Kratochvíl, K. A. Lehmann, and A. R. Subramanian.  Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition.  In Proceedings of the 17th annual ACM-SIAM symposium on Discrete Algorithms (SODA), pages 832–841, 2006.
  * [18] J. M. Keil and P. Belleville.  Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs.  Discrete Applied Mathematics, 140(1-3):73–89, 2004.
  * [19] L. Langley.  Interval tolerance orders and dimension.  PhD thesis, Dartmouth College, 1993.
  * [20] T.-H. Ma and J. P. Spinrad.  On the 2-chain subgraph cover and related problems.  Journal of Algorithms, 17(2):251–268, 1994.
  * [21] G. B. Mertzios and D. G. Corneil.  Vertex splitting and the recognition of trapezoid graphs.  Technical Report AIB-2009-16, Department of Computer Science, RWTH Aachen University, September 2009.
  * [22] G. B. Mertzios, I. Sau, and S. Zaks.  A new intersection model and improved algorithms for tolerance graphs.  SIAM Journal on Discrete Mathematics, 23(4):1800–1813, 2009.
  * [23] G. B. Mertzios, I. Sau, and S. Zaks.  The recognition of tolerance and bounded tolerance graphs is NP-complete.  Technical Report AIB-2009-06, Department of Computer Science, RWTH Aachen University, April 2009.
  * [24] G. Narasimhan and R. Manber.  Stability and chromatic number of tolerance graphs.  Discrete Applied Mathematics, 36:47–56, 1992.
  * [25] S. P. Ryan.  Trapezoid order classification.  Order, 15:341–354, 1998.
  * [26] J. P. Spinrad.  Efficient graph representations, volume 19 of Fields Institute Monographs.  American Mathematical Society, 2003.


# Solvable Periodic Anderson Model with Infinite-Range Hatsugai-Kohmoto
Interaction: Ground-states and beyond

Yin Zhong<EMAIL_ADDRESS>School of Physical Science and Technology $\&$
Key Laboratory for Magnetism and Magnetic Materials of the MoE, Lanzhou
University, Lanzhou 730000, China  Lanzhou Center for Theoretical Physics, Key
Laboratory of Theoretical Physics of Gansu Province

###### Abstract

In this paper we introduce a solvable two-orbital/band model with infinite-
range Hatsugai-Kohmoto interaction, which serves as a modified periodic
Anderson model. Its solvability results from strict locality in momentum
space, and is valid for arbitrary lattice geometry and electron filling. Case
study on a one-dimension ($1D$) chain shows that the ground-states have
Luttinger theorem-violating non-Fermi-liquid-like metallic state,
hybridization-driven insulator and interaction-driven featureless Mott
insulator. The involved quantum phase transition between metallic and
insulating states belongs to the universality of Lifshitz transition, i.e.
change of topology of Fermi surface or band structure. Further investigation
on $2D$ square lattice indicates its similarity with the $1D$ case, thus the
findings in the latter may be generic for all spatial dimensions. We hope the
present model or its modification may be useful for understanding novel
quantum states in $f$-electron compounds, particularly the topological Kondo
insulator candidate SmB6 and YbB12.

##  I Introduction

Recently, solvable quantum many-body systems such as Sachdev-Ye-Kitaev,
Kitaev’s toric code and honeycomb model have attracted great interest due to
emergent novel non-Fermi liquid and quantum spin liquid states.Sachdev ;
Maldacena ; Chowdhury ; Kitaev1 ; Kitaev2 ; Zhou ; Prosko ; Zhong2013 ;
Smith2017 ; Ng2018  Among them, an infinite-range interaction model without
any quenched disorder or local gauge structure called Hatsugai-Kohmoto (HK)
model has been revisited.Hatsugai1992 ; Baskaran1991 ; Hatsugai1996 ;
Phillips2018 ; Yeo2019 ; Phillips2020 ; Yang2021 ; Zhu2021 ; Zhao2022 ;
Setty2021 ; Mai2022 ; Huang2022 ; Li2022  The original HK model provides a
strictly exact example for non-Fermi liquid and featureless Mott insulator in
any spatial dimension, which is rare in statistical mechanics and condensed
matter physics. The solvability of HK model results from its locality in
momentum space and one can diagonalize HK Hamiltonian (only $4\times
4$-matrix) for each momentum. The current studies have mainly focused on an
interesting extension of HK model, i.e. the superconducting instability from
the intrinsic non-Fermi liquid state in HK model,Phillips2020  (note however a
study on Kondo impurity in HK modelSetty2021 ) and unexpected properties
(compared with standard Bardeen-Cooper-Schrieffer (BCS) modelBardeen1957 )
have been discovered, e.g. the emergence of topological $s$-wave pairing, two-
stage superconductivity, tricritical point and absence of Hebel-Slichter
peak.Zhu2021 ; Zhao2022 ; Li2022

In this paper, we introduce another extension of HK model, i.e. a two-
orbital/band lattice electron system which can be considered as a modified
periodic Anderson model (PAM),

$\displaystyle\hat{H}$ $\displaystyle=$
$\displaystyle-\sum_{i,j,\sigma}t_{ij}^{c}\hat{c}_{i\sigma}^{{\dagger}}\hat{c}_{j\sigma}-\sum_{i,j,\sigma}t_{ij}^{f}\hat{f}_{i\sigma}^{{\dagger}}\hat{f}_{j\sigma}+E_{f}\sum_{j\sigma}\hat{f}_{j\sigma}^{{\dagger}}\hat{f}_{j\sigma}$
(1) $\displaystyle+$ $\displaystyle
V\sum_{j\sigma}(\hat{c}_{j\sigma}^{{\dagger}}\hat{f}_{j\sigma}+\hat{f}_{j\sigma}^{{\dagger}}\hat{c}_{j\sigma})-\mu\sum_{j\sigma}(\hat{c}_{j\sigma}^{{\dagger}}\hat{c}_{j\sigma}+\hat{f}_{j\sigma}^{{\dagger}}\hat{f}_{j\sigma})$
$\displaystyle+$
$\displaystyle\frac{U}{N_{s}}\sum_{j_{1},j_{2},j_{3},j_{4}}\delta_{j_{1}+j_{3}=j_{2}+j_{4}}\hat{f}_{j_{1}\uparrow}^{{\dagger}}\hat{f}_{j_{2}\uparrow}\hat{f}_{j_{3}\downarrow}^{{\dagger}}\hat{f}_{j_{4}\downarrow}.$

Here, $\hat{c}_{j\sigma}^{{\dagger}}$ is the creation operator of conduction
electron ($c$-electron) while $\hat{f}_{j\sigma}^{{\dagger}}$ denotes
$f$-electron at site $j$. $t_{ij}^{c},t_{ij}^{f}$ are hopping integral between
$i,j$ sites for $c$ and $f$-electron, respectively. Note that, $t_{ij}^{f}$ is
zero in standard PAM and $f$-electron is strictly local in that case so one
may call it local electron.Tsunetsugu  $E_{f}$ is the energy level of
$f$-electron and the hybridization strength between $c$ and $f$-electron is
$V$. (spin and site-dependent $V$ is also permitted and it leads to non-
trivial quantum topological phase such as topological Kondo insulator,Dzero ;
Dzero2012 ; Griffith2019 ; Dzero2016 ; Ghazaryan2021  and Kondo liquid with
hybridization nodeGhaemi2007 ; Ghaemi2008 ) Furthermore, chemical potential
$\mu$ has been added to fix electron’s density. $N_{s}$ is the number of
sites. The last term of $\hat{H}$ is the less unfamiliar HK
interaction,Hatsugai1992  (unlike the usual Hubbard interaction
$U\sum_{j}\hat{f}_{j\uparrow}^{{\dagger}}\hat{f}_{j\uparrow}\hat{f}_{j\downarrow}^{{\dagger}}\hat{f}_{j\downarrow}$
in standard PAM) which is an infinite-range interaction between four electrons
but preserves the center of motion for $f$-electron due to the constraint of
$\delta$ function. This interaction plays a fundamental role in solving this
model as we will see later.

Importantly, Eq. 1 is local in momentum space after Fourier transformation and
the resultant Hamiltonian reads as $\hat{H}=\sum_{k}\hat{H}_{k}$,

$\displaystyle\hat{H}_{k}$ $\displaystyle=$
$\displaystyle\sum_{\sigma}(\varepsilon_{k}^{c}-\mu)\hat{c}_{k\sigma}^{{\dagger}}\hat{c}_{k\sigma}+\sum_{\sigma}(\varepsilon_{k}^{f}+E_{f}-\mu)\hat{f}_{k\sigma}^{{\dagger}}\hat{f}_{k\sigma}$
(2) $\displaystyle+$ $\displaystyle
V\sum_{\sigma}(\hat{c}_{k\sigma}^{{\dagger}}\hat{f}_{k\sigma}+\hat{f}_{k\sigma}^{{\dagger}}\hat{c}_{k\sigma})+U\hat{f}_{k\uparrow}^{{\dagger}}\hat{f}_{k\uparrow}\hat{f}_{k\downarrow}^{{\dagger}}\hat{f}_{k\downarrow},$

where $\varepsilon_{k}^{c},\varepsilon_{k}^{f}$ are dispersion of electrons.
It is emphasized that the locality of above Hamiltonian stems from infinite-
range HK interaction preserving center of motion. In contrast, the Hubbard
interaction in momentum space is rather nonlocal as
$U\sum_{k,k^{\prime},q}\hat{f}_{k+q\uparrow}^{{\dagger}}\hat{f}_{k\uparrow}\hat{f}_{k^{\prime}-q\downarrow}^{{\dagger}}\hat{f}_{k^{\prime}\downarrow}$,
thus it cannot lead to simple formalism in our model.

Now, if we choose Fock state

$|n_{1},n_{2},n_{3},n_{4}\rangle\equiv(\hat{c}_{k\uparrow}^{{\dagger}})^{n_{1}}|0\rangle(\hat{c}_{k\downarrow}^{{\dagger}})^{n_{2}}|0\rangle(\hat{f}_{k\uparrow}^{{\dagger}})^{n_{3}}|0\rangle(\hat{f}_{k\downarrow}^{{\dagger}})^{n_{4}}|0\rangle$
(3)

with $n_{i}=0,1$ as basis, $\hat{H}_{k}$ can be written as a block-diagonal
$16\times 16$ matrix and a direct numerical diagonalization gives $16$ eigen-
energy $E_{k}(i)$ and eigen-state $\psi_{k}(i)$.($i=1,2...16$ and
$|\psi_{k}(1)\rangle$ is the ground-state for each $\hat{H}_{k}$). Details on
$\hat{H}_{k}$’s matrix is shown in Appendix.A.

Therefore, the many-body ground-state of $\hat{H}$ is just the direct-product
state of each $\hat{H}_{k}$’s ground-state, i.e.
$|\Psi_{g}\rangle=\prod_{k}|\psi_{k}(1)\rangle$ with corresponding ground-
state energy $E_{g}=\sum_{k}E_{k}(1)$. Similarly, excited states and their
energy are easy to be constructed, so our model $\hat{H}$ (Eq. 1) has been
solved since all eigen-states and eigen-energy are found.

It is noted that the solvability of our model involves only locality in
momentum space, therefore Eq. 1 is solvable for arbitrary lattice geometry,
spatial dimension and electron filling, in contrast to standard PAM, where
notorious fermion minus-sign problem and growth of quantum entanglement beyond
area-law prevent exact solution or reliable numerical simulation.Vekic1995 ;
Masuda2015 ; Schafer2019  Furthermore, our solvable model does not rely on
disorder average and large-$N$ limit, which are crucial in classic
Sherrington-Kirkpatrick’s spin glass model and the more recent Sachdev-Ye-
Kitaev model.Sherrington1975 ; Sachdev ; Maldacena ; Chowdhury  In addition,
including pairing term like
$\hat{c}_{k\uparrow}^{{\dagger}}\hat{c}_{-k\downarrow}^{{\dagger}}$,$\hat{f}_{k\uparrow}^{{\dagger}}\hat{f}_{-k\downarrow}^{{\dagger}}$
or $\hat{c}_{k\uparrow}^{{\dagger}}\hat{f}_{-k\downarrow}^{{\dagger}}$ as done
in previous studies on superconductivity of HK,Phillips2020 ; Zhu2021 ;
Zhao2022  does not change the solvability but only enlarges the dimension of
Hamiltonian in momentum space.

The remaining part of this article is organized as follows. In Sec. II, we
study a $1D$ chain from our model and its ground-state diagram has been
established. Several physical quantities like particle density distribution,
density of state, spectral function and Luttinger integral are calculated to
characterize possible states. Sec. III is devoted to some discussions, i.e.
the case study on $2D$ square lattice and the relation between particle
density and metallic states. Brief summary is given in Sec. IV and we also
suggest that modification of our model may be relevant to understand the
strong coupling physics in the topological Kondo insulator.

##  II An explicit example: the $1D$ model

###  II.1 The ground-state

Now, to extract the physics of our model, we focus on its $1D$ version,
(extension to other lattice is straightforward) whose Hamiltonian reads as
follows,

$\displaystyle\hat{H}$ $\displaystyle=$ $\displaystyle\sum_{k}\hat{H}_{k},$
$\displaystyle\hat{H}_{k}$ $\displaystyle=$
$\displaystyle\sum_{\sigma}(\varepsilon_{k}-\mu)\hat{c}_{k\sigma}^{{\dagger}}\hat{c}_{k\sigma}+\sum_{\sigma}(E_{f}-\mu)\hat{f}_{k\sigma}^{{\dagger}}\hat{f}_{k\sigma}$
(4) $\displaystyle+$ $\displaystyle
V\sum_{\sigma}(\hat{c}_{k\sigma}^{{\dagger}}\hat{f}_{k\sigma}+\hat{f}_{k\sigma}^{{\dagger}}\hat{c}_{k\sigma})+U\hat{f}_{k\uparrow}^{{\dagger}}\hat{f}_{k\uparrow}\hat{f}_{k\downarrow}^{{\dagger}}\hat{f}_{k\downarrow},$

where $\varepsilon_{k}=-2t\cos k$ is the $1D$ dispersion from nearest-
neighbor-hopping $t$ and $f$-electron’s dispersion is not included as in
standard PAM. To be specific, we set $t=V=1$ as energy unit (smaller $V$ is
more relevant to experiments in heavy fermion systems but physics will not be
changed) and change $E_{f},\mu,U$ to explore the ground-state phase diagram.

Figure 1:  Ground-state phase diagram of Eq. 4 with fixed $E_{f}=-2$. There
exit three kinds of insulating states like band insulator, hybridization
insulator, Mott insulator and one metallic state called correlated metal.

To characterize possible ground-state phases, we calculate some physical
observable, e.g. the particle distribution function
$n_{k}=\langle\hat{n}_{k}\rangle$,($\hat{n}_{k}=\hat{n}_{k}^{c}+\hat{n}_{k}^{f}=\sum_{\sigma}(\hat{c}_{k\sigma}^{{\dagger}}\hat{c}_{k\sigma}+\hat{f}_{k\sigma}^{{\dagger}}\hat{f}_{k\sigma}$)
and $\langle...\rangle$ is chosen as average over $|\psi_{k}(1)\rangle$ if we
focus on ground-state properties) density of state (DOS) of $c$-electron
$N_{c}(\omega)$, $f$-electron $N_{f}(\omega)$ and the total one $N(\omega)$
and the spectral function of $c$-electron $A_{c}(k,\omega)$ and of
$f$-electron $A_{f}(k,\omega)$.

To calculate the mentioned quantities, we first define retarded Green’s
function for $c$-electron in Heisenberg picture as
$G_{\sigma}^{c}(k,t)=-i\theta(t)\langle[\hat{c}_{k\sigma}(t),\hat{c}_{k\sigma}^{{\dagger}}]_{+}\rangle$.
($\theta(x)=1$ for $x>0$ and vanishes if $x<0$) Then, its Fourier
transformation is denoted as $G_{\sigma}^{c}(k,\omega)$, which has the
following Lehmann spectral representation,Coleman2015

$\displaystyle G_{\sigma}^{c}(k,\omega)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{16}\frac{|\langle\psi_{k}(1)|\hat{c}_{k}|\psi_{k\sigma}(j)\rangle|^{2}}{\omega+i0^{+}+E_{k}(1)-E_{k}(j)}$
$\displaystyle+$
$\displaystyle\sum_{j=1}^{16}\frac{|\langle\psi_{k}(1)|\hat{c}_{k\sigma}^{{\dagger}}|\psi_{k}(j)\rangle|^{2}}{\omega+i0^{+}+E_{k}(j)-E_{k}(1)}.$

At the same time, the retarded Green’s function for $f$-electron has identical
formalism with simple replacement
$\hat{c}_{k\sigma}\rightarrow\hat{f}_{k\sigma}$. Therefore,
$A_{c}(k,\omega)=\sum_{\sigma}A_{c}^{\sigma}(k,\omega)=\sum_{\sigma}-\frac{1}{\pi}\mathrm{Im}G_{\sigma}^{c}(k,\omega)$.
As for DOS, we have the relation
$N(\omega)=N_{c}(\omega)+N_{f}(\omega)=\frac{1}{N_{s}}\sum_{k}(A_{c}(k,\omega)+A_{f}(k,\omega))$.

In Fig. 1, we fix $E_{f}=-2$ and establish a ground-state phase diagram for
different $\mu$ and $U$. (Other choice of $E_{f}$ is explored in Appendix.B
and no physics is changed)

Here, particle density $n=0,4$ ($n=\frac{1}{N_{s}}\sum_{k}n_{k}$) correspond
to trivial band insulator with empty or full occupation for each $k$-state.
(the corresponding wave-functions are
$\prod_{k}|0000\rangle_{k},\prod_{k}|1111\rangle_{k}$ if one utilizes the Fock
state Eq. 3)

For $n=2$, we observe an insulator dominated by hybridization strength $V$ and
we call it hybridization insulator (HI). Physically, the origin of HI can be
understood from $U=0$ limit, and one has the following quasi-particle
Hamiltonian

$\hat{H}_{k}=\sum_{\sigma}(E_{k+}\hat{\alpha}^{{\dagger}}_{k\sigma}\hat{\alpha}_{k\sigma}+E_{k-}\hat{\beta}^{{\dagger}}_{k\sigma}\hat{\beta}_{k\sigma})$
(5)

with the help of Bogoliubov transformation
$\hat{\alpha}_{k\sigma}=\mu_{k}\hat{c}_{k\sigma}+\nu_{k}\hat{f}_{k\sigma}$ and
$\hat{\beta}_{k\sigma}=-\nu_{k}\hat{c}_{k\sigma}+\mu_{k}\hat{f}_{k\sigma}$.
The quasi-particle energy
$E_{k\pm}=\frac{1}{2}(\varepsilon_{k}+E_{f}\pm\sqrt{(\varepsilon_{k}-E_{f})^{2}+4V^{2}})-\mu$
and
$\mu_{k}^{2}=\frac{1}{2}\left(1+\frac{\varepsilon_{k}-E_{f}}{\sqrt{(\varepsilon_{k}-E_{f})^{2}+4V^{2}}}\right)=1-\nu_{k}^{2}$.
Then, if the lower band $E_{k-}$ is fully occupied, but the upper band
$E_{k+}$ is empty, an insulator (with ground-state wave-function
$\prod_{k\sigma}\hat{\beta}^{{\dagger}}_{k\sigma}|0\rangle$) with particle
density $n=2$ appears, which has the indirect gap $\sim V$ and direct gap
$\Delta\equiv\mathrm{min}(E_{k+})-\mathrm{max}(E_{k+})\sim\frac{V^{2}}{t}$.

Next, let us examine the effect of finite $U$. When $U<\Delta$, we expect the
gap does not close and the adiabatic principle of Landau applies, thus the
system is still in HI but with renormalized gap and dispersion. Using
parameters in our model ($t=V=1$), we find $\Delta\sim 1$ and HI is stable if
$U<\Delta\sim 1$. This is indeed the case in Fig. 1 and we think the above
picture is justified. In addition, we note that in standard PAM, HI evolves
into the antiferromagnetic insulator (on square lattice) or Kondo insulator
when Hubbard-$U$ increases from $U=0$.Vekic1995

Figure 2:  Particle density distribution $n_{k},n_{k}^{f}$ and $n_{k}^{c}$
versus momentum $k$ with $E_{f}=-2$. (a) HI with $U=0.5,\mu=-1.3$; (b) MI with
$U=6,\mu=3$; (c) CM with $U=6,\mu=0$. Figure 3:  Density of state
$N(\omega),N_{f}(\omega)$ and $N_{c}(\omega)$ with $E_{f}=-2$. (a) HI with
$U=0.5,\mu=-1.3$; (b) MI with $U=6,\mu=3$; (c) CM with $U=6,\mu=0$.

Next, we turn to $n=3$ regime, which is clearly driven by interaction and it
can be denoted as Mott insulator (MI). From Fig. 2(b), we see that in MI, the
particle density distribution $n_{k}$ is fixed to $3$ for each momentum,
however, neither $n_{k}^{c}$ nor $n_{k}^{f}$ is fixed to integer, (so this
state cannot be an orbital-selective Mott insulator by definitionPepin2007 )
which should be compared with the ones in HI (Fig. 2(a)).

Furthermore, Fig. 3 shows the DOS in HI (Fig. 3(a)) and MI (Fig. 3(b)).
Although both MI and HI have noticeable gap near $\omega=0$, it is clear that
a larger gap opens in MI than in HI and the former exhibits strong asymmetry
for its DOS. Actually, a closer look at MI’s spin-resolved DOS in Fig. 4(a)(b)
implies that the DOS above Fermi energy ($\omega=0$) is dominated by spin-down
electron while the $\omega<0$ part is contributed mainly from spin-up
electron. This property seems to be the generic feature for HK-like models.
Instead, as can seen in Fig. 4(c)(d), the spin degree of freedoms are
degenerated in HI, (see e.g. the quasi-particle Hamiltonian Eq. ) and they
contribute equally to DOS
($N_{f}^{\uparrow}=N_{f}^{\downarrow},N_{c}^{\uparrow}=N_{c}^{\downarrow}$ in
HI).

Figure 4:  The spin-resolved density of state for $f$ and $c$-electron
$N_{f}^{\uparrow}(\omega),N_{f}^{\downarrow}(\omega),N_{c}^{\uparrow}(\omega),N_{c}^{\downarrow}(\omega)$
with $E_{f}=-2$. (a)(b) MI with $U=6,\mu=3$; (c)(d) HI with $U=0.5,\mu=-1.3$.

The spectral function of $c$ and $f$-electron
$A_{c/f}(k,\omega)=\sum_{\sigma}A_{c/f}^{\sigma}(k,\omega)$ is plotted in Fig.
5 and Fig. 6. We have checked that the spin-resolved spectral function
$A_{c}^{\sigma},A_{f}^{\sigma}$ satisfy the sum-rule
$\int_{-\infty}^{\infty}d\omega A_{c/f}^{\sigma}(k,\omega)=1$. It is observed
that in MI, (Fig. 5(b) and Fig. 6(b)) the $c$-electron has dispersive band
below Fermi energy ($\omega=0$) while a rather flat band appears above Fermi
energy for $f$-electron. In contrast, two dispersive bands exist near Fermi
energy for both of $c$ and $f$-electron in HI, (Fig. 5(a) and Fig. 6(a)) which
embody the well-defined quasi-particle band $E_{k\pm}$.

Figure 5:  Spectral function of $c$-electron $A_{c}(k,\omega)$ with
$E_{f}=-2$. (a) HI with $U=0.5,\mu=-1.3$; (b) MI with $U=6,\mu=3$; (c) CM with
$U=6,\mu=0$. Figure 6:  Spectral function of $f$-electron $A_{f}(k,\omega)$
with $E_{f}=-2$. (a) HI with $U=0.5,\mu=-1.3$; (b) MI with $U=6,\mu=3$; (c) CM
with $U=6,\mu=0$.

Finally, the remaining state in the phase diagram is just the metallic one,
which is denoted as correlated metal (CM). The typical particle density
distribution of CM has been shown in Fig. 2(c). It is found that, in contrast
with Fermi Liquid (FL) or more simply the Fermi gas, $n_{k}$ (also for
$n_{k}^{c},n_{k}^{f}$) has two-jump behavior at certain momentum (one may call
it Fermi point), whose structure is comparable with the non-Fermi liquid state
in HK model.Hatsugai1992  Therefore, it indicates CM should not be a FL but
non-Fermi liquid. The corresponding DOS and spectral function of CM have been
investigated in Fig. 3(c), Fig. 5(c) and Fig. 6(c), and an interesting multi-
band structure is visible though we have not found any analytical expression
to explain this structure. (According to Appendix.A, we have $11$ different
energy level for each $k$, thus there exist at most $11$ band-like structure
in DOS or spectral function.)

To encode the nature of CM, we examine whether CM satisfies the Luttinger
theorem,Luttinger1960a ; Luttinger1960b ; Oshikawa2000 ; Else2021  which has
been believed to be defining feature of FL. The Luttinger theorem tells us
that for FL-like states, (including Luttinger liquid in $1D$) the following
integral, i.e. Luttinger integral, must be equal to particle
density,Dzyaloshinskii2003 (here we use its $1D$ version)

$I_{LI}=\sum_{\sigma}\int\frac{dk}{2\pi}\theta(\mathrm{Re}G_{\sigma}(k,\omega=0)).$
(6)

In above formula, the $\theta$-function counts the positive part of the real
part of the retarded Green’s function at zero frequency. In our case, we have
two Luttinger integral $I_{LI}^{c},I_{LI}^{f}$ for $c$ and $f$-electron. In
Fig. 7, we have plotted $I_{LI}^{c},I_{LI}^{f}$ versus particle density
$(n_{c},n_{f})$ for different chemical potential $\mu$ with fixed
$E_{f}=-2,U=6$.

Figure 7:  Luttinger integral ($I_{LI}^{c},I_{LI}^{f}$) versus particle
density $(n_{c},n_{f})$ for different chemical potential $\mu$ with
$E_{f}=-2,U=6$.

It is obvious that $I_{LI}^{c}\neq n_{c}$ and $I_{LI}^{f}\neq n_{f}$, thus the
CM state ($-3<\mu<4$) violates the Luttinger theorem and it is indeed a non-
Fermi liquid.

A careful reader may notice that $I_{LI}^{c},I_{LI}^{f}$ are nonmonotonic when
$\mu$ changes. A straightforward explanation seems to be that such behavior
results from the change of topology of Fermi surface or band structure, i.e.
the famous Lifshitz transition. When Lifshitz transition appears with tuning
$\mu$, the particle density will show kink-like structure. In Fig. 7, one see
that when kinks emerge in $n_{c},n_{f}$, the Luttinger integral
$I_{LI}^{c},I_{LI}^{f}$ exhibit strong deviation from Luttinger theorem.
Therefore, CM is not a single phase but including many Lifshitz transitions.

###  II.2 How about the phase transition?

We have explored the ground-state phase diagram and there exit four states
namely BI, HI, MI and CM. Except for the trivial BI, we expect quantum
transitions between metallic and insulating states (CM-MI and CM-HI). Since
there is no explicit candidate Landau’s order parameter with noticeable
symmetry-breaking, a natural guess suggests these transitions are of nature of
the Lifshitz transition. One may argue that an alternative explanation can be
certain topological order,Wen1990 ; Senthil2001 ; Oshikawa2006  but such
possibility in $1D$ is not plausible since protypical $Z_{2}$ topological
order is not stable in $1D$ unless one ignores the effect of effective
electric field in $Z_{2}$ lattice gauge field theory.Kogut1979 ; Prosko  The
possibility of topological order in $2D$ version of our model or other HK-like
models have not been explored and we suspect that it will not relate to these
mentioned models. After all, in this work, we only examine the Lifshitz
transition.

To locate and characterize such putative transition, we inspect the behavior
of charge susceptibility $\chi_{c}=\frac{\partial n}{\partial\mu}$, which
diverges at critical point driven by charge fluctuation like Lifshitz
transition.

Figure 8:  (a) The charge susceptibility $\chi_{c}$ with $E_{f}=-2$; (b)
Particle density difference $\Delta n$ near critical point versus fitted
scaling formula Eq. 7 with $E_{f}=-2$.

As what can be seen in Fig. 8(a), the divergent $\chi_{c}$ is able to locate
phase boundary, which agrees perfectly with our previous phase diagram Fig. 1.

Now, let we focus on the phase transition between CM and MI. To be specific,
consider $U=5,6,7,8$ while tuning $\mu$ with fixed $E_{f}=-2$. These are the
chemical potential-driven transitions and their critical points locate in
$\mu=\mu_{c}=2.595,2.616,2.640,2.646$. According to general ideas of quantum
phase transition, we expect the particle density near critical point has the
following scaling form,Continentino

$\Delta n=n-n_{0}\sim(\mu-\mu_{c})^{\beta},$ (7)

where $n_{0}$ denotes certain background which should be subtracted, $\mu_{c}$
is the location of critical point and $\beta$ is the critical exponent. The
above scaling formula works well near critical points as shown in Fig. 8(b),
and one finds that $\beta\simeq 0.5$, which is the critical exponent for
expected Lifshitz transition. ($\beta=d/2$ for free fermion Lifshitz
transition universality with dimension of space $d$ and the dynamic critical
exponent $z=2$) Furthermore, the ground-state energy and charge susceptibility
also have scaling form $E_{g}-E_{g}^{0}\sim(\mu-\mu_{c})^{(d+2)/2}$,
$\chi_{c}\sim(\mu-\mu_{c})^{(d-2)/2}$,Continentino ; Vitoriano2000  which are
consistent with our calculation if choosing spatial dimension $d=1$.
Therefore, we conclude that the chemical potential-driven CM-MI transition is
in fact the Lifshitz transition.

One may note that there also exists interaction-driven CM-MI transition.
Although we have not explored its properties in detail, based on our knowledge
on HK-like models, this transition should belong to the universality of
Lifshitz transition, as well.Continentino ; Vitoriano2000  In addition, it is
not surprise to find that the CM-HI transition is of the nature of Lifshitz
transition and we will not investigate it further.

###  II.3 Is there any effective field theory description for CM, MI or HI?

In the study of correlated electron systems, the effective (field) theory
description is very useful since it can give us the low-energy theory, which
is truly responsible for understanding on low-temperature/low-frequency
thermodynamics and transport. Frankly speaking, we have no idea to construct a
suitable effective theory for CM and MI. At this point, one may ask why the
state-of-art $1D$ bosonization is not able to attack our model. The reason is
that the Luttinger theorem, which fixes the Fermi point (Fermi surface in
$1D$) for given particle density,Giamarchi  is violated in our model, thus the
starting point of bosonization, i.e. the low-energy expansion around Fermi
point, is meaningless. Consequently, we do not expect bosonization technique
is useful to our model. (We have also tried to relate metallic CM to
conformal-field-theory (CFT) but have failed since the finite-size scaling of
CM in our model is not consistent with well-known CFT models, like minimal
models.Francesco )

Next, one may note that our model is similar to the original HK model, and the
latter one has many simple and beautiful analytic results. Thus, if we can
project our model into HK model, life will be easy. Let us try this idea in
terms of path integral formalism. The imaginary-time action of our model is
just like

$\displaystyle S$ $\displaystyle=$ $\displaystyle\sum_{k}\int
d\tau\sum_{\sigma}\bar{c}_{k\sigma}(\partial_{\tau}+\varepsilon_{k}-\mu)c_{k\sigma}+\sum_{\sigma}\bar{f}_{k\sigma}(\partial_{\tau}+E_{f}-\mu)f_{k\sigma}$
(8) $\displaystyle+$ $\displaystyle
V\sum_{\sigma}(\bar{c}_{k\sigma}f_{k\sigma}+\bar{f}_{k\sigma}c_{k\sigma})+U\bar{f}_{k\uparrow}f_{k\uparrow}\bar{f}_{k\downarrow}f_{k\downarrow},$

where $\bar{c}_{k\sigma},c_{k\sigma},\bar{f}_{k\sigma},f_{k\sigma}$ are anti-
commutative Grassman field. Note that the HK interaction is active for
$f$-electron, we may integrate $c$-electron out to get a $f$-electron-only
theory. After integrating out c-electron’s degree of freedom, we find the
following action for $f$-electron,

$\displaystyle S_{f}$ $\displaystyle=$ $\displaystyle\sum_{k}\int
d\tau\sum_{\sigma}\bar{f}_{k\sigma}(\partial_{\tau}+E_{f}-\mu)f_{k\sigma}+U\int
d\tau\bar{f}_{k\uparrow}f_{k\uparrow}\bar{f}_{k\downarrow}f_{k\downarrow}$ (9)
$\displaystyle+$ $\displaystyle\int d\tau\int
d\tau^{\prime}\sum_{\sigma}\bar{f}_{k\sigma}(\tau)V^{2}G_{k}^{0}(\tau-\tau^{\prime})f_{k\sigma}(\tau^{\prime}).$

Here, $G_{k}^{0}(\tau)$ is the Fourier transformation of free $c$-electron
Green’s function $G^{0}(k,\omega_{n})=(i\omega_{n}-\varepsilon_{k}+\mu)^{-1}$.
We see that the above action is nonlocal in imaginary-time thus cannot be
written as the HK model.

As for HI, in the previous section, we have analyzed its $U=0$ limit and
argued that it is stable if the gap still opens. Here, motivated by Eq. 8, we
treat HK interaction as perturbation and the induced correction at first order
gives rise to the Hartree self-energy
$\Sigma_{\sigma}(k,\omega)=Un_{k\bar{\sigma}}^{f}$.($n_{k\bar{\sigma}}^{f}=\langle\hat{f}_{k\bar{\sigma}}^{{\dagger}}\hat{f}_{k\bar{\sigma}}\rangle$
with $\bar{\sigma}\equiv-\sigma$) Therefore, we have $f$-electron Green’s
function

$G_{\sigma}^{f}(k,\omega)=\frac{1}{(G_{0}^{f}(k,\omega))^{-1}-Un_{k\bar{\sigma}}^{f}}$
(10)

with $G_{0}^{f}(k,\omega)=(\omega-
E_{f}+\mu-V^{2}(\omega-\varepsilon_{k}+\mu)^{-1})^{-1}$ being the $f$-electron
Green’s function in $U=0$ limit. Now, the pole of $G_{\sigma}^{f}(k,\omega)$
determines the renormalized quasi-particle dispersion, whose form is

$\displaystyle\tilde{E}_{k\sigma\pm}=\frac{1}{2}[\varepsilon_{k}+E_{f}+Un_{k\bar{\sigma}}^{f}\pm
A_{k\sigma}]-\mu$ $\displaystyle
A_{k\sigma}=\sqrt{(\varepsilon_{k}-E_{f})^{2}+(Un_{k\bar{\sigma}}^{f})^{2}+2Un_{k\bar{\sigma}}^{f}(3\varepsilon_{k}+E_{f}-4\mu)}.$

##  III Discussion

###  III.1 Example on $2D$ square lattice

In previous section, we have investigated a $1D$ model and established its
phase diagram. In this subsection, we will briefly discuss the properties on
the $2D$ square lattice. For this lattice, the only difference from $1D$ model
is that the nearest-neighbor-hopping for $c$-electron generates
$\varepsilon_{k}=-2t(\cos k_{x}+\cos k_{y})$ instead of $-2t\cos k$. Others
are the same with our previous discussion.

To get rough intuition on this $2D$ problem, we have plotted its ground-state
phase diagram in Fig. 9 with $t=V=1,E_{f}=-2$. It is seen that the structure
of this phase diagram is quite similar to the $1D$ version Fig. 1, therefore
we expect that the findings in the previous $1D$ model may be generic for all
spatial dimensions.

Figure 9:  Ground-state phase diagram of $2D$ square lattice with fixed
$E_{f}=-2$. Note that it is similar with $1D$ case Fig. 1.

In addition, we have shown the $f$-electron’s zero-frequency spectral function
$A_{f}(k_{x},k_{y},\omega=0)$ on the $2D$ square lattice in Fig. 10, which is
able to encode the structure of Fermi surface. Obviously, one observes that
tuning chemical potential $\mu$ drives the transition of Fermi surface, which
is the counterpart of Lifshitz transition in $2D$.

Figure 10:  The $f$-electron’s zero-frequency spectral function
$A_{f}(k_{x},k_{y},\omega=0)$ on $2D$ square lattice with $E_{f}=-2,U=8$. (a)
$\mu=-4$; (b) $\mu=-2$; (c) $\mu=0$; (d) $\mu=2$; (e) $\mu=4$; (f) $\mu=6$.

The corresponding real part of $f$-electron’s Green’s function at $\omega=0$
has been shown in Fig. 11, where clear jump from $-\infty$ to $\infty$ appears
indicates the existence of Fermi surface.

Figure 11:  The real part $f$-electron’s zero-frequency Green’s function
$\mathrm{Re}G_{f}(k_{x},k_{y},\omega=0)$ on $2D$ square lattice with
$E_{f}=-2,U=8$. (a) $\mu=-4$; (b) $\mu=-2$; (c) $\mu=0$; (d) $\mu=2$; (e)
$\mu=4$; (f) $\mu=6$.

###  III.2 Relation between particle density and metallic state

We have seen that in the ground-state of Eq. 4, the particle density of
insulating states is integer ($n=0,2,3,4$) while the metallic CM is generally
not an integer. Here, following the treatment in Ref. Yamanaka1997  which
utilizes the classic proof of Lieb-Schultz-Mattis (LSM) theorem, we provide an
intuitive argument on this point.

At first, we rewrite Eq. 4 into its real space version, whose Hamiltonian
reads

$\displaystyle\hat{H}$ $\displaystyle=$
$\displaystyle-t\sum_{j\sigma}(\hat{c}_{j\sigma}^{{\dagger}}\hat{c}_{j+1\sigma}+\hat{c}_{j+1\sigma}^{{\dagger}}\hat{c}_{j\sigma})-\mu\sum_{j\sigma}\hat{c}_{j\sigma}^{{\dagger}}\hat{c}_{j\sigma}$
(11) $\displaystyle+$
$\displaystyle\sum_{j\sigma}(E_{f}-\mu)\hat{f}_{j\sigma}^{{\dagger}}\hat{f}_{j\sigma}+V\sum_{j\sigma}(\hat{c}_{j\sigma}^{{\dagger}}\hat{f}_{j\sigma}+\hat{f}_{j\sigma}^{{\dagger}}\hat{c}_{j\sigma})$
$\displaystyle+$
$\displaystyle\frac{U}{N_{s}}\sum_{j_{1}j_{2}j_{3}j_{4}}\delta_{j_{1}+j_{3}=j_{2}+j_{4}}\hat{f}_{j_{1}\uparrow}^{{\dagger}}\hat{f}_{j_{2}\uparrow}\hat{f}_{j_{3}\downarrow}^{{\dagger}}\hat{f}_{j_{4}\downarrow}.$

Then, consider periodic boundary condition and define the twist operator

$\hat{U}=e^{i\sum_{j=1}^{N_{s}}\frac{2\pi
j}{N_{s}}\sum_{\sigma}(\hat{c}_{j\sigma}^{{\dagger}}\hat{c}_{j\sigma}+\hat{f}_{j\sigma}^{{\dagger}}\hat{f}_{j\sigma})}.$
(12)

If we denote the ground-state as $|\Psi_{0}\rangle$, then a new state is
constructed by applying $\hat{U}$, i.e. the twisted state
$\hat{U}|\Psi_{0}\rangle$. So, one can calculate the energy difference

$\displaystyle\Delta E$ $\displaystyle=$
$\displaystyle\langle\Psi_{0}|\hat{U}^{-1}\hat{H}\hat{U}|\Psi_{0}\rangle-\langle\Psi_{0}|\hat{H}|\Psi_{0}\rangle$
$\displaystyle=$
$\displaystyle\sum_{\sigma}\sum_{j=1}^{N_{s}}(2-e^{-i2\pi/N_{s}}-e^{i2\pi/N_{s}})t\langle\hat{c}_{j\sigma}^{{\dagger}}\hat{c}_{j+1\sigma}\rangle.$

When $N_{s}>>1$, $\Delta E\sim\mathcal{O}(1/N_{s})$, thus there exists at
least one low-energy state near ground-state. Furthermore, for the translation
operator $\hat{T}$, we have
$\hat{T}\hat{U}\hat{T}^{-1}=\hat{U}e^{-i2\pi\hat{n}}$.
($\hat{n}=\frac{1}{N_{s}}\sum_{j\sigma}(\hat{c}_{j\sigma}^{{\dagger}}\hat{c}_{j\sigma}+\hat{f}_{j\sigma}^{{\dagger}}\hat{f}_{j\sigma})$)
Assume the ground-state $|\Psi_{0}\rangle$ has particle density $n$ and
momentum $P_{0}$, then

$\hat{T}\hat{U}|\Psi_{0}\rangle=\hat{U}\hat{T}e^{-i2\pi\hat{n}}|\Psi_{0}\rangle=e^{-i2\pi
n}e^{-iP_{0}}\hat{U}|\Psi_{0}\rangle,$ (13)

which means the twisted state is the eigenstate of momentum $2\pi n+P_{0}$. If
$n$ is not an integer, $\hat{U}|\Psi_{0}\rangle$ and $|\Psi_{0}\rangle$ must
be orthogonal, thus the system is gapless in this situation and it corresponds
to metallic state. In contrast, when $n$ is an integer, we expect
$\hat{U}|\Psi_{0}\rangle$ and $|\Psi_{0}\rangle$ are the same state which
suggests that there exist no low-energy state and the system should be an
insulator. Therefore, we now understand why $n=0,2,3,4$ in our model
correspond to insulating states and generic electron’s density implies
metallic state.

##  IV Conclusion and Future direction

In conclusion, we have provided a solvable quantum many-body model, whose
solvability is due to locality in momentum space and analyzed the ground-state
properties in its $1D$ version. Importantly, we find a non-Fermi liquid-like
metallic state violating the Luttinger theorem and an interaction-driven Mott
insulator in ground-state. The involved quantum phase transition between these
two states belongs to the universality of Lifshitz transition. The phase
diagram of the $2D$ version of our model is similar to $1D$ and it is expected
that the findings in the latter may be generic for all spatial dimensions.

In light of recent theoretical and experimental works on topological Kondo
insulator, particularly the unusual quantum oscillation found in SmB6 and
YbB12,Li2014 ; Tan2015 ; Xiang2018 ; Knoll2015 ; Zhang2016 ; Riseborough2017 ;
Baskaran2015 ; Varma2020 ; Erten2016 ; Knolle2017 ; Rao2019  our solvable
model can be modified (with momentum and spin-dependent hybridization
strength) to attack topological phases relevant to these interesting
$f$-electron compounds, for example a solvable model to give insight into $1D$
topological Kondo insulator isZhong2017 ; Lisandrini ; Luo2021

$\displaystyle\hat{H}$ $\displaystyle=$
$\displaystyle-t\sum_{j\sigma}(\hat{c}^{{\dagger}}_{j\sigma}\hat{c}_{j+1\sigma}+\hat{c}^{{\dagger}}_{j+1\sigma}\hat{c}_{j\sigma})-\mu\sum_{j\sigma}\hat{c}_{j\sigma}^{{\dagger}}\hat{c}_{j\sigma}$
$\displaystyle+$ $\displaystyle\frac{1}{2}\sum_{j\sigma,\delta=\pm
1}V_{j,j+\delta}(\hat{c}^{{\dagger}}_{j+\delta\sigma}\hat{f}_{j\sigma}+\hat{f}_{j\sigma}^{{\dagger}}\hat{c}_{j+\delta\sigma})$
$\displaystyle+$ $\displaystyle
E_{f}\sum_{j\sigma}\hat{f}_{j\sigma}^{{\dagger}}\hat{f}_{j\sigma}+\frac{U}{N_{s}}\sum_{j_{1}j_{2}j_{3}j_{4}}\delta_{j_{1}+j_{3}=j_{2}+j_{4}}\hat{f}_{j_{1}\uparrow}^{{\dagger}}\hat{f}_{j_{2}\uparrow}\hat{f}_{j_{3}\downarrow}^{{\dagger}}\hat{f}_{j_{4}\downarrow},$

with $V_{j,j+1}=V,V_{j,j-1}=-V$. Such exciting possibility will be explored in
our future work and we hope our model will be a good starting point to explore
unexpected physics in correlated electron systems.

##  Appendix A Diagonalization of $\hat{H}_{k}$

Before diagonalizing $\hat{H}_{k}$, we observe that particle number
$\hat{n}_{k}=\sum_{\sigma}(\hat{c}_{k\sigma}^{{\dagger}}\hat{c}_{k\sigma}+\hat{f}_{k\sigma}^{{\dagger}}\hat{f}_{k\sigma})$
and spin
$\hat{S}^{z}_{k}=\frac{1}{2}(\hat{c}_{k\uparrow}^{{\dagger}}\hat{c}_{k\uparrow}-\hat{c}_{k\downarrow}^{{\dagger}}\hat{c}_{k\downarrow}+\hat{f}_{k\uparrow}^{{\dagger}}\hat{f}_{k\uparrow}-\hat{f}_{k\downarrow}^{{\dagger}}\hat{f}_{k\downarrow})$,
are both conserved in $\hat{H}_{k}$. Therefore, the $16\times 16$-matrix of
$\hat{H}_{k}$ has the block-diagonal form as $H_{k}=1\oplus 2\oplus 2\oplus
1\oplus 1\oplus 4\oplus 2\oplus 2\oplus 1$. The first $1$ means $|0000\rangle$
with $n_{k}=0,S_{k}^{z}=0$ is the eigen-state with eigen-energy $0$. The
second $2$ encodes that $H_{k}=\left(\begin{array}[]{cc}\xi_{k}^{c}&V\\\
V&\xi_{k}^{f}\\\ \end{array}\right)$ in the subspace formed by $|1000\rangle$
and $|0010\rangle$ with $n_{k}=1,S_{k}^{z}=1/2$. Here, we have introduced
$\xi_{k}^{c}=\varepsilon_{k}^{c}-\mu,\xi_{k}^{f}=\varepsilon_{k}^{f}+E_{f}-\mu$
to simplify the expression. The third $3$ gives the same $2\times 2$-matrix,
which is formed by $|0100\rangle$ and $|0001\rangle$ with
$n_{k}=1,S_{k}^{z}=-1/2$. The fourth and fifth $1$ produce identical energy
$\xi_{k}^{c}+\xi_{k}^{f}$ for $|1010\rangle$ state with $n_{k}=2,S^{z}_{k}=1$
and $|0,1,0,1\rangle$ state with $n_{k}=2,S^{z}_{k}=-1$. Now, we come with the
sixth $4$, whose subspace is formed by
$|1100\rangle$,$|1001\rangle$,$|0110\rangle$ and $|0011\rangle$ with
$n_{k}=2,S_{k}^{z}=0$. Therefore, $\hat{H}_{k}$ has the following $4\times
4$-matrix representation,

$H_{k}=\left(\begin{array}[]{cccc}2\xi_{k}&V&-V&0\\\
V&\xi_{k}^{c}+\xi_{k}^{f}&0&V\\\ -V&0&\xi_{k}^{c}+\xi_{k}^{f}&-V\\\
0&V&-V&2\xi_{k}^{f}+U\\\ \end{array}\right).$ (14)

Although analytic expression of eigen-energy and eigen-state is available, it
is too complicated to use, so we diagonalize above matrix numerically.

Then, the seventh and eighth $2$ give the same
$H_{k}=\left(\begin{array}[]{cc}2\xi_{k}^{c}+\xi_{k}^{f}&-V\\\
-V&\xi_{k}^{c}+2\xi_{k}^{f}+U\\\ \end{array}\right)$ , which is formed by
$|1110\rangle$,$|1011\rangle$ with $n_{k}=3,S_{k}^{z}=1/2$ and
$|1101\rangle$,$|0111\rangle$ with $n_{k}=3,S^{z}_{k}=-1/2$, respectively. The
last $1$ means that $|1111\rangle$ state has eigen-energy
$2\xi_{k}^{c}+2\xi_{k}^{f}+U$.

Based on above results, we conclude that in terms of Fock states
$|n_{1},n_{2},n_{3},n_{4}\rangle$,($n_{i}=0,1$) the Hamiltonian $\hat{H}_{k}$
has been diagonalized and we obtain $16$ eigen-energy $E_{k}(i)$ and eigen-
state $\psi_{k}(i)$.($i=1,2...16$) With the same spirit, one can construct
matrix expression like fermionic operator
$\hat{c}_{k\sigma},\hat{f}_{k\sigma}$, which are useful to calculate Green’s
function and spectral function.

##  Appendix B Phase diagram for $E_{f}=0$ and $E_{f}=2$

Here, we plot the ground-state phase diagram for $1D$ model with $E_{f}=0$ and
$E_{f}=2$ in Fig. 13 and Fig. 12. Other parameters are chosen as the
$E_{f}=-2$ case. We see that the structure of all phase diagrams for
$E_{f}=-2,0,2$ is similar and the generic physics does not change.
Additionally, we observe that increasing $E_{f}$ has the effect to enlarge the
$n=2$ HI and $n=3$ MI regime.

Figure 12:  Ground-state phase diagram of Eq. 3 with fixed $E_{f}=0$. Figure
13:  Ground-state phase diagram of Eq. 3 with fixed $E_{f}=2$.

##  Appendix C Finite temperature

After presenting results on ground-state in the main text, we now study the
finite temperature case. At finite-$T$, the thermodynamics of our model is
determined by its free energy density $f$, which is related to partition
function $\mathcal{Z}$ as

$\displaystyle f=-\frac{T}{N_{s}}\ln\mathcal{Z},$
$\displaystyle\mathcal{Z}=\mathrm{Tr}e^{-\beta\hat{H}}=\prod_{k}\mathrm{Tr}e^{-\beta\hat{H}_{k}}=\prod_{k}\left(\sum_{j=1}^{16}e^{-\beta
E_{k}(j)}\right).$ (15)

Here, one notes that the partition function is easy to calculate since each
$k$-state contributes independently. Then, the typical thermodynamic quantity,
i.e. the heat capacity, is calculated by standard thermodynamic relation
$C_{V}=-T\frac{\partial^{2}f}{\partial T^{2}}$, which has been shown in Fig.
14.

Figure 14:  The heat capacity $C_{V}$ versus $\mu$ and $T$ with fixed
$E_{f}=-2,U=6$.

In addition to $C_{V}$, one can also calculate spin susceptibility $\chi_{s}$
if inserting Zeeman energy term
$\hat{H}_{h}=-h\hat{S}_{k}^{z}=-\frac{h}{2}(\hat{c}_{k\uparrow}^{{\dagger}}\hat{c}_{k\uparrow}-\hat{c}_{k\downarrow}^{{\dagger}}\hat{c}_{k\downarrow}+\hat{f}_{k\uparrow}^{{\dagger}}\hat{f}_{k\uparrow}-\hat{f}_{k\downarrow}^{{\dagger}}\hat{f}_{k\downarrow})$
into Hamiltonian $\hat{H}_{k}$. Then, it follows that the magnetization
$M=-\frac{\partial f}{\partial h}$ and $\chi_{s}=\frac{\partial M}{\partial
h}=-\frac{\partial^{2}f}{\partial h^{2}}$.

## References

  * (1) S. Sachdev and J. Ye, Phys. Rev. Lett. 70, 3339 (1993).
  * (2) J. Maldacena and D. Stanford, Phys. Rev. D 94, 106002 (2016).
  * (3) D. Chowdhury, A. Georges, O. Parcollet and S. Sachdev, arXiv:2109.05037.
  * (4) A. Kitaev, Ann. Phys. 303, 2 (2003).
  * (5) A. Kitaev, Ann. Phys. 321, 2 (2006).
  * (6) Y. Zhou, K. Kanoda and T.-K. Ng, Rev. Mod. Phys. 89, 025003 (2017).
  * (7) C. Prosko, S.-P. Lee and J. Maciejko, Phys. Rev. B 96, 205104 (2017).
  * (8) Y. Zhong, Y.-F. Wang and H.-G. Luo, Phys. Rev. B 88, 045109 (2013).
  * (9) A. Smith, J. Knolle, D. L. Kovrizhin and R. Moessner, Phys. Rev. Lett. 118, 266601 (2017).
  * (10) Z. Chen, X. Li, and T. K. Ng, Phys. Rev. Lett. 120, 046401 (2018).
  * (11) Y. Hatsugai and M. Kohmoto, J. Phys. Soc. Jpn. 61, 2056 (1992).
  * (12) G. Baskaran, Mod. Phys. Lett. B 5, 643 (1991).
  * (13) Y. Hatsugai, M. Kohmoto, T. Koma and Y.-S. Wu, Phys. Rev. B 54, 5358 (1996).
  * (14) P. W. Phillips, C. Setty and S. Zhang, Phys. Rev. B 97, 195102 (2018).
  * (15) L. Yeo and P. W. Phillips, Phys. Rev. D 99, 094030 (2019).
  * (16) P. W. Phillips, L. Yeo and E. W. Huang, Nat. Phys. 16, 1175 (2020).
  * (17) K. Yang, Phys. Rev. B 103, 024529 (2021).
  * (18) H.-S. Zhu, Z. Li, Q. Han, and Z. D. Wang, Phys. Rev. B 103, 024514 (2021).
  * (19) J. Zhao, L. Yeo, E. W. Huang and P. W. Phillips, Phys. Rev. B 105, 184509 (2022).
  * (20) C. Setty, arXiv:2105.15205.
  * (21) P. Mai, B. Feldman and P. W. Phillips, arXiv:2207.01638.
  * (22) E. W. Huang, G. La Nave and P. W. Phillips, Nat. Phys. 18, 511 (2022).
  * (23) Y. Li, V. Mishra, Y. Zhou and F.-C. Zhang, arXiv:2207.01904.
  * (24) J. Bardeen, L. N. Cooper and J. R. Schrieffer, Phys. Rev. 108, 1175 (1957).
  * (25) H. Tsunetsugu, M. Sigrist and K. Ueda, Rev. Mod. Phys. 69, 809 (1997).
  * (26) M. Dzero, K. Sun, V. Galitski and P. Coleman, Phys. Rev. Lett. 104, 106408 (2010).
  * (27) M. Dzero, K. Sun, P. Coleman and V. Galitski, Phys. Rev. B 85, 045130 (2012).
  * (28) M. A. Griffith, M. A. Continentino and T. O. Puel, Phys. Rev B 99, 075109 (2019).
  * (29) M. Dzero, J. Xia, V. Galitski and P. Coleman, Annu. Rev. Condens. Matter Phys. 7, 11 (2016).
  * (30) A. Ghazaryan, E. M. Nica, O. Erten and P. Ghaemi, New J. Phys. 23, 123042 (2021).
  * (31) P. Ghaemi and T. Senthil, Phys. Rev. B 75, 144412 (2007).
  * (32) P. Ghaemi, T. Senthil and P. Coleman, Phys. Rev. B 77, 245108 (2008).
  * (33) M. Vekić, J. W. Cannon, D. J. Scalapino, R. T. Scalettar and R. L. Sugar, Phys. Rev. Lett. 74, 2367 (1995).
  * (34) K. Masuda, and D. Yamamoto, Phys. Rev. B 91, 104508 (2015).
  * (35) T. Schäfer, A. A. Katanin, M. Kitatani, A. Toschi and K. Held, Phys. Rev. Lett. 122, 227201 (2019).
  * (36) D. Sherrington and S. Kirkpatrick, Phys. Rev. Lett. 35, 1792 (1975).
  * (37) P. Coleman, Introduction to Many Body Physics (Cambridge University Press, 2015).
  * (38) C. Pépin, Phys. Rev. Lett. 98, 206401 (2007).
  * (39) J. M. Luttinger, Phys. Rev. 119, 1153 (1960).
  * (40) J. M. Luttinger and J. C. Ward, Phys. Rev. 118, 1417 (1960).
  * (41) M. Oshikawa, Phys. Rev. Lett. 84, 3370 (2000).
  * (42) D. V. Else, R. Thorngren and T. Senthil, Phys. Rev. X 11, 021005 (2021).
  * (43) I. Dzyaloshinskii, Phys. Rev. B 68, 085113 (2003)
  * (44) X. G. Wen and Q. Niu, Phys. Rev. B 41, 9377 (1990).
  * (45) T. Senthil and M. P. A. Fisher, Phys. Rev. B 63, 134521 (2001).
  * (46) M. Oshikawa and T. Senthil, Phys. Rev. Lett. 96, 060601 (2006).
  * (47) J. B. Kogut, Rev. Mod. Phys. 51, 659 (1979).
  * (48) M. Continentino, Quantum Scaling in Many-Body Systems (Cambridge University Press, 2017).
  * (49) C. Vitoriano, L. B. Bejan, A. M. S. Macêdo and M. D. Coutinho-Filho, Phys. Rev. B 61, 7941 (2000).
  * (50) T. Giamarchi, Quantum Physics in One Dimension (Oxford University Press, 2003).
  * (51) P. Di Francesco, P. Mathieu and D. Senechal, Conformal Field Theory (Springer-Verlag, 1997).
  * (52) M. Yamanaka, M. Oshikawa and I. Affleck, Phys. Rev. Lett. 79, 1110 (1997).
  * (53) G. Li et al., Science 346, 1208 (2014).
  * (54) B. S. Tan et al., Science 349, 287 (2015).
  * (55) Z. Xiang et al., Science 362, 65 (2018).
  * (56) J. Knolle and N. R. Cooper, Phys. Rev. Lett. 115, 146401 (2015).
  * (57) L. Zhang, X.-Y. Song and F. Wang, Phys. Rev. Lett. 116, 046404 (2016).
  * (58) P. S. Riseborough and Z. Fisk, Phys. Rev. B 96, 195122 (2017).
  * (59) G. Baskaran, arXiv:1507.03477.
  * (60) C. M. Varma, Phys. Rev. B 102, 155145 (2020).
  * (61) O. Erten, P. Ghaemi and P. Coleman, Phys. Rev. Lett. 116, 046403 (2016).
  * (62) J. Knolle and N. R. Cooper, Phys. Rev. Lett. 118, 096604 (2017).
  * (63) P. Rao and I. Sodemann, Phys. Rev. B 100, 155150 (2019).
  * (64) Y. Zhong, Y. Liu and H.-G. Luo, Eur. Phys. J. B 90, 147 (2017).
  * (65) F. T. Lisandrini, A. M. Lobos, A. O. Dobry and C. J. Gazza, Phys. Rev. B 96, 075124 (2017).
  * (66) Z. Luo , M. Ferrero, D.-X. Yao and W. Wu, Phys. Rev. B 104, L161119 (2021).