Algebraic Connectedness and Bipartiteness of Quantum Graphs

Abstract

Connectedness and bipartiteness are basic properties of classical graphs, and the purpose of this paper is to investigate the case of quantum graphs. We introduce the notion of connectedness and bipartiteness of quantum graphs in terms of graph homomorphisms. This paper shows that regular tracial quantum graphs have the same algebraic characterization of connectedness and bipartiteness as classical graphs. We also prove the equivalence between bipartiteness and two-colorability of quantum graphs by comparing two notions of graph homomorphisms: one respects adjacency matrices and the other respects edge spaces. In particular, all kinds of quantum two-colorability are mutually equivalent for regular connected tracial quantum graphs.

The quantum graphs are a non-commutative analogue of classical graphs and recently developed in the interactions between theories of operator algebras, quantum information, non-commutative geometry, quantum groups, etc.

Since quantum graphs as adjacency matrices were introduced by Musto et al.[16], there has been substantial activity towards clarifying the relation between the property of a quantum graph and the spectrum of the adjacency matrix. It is classically known that the spectrum of the adjacency matrix can characterize some properties of a (regular) classical graph. Hoffman [13] showed that a connected d-regular graph is bipartite if and only if $-d$ is an eigenvalue of the adjacency matrix, and it was already known in Fiedler [10] that the connectedness of a graph is equivalent to the nonzero spectral gap of the graph Laplacian (cf. [7]). So it is natural to expect that quantum graphs have similar spectral characterizations, and indeed Ganesan [11] shows that such a spectral approach is valid for the chromatic numbers of quantum graphs.

Similarly to the classical case, the degree of a regular quantum graph is shown to be the spectral radius of the adjacency matrix. Thus it makes sense to consider the behavior of the spectrum in $[-d,d]$ for d-regular undirected quantum graphs. In this paper, we introduce bipartiteness and connectedness for quantum graphs in terms of graph homomorphisms, and we give their spectral characterizations for regular quantum graphs.

Regarding the notion of graph homomorphisms, we compare two notions of graph homomorphisms, one is defined in this paper and compatible with adjacency matrices, and the other is defined in [3] and compatible with edge spaces. We prove that these two notions are equivalent particularly in the case of quantum-to-classical graph homomorphism, that is, any edge is mapped to the edges if the adjacency matrix is mapped to edges. In the proof, string diagrams (c.f. [15,16,17]) play a significant role to deduce positivity from the symmetry of the diagram. As its corollary, we obtained that the local two-colorability is equivalent to bipartiteness for tracial real quantum graphs. Moreover, combining the results in this paper, it follows that all kinds of quantum two-colorability are mutually equivalent for connected regular undirected tracial quantum graphs.

This paper confirms the spectral characterization of connected and bipartite quantum graphs, which is a base for further topics, including ‘expander’ quantum graphs to be defined by the spectral gap. It is known [9] that a quantum channel in quantum information theory gives a quantum graph as an operator system. If we can associate quantum expander channels with ‘expander’ quantum graphs, we can supply a new approach to the theory of quantum channels.

Apart from quantum graph theory, Lemma 3.3 supplies a way for a trace to control the decomposition of a self-adjoint operator as a subtraction of positive operators, and the proof of Theorem 4.7 shows that string diagrams are indeed useful to show positivity of operators. These techniques would help the wider scope of mathematics.

This paper is organized as follows.

In Sect. 1, we prepare the basic terminology of quantum graphs and string diagrams referring to the preceding research and show some lemmas for later use.

In Sect. 2, we introduce the graph gradient to show the positivity of graph Laplacian. From the positivity, we deduce the spectral bound by the degree of regular real quantum graphs. On the way, we show that quantum graphs do not admit an orientation in general.

FormalPara Theorem

(Proposition 2.10). Let ${\mathcal {G}}=(B,\psi ,A)$ be a d-regular real quantum graph. The spectral radius r(A) of the adjacency matrix satisfies $r(A)=d$.

FormalPara Theorem

(Theorem 2.11). Let ${\mathcal {G}}=(B,\psi ,A)$ be a d-regular quantum graph. Then the identity of the operator norm on $B(L^2({\mathcal {G}}))$ and the degree

$$\begin{aligned} {\left\Vert {A}\right\Vert }_\textrm{op}=d \end{aligned}$$

holds if either of the following is satisfied:

(1):

${\mathcal {G}}$ is undirected, whence $\mathop {\text {spec}}\nolimits (A)\subset [-d,d]$;

(2):

A is real and commutes with the modular automorphism $\sigma _i$;

(3):

${\mathcal {G}}$ is real and tracial.

In Sect. 3, we introduce our notion of graph homomorphism, connectedness, and bipartiteness and prove their algebraic characterizations by the spectrum of the adjacency matrix. In the proof, Lemma 3.3 plays an essential role in controlling the decomposition of a self-adjoint operator into a subtraction of positive elements.

FormalPara Theorem

(Theorem 3.7, Theorem 3.8, Theorem 3.9). Let ${\mathcal {G}} = (B,\psi ,A)$ be a d-regular undirected tracial quantum graph.

• ${\mathcal {G}}$ is connected if and only if $d \in \mathop {\text {spec}}\nolimits (A)$ is a simple root.

• ${\mathcal {G}}$ has a bipartite component if and only if $-d \in \mathop {\text {spec}}\nolimits (A)$. If $d=0$, we require ${\dim B} \ge 2$.

If moreover ${\mathcal {G}}$ is connected, then

• ${\mathcal {G}}$ is bipartite if and only if $-d \in \mathop {\text {spec}}\nolimits (A)$. If $d=0$, we require ${\dim B} \ge 2$.

In Sect. 4, we give a modified generalization of t-homomorphisms ($t \in \{loc,q,qa,qc,C^*,alg\}$) introduced by [3] in the quantum-to-classical cases and show that it agrees with the quantum homomorphism defined by [16] in terms of string diagrams. Then we prove that our graph homomorphisms and loc-homomorphisms coincide under some assumptions.

FormalPara Theorem

(Theorem 4.9). Let ${\mathcal {G}}_j$ for $j=0,1$ be real tracial quantum graphs such that ${\mathcal {G}}_1$ is Schur central. Then $f^\textrm{op}:{\mathcal {G}}_0 \rightarrow {\mathcal {G}}_1$ is a graph homomorphism if and only if $(f,{\mathbb {C}}):{\mathcal {G}}_0 \overset{}{\rightarrow } {\mathcal {G}}_1$ is a loc-homomorphism.

This result yields the equivalence of bipartiteness and local two-colorability, which implies the equivalence of all the t-2 colorability.

FormalPara Theorem

(Theorem 4.13). Let ${\mathcal {G}}$ be a real tracial quantum graph. Then ${\mathcal {G}}$ is bipartite if and only if it is loc-2 colorable.

FormalPara Theorem

(Corollary 4.14). Let ${\mathcal {G}}=(B,\psi ,A)$ be a connected d-regular undirected tracial quantum graph. The following are equivalent:

(1):

${\mathcal {G}}$ is loc-2 colorable;

(2):

${\mathcal {G}}$ is alg-2 colorable;

(3):

${\mathcal {G}}$ has a symmetric spectrum;

(4):

$-d \in \mathop {\text {spec}}\nolimits (A)$. If $d=0$, we require ${\dim B} \ge 2$;

(5):

${\mathcal {G}}$ is bipartite.

Our main results are restricted to regular tracial quantum graphs. So the non-tracial versions and the equivalence of the spectral gap of the graph Laplacian and the connectedness of irregular quantum graphs are left open. The relation between our connectedness and the operator space theoretic connectedness [6] of quantum graphs is also left open.

1 Preliminaries

We denote by $(\cdot )^*$ the involution on a $*$-algebra and by $(\cdot )^\dagger$ the adjoint of an operator between Hilbert spaces.

For a state $\psi$ on a $C^*$-algebra B, we denote the GNS space by $L^2(B,\psi )$, which is the Hausdorff completion of B with respect to the sesquilinear form $\langle x|y\rangle =\langle x|y\rangle _\psi =\psi (x^* y)$ for $x,y \in B$. If $\dim B$ is finite and $\psi$ is faithful, we identify $B \ni x = |x\rangle \in L^2(B,\psi )$. Then we have the multiplication $m:B \otimes B \ni x \otimes y \mapsto xy \in B$ and the comultiplication $m^\dagger : B \rightarrow B \otimes B$. The unit $1_B$ is identified with a map ${\mathbb {C}}\ni 1 \mapsto 1_B \in B$ and its adjoint is the counit $\psi =1_B^\dagger =\langle 1_B|$.

Via a multimatrix presentation $B=\bigoplus _s M_{n_s}$, we denote the direct sum of unnormalized traces by $\mathop {\text {Tr}}\nolimits =\bigoplus _s \mathop {\text {Tr}}\nolimits _{n_s}$ (independent of the choice of the presentation) and denote the density matrix of $\psi =\mathop {\text {Tr}}\nolimits (Q \, \cdot )$ by $Q \in B$. If $\psi$ is faithful, Q is positive and invertible.

1.1 String diagrams

We denote linear operators by string diagrams, which encode the compositions of operators from the bottom to the top. See [16, 17] for string diagrams of Frobenius algebras and tracial quantum graphs and [15] for diagrams of non-tracial quantum graphs.

In particular, we put

We abbreviate

The key point is that the string diagrams allow us graphical calculation (continuous deformation of diagrams) via associativity , coassociativity . If $\psi$ is non-tracial, note that we sometimes need to deal with

where $\sigma _z:B \rightarrow B$ for $z \in {\mathbb {C}}$ are the modular automorphisms $\sigma _z(x)=Q^{iz} x Q^{-iz}$ for the positive invertible density $Q \in B$ of the faithful state $\psi =\mathop {\text {Tr}}\nolimits (Q\, \cdot )$.

1.2 Quantum graphs

Definition 1.1

([1, 16]). A quantum set is $(B,\psi )$ consisting of a finite-dimensional $C^*$-algebra B with a $\delta$-form $\psi :B \rightarrow {\mathbb {C}}$, where the $\delta$-form is defined as a faithful state satisfying $mm^\dagger =\delta ^2 \textrm{id}_B$ for $\delta \ge 0$.

We denote by $\tau _B$ the unique tracial $\delta =\sqrt{\dim B}$-form on B. If $B=\bigoplus _s M_{n_s}$ and $\psi =\mathop {\text {Tr}}\nolimits (Q\, \cdot )$ with $Q=\bigoplus _s Q_s$, then $\psi$ is a $\delta$-form if and only if $\mathop {\text {Tr}}\nolimits (Q_s^{-1})=\delta ^2$ for all s, and $\tau _B= \bigoplus _s n_s \mathop {\text {Tr}}\nolimits _s /\dim B$.

Definition 1.2

([1, 2, 16]). Let $(B,\psi )$ be a quantum set. We define the Schur product $S \bullet T$ and the involution $T^*$ of $S,T \in B(L^2(B,\psi ))$ by

with which $B(L^2(B,\psi ))$ forms a $*$-algebra isomorphic to $B^\textrm{op}\otimes B$. See for example [15, Lemma 2.13] about the identity of the involution and the diagram. The correspondence is given by

where $\sigma _{i/2}=Q^{-1/2}(\cdot )Q^{1/2}:B \rightarrow B$ is a modular automorphism and $p_T= \Psi _{0,1/2}^\prime (T)$ defined in [8, Definition 5.1]. See [12] for the tracial setting and [8, 18] for the details in general setting.

We say that $T:B \rightarrow B$ is real if $T^*=T$ (i.e., $*$-preserving. cf. [16]); T is Schur idempotent if $T \bullet T=T$; and T is a Schur projection if it is real and Schur idempotent.

We often use the realness of $T:B \rightarrow B$ in the form of

Note that if T is real, then $T^\dagger$ is real if and only if T commutes with modular automorphisms $\sigma _z$ (c.f. [15, Proposition 2.15], [18, Lemma 2.1]). This means that we cannot always replace T with $T^\dagger$ in (1.1).

Definition 1.3

(KMS adjoint). Wasilewski [18] pointed out that the KMS inner product $\langle x|y\rangle =\psi (x^* \sigma _{-i/2}(y))$ on B behaves better than the GNS inner product $\langle x|y\rangle _\psi =\psi (x^* y)$ when we define non-tracial quantum Cayley graphs. They coincide if $\psi$ is tracial. The KMS adjoint is the adjoint of an operator on (tensor powers of) B with respect to the KMS inner product.

The relation between the GNS adjoint $T^\dagger$ and the KMS adjoint $T^\ddagger$ of $T:B^{\otimes m}\rightarrow B^{\otimes n}$ is given by $T^\ddagger = \sigma _{i/2}^{\otimes m} T^\dagger \sigma _{-i/2}^{\otimes n}$. Define , , and , where the cusp stands for the operator in the middle of the straight string $\textrm{id}_B$ and the loops $\sigma _{\pm i}$. Then the KMS inner product is drawn as and the relation of the KMS adjoint and the involution is for $T:B\rightarrow B$. Thus in terms of the KMS adjoint, the realness (1.1) of T is replaced by

A benefit of KMS adjoint is that $T^\ddagger$ is real if and only if T is real. Indeed, the flip invariance implies the equivalence between the realness of T and that of $T^\ddagger$ by flipping the strings:

Since the GNS adjoint is easier to treat in string diagrams, we stick to the GNS inner product in this paper.

Lemma 1.4

Let $T:B \rightarrow B$ be an operator on a quantum set $(B,\psi )$. The following are equivalent:

(1):

$T^\dagger =T^\ddagger$;

(2):

T commutes with the modular automorphism $\sigma _i$.

Moreover, if T is real, then (1) and (2) are equivalent to

(3):

$T^\dagger$ is real.

Proof

$((1)\implies (2))$ By the relation between GNS and KMS adjoints, $T^\dagger =T^\ddagger =\sigma _{i/2}T^\dagger \sigma _{-i/2}$. Taking the adjoint, we get $T=\sigma _{-i/2}T \sigma _{i/2}$, hence $T \sigma _{i}=\sigma _{i/2}T \sigma _{i/2}=\sigma _{i} T$.

$((2)\implies (1))$ By the functional calculus, the square root $\sigma _{i/2}$ of a positive definite operator $\sigma _{i} =Q^{-1}(\cdot )Q$ is in the commutant of T. Thus we obtain (1) following the proof of $((1)\implies (2))$ backward.

$((3)\implies (2))$ Assume $T^\dagger$ is real, then we have by the diagrammatic expression of $T^*$ in Definition 1.2. Substituting this to the expression of $T^*$, we obtain

Thus T commutes with $\sigma _i$.

$((1)\implies (3))$ Since T is real, $T^\dagger =T^\ddagger$ is also real by (1.2). $\square$

Definition 1.5

([1, 16]). A quantum graph is a triple ${\mathcal {G}}=(B,\psi ,A)$ consisting of a quantum set $(B,\psi )$ and an operator $A: B \rightarrow B$ satisfying Schur idempotence $A \bullet A=A$, which is called the adjacency matrix.

We denote the GNS space of a quantum graph ${\mathcal {G}}=(B,\psi ,A)$ by $L^2({\mathcal {G}}) {:}{=} L^2(B,\psi )$.

Definition 1.6

Let ${\mathcal {G}}=(B,\psi ,A)$ be a quantum graph.

• [1] ${\mathcal {G}}$ is tracial (or symmetric) if $\psi$ is tracial, i.e., $\psi =\tau _B$;

• [16] ${\mathcal {G}}$ is real if A is real $A^*=A$. The realness is equivalent to the complete positivity by the Schur idempotence of A (cf. [15, Proposition 2.23], [18, Remark 3.2]);

• [16] ${\mathcal {G}}$ is undirected if A is both real and self-adjoint. This is equivalent to GNS symmetry (c.f. [18]) $\psi ((Ax)y)=\psi (x(Ay))$ under the realness by [15, Lemma 2.22];

• [18] ${\mathcal {G}}$ is KMS symmetric if A is both real and KMS self-adjoint $A=A^\ddagger$;

• [16] ${\mathcal {G}}$ is reflexive (or has all loops) if $A \bullet \textrm{id}=\textrm{id}$;

• [16] ${\mathcal {G}}$ is irreflexive (or has no loops) if $A \bullet \textrm{id}=0$;

• [12] ${\mathcal {G}}$ has no partial loops if $A \bullet \textrm{id}=\textrm{id}\bullet A$;

• [15] ${\mathcal {G}}$ is d-regular if $A1_B=d1_B=A^\dagger 1_B$. The $d \in {\mathbb {C}}$ is the degree of ${\mathcal {G}}$;

• ${\mathcal {G}}$ is Schur central if $A \bullet \cdot =\cdot \bullet A$, i.e., A is central with respect to the Schur product.

Lemma 1.7

Let ${\mathcal {G}}=(B,\psi ,A)$ be a d-regular real quantum graph. It follows that $d \in {\mathbb {R}}$.

Proof

We have $d=\langle 1_B | A1_B\rangle =\langle 1_B | A^* 1_B\rangle =\langle 1_B | (A 1_B)^*\rangle =\overline{d}$. $\square$

Definition 1.8

(Weaver [19]). A quantum relation on a von Neumann algebra $B \subset B(H)$ is a weak*-closed $B'$-$B'$-bimodule ${\mathcal {S}} \subset B(H)$, where we regard B(H) as the dual of the trace class TC(H) via the coupling $(S,T)\mapsto \mathop {\text {Tr}}\nolimits (ST)$.

If we chose $H=L^2(B,\psi )$ for a quantum set $(B,\psi )$, then a quantum relation on $B=\lambda (B) \subset B(H)$ is a $\rho (B)$-$\rho (B)$-bimodule ${\mathcal {S}} \subset B(H)$ where $\lambda$ (resp. $\rho$) is the left (resp. right) regular representation with respect to $\psi$.

Quantum relations on a quantum set $(B,\psi )$ are identified with B-B-bimodules ${\mathcal {S}} \subset B \otimes B$ via the identification:

See for example [14, 5, Appendix F] about bimodules over von Neumann algebras, and [16] about the one-to-one correspondence above.

The linear isomorphism $\iota$ is the linear extension of $\iota (|x\rangle \langle y|)=\sigma _{-i}(y^*) \otimes x$ for $x,y \in B$. We endow $B(L^2(B,\psi ))$ with a Hilbert space structure via $\iota$, i.e.,

where is an extension of $\delta ^2 \psi$ on $\rho (B)$ to $B(L^2(B,\psi ))$.

Let $P:L^2(B,\psi )^{\otimes 2 }\rightarrow L^2(B,\psi )^{\otimes 2}$ be the orthogonal projection onto the B-B-bimodule ${\mathcal {S}} \subset B \otimes B = L^2(B,\psi )^{\otimes 2}$. Then P is B-B-bimodule map, i.e., $P(x \xi y)=xP(\xi )y$ for $x,y \in B$ and $\xi \in B \otimes B$.

There is a one-to-one correspondence (cf. [16]) between B-B-bimodule projections P on $B \otimes B$ and real quantum graphs $(B,\psi ,A)$ as follows:

Note that $P_A=\iota \widetilde{P_A} \iota ^{-1}$ is the reformulation of left Schur product by A:

$$\begin{aligned} \widetilde{P_A} = A \bullet (\cdot ):B(L^2(B,\psi )) \ni T \mapsto A\bullet T \in B(L^2(B,\psi )). \end{aligned}$$

Example 1.9

We denote the reflexive trivial graph on a quantum set $(B,\psi )$ by $T(B,\psi )=(B,\psi ,\textrm{id}_B)$, which is undirected 1-regular. This is the quantum version of graphs with all loops. Its corresponding quantum relation is the commutant of B: ${\mathcal {S}}_{T(B,\psi )}=\lambda (B)'=\rho (B) \subset B(L^2(B,\psi ))$. We abbreviate the classical trivial graphs $T_n=T({\mathbb {C}}^n,\tau _{{\mathbb {C}}^n})$ for $n \in {\mathbb {N}}$.

We denote the irreflexive complete graph on a quantum set $(B,\psi )$ with $\delta$-form by $K(B,\psi )=(B,\psi , \delta ^2 \psi (\cdot )1_B - \textrm{id}_B)$, which is undirected $(\delta ^2-1)$-regular. This is the quantum version of graphs with all edges except loops. Its corresponding quantum relation is the orthocomplement of the commutant of B: ${\mathcal {S}}_{K(B,\psi )}={\mathcal {S}}_{T(B,\psi )}^\perp =\rho (B)^\perp \subset B(L^2(B,\psi ))$. We abbreviate the classical complete graphs $K_n=K({\mathbb {C}}^n,\tau _{{\mathbb {C}}^n})$ for $n \in {\mathbb {N}}$. We denote by $J=\delta ^2 \psi (\cdot )1_B$ the adjacency matrix of the reflexive complete quantum graphs.

The degree of a regular classical graph is at most the size of the vertex set. The value $\delta ^2$ plays the role of the size of a quantum set and it bounds the degree.

Lemma 1.10

Let ${\mathcal {G}}=(B,\psi ,A)$ be a d-regular real quantum graph. Then $0 \le d \le \delta ^2$. In particular, $d=0$ if and only if $A=0$, and $d=\delta ^2$ if and only if $A=\delta ^2 \psi (\cdot )1_B$.

Proof

We use the correspondence between A and a projection $p_A \in B^\textrm{op}\otimes B$. Note that the reflexive complete graph $(B,\psi , J=\delta ^2 \psi (\cdot )1_B)$ corresponds to the maximal projection $p_J =1 \otimes 1 \in B^\textrm{op}\otimes B$. Since $0 \le p_A \le p_J$ and $\psi ^{\otimes 2}$ is a state on $B^\textrm{op}\otimes B$, we have

$$\begin{aligned} 0 \le d=\psi (A1_B)=\delta ^2 \psi ^{\otimes 2}(p_A) \le \delta ^2 \psi ^{\otimes 2}(p_J)=\psi (J1_B)=\delta ^2. \end{aligned}$$

Since $\psi ^{\otimes 2}$ is faithful, $d=0$ holds if and only if $A=0$, and $d=\delta ^2$ holds if and only if $A=J$. $\square$

Gromada [12, section 2.3] pointed out that the value $\delta ^2 \langle 1_B|A|1_B\rangle = \delta ^2\psi (A1_B)$ is the number of edges. This value is strictly positive whenever A is nonzero and real:

Lemma 1.11

Let ${\mathcal {G}}=(B,\psi , A)$ be a real quantum graph. Then $\langle 1_B|A|1_B\rangle \ge 0$ with equality if and only if $A=0$.

Proof

Similarly to the proof of Lemma 1.10, we have

$$\begin{aligned} \langle 1_B|A|1_B\rangle =\psi ^{\otimes 2}(p_A)\ge 0. \end{aligned}$$

Since $\psi ^{\otimes 2}$ is faithful, $\langle 1_B|A|1_B\rangle =0$ holds if and only if $A=0$. $\square$

For later use, we show that the eigenspace for any real eigenvalue of a real quantum graph is spanned by self-adjoint elements:

Lemma 1.12

Let $(B,\psi ,A)$ be a real quantum graph and $x \in B$ be an eigenvector for an eigenvalue $\lambda$ of A. Then $x^*$ is an eigenvector for the eigenvalue $\overline{\lambda }$ of A. In particular if $\lambda \in \mathop {\text {spec}}\nolimits (A) \cap {\mathbb {R}}$, then the eigenspace $\ker (\lambda \, \textrm{id}-A)$ and the generalized eigenspace $\ker (\lambda \, \textrm{id}-A)^{\dim B}$ are spanned by self-adjoint elements.

Proof

Taking the involution of $(\lambda \, \textrm{id}-A)x = 0$, we get $(\overline{\lambda }\, \textrm{id}-A)x^* = (\lambda x)^* -(Ax)^* = ((\lambda \, \textrm{id}-A)x)^* = 0$. If $\lambda$ is real, then both x and $x^*$ are eigenvectors for $\lambda$, hence $\Re x=\frac{x+x^*}{2}, \Im x=\frac{x-x^*}{2i}$ are also eigenvectors for $\lambda$. Since x is arbitrary, $\ker (\lambda \, \textrm{id}-A)$ is spanned by self-adjoint elements. Similarly $\ker (\lambda \, \textrm{id}-A)^{\dim B}$ is so. $\square$

2 Spectral Bound for Regular Quantum Graphs

In classical graph theory, d-regular graph is known to have spectral radius d (cf. [7]) and hence it makes sense to argue whether the second largest eigenvalue is d and the smallest eigenvalue is $-d$. Here we introduce the notion of graph gradient to prove this spectral bound for regular quantum graphs.

2.1 Graph gradient of quantum graphs

Definition 2.1

Let $(B,\psi ,A)$ be a quantum graph. Define a linear operator $\nabla =\nabla _A: B \rightarrow B \otimes B$ by

We call $\nabla _A$ the graph gradient.

This gradient coincides with the classical one in the following manner.

Lemma 2.2

Let $(V,E \subset V \times V)$ be a classical directed graph corresponding to $(C(V)={\mathbb {C}}^n, \tau , A)$ with $A_{ij}=\chi _E (j,i)$ where $\chi _E$ is the indicator function of E. The classical graph gradient $\nabla _E:C(V) \rightarrow C(E)$ (the so-called coboundary operator in [7]) is defined by

$$\begin{aligned} \nabla _E f (i,j)=f(j)-f(i) \qquad f\in C(V), \ \ (i,j)\in E. \end{aligned}$$

It holds that $\nabla _A=\iota \circ \nabla _E$, where $\iota : C(E) \rightarrow C(V)\otimes C(V)=C(V\times V)$ is the extension of functions on E to $V \times V$ with outside zero.

Proof

Note that the evaluation map $C(V) \ni f \mapsto f(i) \in {\mathbb {C}}$ at $i\in V$ is given by $n \langle e_i|=n \tau (e_i \ \cdot )$ for the tracial $\sqrt{n}$-form $\tau$ and $m^\dagger e_k=n e_k \otimes e_k$. By direct computation we have for $f\in C(V)$ and $i,j \in V$ that

$$\begin{aligned} \nabla _A f (i,j)&= n^2 (\langle e_i| \otimes \langle e_j|) \nabla _A f \\&= n^2 n^{-1} \left( \langle e_i|A^\dagger \otimes \langle e_j| - \langle e_i| \otimes \langle e_j| A \right) n \sum _k f(k) e_k \otimes e_k \\&= n^2 (\langle e_i | A^\dagger f(j) | e_j\rangle n^{-1} - n^{-1} \langle e_j | A f(i) |e_i\rangle ) \\&= n \sum _{(k,j) \in E} \langle e_i | e_k\rangle f(j) - n \sum _{(i,k) \in E}\langle e_j |e_k\rangle f(i) \\&= (f(j)-f(i)) \chi _E (i,j) = (\iota \nabla _E f)(i,j). \end{aligned}$$

$\square$

The graph gradient $\nabla _A$ is the commutator of the right regular representation $\rho (\cdot )$ and A via the identification (1.3) $\iota : B(L^2({\mathcal {G}}))\cong B \otimes B$:

Proposition 2.3

Let $(B,\psi ,A)$ be a real quantum graph. For $x \in B$, we have

$$\begin{aligned} \delta ^{2} \iota ^{-1} (\nabla _A x) = [\rho (x),A] {:}{=} \rho (x)A-A\rho (x). \end{aligned}$$

Proof

By direct computation, we get

$\square$

Recall the one-to-one correspondence (1.5) between real quantum graphs A on $(B,\psi )$ and ‘edge space’ B-B-bimodules ${\mathcal {S}}=\mathop {\text {range}}\nolimits P_A \subset B \otimes B$ represented by orthogonal projection $P_A$ onto ${\mathcal {S}} \subset L^2(B,\psi )^{\otimes 2}$. Similarly to the classical case, $\nabla _A$ is a map to the edge space.

Proposition 2.4

Let $(B,\psi ,A)$ be a real quantum graph. Then the following holds.

(1):

The range of $\nabla _A$ is included in $\mathop {\text {range}}\nolimits P_A$, i.e., $P_A \nabla _A=\nabla _A$.

(2):

The operator $\nabla _A$ is a ${\mathbb {C}}$-derivation, i.e., $\nabla _A(xy)=(\nabla _A x)y+x(\nabla _A y)$ for all $x,y \in B$ and $\nabla _A(\lambda )=0$ for any $\lambda \in {\mathbb {C}}\subset B$.

Proof

(1) Note that the real condition (1.1) implies

Thus we have $\nabla _A=P_A(1 \otimes \cdot -\cdot \otimes 1)$, and

$$\begin{aligned} P_A \nabla _A=P_A^2(1 \otimes \cdot -\cdot \otimes 1)=\nabla _A \end{aligned}$$

by idempotence of $P_A$.

(2) Now we have $\nabla _A 1= P_A(1 \otimes 1-1 \otimes 1)=0$. It remains to show $\nabla _A(xy)=(\nabla _A x)y+x(\nabla _A y)$ for $x,y \in B$. Indeed by bimodule property $P_A(xzy)=x(P_A z)y$ for $x,y \in B, z \in B^{\otimes 2}$, we obtain

$\square$

Definition 2.5

(Generalization of Ganesan [11] to directed graphs). Let ${\mathcal {G}}=(B,\psi ,A)$ be a quantum graph. We define the (left) indegree matrix $D_\textrm{in}:B \rightarrow B$ and (right) outdegree matrix $D_\textrm{out}:B \rightarrow B$ by

where $\lambda$ (resp. $\rho$) is the left (resp. right) multiplication.

If ${\mathcal {G}}$ is undirected, then $D_\textrm{out}=D_\textrm{in}^*$ by

$$\begin{aligned} D_\textrm{in}^* x = ((A1) x^*)^* = x (A1)^* = x (A^* 1) \overset{\text {(undirected)}}{=} x (A^\dagger 1) =D_\textrm{out} x. \end{aligned}$$

And $D_\textrm{out}=D_\textrm{in}=d \,\textrm{id}_B$ if ${\mathcal {G}}$ is d-regular.

Lemma 2.6

Let ${\mathcal {G}}=(B,\psi ,A)$ be a real quantum graph. Then

$$\begin{aligned} 0 \le \nabla _A^\dagger \nabla _A=\delta ^{-2} \left( D_\textrm{in} - A + D_\textrm{out} - A^\dagger \right) . \end{aligned}$$

Moreover if ${\mathcal {G}}$ is d-regular,

$$\begin{aligned} 0 \le \nabla _A^\dagger \nabla _A=2\delta ^{-2} \left( d \, \textrm{id}_B- \frac{A+A^\dagger }{2} \right) . \end{aligned}$$

In particular $\frac{\theta A+\overline{\theta }A^\dagger }{2} \le d \, \textrm{id}_B$ for all $\theta \in {\mathbb {T}}$.

Proof

We can compute directly

If it is d-regular, then $D_\textrm{out}=D_\textrm{in}=d \,\textrm{id}_B$ yields

$$\begin{aligned} \nabla ^\dagger \nabla =2\delta ^{-2} \left( d \, \textrm{id}_B- \frac{A+A^\dagger }{2} \right) . \end{aligned}$$

Replacing A by $\lambda A$ and $A^\dagger$ by $\overline{\lambda } A^\dagger$ in $\nabla _A$, we deduce $d \, \textrm{id}_B - \frac{\lambda ^2 A+\overline{\lambda }^2 A^\dagger }{2} \ge 0$ for any $\lambda \in {\mathbb {T}}$. Since $\theta =\lambda ^2$ ranges all $\theta \in {\mathbb {T}}$, we obtain $\frac{\theta A+\overline{\theta }A^\dagger }{2} \le d \, \textrm{id}_B$. $\square$

Remark 2.7

Ganesan [11] defined the graph Laplacian L by $L=D-A$ for undirected quantum graphs with right degree matrix $D=D_\textrm{out}$. In this case, our Laplacian $\Delta {:}{=} \delta ^{2}\nabla ^\dagger \nabla =L^* +L$ is a ‘double’ of usual Laplacian. Usually, the gradient of an undirected classical graph is defined by the gradient as in Lemma 2.2 of an orientation (i.e., a half) of the original graph. This is why we obtained the doubled Laplacian, and such duplication is inevitable because quantum graphs do not always have an orientation as shown below.

Definition 2.8

Let ${\mathcal {G}}=(B,\psi ,A)$ be an undirected quantum graph. We say that a Schur projection $T: B\rightarrow B$ is an orientation of ${\mathcal {G}}$ if $A\bullet T=T$, $T\bullet T^\dagger =0$, and $\mathop {\text {range}}\nolimits (T\bullet \cdot )+\mathop {\text {range}}\nolimits (T^\dagger \bullet \cdot )=\mathop {\text {range}}\nolimits (A\bullet \cdot )$.

Note that this definition is equivalent to $A=T+T^\dagger$ if $T^\dagger$ is also a Schur projection. The definition states that T is a directed subgraph (edge subset) of A over the same quantum set, $T^\dagger$ is the opposite orientation of T, and T and $T^\dagger$ disjointly cover A.

If ${\mathcal {G}}$ is non-tracial, then the GNS adjoint $T^\dagger$ is not always real, hence not necessarily a Schur projection and $A=T+T^\dagger$ may not hold. To avoid such a problem, we can instead consider a KMS symmetric quantum graph ${\mathcal {G}}$ and the KMS adjoint $T^\ddagger$ to define an orientation simply by $A=T+T^\ddagger$.

Example 2.9

(A non-orientable quantum graph). Consider 1-regular irreflexive undirected quantum graph ${\mathcal {G}}=(M_2, \tau =\mathop {\text {Tr}}\nolimits /2, A=2E_{{\mathbb {C}}^2}-\textrm{id}_{M_2}:\begin{pmatrix}a &{} b \\ c &{} d \end{pmatrix} \mapsto \begin{pmatrix}a &{} -b \\ -c &{} d \end{pmatrix})$ (c.f. [12, 15]), where $E_{{\mathbb {C}}^2}$ is the conditional expectation onto the diagonal subalgebra. Its corresponding projection

$$\begin{aligned} p_A=\frac{1}{2}\begin{pmatrix} 1&{}\quad 0&{}\quad 0&{}\quad -1\\ 0&{}\quad 0&{}\quad 0&{}\quad 0\\ 0&{}\quad 0&{}\quad 0&{}\quad 0\\ -1&{}\quad 0&{}\quad 0&{}\quad 1 \end{pmatrix} \in M_2^\textrm{op}\otimes M_2 =M_4 \end{aligned}$$

is rank one, hence it does not have an orientation T whose corresponding projection $p_T$ must satisfy $p_A=p_T+p_{T^\dagger }$.

2.2 Spectral bound by the degree

Proposition 2.10

Let ${\mathcal {G}}$ be a d-regular real quantum graph. The spectral radius r(A) of the adjacency operator satisfies $r(A)=d$.

Proof

For a nonzero $\lambda \in \mathop {\text {spec}}\nolimits (A)$ and a unit eigenvector $x \in \ker (\lambda \,\textrm{id}_B -A)$, choose $\theta \in {\mathbb {T}}$ so that $\theta \lambda ={\left|{\lambda }\right|}$. Then Lemma 2.6 shows

$$\begin{aligned} d = d \langle x|x\rangle \ge \frac{\langle x| \theta A+\overline{\theta }A^\dagger |x\rangle }{2} = \frac{\theta \langle x|Ax\rangle +\overline{\theta }\langle Ax|x\rangle }{2} = \frac{\theta \lambda + \overline{\theta \lambda }}{2} ={\left|{\lambda }\right|}. \end{aligned}$$

Thus $r(A) = \sup _{\lambda \in \mathop {\text {spec}}\nolimits (A)} {\left|{\lambda }\right|} \le d$. Since $d \in \mathop {\text {spec}}\nolimits (A)$, we have $r(A)=d$. $\square$

Theorem 2.11

Let ${\mathcal {G}}=(B,\psi ,A)$ be a d-regular quantum graph. Then the identity of the operator norm on $B(L^2({\mathcal {G}}))$ and the degree

$$\begin{aligned} {\left\Vert {A}\right\Vert }_\textrm{op}=d \end{aligned}$$

holds if either of the following is satisfied:

(1):

${\mathcal {G}}$ is undirected, whence $\mathop {\text {spec}}\nolimits (A)\subset [-d,d]$;

(2):

A is real and commutes with $\sigma _i$;

(3):

${\mathcal {G}}$ is real and tracial, i.e., A is real and $\psi =\tau _B$.

Proof

(1) Since A is normal $AA^\dagger =A^\dagger A$, Proposition 2.10 implies ${\left\Vert {A}\right\Vert }_\textrm{op}=r(A)=d$. Thus self-adjointness shows $\mathop {\text {spec}}\nolimits (A)\subset [-d,d]$.

(2) By Lemma 1.4, (2) means that both A and $A^\dagger$ are real. We prove the identity by embedding A into an undirected d-regular quantum graph

$$\begin{aligned} \left( B\otimes {\mathbb {C}}^2, {\widetilde{\psi }}=\psi \otimes \tau _{{\mathbb {C}}^2}, {\widetilde{A}} {:}{=} A\otimes E_{12}+A^\dagger \otimes E_{21} \right) = \left( B\oplus B, \frac{\psi \oplus \psi }{2}, \begin{pmatrix} 0 &{} A \\ A^\dagger &{} 0 \end{pmatrix} \right) \end{aligned}$$

where $E_{ij}$ are matrix units in $M_2$. By definition ${\widetilde{A}}$ is self-adjoint. Note that $A,A^\dagger$ are quantum graphs on $(B,\psi )$ and $E_{ij}$ are (quantum) graphs on $({\mathbb {C}}^2,\tau _{{\mathbb {C}}^2})$. Then $A \otimes E_{12}$ and $A^\dagger \otimes E_{21}$ are quantum graphs on $(B\otimes {\mathbb {C}}^2,\psi \otimes \tau _{{\mathbb {C}}^2})$. Since the Schur product of $E_{12}$ and $E_{21}$ is zero, ${\widetilde{A}} = A \otimes E_{12} + A^\dagger \otimes E_{21}$ is also a quantum graph.

By assumption, A and $A^\dagger$ are real. So are $A \otimes E_{12}$ and $A^\dagger \otimes E_{21}$, hence ${\widetilde{A}}$ is real.

The regularity follows from ${\widetilde{A}}(1_B \otimes 1_{{\mathbb {C}}^2})=d1_B\otimes e_1 +d1_B\otimes e_2 =d (1_B \otimes 1_{{\mathbb {C}}^2})$.

Therefore we have

$$\begin{aligned} d={\left\Vert {{\widetilde{A}}}\right\Vert }_{B(L^2(B\otimes {\mathbb {C}}^2))} \ge {\left\Vert {{\widetilde{A}}|_{L^2(B)\otimes e_2 \rightarrow L^2(B)\otimes e_1}}\right\Vert } = {\left\Vert {A}\right\Vert }_{B(L^2(B))} \end{aligned}$$

via isometric identifications $L^2(B) \ni x \mapsto x \otimes \sqrt{2}e_i \in L^2(B)\otimes e_i$ for $i=1,2$. By $d \in \mathop {\text {spec}}\nolimits (A)$, we obtain ${\left\Vert {A}\right\Vert }=d$.

(3) By traciality, $\sigma _i=\textrm{id}_B$. Thus (3) follows from (2). $\square$

Corollary 2.12

Let ${\mathcal {G}}=(B,\psi ,A)$ be a d-regular real quantum graph. Then we have the identity of the degree and the operator norm with respect to the KMS inner product on B:

$$\begin{aligned} {\left\Vert {A}\right\Vert }_\textrm{op}=d. \end{aligned}$$

Proof

By (1.2), the realness of A implies that $A^\ddagger$ is also real. Thus we have the KMS version of Theorem 2.11 (2): both A and $A^\ddagger$ are real. Since the spectral radius does not depend on the inner product structure, we have $r(A)=d$ by Proposition 2.10. Therefore by the same argument as in the proof of Theorem 2.11, we obtain ${\left\Vert {A}\right\Vert }_\textrm{op}=d$ over the KMS Hilbert space B. $\square$

Corollary 2.13

Let ${\mathcal {G}}=(B,\psi ,A)$ be a d-regular undirected irreflexive quantum graph. Then $\mathop {\text {spec}}\nolimits (A)\subset [-d,d]$ and $0 \le d \le \delta ^2-1$. Equivalently if ${\mathcal {G}}$ is a d-regular undirected reflexive quantum graph, then $\mathop {\text {spec}}\nolimits (A)\subset [-d+2,d]$ and $1 \le d \le \delta ^2$.

Proof

If ${\mathcal {G}}$ is irreflexive, then $\mathop {\text {spec}}\nolimits A \subset [-d,d]$ follows from Theorem 2.11. Its reflexive version is given by $(B,\psi ,A+\textrm{id})$ as a $(d+1)$-regular undirected quantum graph, hence Lemma 1.10 shows that $0 \le d \le \delta ^2-1$. If ${\mathcal {G}}$ is reflexive, we may replace d in the previous argumant by $d-1$ and obtain $\mathop {\text {spec}}\nolimits (A-\textrm{id}) \subset [-d+1,d-1]$, i.e., $\mathop {\text {spec}}\nolimits A \subset [-d+2,d]$, and $1 \le d \le \delta ^2$. $\square$

OpenProblems

In view of the above, we wonder if ${\left\Vert {A}\right\Vert }_\textrm{op}=d$ holds with a weaker assumption with respect to the GNS inner product.

Although we showed that some irreflexive quantum graphs do not admit an orientation, there may be a better definition that makes any irreflexive undirected quantum graphs orientable.

As we have the quantum graph Laplacians $\Delta =\delta ^2 \nabla ^\dagger \nabla$ and L, it is natural to consider a quantum Markov semigroup $e^{-t \Delta }$, which is the heat semigroup over the quantum graph. We leave it as an open question for future work to investigate the property of $e^{-t \Delta }$ such as the complete logarithmic Sobolev inequality (cf. [4]).

3 Characterization of Graph Properties

In this section, we introduce graph homomorphisms respecting the adjacency matrices and define the connectedness and bipartiteness of quantum graphs in terms of graph homomorphisms. After that, we give algebraic characterizations of these properties for regular quantum graphs.

3.1 Graph properties defined by homomorphisms

Definition 3.1

Let ${\mathcal {G}} = (B,\psi ,A), {\mathcal {G}}' = (B',\psi ',A')$ be quantum graphs. A graph homomorphism $f^\textrm{op}: {\mathcal {G}} \rightarrow {\mathcal {G}}'$ is a unital $*$-homomorphism $f: B' \rightarrow B$ satisfying $A' \bullet (f^\dagger A f) =f^\dagger A f$.

We say that $f^\textrm{op}$ is surjective if f is injective, and $f^\textrm{op}$ is injective if f is surjective.

This definition states that the pushforward $f^\dagger A f$ of the adjacency matrix of ${\mathcal {G}}$ is in the edges of ${\mathcal {G}}'$.

Definition 3.2

Let ${\mathcal {G}}$ be a quantum graph.

• ${\mathcal {G}}$ is disconnected if there is a surjective graph homomorphism ${\mathcal {G}} \rightarrow T_2$;

• ${\mathcal {G}}$ is connected if it is not disconnected, i.e., there is no surjective graph homomorphism ${\mathcal {G}} \rightarrow T_2$;

• ${\mathcal {G}}$ is bipartite if there is a surjective graph homomorphism ${\mathcal {G}} \rightarrow K_2$;

• ${\mathcal {G}}$ has a bipartite component if there is a graph homomorphism ${\mathcal {G}} \rightarrow K_2 \sqcup T_1$ that is onto $K_2$, i.e., there is a unital $*$-homomorphism $f: {\mathbb {C}}^2 \oplus {\mathbb {C}}\rightarrow B$ satisfying $\begin{pmatrix} 0 &{} 1 &{} 0 \\ 1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 \end{pmatrix} \bullet f^\dagger A f = f^\dagger A f$ and f is injective on ${\mathbb {C}}^2 \oplus 0$.

If ${\mathcal {G}}=(V,E)$ is classical, these definitions agree with classical definitions: ${\mathcal {G}}$ is disconnected (resp. bipartite) if there is a decomposition $V=V_0 \sqcup V_1$ with no edges between $V_0$ and $V_1$ (resp. with all edges between $V_0$ and $V_1$). The equivalence is proved by mapping $V_0$ and $V_1$ to the distinct vertices of $K_2$ or $T_2$.

A naive definition of these properties by $A=\begin{pmatrix} * &{} 0 \\ 0 &{} * \end{pmatrix}$ or $\begin{pmatrix} 0 &{} * \\ * &{} 0 \end{pmatrix}$ along some nontrivial decomposition $B=B_0\oplus B_1$ of the quantum set is too restrictive for quantum graphs. Indeed there exists a 1-regular undirected irreflexive quantum graph $(M_2,\tau ,A=2E_{{\mathbb {C}}^2}-\textrm{id})$ (c.f. [12, 15]) with $\mathop {\text {spec}}\nolimits A=\{-1,-1,1,1\}$, which looks like bipartite and disconnected but has no nontrivial decomposition $M_2=B_0\oplus B_1$. That is why we defined as above.

The following is the key lemma to prove spectral characterizations of these properties. This lemma allows us to control the decomposition of a self-adjoint operator into positive and negative parts.

Lemma 3.3

Let B be a $C^*$-algebra with a faithful state $\psi$, and $x_\pm , y_\pm \in B$ be positive elements satisfying

$$\begin{aligned} x_+ - x_- = y_+ - y_- \end{aligned}$$

with $\psi (x_+) = \psi (y_+), \psi (x_-) = \psi (y_-)$. Assume that there is a projection $p \in B$ such that

$$\begin{aligned} p x_+=x_+=x_+ p, \quad (1-p) x_-=x_-=x_- (1-p), \quad \psi (p \ \cdot )=\psi (\cdot \ p). \end{aligned}$$

Then it follows that $x_+=y_+, x_-=y_-$.

Proof

We show that $\xi {:}{=} y_+ - x_+=y_- - x_-$ is zero. By assumptions on p, we have

$$\begin{aligned} p \xi p&= p y_+ p - x_+ = p y_- p \ge 0 \\ (1-p) \xi (1-p)&= (1-p) y_- (1-p) - x_- = (1-p) y_+ (1-p) \ge 0 \\ p \xi (1-p)&= p y_+ (1-p) = p y_- (1-p). \end{aligned}$$

By $\psi (\xi )=\psi (y_+)-\psi (x_+)=0$ and $\psi (p\xi (1-p))=\psi (\xi (1-p)p)=0$, we have

$$\begin{aligned} 0 = \psi (\xi )&= \psi (p \xi p) + \psi ((1-p) \xi (1-p)) +\psi (p \xi (1-p)) +\psi ((1-p) \xi p) \\&= \psi (p \xi p) + \psi ((1-p) \xi (1-p)). \end{aligned}$$

Since $p \xi p$ and $(1-p) \xi (1-p)$ are positive, faithfulness of $\psi$ implies

$$\begin{aligned} p\xi p = (1-p) \xi (1-p) =0. \end{aligned}$$

By positivity of $y_+=x_+ + \xi$, it follows for all $t \in {\mathbb {R}}$ that

$$\begin{aligned} (p + t(1-p))y_+ (p + t(1-p))=x_+ + t(p \xi (1-p) + (1-p) \xi p) \end{aligned}$$

is positive. Since $p \xi (1-p) + (1-p) \xi p$ is self-adjoint, if it has a nonzero positive or negative part, $x_+ + t(p \xi (1-p) + (1-p) \xi p)$ cannot be always positive. Therefore $p \xi (1-p) + (1-p) \xi p=0$, hence $\xi =(p + (1-p))\xi (p + (1-p))=0$. $\square$

Lemma 3.4

Let B be a von Neumann algebra with a faithful tracial state $\tau$, and $x_\pm , y_\pm \in B$ be positive elements satisfying

$$\begin{aligned} x_+ - x_- = y_+ - y_-, \quad x_+ x_-=x_- x_+=0 \end{aligned}$$

with $\tau (x_+) = \tau (y_+), \tau (x_-) = \tau (y_-)$. Then it follows that $x_+=y_+, x_-=y_-$.

Proof

Since $x_+ x_-=x_- x_+=0$, the range projection p of $x_+$ satisfies $p x_+=x_+=x_+ p$ and $(1-p) x_-=x_-=x_- (1-p)$. Since $\tau$ is tracial, we also have $\tau (p \ \cdot )=\tau (\cdot \ p)$. Thus Lemma 3.3 shows $x_+=y_+, x_-=y_-$. $\square$

Remark 3.5

Note that the assumption $\psi (p \ \cdot )=\psi (\cdot \ p)$ is essential in Lemma 3.3. Indeed we have the following counterexample without this property. Let $B=M_2, \psi =\omega _q \circ \mathop {\text {ad}}\nolimits (u)=\mathop {\text {Tr}}\nolimits (u^* Qu \cdot )$ where $\displaystyle Q=\frac{1}{1+q^2} \begin{pmatrix} 1 &{} 0 \\ 0 &{} q^2 \end{pmatrix}, q \in (0,1), u=\frac{1}{\sqrt{2}} \begin{pmatrix} 1 &{} -1 \\ 1 &{} 1 \end{pmatrix}$. Put

$$\begin{aligned} x_+&= \begin{pmatrix} 1 &{} 0 \\ 0 &{} 0 \end{pmatrix} \ge 0,&x_-&= \begin{pmatrix} 0 &{} 0 \\ 0 &{} 1 \end{pmatrix} \ge 0,&\xi&= \alpha \begin{pmatrix} 1 &{} \frac{1+q^2}{1-q^2} \\ \frac{1+q^2}{1-q^2} &{} 1 \end{pmatrix} : \text {s.a.}, \end{aligned}$$

for $\alpha \in \left( 0, \frac{(q^{-1}-q)^2}{4} \right]$. It follows that

$$\begin{aligned} y_\pm&= x_\pm +\xi \ge 0,&\psi (\xi )&= 0 \text {, i.e., } \psi (x_\pm ) = \psi (y_\pm ), \end{aligned}$$

and $x_+, x_-$ are orthogonal projections, but $\xi \ne 0$.

Proof

We have

$$\begin{aligned} y_+=\begin{pmatrix} 1+\alpha &{} \frac{1+q^2}{1-q^2}\alpha \\ \frac{1+q^2}{1-q^2}\alpha &{} \alpha \end{pmatrix}, \end{aligned}$$

hence $\mathop {\text {Tr}}\nolimits (y_+)=1+2\alpha >0$ and

$$\begin{aligned} \det y_+ = \alpha +\alpha ^2 \left( 1 - \left( \frac{1+q^2}{1-q^2}\right) ^2 \right) = \alpha \left( 1 - \alpha \frac{4 q^2}{(1-q^2)^2} \right) \ge 0 \end{aligned}$$

show that $y_+ \ge 0$, and $y_- \ge 0$ as well. By simple computation, we get

$$\begin{aligned} \psi (\xi )=\mathop {\text {Tr}}\nolimits (u^* Qu \xi ) =\frac{\alpha }{2} \mathop {\text {Tr}}\nolimits \left( \begin{pmatrix} 1 &{} \frac{-1+q^2}{1+q^2} \\ \frac{-1+q^2}{1+q^2} &{} 1 \end{pmatrix} \begin{pmatrix} 1 &{} \frac{1+q^2}{1-q^2} \\ \frac{1+q^2}{1-q^2} &{} 1 \end{pmatrix} \right) =0. \end{aligned}$$

$\square$

Lemma 3.6

Let ${\mathcal {G}} = (B,\psi ,A)$ be a d-regular undirected tracial quantum graph. It follows for any self-adjoint $x \in \ker (d \,\textrm{id}-A)$ that $C^*(x) \subset \ker (d \,\textrm{id}-A)$.

Proof

It suffices to show that $A p_i = d p_i$ for the spectral projections $\{p_1,\ldots , p_k \}$ of $x= \sum _{i=1}^k \lambda _i p_i$ with $\lambda _1> \cdots > \lambda _k$. Consider $\ker (d\, \textrm{id}-A) \ni x-\lambda _2 1_B = (\lambda _1 - \lambda _2) p_1 - \sum _{i=2}^k (\lambda _2 - \lambda _i) p_i$, then

$$\begin{aligned} (\lambda _1 - \lambda _2) Ap_1 - \sum _{i=2}^k (\lambda _2 - \lambda _i) Ap_i = d(\lambda _1 - \lambda _2) p_1 - d \sum _{i=2}^k (\lambda _2 - \lambda _i) p_i. \end{aligned}$$

Since $(\lambda _1 - \lambda _2) p_1$ and $\sum _{i=2}^k (\lambda _2 - \lambda _i) p_i$ are positive and have disjoint supports, $\psi A=d \psi$ shows that we can apply Lemma 3.4. Thus

$$\begin{aligned} (\lambda _1 - \lambda _2) Ap_1 = d(\lambda _1 - \lambda _2) p_1, \end{aligned}$$

hence $p_1, \sum _{i=2}^k \lambda _i p_i \in \ker (d \,\textrm{id}-A)$. Inductively we get $p_1,\ldots , p_k \in \ker (d \,\textrm{id} -A)$. $\square$

3.2 Connected quantum graphs

Theorem 3.7

Let ${\mathcal {G}} = (B,\psi ,A)$ be a d-regular undirected tracial quantum graph. The following are equivalent:

(1):

${\mathcal {G}}$ is connected.

(2):

$d \in \mathop {\text {spec}}\nolimits (A)$ is a simple root, i.e., $\dim \ker (d \,\textrm{id}-A)=1$.

Proof

If $\dim B=1$, then ${\mathcal {G}}$ is connected and d is simple. If ${\dim B}\ge 2$ and $d=0$, then $A=0$ by Lemma 1.11 and d has multiplicity $\ge 2$, whence there is an injective unital $*$-homomorphism $f: {\mathbb {C}}^2 \rightarrow B$. Hence neither ${\mathcal {G}}$ is connected nor d is simple. In the sequel of the proof, we may assume $d>0$ and $\dim B \ge 2$.

$((2) \implies (1))$: We show that d is a multiple root if ${\mathcal {G}}$ is disconnected.

We have an injective unital $*$-homomorphism $f: {\mathbb {C}}^2 \rightarrow B$ such that $\begin{pmatrix} 1 &{} 0 \\ 0 &{} 1 \end{pmatrix} \bullet f^\dagger A f =f^\dagger A f$. Put $x_1=f(e_1), x_2=f(e_2) \in B$, which are mutually orthogonal nonzero projections satisfying $x_1+ x_2 = 1_B$. The regularity shows $Ax_1 + Ax_2=A1_B=dx_1 + dx_2$. By $(f^\dagger A f)_{ij}=2\langle e_i|f^\dagger A f |e_j\rangle =2\langle x_i| A x_j\rangle$ and $\begin{pmatrix} 1 &{} 0 \\ 0 &{} 1 \end{pmatrix} \bullet f^\dagger A f =f^\dagger A f$, it follows that

$$\begin{aligned} \langle x_1| A x_2\rangle&= \langle x_2| A x_1\rangle = 0; \\ \langle x_1| A x_1\rangle&= \langle x_1+x_2| A x_1\rangle = \psi (A x_1) = d\psi (x_1); \\ \langle x_2| A x_2\rangle&= \langle x_1+x_2| A x_2\rangle = \psi (A x_2) = d\psi (x_2). \end{aligned}$$

Thus $Ax_1= dx_1 + (dx_2-Ax_2)$ gives the orthogonal decomposition of $Ax_1$ along ${\mathbb {C}}x_1 \oplus (x_1)^\perp$. Then we have

$$\begin{aligned} d^2 \psi (x_1) \ge {\left\Vert {Ax_1}\right\Vert }_2^2 = {\left\Vert {d x_1}\right\Vert }_2^2 + {\left\Vert {dx_2-Ax_2}\right\Vert }_2^2 = d^2 \psi (x_1) + {\left\Vert {dx_1-Ax_2}\right\Vert }_2^2, \end{aligned}$$

hence ${\left\Vert {dx_2-Ax_2}\right\Vert }_2=0$, i.e., $Ax_2=dx_2$ and $Ax_1=dx_1$. Therefore $d \in \mathop {\text {spec}}\nolimits (A)$ has multiplicity more than 1.

$((1) \implies (2))$: We show that ${\mathcal {G}}$ is disconnected if d is not simple.

By Lemma 1.12 and the multiplicity of d, there is a self-adjoint $x \in \ker (d\, \textrm{id}-A) {\setminus } {\mathbb {C}}1$, and Lemma 3.6 allows us to take mutually orthogonal projections $x_1,x_2 \in \ker (d\, \textrm{id}-A)$ satisfying $x_1+ x_2=1$ as spectral projections of x. Thus we obtain an injective $*$-homomorphism $f: {\mathbb {C}}^2 \rightarrow B$ defined by $f(e_i)=x_i$ for $i=1,2$. It satisfies

$$\begin{aligned} 2 \langle e_i|f^\dagger Af | e_j\rangle&= 2 \langle x_i | A x_j\rangle = 2d \langle x_i | x_j\rangle =2d \psi (x_i) \delta _{ij}. \end{aligned}$$

Thus $f^\dagger Af = \begin{pmatrix} 2d \psi (x_1) &{} 0 \\ 0 &{} 2d \psi (x_2) \end{pmatrix}$, which gives a surjective graph homomorphism $f^\textrm{op}: {\mathcal {G}} \rightarrow T_2$. $\square$

3.3 Bipartite quantum graphs

Theorem 3.8

Let ${\mathcal {G}} = (B,\psi ,A)$ be a d-regular connected undirected tracial quantum graph. The following are equivalent:

(1):

${\mathcal {G}}$ is bipartite.

(2):

$-d \in \mathop {\text {spec}}\nolimits (A)$. If $d=0$, we require that the multiplicity of $0 \in \mathop {\text {spec}}\nolimits (A)$ is at least two, i.e., ${\dim B} \ge 2$.

Proof

If ${\dim B} =1$, then $A=0$ with simple root $d=0$ or $A=\textrm{id}_{\mathbb {C}}$ with $d=1\ne -d$, hence neither bipartite nor $-d \in \mathop {\text {spec}}\nolimits (A)$. We may assume ${\dim B}\ge 2$, then the connectedness implies $d>0$ as argued in the proof of Theorem 3.7.

$((1) \implies (2))$: We have an injective unital $*$-homomorphism $f: {\mathbb {C}}^2 \rightarrow B$ such that $\begin{pmatrix} 0 &{} 1 \\ 1 &{} 0 \end{pmatrix} \bullet f^\dagger A f =f^\dagger A f$. Put $x_1=f(e_1), x_2=f(e_2) \in B$, which are mutually orthogonal nonzero projections satisfying $x_1+ x_2 = 1_B$. The regularity shows $Ax_1 + Ax_2=A1_B=dx_1 + dx_2$. By $(f^\dagger A f)_{ij}=2\langle e_i|f^\dagger A f |e_j\rangle =2\langle x_i| A x_j\rangle$ and $\begin{pmatrix} 0 &{} 1 \\ 1 &{} 0 \end{pmatrix} \bullet f^\dagger A f =f^\dagger A f$, it follows that

$$\begin{aligned} \langle x_1| A x_1\rangle&= \langle x_2| A x_2\rangle = 0; \\ \langle x_1| A x_2\rangle&= \langle x_1+x_2| A x_2\rangle = \psi (A x_2) = d\psi (x_2) \\&=\overline{\langle x_2| A x_1\rangle }=d\psi (x_1). \end{aligned}$$

Thus $\psi (x_1)=\psi (x_2)=1/2$, and $Ax_1= dx_2 + (dx_1-Ax_2)$ gives the orthogonal decomposition of $Ax_1$ along ${\mathbb {C}}x_2 \oplus (x_2)^\perp$. This yields

$$\begin{aligned} \frac{d^2}{2} = d^2 \psi (x_1) \ge {\left\Vert {Ax_1}\right\Vert }_2^2 = {\left\Vert {d x_2}\right\Vert }_2^2 + {\left\Vert {dx_1-Ax_2}\right\Vert }_2^2 = \frac{d^2}{2} + {\left\Vert {dx_1-Ax_2}\right\Vert }_2^2, \end{aligned}$$

hence ${\left\Vert {dx_1-Ax_2}\right\Vert }_2=0$, i.e., $Ax_1=dx_2$ and $Ax_2=dx_1$. Therefore we obtain $A(x_1-x_2) = -d(x_1-x_2)$, which shows $-d \in \mathop {\text {spec}}\nolimits (A)$.

$((2) \implies (1))$: By Lemma 1.12, we can take a self-adjoint $x \in \ker (d \,\textrm{id}+A)$ with ${\left\Vert {x}\right\Vert }_2=1$. Decompose $x=x_+ - x_-$ into positive and negative parts $x_\pm \in B_+$, Then we have

$$\begin{aligned} A x_+ - A x_-= Ax = -dx =dx_- - dx_+. \end{aligned}$$

The self-adjointness of A implies the orthogonality of eigenvectors $\psi (x)=\langle 1 | x\rangle =0$, i.e., $\psi (x_+)=\psi (x_-)$, hence the regularity implies $\psi (Ax_\pm )=d \psi (x_\pm )=d \psi (x_\mp )=\psi (d x_\mp )$. Note that the real quantum graph A is CP; hence $Ax_\pm$ are positive. Since $\psi$ is tracial and $x_\pm$ have disjoint supports, Lemma 3.4 shows

$$\begin{aligned} Ax_\pm = dx_\mp . \end{aligned}$$

Thus $A(x_+ + x_-)=d(x_+ + x_-)$. Since ${\mathcal {G}}$ is connected, we get $x_+ + x_- =c1_B$ for some $c>0$. By $1={\left\Vert {x}\right\Vert }_2^2={\left\Vert {x_+}\right\Vert }_2^2 + {\left\Vert {x_-}\right\Vert }_2^2={\left\Vert {x_+ + x_-}\right\Vert }_2^2 =c^2$, we have $c=1, x_+ + x_- =1_B$. Then $x_+ x_-=0$ shows $x_\pm ^2=x_\pm (x_\pm + x_\mp )=x_\pm$, hence $x_\pm$ are mutually orthogonal projections with $\psi (x_\pm )=1/2$. Thus we obtain an injective $*$-homomorphism $f: {\mathbb {C}}^2 \rightarrow B$ defined by $f(e_1)=x_+, f(e_2)=x_-$. It satisfies

$$\begin{aligned} 2 \langle e_i|f^\dagger Af | e_i\rangle&= 2 \langle x_\pm | A x_\pm \rangle = 2d \langle x_\pm | x_\mp \rangle =0 \quad (i=1,2); \\ 2 \langle e_1|f^\dagger Af | e_2\rangle&= 2 \langle x_+ | A x_-\rangle = 2d \langle x_+ | x_+\rangle =d. \end{aligned}$$

Thus $f^\dagger Af = \begin{pmatrix} 0 &{} d \\ d &{} 0 \end{pmatrix}$, which gives a surjective graph homomorphism $f^\textrm{op}: {\mathcal {G}} \rightarrow K_2$. $\square$

Theorem 3.9

Let ${\mathcal {G}} = (B,\psi ,A)$ be a d-regular undirected tracial quantum graph. The following are equivalent:

(1):

${\mathcal {G}}$ has a bipartite component.

(2):

$-d \in \mathop {\text {spec}}\nolimits (A)$. If $d=0$, we require that the multiplicity of $0 \in \mathop {\text {spec}}\nolimits (A)$ is at least two, i.e., ${\dim B} \ge 2$.

Proof

If $\dim B=1$, ${\mathcal {G}}\rightarrow K_2\sqcup T_1$ cannot be surjective to $K_2$. Hence ${\mathcal {G}}$ does not have a bipartite component, and $-d \in \mathop {\text {spec}}\nolimits (A)$ does not hold as in the previous proof. If $d=0$ and ${\dim B} \ge 2$, then $d=0=-d$ is the multiple root of $A=0$ and has a graph homomorphism ${\mathcal {G}}\rightarrow K_2\sqcup T_1$ that is surjective to $K_2$, hence ${\mathcal {G}}$ has a bipartite component and $-d \in \mathop {\text {spec}}\nolimits (A)$. In the sequel of the proof, we may assume $d>0$ and ${\dim B} \ge 2$.

$((1) \implies (2))$: We have a unital $*$-homomorphism $f: {\mathbb {C}}^3 \rightarrow B$ such that $\begin{pmatrix} 0 &{} 1 &{} 0 \\ 1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 \end{pmatrix} \bullet f^\dagger A f =f^\dagger A f$ and f is injective on ${\mathbb {C}}^2 \oplus 0$. Put $x_i=f(e_i) \in B$ for $i=1,2,3$, which are mutually orthogonal projections satisfying $x_1+x_2+x_3=1$ and $x_1,x_2$ are nonzero. Then the regularity implies

$$\begin{aligned} Ax_1 + A(1-x_1)=A1_B=dx_2 + d(1-x_2). \end{aligned}$$

By $(f^\dagger A f)_{ij}=3\langle e_i|f^\dagger A f |e_j\rangle =3\langle x_i| A x_j\rangle$ and $\begin{pmatrix} 0 &{} 1 &{} 0 \\ 1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 \end{pmatrix} \bullet f^\dagger A f =f^\dagger A f$, it follows that

$$\begin{aligned} \langle 1-x_1| A x_2\rangle&= \langle 1-x_2| A x_1\rangle = \langle 1-x_3| A x_3\rangle = 0; \\ \langle x_1| A x_2\rangle&= \langle x_1+(1-x_1)| A x_2\rangle = \psi (A x_2) = d\psi (x_2) \\&=\overline{\langle x_2| A x_1\rangle }=d\psi (x_1). \end{aligned}$$

Thus $\psi (x_1)=\psi (x_2)$, and $Ax_1= dx_2 + (d(1-x_2)-A(1-x_1))$ gives the orthogonal decomposition of $Ax_1$ along ${\mathbb {C}}x_2 \oplus (x_2)^\perp$. Then we have

$$\begin{aligned} d^2 \psi (x_1) = {\left\Vert {A}\right\Vert }^2 {\left\Vert {x_1}\right\Vert }_2^2&\ge {\left\Vert {Ax_1}\right\Vert }_2^2 = {\left\Vert {d x_2}\right\Vert }_2^2 + {\left\Vert {d(1-x_2)-A(1-x_1)}\right\Vert }_2^2 \\&= d^2 \psi (x_2) + {\left\Vert {d(1-x_2)-A(1-x_1)}\right\Vert }_2^2, \end{aligned}$$

hence ${\left\Vert {d(1-x_2)-A(1-x_1)}\right\Vert }_2=0$, i.e., $A(1-x_1)=d(1-x_2)$ and $Ax_1=dx_2$. By symmetry, we also have $Ax_2=dx_1$. Therefore we obtain

$$\begin{aligned} A(x_1-x_2) = -d(x_1-x_2), \end{aligned}$$

which shows $-d \in \mathop {\text {spec}}\nolimits (A)$.

$((2) \implies (1))$: By Lemma 1.12, we can take a self-adjoint $x \in \ker (d\, \textrm{id}+A)$. Consider the spectral projections $\{ p_\lambda | \lambda \in \mathop {\text {spec}}\nolimits (x)\}$ of

$$\begin{aligned} x=\sum _{\lambda } \lambda p_\lambda = \sum _{\lambda>0} \lambda (p_\lambda - p_{-\lambda }); \quad x_+ = \sum _{\lambda>0} \lambda p_\lambda ; \quad x_- = \sum _{\lambda >0} \lambda p_{-\lambda }. \end{aligned}$$

In the same way as the proof of Theorem 3.8, we obtain $Ax_\pm =d x_\mp$ and $x_+ + x_- \in \ker (d\, \textrm{id}- A)$. Therefore it follows from Lemma 3.6 that $p_\lambda + p_{-\lambda } \in \ker (d \,\textrm{id}- A)$ for all $\lambda > 0$. Thus it follows for a fixed $\lambda >0$ that

$$\begin{aligned} A p_{\lambda } = d p_\lambda + d p_{-\lambda } - A p_{-\lambda } \le d p_\lambda + d p_{-\lambda }. \end{aligned}$$

(3.1)

Now $\lambda p_\lambda \le x_+$ implies

$$\begin{aligned} A p_\lambda \le \lambda ^{-1} Ax_+ = \frac{d}{\lambda } x_- = \sum _{\mu >0} \frac{d \mu }{\lambda } p_{-\mu }. \end{aligned}$$

(3.2)

By taking the meet of (3.1) and (3.2) in the lattice of self-adjoint elements in the commutative algebra $C^*(x)$, we obtain

$$\begin{aligned} A p_\lambda \le (d p_\lambda + d p_{-\lambda }) \wedge \sum _{\mu >0} \frac{d \mu }{\lambda } p_{-\mu } = d p_{-\lambda }. \end{aligned}$$

(3.3)

Similarly we have $A p_{-\lambda } \le d p_{\lambda }$, i.e.,

$$\begin{aligned} A p_\lambda = A(1 - p_{-\lambda }) \ge d(1 - p_{\lambda })= d p_{-\lambda }. \end{aligned}$$

(3.4)

Combining (3.3) and (3.4) we get $A p_\lambda = d p_{-\lambda }$ and $A p_{-\lambda } = d p_{\lambda }$. Hence $p_\lambda - p_{-\lambda } \in \ker (d \,\textrm{id}+A)$ for all $\lambda > 0$. Thus we may initially take $x=x_+ - x_- \in \ker (d \,\textrm{id}+A)$ for mutually orthogonal nonzero projections $x_\pm \in B$ satisfying

$$\begin{aligned} Ax_\pm = dx_\mp . \end{aligned}$$

Then we have a $*$-homomorphism $f: {\mathbb {C}}^2 \oplus {\mathbb {C}}\rightarrow B$ defined by $f(e_1)=x_+, f(e_2)=x_-, f(e_3)=1-x_+ - x_-$ that is injective on ${\mathbb {C}}^2 \oplus 0$. It satisfies

$$\begin{aligned} 3 \langle e_i|f^\dagger Af | e_i\rangle&= 3 \langle x_\pm | A x_\pm \rangle = 3d \langle x_\pm | x_\mp \rangle =0 \quad (i=1,2); \\ 3 \langle e_1|f^\dagger Af | e_2\rangle&= 3 \langle x_+ | A x_-\rangle = 3d \langle x_+ | x_+\rangle =3d \psi (x_+); \\ 3 \langle e_i|f^\dagger Af | e_3\rangle&= 3 \langle x_\pm | d1- dx_+ - dx_-\rangle = 0 \quad (i=1,2); \\ 3 \langle e_3|f^\dagger Af | e_3\rangle&= 3d \langle 1-x_+ - x_- | 1-x_+ - x_-\rangle = 3d (1-2\psi (x_+)). \end{aligned}$$

Thus $f^\dagger Af = \begin{pmatrix} 0 &{} 3d \psi (x_+) &{} 0 \\ 3d \psi (x_+) &{} 0 &{} 0 \\ 0 &{} 0 &{} 3d (1-2\psi (x_+)) \end{pmatrix}$, which gives a graph homomorphism $f^\textrm{op}: {\mathcal {G}} \rightarrow K_2 \sqcup T_1$. $\square$

4 Two-Colorability and Bipartiteness

It is known that a classical graph is bipartite if and only if it is two-colorable. We compare the bipartiteness defined in this paper and the local two-colorability introduced in [3].

4.1 t-homomorphism

The gap of bipartiteness and two-colorability arises from the two notions of graph homomorphisms: one is Definition 3.1 and the other is the following t-homomorphisms:

Definition 4.1

(Modified generalization of Brannan et al. [3]). Let ${\mathcal {G}}_0 = (B_0,\psi _0,A_0,{\mathcal {S}}_0), {\mathcal {G}}_1 = (B_1,\psi _1,A_1,{\mathcal {S}}_1)$ be quantum graphs with $\delta _i$-forms $\psi _i$ and quantum relations ${\mathcal {S}}_i=\mathop {\text {range}}\nolimits (A_i\bullet \cdot )\subset B(L^2({\mathcal {G}}_i))$. A t-homomorphism $(f,{\mathcal {A}}):{\mathcal {G}}_0 \overset{t}{\rightarrow }\ {\mathcal {G}}_1$ ($t \in \{loc,q,qa,qc,C^*,alg\}$) is consisting of a unital $*$-homomorphism $f: B_1 \rightarrow B_0 \otimes {\mathcal {A}}$ and a unital $*$-algebra ${\mathcal {A}}$ satisfying

$$\begin{aligned} f^\dagger ({\mathcal {S}}_0 \otimes 1_{\mathcal {A}}) f&\subset {\mathcal {S}}_1 \otimes {\mathcal {A}}, \end{aligned}$$

(4.1)

where $f^\dagger \in B(L^2({\mathcal {G}}_0),L^2({\mathcal {G}}_1)) \otimes {\mathcal {A}}$ is the adjoint $(\cdot )^\dagger \otimes (\cdot )^*$ of f as an operator in $B(L^2({\mathcal {G}}_1),L^2({\mathcal {G}}_0)) \otimes {\mathcal {A}}$, and

• ${\mathcal {A}}={\mathbb {C}}$ if $t=loc$ (local, classical);

• ${\mathcal {A}}$ is finite-dimensional if $t=q$ (quantum);

• ${\mathcal {A}}={\mathcal {R}}^\omega$ is the ultrapower of the hyperfinite $II_1$-factor ${\mathcal {R}}$ by a free ultrafilter $\omega$ on ${\mathbb {N}}$ if $t=qa$ (quantum approximate);

• ${\mathcal {A}}$ is a tracial $C^*$-algebra if $t=qc$ (quantum commuting);

• ${\mathcal {A}}$ is a $C^*$-algebra if $t=C^*$;

• ${\mathcal {A}}$ is a unital $*$-algebra if $t=alg$.

These notions of t show what kind of quantum correlation is allowed in the corresponding graph homomorphism game.

We say that a t-homomorphism $(f,{\mathcal {A}}):{\mathcal {G}}_0 \overset{t}{\rightarrow }\ {\mathcal {G}}_1$ is:

• (vertex-)surjective if $f: B_1 \rightarrow B_0 \otimes {\mathcal {A}}$ is injective.

This definition means that the pushforward of the edges of ${\mathcal {G}}_0$ by the mapping $(f,{\mathcal {A}})$ are edges of ${\mathcal {G}}_1$.

Remark 4.2

For a t-homomorphism $(f,{\mathcal {A}}):{\mathcal {G}}_0 \overset{t}{\rightarrow }\ {\mathcal {G}}_1$, the best definition of (vertex-)injectivity is not sure. If it is a classical homomorphism between classical graphs, then $(f,{\mathcal {A}}={\mathbb {C}})$ is injective if and only if $(\delta _0/\delta _1)f$ is a coisometry $f f^\dagger = (\delta _1/\delta _0)^2 \textrm{id}_{B_1} \otimes 1_{\mathcal {A}}$, so this is a candidate for the definition of injectivity. Another weaker candidate is the injectivity of $f^\dagger : B_0 \rightarrow B_1 \otimes {\mathcal {A}}$.

On the other hand, in classical case $(f,{\mathbb {C}})$ is surjective if and only if $f^\dagger f \ge (\delta _1/\delta _0)^2 \textrm{id}_{B_0} \otimes 1_{\mathcal {A}}$, which may be too strong for the definition of surjectivity of general $(f,{\mathcal {A}})$.

Consider a toy model $f: {\mathbb {C}}^4 \rightarrow {\mathbb {C}}^2 \otimes M_2$ of a quantum 4-coloring of 2 vertices $(f,M_2):({\mathbb {C}}^2,\tau ,0)\overset{q}{\rightarrow }K_4$ given by

$$\begin{aligned} f(e_1)=e_1 \otimes e_{11}; \quad f(e_2)=e_2 \otimes e_{11}; \quad f(e_3)=e_1 \otimes e_{22}; \quad f(e_4)=e_2 \otimes e_{22}. \end{aligned}$$

Then coisometry condition $ff^\dagger =2\, \textrm{id}_{{\mathbb {C}}^2} \otimes 1_{M_2}$ holds, hence $(f,M_2)$ is injective in the strong sense. On the other hand, we have an injective homomorphism f but $f^\dagger f=2 [(e_1+e_2)\otimes e_{11} + (e_3+e_4)\otimes e_{22} ] \not \ge 2\ \textrm{id}_{{\mathbb {C}}^4} \otimes 1_{M_2}$, hence $(f,M_2)$ is surjective only in the weak sense as defined above.

Notation

For a quantum graph ${\mathcal {G}}=(B.\psi ,A)$ and a unital algebra ${\mathcal {A}}$, we abbreviate by $A\bullet \cdot$ the left Schur product by A acting on the first tensor component of $B(L^2({\mathcal {G}})) \otimes {\mathcal {A}}$.

If we faithfully represent ${\mathcal {A}}\subset B(H)$ on a Hilbert space H, we may regard $f: B_1 \rightarrow B_0 \otimes {\mathcal {A}}$ as $f: L^2({\mathcal {G}}_1)\otimes H \rightarrow H \otimes L^2({\mathcal {G}}_0) \in B(L^2({\mathcal {G}}_1),L^2({\mathcal {G}}_0)) \otimes B(H)$. By this identification, we denote f in string diagrams by

where H is drawn as oriented strings. Even if ${\mathcal {A}}$ is not a $C^*$-algebra, such a diagram formally makes sense by thinking of the string of H as an indicator of the order of multiplication in ${\mathcal {A}}$.

Note that f is unital; multiplicative; $*$-preserving (real) respectively if and only if the following are satisfied:

Proposition 4.3

Let $(f,{\mathcal {A}}):{\mathcal {G}}_0 \overset{t}{\rightarrow } {\mathcal {G}}_1$ be as in Definition 4.1 without assumption (4.1). The following are equivalent:

(1):

The inclusion (4.1): $f^\dagger ({\mathcal {S}}_0 \otimes 1_{\mathcal {A}}) f \subset {\mathcal {S}}_1 \otimes {\mathcal {A}}$;

(2):

$A_1 \bullet (f^\dagger (A_0 \bullet T\otimes 1_{\mathcal {A}}) f ) =f^\dagger (A_0 \bullet T\otimes 1_{\mathcal {A}}) f$ for any $T \in B(L^2({\mathcal {G}}_0))$;

(3):

$\langle S | f^\dagger (T\otimes 1_{\mathcal {A}}) f\rangle =0$ in ${\mathcal {A}}$ for any $S \in {\mathcal {S}}_1^\perp$ and $T \in {\mathcal {S}}_0$, where $\langle S | \cdot \rangle =\Psi _1(S^\dagger \cdot ) =\delta _1^2 \langle 1_{B_1}|S^* \bullet \cdot |1_{B_1}\rangle _{\psi _1}$ as in (1.4) acts on the first tensor component;

(4):

The (adjoint of) diagrammatic definition of quantum graph homomorphism by [16, Definition 5.4]:

Proof

$((1) \iff (2))$: Since ${\mathcal {S}}_1 \otimes {\mathcal {A}} =\mathop {\text {range}}\nolimits (A_1 \bullet \cdot ) \otimes {\mathcal {A}}$ and $A_1 \bullet \cdot$ is a projection, (1) means that $f^\dagger (S\otimes 1_{\mathcal {A}}) f$ is invariant under the action of $A_1 \bullet \cdot$ for all $S \in {\mathcal {S}}_0$. Thus (1) is equivalent to

$$\begin{aligned} A_1 \bullet (f^\dagger (A_0 \bullet T\otimes 1_{\mathcal {A}}) f ) =f^\dagger (A_0 \bullet T \otimes 1_{\mathcal {A}}) f \qquad \forall T \in B(L^2({\mathcal {G}}_0)). \end{aligned}$$

$((1)\iff (3))$: Note that

$$\begin{aligned} ({\mathcal {S}}_1^\perp )^\perp \otimes {\mathcal {A}} =\{ X \in B(L^2({\mathcal {G}}_1))\otimes {\mathcal {A}} \vert \langle S|X\rangle =0 \ \forall S \in {\mathcal {S}}_1^\perp \}. \end{aligned}$$

Indeed $\subset$ is obvious and $\supset$ is shown by choosing a presentation $X=\sum _j T_j \otimes a_j \in \text {(RHS)}$ with independent $a_j$’s in ${\mathcal {A}}$ to deduce $\langle S|T_j\rangle =0$ from $\langle S|X\rangle = \sum _j \langle S|T_j\rangle a_j=0$. Thus (1) is equivalent to (3).

$((2)\implies (4))$: In string diagrams, (2) is expressed as follows:

Since $T \in B(L^2({\mathcal {G}}_0)) \cong B_0 \otimes B_0^*$ is arbitrary, we may replace with open ends of strings of $B_0$. We move the open ends to the top (insert ) and move the top left string of $B_1$ to the bottom (postcompose the right end of ) to obtain

Therefore it follows by the realness (4.2) of f that

$((4)\implies (2))$: We can transform the diagrams conversely to go back from (4) to (2). $\square$

Note that [3] defined the quantum-to-classical t-homomorphisms by the following conditions instead of (4.1) to omit self-loops in particular for the coloring problem.

$$\begin{aligned} f^\dagger ({\mathcal {S}}_0 \cap {\mathcal {S}}_{T(B_0,\psi _0)}^\perp \otimes 1_{\mathcal {A}}) f&\subset {\mathcal {S}}_1 \otimes {\mathcal {A}}; \end{aligned}$$

(4.3)

$$\begin{aligned} f^\dagger ({\mathcal {S}}_{T(B_0,\psi _0)} \otimes 1_{\mathcal {A}}) f&\subset {\mathcal {S}}_{T(B_1,\psi _1)} \otimes {\mathcal {A}}. \end{aligned}$$

(4.4)

(4.1) and (4.3) coincide under some assumptions, and as a generalization of [3, Lemma 4.8], the second condition (4.4) is redundant as shown below.

Lemma 4.4

Let $(f,{\mathcal {A}}):{\mathcal {G}}_0 \overset{t}{\rightarrow } {\mathcal {G}}_1$ be as in Definition 4.1 without assumption (4.1).

(1):

The inclusion (4.4) always holds.

(2):

(4.1) is equivalent to (4.3) if ${\mathcal {G}}_0$ is irreflexive, or if ${\mathcal {G}}_0$ has no partial loops and ${\mathcal {G}}_1$ is reflexive.

Proof

(1) Recall that the adjacency matrix of the trivial graph $T(B_i,\psi _i)$ is $\textrm{id}_{B_i}$. Thus (4.4) is equivalent to

This is proved by the multiplicativity (4.2) of f and Frobenius equality:

(2) (i) If ${\mathcal {G}}_0$ is irreflexive, then ${\mathcal {S}}_0 \subset {\mathcal {S}}_{T(B_0,\psi _0)}^\perp ={\mathcal {S}}_{K(B_0,\psi _0)}$. Thus (4.3) is exactly equal to (4.1). (ii) Note that (4.1) always implies (4.3) by the trivial inclusion

$$\begin{aligned} f^\dagger ({\mathcal {S}}_0 \cap {\mathcal {S}}_{T(B_0,\psi _0)}^\perp \otimes 1_{\mathcal {A}})f \subset f^\dagger ({\mathcal {S}}_0 \otimes 1_{\mathcal {A}})f \overset{(4.1)}{\subset } {\mathcal {S}}_1 \otimes {\mathcal {A}}. \end{aligned}$$

If ${\mathcal {G}}_1$ is reflexive, then ${\mathcal {S}}_{T(B_1,\psi _1)} \subset {\mathcal {S}}_1$, and no partial loops means that ${\mathcal {S}}_0={\mathcal {S}}_0 \cap {\mathcal {S}}_{T(B_0,\psi _0)}^\perp \oplus {\mathcal {S}}_0 \cap {\mathcal {S}}_{T(B_0,\psi _0)}$ gives an orthogonal decomposition. Thus (4.4) and (4.3) implies

$$\begin{aligned} f^\dagger ({\mathcal {S}}_0 \otimes 1_{\mathcal {A}})f&\subset f^\dagger (({\mathcal {S}}_0 \cap {\mathcal {S}}_{T(B_0,\psi _0)}^\perp \oplus {\mathcal {S}}_{T(B_0,\psi _0)}) \otimes 1_{\mathcal {A}})f \\&\overset{(4.3)}{\subset } ({\mathcal {S}}_1 + {\mathcal {S}}_{T(B_1,\psi _1)}) \otimes {\mathcal {A}} \overset{(4.4)}{=} {\mathcal {S}}_1 \otimes {\mathcal {A}}. \end{aligned}$$

$\square$

Remark 4.5

For a quantum-to-classical t-homomorphism $(f,{\mathcal {A}}):{\mathcal {G}}_0 \overset{t}{\rightarrow } {\mathcal {G}}_1=({\mathbb {C}}^n,\tau ,A_1)$, Proposition 4.3 (4) is equivalent to the existence of projections $P_1,\ldots ,P_n \in B_0 \otimes {\mathcal {A}}$ satisfying $P_i({\mathcal {S}}_0\otimes {\mathcal {A}})P_j=0$ for all (i, j) with $\langle e_i|A_1|e_j\rangle =0$. Indeed, RHS−LHS of (4) with imput $e_i \otimes e_j$ yields

where $A_1^c=J-A_1$ is the complement of $A_1$ satisfying $n\langle e_i|A_1^c|e_j\rangle =1$. We may put $P_i=f(e_i)$ and take Schur product with ${\mathcal {S}}_0$ from the right to obtain $P_i({\mathcal {S}}_0\otimes {\mathcal {A}})P_j=0$. Conversely, if we have $P_i$’s, then the desired f is given by $f(e_i)=P_i$.

The notion of local homomorphism is stronger than that of graph homomorphism as follows.

Proposition 4.6

Let $(f,{\mathbb {C}}):{\mathcal {G}}_0 \overset{loc}{\rightarrow }\ {\mathcal {G}}_1$ be a loc-homomorphism. Then $f^\textrm{op}:{\mathcal {G}}_0 \overset{}{\rightarrow } {\mathcal {G}}_1$ is a graph homomorphism.

Proof

Since $A_0 \in {\mathcal {S}}_0$ and ${\mathbb {C}}$ is the tensor unit, Proposition 4.3 (2) with $T=A_0$ shows $A_1 \bullet (f^\dagger A_0 f ) =f^\dagger A_0 f$. $\square$

The following theorem gives a sufficient condition to make the two notions of homomorphisms coincide.

Theorem 4.7

Let ${\mathcal {G}}_j = (B_j,\psi _j,A_j,{\mathcal {S}}_j)$ for $j=0,1$ be real quantum graphs with $\delta _j$-forms $\psi _j$ and quantum relations ${\mathcal {S}}_j=\mathop {\text {range}}\nolimits (A_j\bullet \cdot )\subset B(L^2({\mathcal {G}}_j))$. Suppose that $f:B_1 \rightarrow B_0$ is modular invariant $\sigma _i \circ f=f=f \circ \sigma _i$ and ${\mathcal {G}}_1$ is Schur central. Then $f^\textrm{op}:{\mathcal {G}}_0 \rightarrow {\mathcal {G}}_1$ is a graph homomorphism if and only if $(f,{\mathbb {C}}):{\mathcal {G}}_0 \overset{}{\rightarrow } {\mathcal {G}}_1$ is a loc-homomorphism.

Proof

Proposition 4.6 shows that a local homomorphism is a graph homomorphism. It suffices to show the converse, i.e.,

holds for any $T \in S_0$ and $S \in S_1^\perp$ from the assumption that (4.5) holds for $T=A_0$.

Take T as a normal vector $\langle T|T\rangle _{\Psi _0}=1$ in $S_0$.

By the following Lemma 4.8, we may assume that $S \in S_1^\perp$ is a Schur projection because ${\mathcal {G}}_1$ is Schur central and so is its complement $(B_1, \psi _1, J-A_1, S_1^\perp =\mathop {\text {range}}\nolimits (J-A_1))$.

Lemma 4.8

Let ${\mathcal {G}} = (B,\psi ,A,{\mathcal {S}})$ be a real quantum graph. Then ${\mathcal {G}}$ is Schur central if and only if ${\mathcal {S}}$ is generated by Schur projections.

And the modular invariance of f enables us to eliminate loops in diagrams as follows:

Now we have

where the non-indicated equalities are continuous deformations.

Recall (1.5) that is a projection onto $\iota ({\mathcal {S}}_0)\subset B_0 \otimes B_0$. Since $\iota (T) \in \iota ({\mathcal {S}}_0)$, the rank one projection is smaller than or equal to $P_{A_0}$, hence $P=P_{A_0}-|\iota (T)\rangle \langle \iota (T)|$ is also a projection. Therefore we obtain

By the vertical symmetry, each term is nonnegative, hence they must be zero. The first term is what we desired:

$\square$

Theorem 4.9

Let ${\mathcal {G}}_j = (B_j,\psi _j,A_j,{\mathcal {S}}_j)$ for $j=0,1$ be real tracial quantum graphs such that ${\mathcal {G}}_1$ is Schur central. Then $f^\textrm{op}:{\mathcal {G}}_0 \rightarrow {\mathcal {G}}_1$ is a graph homomorphism if and only if $(f,{\mathbb {C}}):{\mathcal {G}}_0 \overset{}{\rightarrow } {\mathcal {G}}_1$ is a loc-homomorphism.

Proof

Since each $\psi _j=\mathop {\text {Tr}}\nolimits (Q_j \cdot )$ is tracial, the density $Q_j$ is central and its modular automorphism is $\sigma _i=Q_j^{-1} (\cdot ) Q_j=\textrm{id}_{B_j}$. Thus we have $\sigma _i \circ f=f=f \circ \sigma _i$. Therefore the statement follows from Theorem 4.7. $\square$

Proof of Lemma 4.8

Since the statement depends only on the Schur product structure, it suffices to show for a von Neumann algebra ${\mathcal {M}}(=B^\textrm{op}\otimes B)$ and a projection $p \in {\mathcal {M}}$ that p is central if and only if $p{\mathcal {M}}$ is linearly generated by projections in weak operator topology (WOT).

Suppose p is central, then $p{\mathcal {M}}=p{\mathcal {M}}p$ is a WOT-closed subalgebra of ${\mathcal {M}}$. Then we can decompose $x \in p{\mathcal {M}}p$ into real and imaginary parts, which have spectral projections in $p{\mathcal {M}}p$. Since x lies in the WOT-closed linear span of such spectral projections, we are done.

Suppose that $p{\mathcal {M}}$ is generated by projections. It follows for any projection $q\in p{\mathcal {M}}$ that $pq=q=q^*=qp$. Since such projections q span $p{\mathcal {M}}$ in WOT, we have $px=pxp$ for any $x \in {\mathcal {M}}$, and $px^*=px^*p$ as well. Thus we get $px=xp$, i.e., p is central. $\square$

4.2 t-2 colorability compared with bipartiteness

Definition 4.10

([3]). Let $t \in \{loc, q, qa, qc, C^*, alg\}$ and $c \in {\mathbb {Z}}_{>0}$. A quantum graph ${\mathcal {G}}$ is t-c colorable if there exists a t-homomorphism ${\mathcal {G}} \rightarrow K_c$, which is called a t-c coloring of ${\mathcal {G}}$. The t-chromatic number of ${\mathcal {G}}$ is defined by $\chi _t({\mathcal {G}})=\inf \{c \in {\mathbb {Z}}_{>0} \vert {\mathcal {G}}: t \text {-} c\text { colorable}\}$.

Note that a t-c coloring need not be a surjective t-homomorphism. Surjectivity means that it uses all the c colors.

Remark 4.11

By the obvious inclusion of the classes of algebras, c-colorability has the following implication: $loc \Rightarrow q \Rightarrow qa \Rightarrow qc \Rightarrow C^* \Rightarrow alg,$ and hence the chromatic numbers satisfy

$$\begin{aligned} \chi _{loc} \ge \chi _q \ge \chi _{qa} \ge \chi _{qc} \ge \chi _{C^*} \ge \chi _{alg}. \end{aligned}$$

Proposition 4.12

Let ${\mathcal {G}}=(B,\psi ,A)$ be an alg-2 colorable real quantum graph. Then ${\mathcal {G}}$ has a symmetric spectrum $\mathop {\text {spec}}\nolimits A=-\mathop {\text {spec}}\nolimits A$. Moreover, if it is q-2 colorable, then the symmetry of the spectrum holds with its multiplicity.

Proof

If $A=0$, the statement is trivial. So we may assume $A \ne 0$. Let $(f,{\mathcal {A}}): {\mathcal {G}} \rightarrow K_2 =({\mathbb {C}}^2, \tau , A_{K_2},{\mathcal {S}}_{K_2})$ be an alg-homomorphism. In this case $(f,{\mathcal {A}})$ is automatically surjective, i.e., $f:{\mathbb {C}}^2 \rightarrow B\otimes {\mathcal {A}}$ is injective. Indeed if f is not injective, then we may assume $f(e_1)=1_B \otimes 1_{\mathcal {A}}$ and $f(e_2)=0$ without loss of generality. But this implies for $e_1 e_1^\dagger \in {\mathcal {S}}_{K_2}^\perp$ that $\langle e_1 e_1^\dagger | f^\dagger (A \otimes 1_{\mathcal {A}}) f\rangle _{\mathop {\text {Tr}}\nolimits } =\langle e_1| f^\dagger (A \otimes 1_{\mathcal {A}}) f|e_1\rangle _{\tau } =\langle 1| A |1\rangle _{\psi } 1_{\mathcal {A}} \ne 0$ by Lemma 1.11, which contradicts that $(f,{\mathcal {A}})$ is an alg-homomorphism (Proposition 4.3 (3)).

Now we have nonzero projections $P_j=\lambda (f(e_j)) \in B(L^2({\mathcal {G}})) \otimes {\mathcal {A}}$, where $\lambda$ denotes the left multiplication, satisfying $P_j(A\otimes 1_{\mathcal {A}})P_j=0$ for each $j=1,2$. Then we have

$$\begin{aligned} A\otimes 1_{\mathcal {A}} =P_1(A\otimes 1_{\mathcal {A}})P_2 + P_2(A\otimes 1_{\mathcal {A}})P_1. \end{aligned}$$

and hence

$$\begin{aligned} (A\otimes 1_{\mathcal {A}})(P_1-P_2)&= P_2(A\otimes 1_{\mathcal {A}})P_1 - P_1(A\otimes 1_{\mathcal {A}})P_2 \\&= (P_2-P_1)(A\otimes 1_{\mathcal {A}}), \\ ((\alpha \,\textrm{id}+A)\otimes 1_{\mathcal {A}})(P_1-P_2)&=(P_1-P_2)((\alpha \,\textrm{id}- A)\otimes 1_{\mathcal {A}}) \end{aligned}$$

It follows for $\alpha \in \mathop {\text {spec}}\nolimits A$ and $v \in \ker (\alpha \,\textrm{id}_B -A)$ that $(P_1-P_2)v \in \ker (\alpha \,\textrm{id}_B +A) \otimes {\mathcal {A}}$. Indeed v satisfies

$$\begin{aligned} ((\alpha \,\textrm{id}+A)\otimes 1_{\mathcal {A}})(P_1-P_2)v&= (P_1-P_2)((\alpha \,\textrm{id}- A)\otimes 1_{\mathcal {A}})v=0. \end{aligned}$$

For a generalized eigenvector $v \in \ker (\alpha \,\textrm{id}_B -A)^k$ for some positive integer k, we similarly have $(P_1-P_2)v \in \ker (\alpha \,\textrm{id}_B +A)^k \otimes {\mathcal {A}}$ by

$$\begin{aligned} ((\alpha \,\textrm{id}+A)^k\otimes 1_{\mathcal {A}})(P_1-P_2)v&= (P_1-P_2)((\alpha \,\textrm{id}- A)^k\otimes 1_{\mathcal {A}})v=0. \end{aligned}$$

Therefore $-\alpha \in \mathop {\text {spec}}\nolimits A$, i.e., ${\mathcal {G}}$ has a symmetric spectrum.

If $(f,{\mathcal {A}})$ is a q-2 coloring, then ${\mathcal {A}}\subset M_n=B({\mathbb {C}}^n)$ for some positive integer n. Thus $P_1-P_2$ restricts to linear isomorphisms between generalized eigenspaces $\ker (\alpha \,\textrm{id}_B -A)^{\dim B} \otimes {\mathbb {C}}^n \cong \ker (\alpha \,\textrm{id}_B +A)^{\dim B} \otimes {\mathbb {C}}^n$, hence the multiplicities coincide as $\dim \ker (\alpha \,\textrm{id}_B -A)^{\dim B} =\dim \ker (\alpha \,\textrm{id}_B +A)^{\dim B}$. $\square$

Theorem 4.13

Let ${\mathcal {G}}=(B,\psi ,A)$ be a real tracial quantum graph. Then ${\mathcal {G}}$ is bipartite if and only if it is loc-2 colorable.

Proof

By Theorem 4.9, the existence of a graph homomorphism ${\mathcal {G}} \rightarrow K_2$ is equivalent to the existence of a loc-homomorphism ${\mathcal {G}} \rightarrow K_2$ because these are tracial real quantum graphs and the classical $K_2$ is Schur central. Thus ${\mathcal {G}}$ is bipartite if and only if it is loc-2 colorable. $\square$

Corollary 4.14

Let ${\mathcal {G}}=(B,\psi ,A)$ be a connected d-regular undirected tracial quantum graph. The following are equivalent:

(1):

${\mathcal {G}}$ is loc-2 colorable;

(2):

${\mathcal {G}}$ is alg-2 colorable;

(3):

${\mathcal {G}}$ has a symmetric spectrum;

(4):

$-d \in \mathop {\text {spec}}\nolimits (A)$. If $d=0$, we require ${\dim B} \ge 2$;

(5):

${\mathcal {G}}$ is bipartite.

In this case, the symmetry of the spectrum in (3) holds with multiplicity.

Proof

$((1)\implies (2))$: Obvious by definition.

$((2)\implies (3))$: The symmetry follows from Proposition 4.12. In particular, if we assume (1), the symmetry holds with multiplicity.

$((3)\implies (4))$: Since ${\mathcal {G}}$ is d-regular, the symmetry of spectrum shows $-d \in \mathop {\text {spec}}\nolimits A$.

$((4)\implies (5))$: This is shown by Theorem 3.8 as we assumed that ${\mathcal {G}}$ is connected.

$((5)\implies (1))$: This is the direct consequence of Theorem 4.13. $\square$