# Graph C*-algebra

In mathematics, a graph C*-algebra is a universal C*-algebra constructed from a directed graph. Graph C*-algebras are direct generalizations of the Cuntz algebras and Cuntz-Krieger algebras, but the class of graph C*-algebras has been shown to also include several other widely studied classes of C*-algebras. As a result, graph C*-algebras provide a common framework for investigating many well-known classes of C*-algebras that were previously studied independently. Among other benefits, this provides a context in which one can formulate theorems that apply simultaneously to all of these subclasses and contain specific results for each subclass as special cases.
Although graph C*-algebras include numerous examples, they provide a class of C*-algebras that are surprisingly amenable to study and much more manageable than general C*-algebras. The graph not only determines the associated C*-algebra by specifying relations for generators, it also provides a useful tool for describing and visualizing properties of the C*-algebra. This visual quality has led to graph C*-algebras being referred to as "operator algebras we can see." Another advantage of graph C*-algebras is that much of their structure and many of their invariants can be readily computed. Using data coming from the graph, one can determine whether the associated C*-algebra has particular properties, describe the lattice of ideals, and compute K-theoretic invariants.

## Graph terminology

The terminology for graphs used by C*-algebraists differs slightly from that used by graph theorists. The term graph is typically taken to mean a directed graph $E=(E^{0},E^{1},r,s)$ consisting of a countable set of vertices $E^{0}$, a countable set of edges $E^{1}$, and maps $r,s:E^{1}\rightarrow E^{0}$ identifying the range and source of each edge, respectively. A vertex $v\in E^{0}$ is called a sink when $s^{-1}(v)=\emptyset$; i.e., there are no edges in $E$ with source $v$. A vertex $v\in E^{0}$ is called an infinite emitter when $s^{-1}(v)$ is infinite; i.e., there are infinitely many edges in $E$ with source $v$. A vertex is called a singular vertex if it is either a sink or an infinite emitter, and a vertex is called a regular vertex if it is not a singular vertex. Note that a vertex $v$ is regular if and only if the number of edges in $E$ with source $v$ is finite and nonzero. A graph is called row-finite if it has no infinite emitters; i.e., if every vertex is either a regular vertex or a sink.
A path is a finite sequence of edges $e_{1}e_{2}\ldots e_{n}$ with $r(e_{i})=s(e_{i+1})$ for all $1\leq i\leq n-1$. An infinite path is a countably infinite sequence of edges $e_{1}e_{2}\ldots$ with $r(e_{i})=s(e_{i+1})$ for all $i\geq 1$. A cycle is a path $e_{1}e_{2}\ldots e_{n}$ with $r(e_{n})=s(e_{1})$, and an exit for a cycle $e_{1}e_{2}\ldots e_{n}$ is an edge $f\in E^{1}$ such that $s(f)=s(e_{i})$ and $f\neq e_{i}$ for some $1\leq i\leq n$. A cycle $e_{1}e_{2}\ldots e_{n}$ is called a simple cycle if $s(e_{i})\neq s(e_{1})$ for all $2\leq i\leq n$.
The following are two important graph conditions that arise in the study of graph C*-algebras.
Condition (L): Every cycle in the graph has an exit.
Condition (K): There is no vertex in the graph that is on exactly one simple cycle. That is, a graph satisfies Condition (K) if and only if each vertex in the graph is either on no cycles or on two or more simple cycles.

## The Cuntz-Krieger Relations and the universal property

A Cuntz-Krieger $E$-family is a collection $\left\{s_{e},p_{v}:e\in E^{1},v\in E^{0}\right\}$ in a C*-algebra such that the elements of $\left\{s_{e}:e\in E^{1}\right\}$ are partial isometries with mutually orthogonal ranges, the elements of $\left\{p_{v}:v\in E^{0}\right\}$ are mutually orthogonal projections, and the following three relations (called the Cuntz-Krieger relations) are satisfied:
* (CK1) $s_{e}^{*}s_{e}=p_{r(e)}$ for all $e\in E^{1}$,
* (CK2) $p_{v}=\sum _{s(e)=v}s_{e}s_{e}^{*}$ whenever $v$ is a regular vertex, and
* (CK3) $s_{e}s_{e}^{*}\leq p_{s(e)}$ for all $e\in E^{1}$.
The graph C*-algebra corresponding to $E$, denoted by $C^{*}(E)$, is defined to be the C*-algebra generated by a Cuntz-Krieger $E$-family that is universal in the sense that whenever $\left\{t_{e},q_{v}:e\in E^{1},v\in E^{0}\right\}$ is a Cuntz-Krieger $E$-family in a C*-algebra $A$ there exists a $*$-homomorphism $\phi :C^{*}(E)\to A$ with $\phi (s_{e})=t_{e}$ for all $e\in E^{1}$ and $\phi (p_{v})=q_{v}$ for all $v\in E^{0}$. Existence of $C^{*}(E)$ for any graph $E$ was established by Kumjian, Pask, and Raeburn. Uniqueness of $C^{*}(E)$ (up to $*$-isomorphism) follows directly from the universal property.

### Edge Direction Convention

It is important to be aware that there are competing conventions regarding the "direction of the edges" in the Cuntz-Krieger relations. Throughout this article, and in the way that the relations are stated above, we use the convention first established in the seminal papers on graph C*-algebras. The alternate convention, which is used in Raeburn's CBMS book on Graph Algebras, interchanges the roles of the range map $r$ and the source map $s$ in the Cuntz-Krieger relations. The effect of this change is that the C*-algebra of a graph for one convention is equal to the C*-algebra of the graph with the edges reversed when using the other convention.

### Row-Finite Graphs

In the Cuntz-Krieger relations, (CK2) is imposed only on regular vertices. Moreover, if $v\in E^{0}$ is a regular vertex, then (CK2) implies that (CK3) holds at $v$. Furthermore, if $v\in E^{0}$ is a sink, then (CK3) vacuously holds at $v$. Thus, if $E$ is a row-finite graph, the relation (CK3) is superfluous and a collection $\left\{s_{e},p_{v}:e\in E^{1},v\in E^{0}\right\}$ of partial isometries with mutually orthogonal ranges and mutually orthogonal projections is a Cuntz-Krieger $E$-family if and only if the relation in (CK1) holds at all edges in $E$ and the relation in (CK2) holds at all vertices in $E$ that are not sinks. The fact that the Cuntz-Krieger relations take a simpler form for row-finite graphs has technical consequences for many results in the subject. Not only are results easier to prove in the row-finite case, but also the statements of theorems are simplified when describing C*-algebras of row-finite graphs. Historically, much of the early work on graph C*-algebras was done exclusively in the row-finite case. Even in modern work, where infinite emitters are allowed and C*-algebras of general graphs are considered, it is common to state the row-finite case of a theorem separately or as a corollary, since results are often more intuitive and transparent in this situation.

## Examples

The graph C*-algebra has been computed for many graphs. Conversely, for certain classes of C*-algebras it has been shown how to construct a graph whose C*-algebra is $*$-isomorphic or Morita equivalent to a given C*-algebra of that class.
The following table shows a number of directed graphs and their C*-algebras. We use the convention that a double arrow drawn from one vertex to another and labeled $\infty$ indicates that there are a countably infinite number of edges from the first vertex to the second.
| Directed Graph $E$ | Graph C*-algebra $C^{*}(E)$ |
| $\bullet$ | $\mathbb {C}$, the complex numbers |
| | $C(\mathbb {T} )$, the complex-valued continuous functions on the circle $\mathbb {T}$ |
| $v_{1}\longrightarrow v_{2}\longrightarrow \cdots \longrightarrow v_{n-1}\longrightarrow v_{n}$ | $M_{n}(\mathbb {C} )$, the $n\times n$ matrices with entries in $\mathbb {C}$ |
| $\bullet \longrightarrow \bullet \longrightarrow \bullet \longrightarrow \cdots$ | ${\mathcal {K}}$, the compact operators on a separable infinite-dimensional Hilbert space |
| | $M_{n}(C(\mathbb {T} ))$, the $n\times n$ matrices with entries in $C(\mathbb {T} )$ |
| | ${\mathcal {O}}_{n}$, the Cuntz algebra generated by $n$ isometries |
| | ${\mathcal {O}}_{\infty }$, the Cuntz algebra generated by a countably infinite number of isometries |
| | ${\mathcal {K}}^{1}$, the unitization of the algebra of compact operators ${\mathcal {K}}$ |
| | ${\mathcal {T}}$, the Toeplitz algebra |
The class of graph C*-algebras has been shown to contain various classes of C*-algebras. The C*-algebras in each of the following classes may be realized as graph C*-algebras up to $*$-isomorphism:
* Cuntz algebras
* Cuntz-Krieger algebras
* finite-dimensional C*-algebras
* stable AF algebras
The C*-algebras in each of the following classes may be realized as graph C*-algebras up to Morita equivalence:
* AF algebras
* Kirchberg algebras with free K$_1$-group

## Correspondence between graph and C*-algebraic properties

One remarkable aspect of graph C*-algebras is that the graph $E$ not only describes the relations for the generators of $C^{*}(E)$, but also various graph-theoretic properties of $E$ can be shown to be equivalent to C*-algebraic properties of $C^{*}(E)$. Indeed, much of the study of graph C*-algebras is concerned with developing a lexicon for the correspondence between these properties, and establishing theorems of the form "The graph $E$ has a certain graph-theoretic property if and only if the C*-algebra $C^{*}(E)$ has a corresponding C*-algebraic property." The following table provides a short list of some of the more well-known equivalences.
| Property of $E$ | Property of $C^{*}(E)$ |
| $E$ is a finite graph and contains no cycles. | $C^{*}(E)$ is finite-dimensional. |
| The vertex set $E^{0}$ is finite. | $C^{*}(E)$ is unital (i.e., $C^{*}(E)$ contains a multiplicative identity). |
| $E$ has no cycles. | $C^{*}(E)$ is an AF algebra. |
| $E$ satisfies the following three properties: Condition (L), for each vertex $v$ and each infinite path $\alpha$ there exists a directed path from $v$ to a vertex on $\alpha$, and for each vertex $v$ and each singular vertex $w$ there exists a directed path from $v$ to $w$ | $C^{*}(E)$ is simple. |
| $E$ satisfies the following three properties: Condition (L), for each vertex $v$ in $E$ there is a path from $v$ to a cycle. | Every hereditary subalgebra of $C^{*}(E)$ contains an infinite projection. (When $C^{*}(E)$ is simple this is equivalent to $C^{*}(E)$ being purely infinite.) |

## The gauge action

The universal property produces a natural action of the circle group $\mathbb {T} :=\{z\in \mathbb {C} :|z|=1\}$ on $C^{*}(E)$ as follows: If $\left\{s_{e},p_{v}:e\in E^{1},v\in E^{0}\right\}$ is a universal Cuntz-Krieger $E$-family, then for any unimodular complex number $z\in \mathbb {T}$, the collection $\left\{zs_{e},p_{v}:e\in E^{1},v\in E^{0}\right\}$ is a Cuntz-Krieger $E$-family, and the universal property of $C^{*}(E)$ implies there exists a $*$-homomorphism $\gamma _{z}:C^{*}(E)\to C^{*}(E)$ with $\gamma _{z}(s_{e})=zs_{e}$ for all $e\in E^{1}$ and $\gamma _{z}(p_{v})=p_{v}$ for all $v\in E^{0}$. For each $z\in \mathbb {T}$ the $*$-homomorphism $\gamma _{\overline {z}}$ is an inverse for $\gamma _{z}$, and thus $\gamma _{z}$ is an automorphism. This yields a strongly continuous action $\gamma :\mathbb {T} \to \operatorname {Aut} C^{*}(E)$ by defining $\gamma (z):=\gamma _{z}$. The gauge action $\gamma$ is sometimes called the canonical gauge action on $C^{*}(E)$. It is important to note that the canonical gauge action depends on the choice of the generating Cuntz-Krieger $E$-family $\left\{s_{e},p_{v}:e\in E^{1},v\in E^{0}\right\}$. The canonical gauge action is a fundamental tool in the study of $C^{*}(E)$. It appears in statements of theorems, and it is also used behind the scenes as a technical device in proofs.

## The uniqueness theorems

There are two well-known uniqueness theorems for graph C*-algebras: the gauge-invariant uniqueness theorem and the Cuntz-Krieger uniqueness theorem. The uniqueness theorems are fundamental results in the study of graph C*-algebras, and they serve as cornerstones of the theory. Each provides sufficient conditions for a $*$-homomorphism from $C^{*}(E)$ into a C*-algebra to be injective. Consequently, the uniqueness theorems can be used to determine when a C*-algebra generated by a Cuntz-Krieger $E$-family is isomorphic to $C^{*}(E)$; in particular, if $A$ is a C*-algebra generated by a Cuntz-Krieger $E$-family, the universal property of $C^{*}(E)$ produces a surjective $*$-homomorphism $\phi :C^{*}(E)\to A$, and the uniqueness theorems each give conditions under which $\phi$ is injective, and hence an isomorphism. Formal statements of the uniqueness theorems are as follows:
The Gauge-Invariant Uniqueness Theorem: Let $E$ be a graph, and let $C^{*}(E)$ be the associated graph C*-algebra. If $A$ is a C*-algebra and $\phi :C^{*}(E)\to A$ is a $*$-homomorphism satisfying the following two conditions:
* there exists a gauge action $\beta :\mathbb {T} \to \operatorname {Aut} A$ such that $\phi \circ \beta _{z}=\gamma _{z}\circ \phi$ for all $z\in \mathbb {T}$, where $\gamma$ denotes the canonical gauge action on $C^{*}(E)$, and
* $\phi (p_{v})\neq 0$ for all $v\in E^{0}$,
then $\phi$ is injective.
The Cuntz-Krieger Uniqueness Theorem: Let $E$ be a graph satisfying Condition (L), and let $C^{*}(E)$ be the associated graph C*-algebra. If $A$ is a C*-algebra and $\phi :C^{*}(E)\to A$ is a $*$-homomorphism with $\phi (p_{v})\neq 0$ for all $v\in E^{0}$, then $\phi$ is injective.
The gauge-invariant uniqueness theorem implies that if $\left\{s_{e},p_{v}:e\in E^{1},v\in E^{0}\right\}$ is a Cuntz-Krieger $E$-family with nonzero projections and there exists a gauge action $\beta$ with $\beta _{z}(p_{v})=p_{v}$ and $\beta _{z}(s_{e})=zs_{e}$ for all $v\in E^{0}$, $e\in E^{1}$, and $z\in \mathbb {T}$, then $\{s_{e},p_{v}:e\in E^{1},v\in E^{0}\}$ generates a C*-algebra isomorphic to $C^{*}(E)$. The Cuntz-Krieger uniqueness theorem shows that when the graph satisfies Condition (L) the existence of the gauge action is unnecessary; if a graph $E$ satisfies Condition (L), then any Cuntz-Krieger $E$-family with nonzero projections generates a C*-algebra isomorphic to $C^{*}(E)$.

## Ideal structure

The ideal structure of $C^{*}(E)$ can be determined from $E$. A subset of vertices $H\subseteq E^{0}$ is called hereditary if for all $e\in E^{1}$, $s(e)\in H$ implies $r(e)\in H$. A hereditary subset $H$ is called saturated if whenever $v$ is a regular vertex with $\{r(e):e\in E^{0},s(e)=v\}\subseteq H$, then $v\in H$. The saturated hereditary subsets of $E$ are partially ordered by inclusion, and they form a lattice with meet $H_{1}\wedge H_{2}:=H_{1}\cap H_{2}$ and join $H_{1}\vee H_{2}$ defined to be the smallest saturated hereditary subset containing $H_{1}\cup H_{2}$.
If $H$ is a saturated hereditary subset, $I_{H}$ is defined to be closed two-sided ideal in $C^{*}(E)$ generated by $\{p_{v}:v\in H\}$. A closed two-sided ideal $I$ of $C^{*}(E)$ is called gauge invariant if $\gamma _{z}(a)\in C^{*}(E)$ for all $a\in I$ and $z\in \mathbb {T}$. The gauge-invariant ideals are partially ordered by inclusion and form a lattice with meet $I_{1}\wedge I_{2}:=I_{1}\cap I_{2}$ and joint $I_{1}\vee I_{2}$ defined to be the ideal generated by $I_{1}\cup I_{2}$. For any saturated hereditary subset $H$, the ideal $I_{H}$ is gauge invariant.
The following theorem shows that gauge-invariant ideals correspond to saturated hereditary subsets.
Theorem: Let $E$ be a row-finite graph. Then the following hold:
* The function $H\mapsto I_{H}$ is a lattice isomorphism from the lattice of saturated hereditary subsets of $E$ onto the lattice of gauge-invariant ideals of $C^{*}(E)$ with inverse given by $I\mapsto \left\{v\in E^{0}:p_{v}\in I\right\}$.
* For any saturated hereditary subset $H$, the quotient $C^{*}(E)/I_{H}$ is $*$-isomorphic to $C^{*}(E\setminus H)$, where $E\setminus H$ is the subgraph of $E$ with vertex set $(E\setminus H)^{0}:=E^{0}\setminus H$ and edge set $(E\setminus H)^{1}:=E^{1}\setminus r^{-1}(H)$.
* For any saturated hereditary subset $H$, the ideal $I_{H}$ is Morita equivalent to $C^{*}(E_{H})$, where $E_{H}$ is the subgraph of $E$ with vertex set $E_{H}^{0}:=H$ and edge set $E_{H}^{1}:=s^{-1}(H)$.
* If $E$ satisfies Condition (K), then every ideal of $C^{*}(E)$ is gauge invariant, and the ideals of $C^{*}(E)$ are in one-to-one correspondence with the saturated hereditary subsets of $E$.

## Desingularization

The Drinen-Tomforde Desingularization, often simply called desingularization, is a technique used to extend results for C*-algebras of row-finite graphs to C*-algebras of countable graphs. If $E$ is a graph, a desingularization of $E$ is a row-finite graph $F$ such that $C^{*}(E)$ is Morita equivalent to $C^{*}(F)$. Drinen and Tomforde described a method for constructing a desingularization from any countable graph: If $E$ is a countable graph, then for each vertex $v_{0}$ that emits an infinite number of edges, one first chooses a listing of the outgoing edges as $s^{-1}(v_{0})=\{e_{0},e_{1},e_{2},\ldots \}$, one next attaches a tail of the form
to $E$ at $v_{0}$, and finally one erases the edges $e_{0},e_{1},e_{2},\ldots$ from the graph and redistributes each along the tail by drawing a new edge $f_{i}$ from $v_{i}$ to $r(e_{i})$ for each $i=0,1,2,\ldots$.
Here are some examples of this construction. For the first example, note that if $E$ is the graph
then a desingularization $F$ is given by the graph
For the second example, suppose $E$ is the ${\mathcal {O}}_{\infty }$ graph with one vertex and a countably infinite number of edges (each beginning and ending at this vertex). Then a desingularization $F$ is given by the graph
Desingularization has become a standard tool in the theory of graph C*-algebras, and it can simplify proofs of results by allowing one to first prove the result in the (typically much easier) row-finite case, and then extend the result to countable graphs via desingularization, often with little additional effort.
The technique of desingularization may not work for graphs containing a vertex that emits an uncountable number of edges. However, in the study of C*-algebras it is common to restrict attention to separable C*-algebras. Since a graph C*-algebra $C^{*}(E)$ is separable precisely when the graph $E$ is countable, much of the theory of graph C*-algebras has focused on countable graphs.

## K-theory

The K-groups of a graph C*-algebra may be computed entirely in terms of information coming from the graph. If $E$ is a row-finite graph, the vertex matrix of $E$ is the $E^{0}\!\times \!E^{0}$ matrix $A_{E}$ with entry $A_{E}(v,w)$ defined to be the number of edges in $E$ from $v$ to $w$. Since $E$ is row-finite, $A_{E}$ has entries in $\mathbb {N} \cup \{0\}$ and each row of $A_{E}$ has only finitely many nonzero entries. (In fact, this is where the term "row-finite" comes from.) Consequently, each column of the transpose $A_{E}^{t}$ contains only finitely many nonzero entries, and we obtain a map A$_E$$^t$:⨁$_{E0}$Z→⨁$_{E0}$Z{\textstyle A_{E}^{t}:\bigoplus _{E^{0}}\mathbb {Z} \to \bigoplus _{E^{0}}\mathbb {Z} } given by left multiplication. Likewise, if $I$ denotes the $E^{0}\!\times \!E^{0}$ identity matrix, then I−A$_E$$^t$:⨁$_{E0}$Z→⨁$_{E0}$Z{\textstyle I-A_{E}^{t}:\bigoplus _{E^{0}}\mathbb {Z} \to \bigoplus _{E^{0}}\mathbb {Z} } provides a map given by left multiplication.
Theorem: Let $E$ be a row-finite graph with no sinks, and let $A_{E}$ denote the vertex matrix of $E$. Then $I-A_{E}^{t}:\bigoplus _{E^{0}}\mathbb {Z} \to \bigoplus _{E^{0}}\mathbb {Z}$ gives a well-defined map by left multiplication. Furthermore, $K_{0}(C^{*}(E))\cong \operatorname {coker} (I-A_{E}^{t})\quad {\text{ and }}\quad K_{1}(C^{*}(E))\cong \ker(I-A_{E}^{t}).$
In addition, if $C^{*}(E)$ is unital (or, equivalently, $E^{0}$ is finite), then the isomorphism $K_{0}(C^{*}(E))\cong \operatorname {coker} (I-A_{E}^{t})$ takes the class of the unit in $K_{0}(C^{*}(E))$ to the class of the vector $(1,1,\ldots ,1)$ in $\operatorname {coker} (I-A_{E}^{t})$.
Since $K_{1}(C^{*}(E))$ is isomorphic to a subgroup of the free group ⨁$_{E0}$Z{\textstyle \bigoplus _{E^{0}}\mathbb {Z} }, we may conclude that $K_{1}(C^{*}(E))$ is a free group. It can be shown that in the general case (i.e., when $E$ is allowed to contain sinks or infinite emitters) that $K_{1}(C^{*}(E))$ remains a free group. This allows one to produce examples of C*-algebras that are not graph C*-algebras: Any C*-algebra with a non-free K$_1$-group is not Morita equivalent (and hence not isomorphic) to a graph C*-algebra.