text:
# Untitled Document

A Functorial Approach to the $`C^{}`$-algebras of a Graph

1991 Mathematics Subject Classification. Primary 46L55

Jack Spielberg

Department of Mathematics

Arizona State University

Tempe, AZ 85287-1804

jss@math.la.asu.edu

Abstract.

A functor from the category of directed trees with inclusions to the category of commutative $`C^{}`$-algebras with injective $``$-homomorphisms is constructed. This is used to define a functor from the category of directed graphs with inclusions to the category of $`C^{}`$-algebras with injective $``$-homomorphisms. The resulting $`C^{}`$-algebras are identified as Toeplitz graph algebras. Graph algebras are proved to have inductive limit decompositions over any family of subgraphs with union equal to the whole graph. The construction is used to prove various structural properties of graph algebras.

Introduction.

Since the paper of Cuntz and Krieger in 1976, much work has gone into elucidating the brief remarks made there regarding the case of infinite $`01`$ matrices. While perhaps the most far-reaching solution put forward has been a direct generalization to infinite $`01`$ matrices (), most of the papers on the subject generalize to a class of infinite directed graphs. (In fact, this is the direction indicated in .) In this paper we propose a new method of accomplishing this generalization to infinite graphs, based on a construction of a boundary for an arbitrary directed tree. For a locally finite tree, (or more generally, a directed tree in which each vertex emits finitely many edges), the obvious space of (directed) ends serves as a boundary. Without the finiteness condition, however, the space of ends is not locally compact. This difficulty has been solved in certain cases by ad-hoc methods (e.g., ). More recently these difficulties have been overcome more generally, though again by ad-hoc methods (). Our approach is to give a natural solution in the form of a functor from the category of directed trees (with inclusion) to the category of commutative $`C^{}`$-algebras (with injective $``$-homomorphisms). In the case of a locally finite tree, this functor yields the algebra of continuous functions vanishing at infinity on the space of ends. Given a directed graph, the (combinatorial) universal cover is a bundle of directed trees, on which acts the (combinatorial) fundamental groupoid. Applying our boundary functor, we may let the groupoid act on the resulting $`C^{}`$-algebra. We prove that this yields the same graph algebra (up to strong Morita equivalence) as has been defined by others. The chief virtue of our approach seems to us to be its naturality. We obtain a morphism of graph algebras from an inclusion of directed graphs. This leads us to introduce a family of Toeplitz graph algebras associated to a directed graph. We immediately obtain an inductive limit decomposition of a graph algebra over any directed family of subgraphs. We use this theorem in  to establish semiprojectivity for classifiable simple purely infinite $`C^{}`$-algebras having finitely generated $`K`$-theory and torsion-free $`K_1`$. Moreover, we mention that all of the structure of the graph algebras is obtained without any restrictions on the size or structure of the graph. (A different method for obtaining the direct limit decomposition over the finite subgraphs is given in .)

The outline of the paper is as follows. We finish the introduction with the basic notation we will use. We find it convenient to separate the graphical properties of an edge from the groupoid properties. Thus we adopt the terminology of origin and terminus, as in , leaving source and range exclusively as groupoid terms. In section 1 we introduce our boundary functor for directed trees. We include a classification of the open subsets of the boundary, as this is needed to classify the ideals in the graph algebras. In section 2 we construct the groupoids and $`C^{}`$-algebras obtained from a directed graph by following the above approach. We prove the standard presentation by generators and relations, and define the fundamental cocycle. This allows us to exhibit the AF core as the $`C^{}`$-algebra of an equivalence relation, and prove nuclearity for all graph algebras. We also prove the inductive limit decomposition described above. In section 3 we prove the basic structure theorems regarding simplicity and pure infiniteness. These properties follow quite easily from the theorems already established.

The idea of using a Boolean ring of subsets of the vertices of a(n undirected) tree in order to define its boundary was discovered jointly with Marcelo Laca, when the author was visiting the Mathematics Department at the University of Newcastle. He wishes to thank the members of the Department, and Marcelo Laca and Iain Raeburn in particular, for their wonderful generosity and hospitality during that stay.

Following  we let a graph, $`E`$, consist of a set $`E^0`$ of vertices, a set $`E^1`$ of edges, maps $`o`$, $`t:E^1E^0`$ (origin and terminus), and a map $`e\overline{e}`$ on $`E^1`$ (reversal), satisfying:

$$\begin{array}{cc}\hfill \overline{\overline{e}}& =e\hfill \\ \hfill \overline{e}& e\hfill \\ \hfill o(\overline{e})& =t(e).\hfill \end{array}$$

A directed graph consists of a graph $`E`$ together with a subset $`E_+^1E^1`$ containing exactly one edge from each pair $`\{e,\overline{e}\}`$. (When drawing $`E`$ it is usual to give only one segment to represent $`\{e,\overline{e}\}`$. If $`E`$ is directed, the segment representing $`\{e,\overline{e}\}`$ is given an arrowhead pointing toward $`t(|e|)`$, where $`|e|`$ is the element of $`\{e,\overline{e}\}E_+^1`$.) A path in $`E`$ is a (finite or infinite) sequence of edges $`e_1e_2\mathrm{}`$ such that $`t(e_{i1})=o(e_i)`$ and $`e_i\overline{e_{i1}}`$ for all $`i>1`$. We write $`o(e_1e_2\mathrm{})=o(e_1)`$, $`t(e_1\mathrm{}e_n)=t(e_n)`$, and $`\overline{e_1\mathrm{}e_n}=\overline{e_n}\mathrm{}\overline{e_1}`$. If $`p`$ is a path in $`E`$ we let $`\mathrm{}(p)`$ denote the length of $`p`$ ($`0\mathrm{}(p)\mathrm{}`$). If $`E`$ is a directed graph we call a path $`e_1e_2\mathrm{}`$ directed if $`e_iE_+^1`$ for all $`i`$. (A path of length zero consists of a single vertex, and is considered to be directed.) We let $`E^n`$ (respectively $`E_+^n`$) denote the paths (respectively directed paths) of length $`n`$, for $`0n\mathrm{}`$, $`E^{}=_{0n<\mathrm{}}E^n`$, $`E_+^{}=_{0n<\mathrm{}}E_+^n`$, and $`E^{}=E^{}E^{\mathrm{}}`$, $`E_+^{}=E_+^{}E_+^{\mathrm{}}`$. The graph $`E`$ is a tree if for all $`u,vE^0`$ there exists a unique path $`pE^{}`$ with $`o(p)=u`$ and $`t(p)=v`$. A graph is a forest if it is a disjoint union of trees. More precisely, the graph $`E`$ is a forest if for all $`u,vE^0`$ there exists at most one path $`pE^{}`$ with $`o(p)=u`$ and $`t(p)=v`$.

Let $`E`$ be a directed graph. For $`vE^0`$ let

$$\begin{array}{ccc}\hfill V(v)V_E(v)& =\left\{t(p)\right|pE_+^{},o(p)=v\},\hfill & \\ \hfill \mathrm{\Delta }_1(v)\mathrm{\Delta }_{1,E}(v)& =\left\{eE_+^1\right|o(e)=v\}\hfill & \\ \hfill \mathrm{\Omega }\mathrm{\Omega }(E)& =\left\{uE^0\right|\mathrm{\Delta }_1(u)=\mathrm{}\}\hfill & \\ \hfill \mathrm{\Sigma }\mathrm{\Sigma }(E)& =\left\{uE^0\right|0<\mathrm{\#}\mathrm{\Delta }_1(u)<\mathrm{}\},\hfill & \\ \multicolumn{3}{c}{\text{and for }F\mathrm{\Delta }_1(v)\text{ a finite subset,}}\\ \hfill V(v;F)V_E(v;F)& =\{v\}\underset{e\mathrm{\Delta }_1(v)F}{}V\left(t(e)\right).\hfill & \end{array}$$

Thus $`V(v)`$ is the set of vertices that can be found by following a finite directed path from $`v`$, $`V(v;F)`$ is the set of vertices that can be found by following a directed path from $`v`$ that does not begin with an edge from the finite set $`F`$, and $`\mathrm{\Omega }`$ is the set of vertices often termed sinks. If $`e\mathrm{\Delta }_1(v)`$, we will also write $`V(v;e)`$ for $`V(v;\{e\})`$. We will also use the following notations for paths, respectively directed paths, ending at a sink:

$$\begin{array}{cc}\hfill \mathrm{\Omega }^{}& =t^1(\mathrm{\Omega })E^{}\hfill \\ \hfill \mathrm{\Omega }_+^{}& =\mathrm{\Omega }^{}E_+^{}.\hfill \end{array}$$

1. The Boundary of a Directed Tree.

Remark 1.1. Suppose that $`T`$ is a directed tree, and $`vT^0`$. If $`e`$, $`f\mathrm{\Delta }_1(v)`$ are distinct, then $`V\left(t(e)\right)V\left(t(f)\right)=\mathrm{}`$. It follows that for a directed tree $`T`$, we may also write

$$V_T(v;F)=V_T(v)\underset{eF}{}V_T\left(t(e)\right).$$

For $`T`$ a directed tree, we define

$$\begin{array}{cc}\hfill (T)& =\left\{V(v;F)\right|vT^0,F\mathrm{\Delta }_1(v)\text{ finite}\}\left\{\mathrm{}\right\},\hfill \\ \hfill 𝒜𝒜(T)& =\{_{i=1}^kB_i|B_1,\mathrm{},B_k\text{ are disjoint},k1\}.\hfill \end{array}$$

Lemma 1.2. If $`B`$, $`C`$, then $`BC`$, $`BC𝒜`$.

Proof. Let $`B=V(u;F)`$, $`C=V(v;G)`$, where $`F=\{f_1,\mathrm{},f_k\}`$, $`G=\{g_1,\mathrm{},g_{\mathrm{}}\}`$. Suppose first that $`u=v`$. Then $`BC=V(u;FG)`$ and $`BC=_{eGF}V\left(t(e)\right)`$; both are in $`𝒜`$ (the second by Remark 1.1).

Now suppose that $`uv`$. We distinguish three cases. case (i): $`vV(u)`$. Let $`e_1\mathrm{}e_n`$ be the (unique directed) path from $`u`$ to $`v`$. If $`e_1F`$, then $`V\left(t(e_1)\right)B=\mathrm{}`$. Since $`CV\left(t(e_1)\right)`$, it follows that $`BC=\mathrm{}`$, $`BC=B`$, and $`CB=C`$. If $`e_1F`$, then $`CV(v)B`$, so $`BC=C`$. Thus $`CB=\mathrm{}`$, and

$$BC=V(u;F\{e_1\})V(t(e_1);e_2)\mathrm{}V(t(e_{n1});e_n)\underset{eG}{}V\left(t(e)\right),$$

a disjoint union of sets from $``$.

case (ii): $`uV(v)`$. This case is analogous to case (i).

case (iii): $`uV(v)`$ and $`vV(u)`$. If $`V(u)V(v)=\mathrm{}`$, then $`BC=\mathrm{}`$ and $`BC=B`$. Otherwise, the path from $`u`$ to $`v`$ has the form $`p\overline{q}`$, where $`p`$, $`qE_+^{}`$. Then $`BC=V\left(t(p)\right)`$, and $`BC=BV\left(t(p)\right)`$, which falls under case (i).

Lemma 1.3. $`𝒜`$ is a (Boolean) ring of sets.

Proof. It is a standard fact that if $``$ is a collection of sets containing $`\mathrm{}`$, $`𝒜`$ is the collection of finite disjoint unions of sets from $``$, and if for any $`B`$, $`C`$ we have $`BC`$, $`BC𝒜`$, then $`𝒜`$ is a ring of sets.

Before continuing, we need some more properties of sets in the ring $`𝒜(T)`$. In the following lemma, the notation $`V(x;y)`$ will mean that $`xT^0`$ and that $`y`$ is a finite subset of $`\mathrm{\Delta }_1(x)`$.

Lemma 1.4. Let $`T`$ be a directed tree.

(i) $`V(u;F)V(v;G)`$ if and only if one of the following two conditions holds:

(a) $`u=v`$ and $`FG`$, or

(b) $`uv`$, and if $`p=e_1e_2\mathrm{}T^{}`$ is the unique path with $`o(p)=v`$ and $`t(p)=u`$, then $`pT_+^{}`$ and $`e_1G`$.

(ii) If $`V(u;F)V(v;G)`$, then $`vV(u;F)u=v`$.

(iii) If $`V(v;G)=_{i=1}^kV(u_i;F_i)`$ is a disjoint union, then

$$\begin{array}{c}\text{ }\text{(a)}u_i=v\text{ for some }i\text{, say }i=1,\text{ }\hfill \\ \text{ }\text{(b)}F_1G,\text{ }\hfill \\ \text{ }\text{(c)}\underset{i=2}{\overset{k}{}}V(u_i;F_i)=\underset{eF_1G}{}V\left(t(e)\right).\text{ }\hfill \end{array}$$

Proof. (i) The if is clear. For the only if, part (a) is clear. Suppose that $`uv`$. Then part (b) follows from the fact that $`uV(v;G)`$. (ii) Let $`p`$ be as in (i). Then $`pT_+^{}`$ by (i). Now $`vV(u;F)\overline{p}T_+^{}u=v`$. (iii) Part (a) follows from (ii). Then part (b) follows from (ia). Finally, for part (c) note that

$$\begin{array}{cc}\hfill \underset{2}{\overset{k}{}}V(u_i;F_i)& =V(v;G)V(v;F_1)\hfill \\ & =\underset{eF_1G}{}V\left(t(e)\right).\text{ }\hfill \end{array}$$

In the next result we charactize Boolean ring homomorphisms from $`𝒜(T)`$.

Lemma 1.5. Let $`\mathrm{\Theta }`$ be a Boolean ring, and for $`uT^0`$ let $`\theta _u\mathrm{\Theta }`$ satisfy

(i) $`e\mathrm{\Delta }_1(v)\theta _{t(e)}\theta _v`$

(ii) $`e_1,e_2\mathrm{\Delta }_1(v)`$ and $`e_1e_2\theta _{t(e_1)}\theta _{t(e_2)}=\mathrm{}`$. Then there exists a unique Boolean ring homomorphism $`\mu :𝒜(T)\mathrm{\Theta }`$ such that $`\mu \left(V(u)\right)`$ $`=\theta _u`$, for $`uT^0`$.

Proof. We claim that the assignment $`V(u;F)\theta _u\{\theta _{t(e)}eF\}`$ is well-defined. First, if $`V(u;F)=V(v;G)`$, then by Lemma 1.4 (i) and (ii) we have $`u=v`$ and $`F=G`$. Suppose inductively that $`\mu (B)=_i\mu (B_i)`$ whenever $`B,B_i`$ and $`B=_iB_i`$ is a disjoint union of fewer than $`n`$ sets, and let $`V(v;G)=_{i=1}^nV(u_i;F_i)`$ be a disjoint union. By Lemma 1.4, possibly after reordering the $`\{u_i\}`$, we have

$$\begin{array}{c}\text{ }u_1=v\text{ }\hfill \\ \text{ }V(v;G)=V(v;F_1)\underset{eF_1G}{}V\left(t(e)\right),\text{ a disjoint union,}\text{ }\hfill \\ \text{ }V\left(t(e)\right)=\left\{V(u_i;F_i)\right|u_iV\left(t(e)\right)\},\text{ for }eF_1G.\text{ }\hfill \end{array}$$

Since $`GF_1`$, we have

$$\theta _v\underset{eG}{}\theta _{t(e)}=\left(\theta _v\underset{eF_1}{}\theta _{t(e)}\right)\underset{fF_1G}{}\theta _{t(f)}.$$

For $`eF_1G`$, $`\mathrm{\#}\{iu_iV_{T_1}\left(t(e)\right)\}<n`$. By the inductive hypothesis, we have for each $`eF_1G`$,

$$\theta _{t(e)}=\underset{u_iV\left(t(e)\right)}{}\mu \left(V(u_i;F_i)\right).$$

Thus

$$\begin{array}{cc}\hfill \mu \left(V(v;G)\right)& =\mu \left(V(v;F_1)\right)\underset{eF_1G}{}\theta _{t(e)}\hfill \\ & =\mu \left(V(v;F_1)\right)\underset{eF_1G}{}\underset{u_iV\left(t(e)\right)}{}\mu \left(V(u_i;F_i)\right)\hfill \\ & =\underset{i=1}{\overset{n}{}}\mu \left(V(u_i;F_i)\right).\hfill \end{array}$$

This shows that $`\mu `$ is well-defined on elements of $``$. It follows that $`\mu `$ is well-defined on $`𝒜`$ by $`\mu (_iB_i)=_i\mu (B_i)`$ for finite disjoint collections $`\{B_i\}`$. By following the proof of Lemma 1.2, it is now easy to see that $`\mu (BC)=\mu (B)\mu (C)`$ and $`\mu (BC)=\mu (B)\mu (C)`$ for any $`B,C`$, and hence for $`B,C𝒜`$. Thus $`\mu `$ is a homomorphism of Boolean rings. Uniqueness follows from the fact that $`𝒜`$ is generated by $`\{V(u)uT^0\}`$.

Remark 1.6. With $`\mu `$ as in Lemma 1.5, $`\mathrm{ker}(\mu )`$ is the set of finite unions of sets of the form $`V(u;F)`$ for which $`\theta _u=_{eF}\theta _{t(e)}`$.

We now let $`AA(T)\mathrm{}^{\mathrm{}}(T^0)`$ be the closed linear span of $`\left\{\chi _B\right|B𝒜\}`$. Then $`A`$ is a commutative $`C^{}`$-algebra, and $`𝒜`$ can be identified with the Boolean ring of projections in $`A`$. We note that there is a bijective correspondence between the $``$-representations of $`A`$ into a $`C^{}`$-algebra $`L`$, and the ring homomorphisms of $`𝒜`$ into the ring of projections in a commutative $`C^{}`$-subalgebra of $`L`$. (The correspondence is obtained as follows: if $`\varphi :AL`$ is a $``$-homomorphism, then define $`\mu :𝒜Proj\left(\varphi (A)\right)`$ by $`\mu (B)=\varphi (\chi _B)`$. Moreover, $`\mathrm{ker}\varphi =\overline{\text{span}}\{\chi _B\mu (B)=0\}`$.) We will identify $`\widehat{A}`$ with the set of $`𝒜`$-ultrafilters: for $`\omega \widehat{A}`$ we have the $`𝒜`$-ultrafilter $`\{B𝒜\omega ,\chi _B=1\}`$. (It is elementary to show that this coincides with the Stone space of $`𝒜`$ (, 5.S).) Of course the fixed $`𝒜`$-ultrafilters correspond to the elements of $`T^0`$: for $`vT^0`$, $`𝒰_v=\{B𝒜vB\}`$. We will characterize the free $`𝒜`$-ultrafilters.

For $`p=e_1e_2\mathrm{}T_+^{\mathrm{}}`$ let $`𝒰_p=\left\{B𝒜\right|V\left(o(e_j)\right)B\text{ for some }j\}`$. It is clear that $`𝒰_p`$ is an $`𝒜`$-filter.

Lemma 1.7. $`𝒰_p`$ is an $`𝒜`$-ultrafilter.

Proof. Let $`B𝒜`$, $`B\mathrm{}`$, $`B𝒰_p`$. Write $`B=_1^kB_i`$ with $`\{B_i\}`$ disjoint. Then $`B_i𝒰_p`$ for each $`i`$. Let $`B_i=V(v_i;F_i)`$, and let $`q_iT^{}`$ be the geodesic from $`v_i`$ to $`p`$ (cf. , 6.3 Lemma 9). Since $`B_i𝒰_p`$, then either $`q_iT_+^{}`$ or the first edge of $`q_i`$ is in $`F_i`$. In either case, it follows that if $`t(q_i)=o(e_{n_i})`$, then $`B_iV\left(t(e_{n_i})\right)=\mathrm{}`$. Let $`n=\mathrm{max}(n_1,\mathrm{},n_k)`$. Then $`V\left(o(e_n)\right)𝒰_p`$ and $`BV\left(o(e_n)\right)=\mathrm{}`$. Hence $`𝒰_p`$ is a maximal $`𝒜`$-filter.

Definition 1.8. (cf. , section 4) If $`p=e_1e_2\mathrm{}`$ and $`q=f_1f_2\mathrm{}T_+^{\mathrm{}}`$ we say that $`pq`$ if there exist $`j`$ and $`k`$ so that $`e_{j+r}=f_{k+r}`$ for $`r0`$.

It is clear that $`pq`$ if and only if $`𝒰_p=𝒰_q`$. We let $`𝒰_{[p]}`$ denote the common $`𝒜`$-ultrafilter corresponding to the infinite paths in $`[p]T_+^{\mathrm{}}/`$.

Lemma 1.9. $`\widehat{A}=T^0(T_+^{\mathrm{}}/)`$.

Proof. Let $`𝒰`$ be a free $`𝒜`$-ultrafilter. Let $`V(v)𝒰`$, for some $`vT^0`$. We claim that there is $`eE_+^1`$ with $`v=o(e)`$ and $`V\left(t(e)\right)𝒰`$. For suppose not. Then for any finite set $`F\mathrm{\Delta }_1(v)`$, $`V(v;F)𝒰`$ (we have used the fact that if a finite union of disjoint sets is contained in an $`𝒜`$-ultrafilter, then one of the sets must be in the $`𝒜`$-ultrafilter). But then $`B𝒰`$ whenever $`B𝒜`$ and $`vB`$. Thus $`𝒰𝒰_v`$, and hence $`𝒰=𝒰_v`$ is a not a free $`𝒜`$-ultrafilter. This establishes the claim. Since $`𝒰\mathrm{}`$ there exists $`vT_0`$ with $`V(v)𝒰`$. Then we may use the claim to find $`p=e_1e_2\mathrm{}T_+^{\mathrm{}}`$ such that $`V\left(t(e_j)\right)𝒰`$ for all $`j`$. Then $`𝒰𝒰_{[p]}`$. Since $`𝒰_{[p]}`$ is an $`𝒜`$-ultrafilter, $`𝒰=𝒰_{[p]}`$.

Remark 1.10. We will extend the definition of the equivalence $``$ from $`T_+^{\mathrm{}}`$ to $`T_+^{\mathrm{}}T_+^{}`$: for $`p`$, $`qT_+^{}`$ we say that $`pq`$ if $`t(p)=t(q)`$. For example, while it is true that $`\mathrm{\Omega }_+^{}/\mathrm{\Omega }`$, it will prove useful to have the classes represented by paths.

We next define the boundary of a directed tree. Our definition coincides with the usual space of ends in the case where $`\mathrm{\Delta }_1(u)`$ is finite for all vertices $`u`$ (that is, in the case of a row-finite tree). Definition 1.11. The boundary of the directed tree $`T`$ is the closure in $`\widehat{A}`$ of the set of equivalence classes of infinite directed paths and finite directed paths ending in $`\mathrm{\Omega }`$:

$$T=\overline{(T_+^{\mathrm{}}\mathrm{\Omega }_+^{})/}.$$

Remark 1.12. For $`B𝒜`$, we will let $`[B]`$ denote the support of $`\chi _B`$ in $`\widehat{A}`$ (that is, the set of $`𝒜`$-ultrafilters containing $`B`$). We will let $`[B]_{}=[B]T`$.

Remark 1.13. For $`vT^0`$, a neighborhood base at $`v`$ in $`\widehat{A}`$ is given by $`\left\{[V(v;F)]\right|F\mathrm{\Delta }_1(v)\text{ finite}\}`$. For $`p=e_1e_2\mathrm{}T_+^{\mathrm{}}`$, a neighborhood base at $`[p]`$ in $`\widehat{A}`$ is given by $`\left\{\left[V\left(o(e_j)\right)\right]\right|j=1,2,\mathrm{}\}`$.

Lemma 1.14. Let $`vT^0`$. Then $`vT`$ iff $`\mathrm{\Delta }_1(v)`$ is infinite or empty.

Proof. If $`\mathrm{\Delta }_1(v)`$ is empty, then $`v\mathrm{\Omega }T`$. If $`\mathrm{\Delta }_1(v)`$ is infinite, then for every finite $`F\mathrm{\Delta }_1(v)`$, there is $`p=e_1e_2\mathrm{}T_+^{\mathrm{}}\mathrm{\Omega }_+^{}`$ with $`e_1F`$. Then $`[p]\left[V(v;F)\right]`$. Hence $`v\overline{(T_+^{\mathrm{}}\mathrm{\Omega }_+^{})/}`$. If $`\mathrm{\Delta }_1(v)`$ is nonempty and finite, then $`\{v\}=V(v;\mathrm{\Delta }_1(v))`$. Hence $`vT`$.

Remark 1.15.$`\mathrm{\Sigma }(T)=A(T)\widehat{}T`$, and is a discrete clopen subset of $`A(T)\widehat{}`$.

Definition 1.16. For $`S\mathrm{\Sigma }`$ we let

$$\begin{array}{cc}\hfill A(T,S)& =A(T)/C_0(S)C_0\left(T(\mathrm{\Sigma }S)\right)\hfill \\ \hfill (T,S)& =A(T,S)\widehat{}S^c.\hfill \end{array}$$

Thus $`A(T,\mathrm{})=A`$ and $`A(T,\mathrm{\Sigma })=C_0(T)`$; $`(T,\mathrm{})=\widehat{A}`$, and $`(T,\mathrm{\Sigma })=T`$.

Lemma 1.17. Let $`S\mathrm{\Sigma }(T)`$, let $`\pi :A(T)A(T,S)`$ be the quotient map, and let $`\theta :𝒜(T)\text{Proj}\left(A(T,S)\right)`$ be the corresponding Boolean ring homomorphism. Then $`\mathrm{ker}\theta `$ equals the collection of finite subsets of $`S`$.

Proof. We have $`\mathrm{\Sigma }(T)𝒜(T)`$ via the singleton sets $`\left\{V(u;\mathrm{\Delta }_1(u))\right|u\mathrm{\Sigma }(T)\}`$. The finite unions of these sets are precisely the elements of $`𝒜(T)`$ sent to $`\mathrm{}`$ by $`\theta `$.

Next we discuss the behavior of the algebras $`A(T,S)`$ under mappings of trees. By a morphism of directed graphs we mean a pair of maps from the set of vertices (edges) of the first graph to the set of vertices (edges) of the second graph that intertwine $`o`$, $`t`$, and $`\overline{()}`$, and map directed edges to directed edges. It is a monomorphism if it is injective on the sets of vertices and edges.

Lemma 1.18. Let $`\alpha :T_1T_2`$ be a monomorphism of directed trees. Then

$$\begin{array}{cc}\hfill V_{T_1}(v;F)& \alpha _{}\left(V_{T_1}(v;F)\right)V_{T_2}(\alpha (v);\alpha (F))\hfill \\ \hfill _iB_i& _i\alpha _{}(B_i)\text{ (}\{B_i\}(T_1)\text{ finite disjoint)}\hfill \end{array}$$

defines a Boolean ring monomorphism $`\alpha _{}:𝒜(T_1)𝒜(T_2)`$.

Proof. We will check the conditions of Lemma 1.5. Let $`e\mathrm{\Delta }_{1,T_1}(v)`$. Then $`\alpha (e)\mathrm{\Delta }_{1,T_2}\left(\alpha (v)\right)`$, so $`V_{T_2}\left(\alpha \left(t(e)\right)\right)V_{T_2}\left(\alpha (v)\right)`$. Now let $`e_1e_2\mathrm{\Delta }_{1,T_1}(v)`$. Since $`\alpha `$ is one-to-one on edges, $`\alpha (e_1)\alpha (e_2)\mathrm{\Delta }_{1,T_2}\left(\alpha (v)\right)`$. Thus, since $`T_2`$ is a tree, $`V_{T_2}\left(t\left(\alpha (e_1)\right)\right)V_{T_2}\left(t\left(\alpha (e_2)\right)\right)=\mathrm{}`$. By Lemma 1.5 there is a Boolean ring homomorphism $`\alpha _{}:𝒜(T_1)𝒜(T_2)`$ such that $`\alpha _{}\left(V_{T_1}(v)\right)=V_{T_2}\left(\alpha (v)\right)`$, for $`vT_1^0`$. Then

$$\begin{array}{cc}\hfill \alpha _{}\left(V_{T_1}(v;F)\right)& =\alpha _{}\left(V_{T_1}(v)\underset{eS}{}V_{T_1}\left(t(e)\right)\right)\hfill \\ & =V_{T_2}\left(\alpha (v)\right)\underset{eS}{}V_{T_2}\left(\alpha \left(t(e)\right)\right)\hfill \\ & =V_{T_2}\left(\alpha (v)\right)\underset{f\alpha (S)}{}V_{T_2}\left(t(f)\right)\hfill \\ & =V_{T_2}(\alpha (v);\alpha (F)).\hfill \end{array}$$

Finally $`\alpha _{}`$ is a monomorphism since $`B`$ nonempty implies $`\alpha _{}(B)`$ nonempty.

Remark 1.19. If $`\alpha :T_1T_2`$ is a monomorphism of directed trees, then the ring monomorphism $`\alpha _{}:𝒜(T_1)𝒜(T_2)`$ induces an injective $``$-homomorphism $`\alpha _{}:A(T_1)A(T_2)`$.

Lemma 1.20. Let $`\alpha :T_1T_2`$ be a monomorphism of directed trees, and let $`S_2\mathrm{\Sigma }(T_2)`$. Let

$$S_1=\left\{v\mathrm{\Sigma }(T_1)\right|\alpha (v)S_2\text{ and }\alpha \left(\mathrm{\Delta }_{1,T_1}(v)\right)=\mathrm{\Delta }_{1,T_2}\left(\alpha (v)\right)\}.$$

Then $`\mathrm{ker}(\pi _2\alpha _{})=C_0(S_1)`$, so that the following diagram commutes, has surjective columns (given by restrictions), and has injective rows:

$$\begin{array}{ccc}A(T_1)& \stackrel{\alpha _{}}{}& A(T_2)\\ \\ & & \pi _2\\ \\ A(T_1,S_1)& & A(T_2,S_2).\end{array}$$

Proof. Let $`\theta :𝒜(T_1)\text{Proj}\left(A(T_2,S_2)\right)`$ be the Boolean ring homomorphism associated to $`\pi _2\alpha _{}`$. Then $`V_{T_1}(v;F)\mathrm{ker}\theta `$ if and only if

$$\theta \left(V_{T_1}(v)\right)=\underset{eF}{}\theta \left(V_{T_1}\left(t(e)\right)\right).$$

Since $`\alpha _{}`$ is a monomorphism, this happens if and only if the characteristic function of $`\left[V(\alpha (v);\alpha (F))\right]`$ is in $`\mathrm{ker}\pi _2`$. By Lemma 1.17, this happens if and only if $`\alpha (v)S_2`$, $`F=\mathrm{\Delta }_{1,T_1}(v)`$, and $`\alpha \left(\mathrm{\Delta }_{1,T_1}(v)\right)=\mathrm{\Delta }_{1,T_2}\left(\alpha (v)\right)`$.

Remark 1.21. If $`\alpha :T_1T_2`$ and $`\beta :T_2T_3`$ are monomorphisms of directed trees, then it is clear that $`\beta _{}\alpha _{}=(\beta \alpha )_{}`$ at the level of Boolean rings, and hence also as $``$-homomorphisms. Let $`S_3\mathrm{\Sigma }(T_3)`$. Applying Lemma 1.20 to $`\beta `$ and $`S_3`$ yields $`S_2\mathrm{\Sigma }(T_2)`$. Applying Lemma 1.20 to $`\alpha `$ and $`S_2`$ yields $`S_1\mathrm{\Sigma }(T_1)`$. It is easily verified that an application of Lemma 1.20 to $`\beta \alpha `$ and $`S_3`$ would give the same subset $`S_1`$ of $`\mathrm{\Sigma }(T_1)`$. Hence the concatenation of commuting squares obtained from Lemma 1.20 gives the commuting square for a composition.

Corollary 1.22. Let $`\pi :A(T_2)C_0(T_2)`$ be the restriction mapping. Then $`\mathrm{ker}(\pi \alpha _{})=C_0(S)`$, where

$$S=\{v\mathrm{\Sigma }(T_1)|\alpha \left(\mathrm{\Delta }_{1,T_1}(v)\right)=\mathrm{\Delta }_{1,T_2}\left(\alpha (v)\right)\}.\text{ }$$

We next characterize the open subsets of the boundary of a directed tree. This will be crucial for determining the ideals in graph $`C^{}`$-algebras later on. We will eventually need the generalizations of these notions to directed graphs. Therefore, we state the definitions now in that generality.

Definition 1.23. Let $`E`$ be a directed graph. An invariant of $`E`$ is a pair $`(N,F)`$ consisting of a subset $`NE^0`$ and a family $`\{F_uuN\}`$, where $`F_u\mathrm{\Delta }_1(u)`$ is a finite set, satisfying the following conditions.

(i) If $`uN`$ and $`\mathrm{\Delta }_1(u)`$ is finite, then $`F_u=\mathrm{}`$.

(ii) Let $`uN`$ and $`e\mathrm{\Delta }_1(u)`$. Then

(a) If $`eF_u`$, then $`t(e)N`$ and $`F_{t(e)}=\mathrm{}`$.

(b) If $`eF_u`$ and $`t(e)N`$, then $`F_{t(e)}\mathrm{}`$.

(iii) Let $`uE^0`$ with $`\mathrm{\Delta }_1(u)`$ finite and nonempty. If $`t\left(\mathrm{\Delta }_1(u)\right)N`$, and $`F_{t(e)}=\mathrm{}`$ for all $`e\mathrm{\Delta }_1(u)`$, then $`uN`$. We let $`(E)`$ denote the set of invariants of $`E`$. We remark that the notions of hereditary and saturated subsets of $`E^0`$ appearing in other work are being replaced by conditions (i) and (ii)(a), respectively (ii)(b) and (iii), in the context of general directed graphs. We define a partial ordering in $``$ by $`(N_1,F_1)(N_2,F_2)`$ if $`N_1N_2`$ and $`F_{1,u}F_{2,u}`$ for each $`uN_1`$. Example 1.24. Let $`E^0=𝐙`$ and let $`E`$ have infinitely many directed edges from $`n`$ to $`n+1`$, for each $`nE^0`$. Then for $`n𝐙`$ we may let $`N=[n,\mathrm{})`$ and $`F_k=\mathrm{}`$ for $`kN`$. These are the only elements of $`(E)`$. We again specialize to directed trees. Definition 1.25. Let $`T`$ be a directed tree. Let $`𝒥𝒥(T)`$ be the set of open subsets of $`T`$. We let $`𝒥`$ be ordered by inclusion. We define maps $`U_{}:𝒥`$ and $`L:𝒥`$ as follows.

$$\begin{array}{cc}\hfill U_{}(N,F)& =\underset{uN}{}\left[V(u;F_u)\right]_{}\hfill \\ & \\ \hfill L(W)& =(N,F)(N(W),F(W)),\hfill \end{array}$$

where

$$\begin{array}{c}\text{ }N=\left\{uT^0\mathrm{\Sigma }(T)\right|F\mathrm{\Delta }_1(u)\text{ finite with }\left[V(u;F)\right]_{}W\}\text{ }\hfill \\ \text{ }\left\{uT^0\right|\left[V(u)\right]_{}W\},\text{ }\hfill \\ \text{ }\hfill \\ \text{ }F_u=\left\{F\mathrm{\Delta }_1(u)\right|\left[V(u;F)\right]_{}W\},uN.\text{ }\hfill \end{array}$$

Lemma 1.26. The above definitions make sense, in that $`U_{}(N,F)𝒥`$ and $`L(W)`$ whenever $`(N,F)`$ and $`W𝒥`$.

Proof. Left to the reader.  Remark 1.27. It is immediate that the maps $`L`$ and $`U_{}`$ are order-preserving.

Theorem 1.28. The maps $`L`$ and $`U_{}`$ are inverses.

Proof. We first show that $`U_{}L`$ is the identity on $`𝒥`$. Let $`W𝒥`$, and let $`L(W)=(N,F)`$. Let $`uN`$. Then $`\left[V(u;F_u)\right]_{}`$ is one of the defining sets of $`U_{}\left(L(W)\right)`$. By the definition of $`L(W)`$ we have $`\left[V(u;F_u)\right]_{}W`$. It follows that $`U_{}\left(L(W)\right)W`$.

For the reverse inclusion, note that since $`W`$ is open, it is a union of basic open sets. Let $`\left[V(u;F)\right]_{}W`$ be one, where $`F`$ is a finite subset of $`\mathrm{\Delta }_1(u)`$. We may assume that $`F`$ is the smallest subset of $`\mathrm{\Delta }_1(u)`$ for which the containment holds. Now, if $`uT`$, then $`uN`$. It follows that $`\left[V(u;F)\right]_{}U_{}\left(L(W)\right)`$. The same argument holds if $`uT`$ but $`uN`$. Finally, we suppose that $`uN`$. Then we must have $`uT`$ and $`\left[V(u)\right]_{}W`$. Then $`\mathrm{\Delta }_1(u)`$ is finite. We have

$$\begin{array}{cc}\hfill W& \left[V(u;F)\right]_{}\hfill \\ & =\underset{e\mathrm{\Delta }_1(u)F}{}\left[V\left(t(e)\right)\right]_{}.\hfill \end{array}$$

Since $`\left[V\left(t(e)\right)\right]_{}W`$ for such $`e`$, we have $`t(e)N`$. Then $`\left[V\left(t(e)\right)\right]_{}U_{}\left(L(W)\right)`$. It now follows that $`\left[V(u;F)\right]_{}U_{}\left(L(W)\right)`$. Therefore $`WU_{}\left(L(W)\right)`$.

We next show that $`LU_{}`$ is the identity on $``$. Let $`(N,F)`$, and let $`L\left(U_{}(N,F)\right)=(M,G)`$. Let $`uN`$. Then $`\left[V(u;F_u)\right]_{}U_{}(N,F)`$, (where $`F_u=\mathrm{}`$ if $`\mathrm{\Delta }_1(u)`$ is finite). Hence $`uM`$, and so $`NM`$. It also follows that $`G_uF_u`$.

We now prove $`NM`$. Let $`w_0T^0`$ and $`w_0N`$. We distinguish two cases. Case (i). There exists $`p_0T_+^{}`$ with $`w_0=o(p_0)`$, $`t(p_0)T`$, and $`t(p_0)N`$. In this case, we claim first that $`\left[t(p_0)\right]U_{}(N,F)`$. For suppose otherwise. Then there is $`uN`$ with

$$\left[t(p_0)\right]\left[V(u;F_u)\right]_{}.$$

But then $`t(p_0)V(u;F_u)N`$, a contradiction. This establishes the claim.

Now, if $`w_0T`$, then letting $`p_0=w_0`$ above we obtain $`w_0U_{}(N,F)`$. Hence $`w_0M`$. On the other hand, if $`\mathrm{\Delta }_1(w_0)`$ is finite and nonempty, the above shows that $`t(p_0)U_{}(N,F)`$, while $`t(p_0)\left[V(w_0)\right]_{}`$. Hence $`\left[V(w_0)\right]_{}U_{}(N,F)`$, so $`w_0M`$. Case (ii). For all $`p_0T_+^{}o^1(w_0)`$, if $`t(p_0)T`$ then $`t(p_0)N`$. In particular, since $`w_0N`$, we have that $`\mathrm{\Delta }_1(w_0)`$ is finite and nonempty. Applying Definition 1.23 (iii) to $`w_0`$, we have two possibilities:

(iia) There is $`w_1V(w_0)\{w_0\}`$ with $`w_1N`$ and $`F_{w_1}\mathrm{}`$, (and hence $`w_1T`$).

(iib) For every $`wV(w_0)\{w_0\}`$ we have $`wNF_w=\mathrm{}`$, and there exists $`w_1V(w_0)\{w_0\}N`$. We will treat case (iib) first. By the assumption of case (ii), we must have $`\mathrm{\Delta }_1(w_1)`$ finite. If $`w_1`$ leads to a vertex in $`TN`$, then so does $`w_0`$, contradicting the assumption of case (ii). By the hypothesis of case (iib), $`w_1`$ must also fall under case (iib). So we obtain $`w_2V(w_1)\{w_1\}N`$. Inductively, we obtain a sequence $`w_0`$, $`w_1`$, $`\mathrm{}`$ in $`T^0N`$ with $`\mathrm{\Delta }_1(w_j)`$ finite for all $`j`$, and a path $`qT_+^{\mathrm{}}o^1(w_0)`$ passing through all of the $`w_j`$.

In case (iia), we have $`w_1V(w_0)\{w_0\}`$ with $`w_1N`$ and $`F_{w_1}\mathrm{}`$. Let $`e_1F_{w_1}`$. If $`t(e_1)N`$, then Definition 1.23 (ii) (b) implies that $`F_{t(e_1)}\mathrm{}`$. Hence if $`eF_{t(e_1)}`$, then $`eF_{o(e)}`$. If $`t(e_1)N`$, then since we are in case (ii) (for $`w_0`$), $`\mathrm{\Delta }_1\left(t(e_1)\right)`$ is finite. We then have case (iia) or (iib) for $`t(e_1)`$. If case (iib) applies, then as before, we may extend from $`t(e_1)`$ an infinite directed path having infinitely many vertices not in $`N`$. If case (iia) applies, then we may extend from $`t(e_1)`$ a finite directed path whose last edge satisfies $`eF_{o(e)}`$, and we repeat this process.

Thus in all cases, either we have extended from $`w_0`$ an infinite directed path having infinitely many vertices not in $`N`$, or we have extended from $`w_0`$ an infinite directed path having infinitely many edges satisfying $`eF_{o(e)}`$.

Let $`q`$ be this path. We claim that $`[q]U_{}(N,F)`$. For if it were, there would be $`uN`$ such that $`[q]\left[V(u;F_u)\right]_{}`$. It then follows that there is a path $`pT^{}o^1(u)`$ such that $`o(p)=w_0`$ and $`q=pf_1f_2\mathrm{}`$ in $`T^{\mathrm{}}`$, where $`f_jT_+^1`$ (there may be some cancellations in the product $`pf_1f_2\mathrm{}`$). Since $`f_1\mathrm{\Delta }_1(u)F_u`$, we have $`V\left(t(f_1)\right)N`$, and $`F_v=\mathrm{}`$ for all $`vV\left(t(f_1)\right)`$, by Definition 1.23 (ii) (a). Since at most finitely many $`f_j`$ can have cancelled, we have contradicted the construction of $`q`$. Therefore $`[q]U_{}(N,F)`$, and hence $`\left[V(w_0)\right]_{}U_{}(N,F)`$. Therefore $`w_0M`$, since $`\mathrm{\Delta }_1(w_0)`$ is finite and nonempty, and we have shown that $`N=M`$.

Finally, we show that $`G=F`$. We already know that $`G_uF_u`$ for all $`uN`$. Suppose that there is $`uN`$ such that $`G_uF_u`$. Let $`e_1F_uG_u`$. Then $`t(e_1)N`$, $`G_{t(e_1)}=\mathrm{}`$, and $`F_{t(e_1)}\mathrm{}`$ (by Definition 1.23 (iii)). We choose $`e_2F_{t(e_1)}`$. Since $`e_2G_{t(e_1)}`$, $`t(e_2)N`$, $`G_{t(e_2)}=\mathrm{}`$, and $`F_{t(e_2)}\mathrm{}`$. Inductively, we obtain $`q=e_1e_2\mathrm{}T_+^{\mathrm{}}`$ such that

$$\begin{array}{cc}\hfill o(q)& =u\hfill \\ \hfill G_{t(e_j)}& =\mathrm{},\text{ for all }j\hfill \\ \hfill e_j& F_{o(e_j)},\text{ for all }j.\hfill \end{array}$$

It is clear that $`[q]U_{}(N,G)`$. In the same way as in the previous proof, it follows that $`[q]U_{}(N,F)`$. But since $`(N,G)=U_{}\left(L\left(U_{}(N,F)\right)\right)`$, it follows from the fact that $`U_{}L=\text{id}_𝒥`$ that $`U_{}(N,G)=U_{}(N,F)`$. This contradiction finishes the proof.

We next show that a closed subset of the boundary of a directed tree corresponds to an algebra as described in Definition 1.16, corresponding to a certain subforest of the tree. Again, since we will need to apply this idea to graphs later, we define it now for directed graphs. Definition 1.29. Let $`E`$ be a directed graph, and let $`(N,F)(E)`$ be an invariant of $`E`$.

(i) $`R(N,F)=\left\{uN\right|F_u\mathrm{}\}`$.

(ii) $`E(N,F)`$ is the subgraph of $`E`$ given by

$`E(N,F)^0=(E^0N)R(N,F)`$

$`E(N,F)_+^1=E_+^1o^1\left(E(N,F)^0\right)t^1\left(E(N,F)^0\right)`$.

(iii) $`S(N,F)=R(N,F)\left\{uE^0N\right|0<\mathrm{\#}\mathrm{\Delta }_1(u)<\mathrm{}\}`$.

Proposition 1.30. Let $`T`$ be a directed tree and let $`(N,F)(T)`$. Then

$$C_0\left(T\right)/C_0\left(U_{}(N,F)\right)A(T(N,F),S(N,F)).$$

Proof. We define open subsets of $`A(T)\widehat{}`$ by

$$\begin{array}{cc}\hfill U(N,F)& =\underset{uN}{}\left[V(u;F_u)\right]\hfill \\ \hfill P(N,F)& =\underset{uNR(N,F)}{}\left[V(u)\right].\hfill \end{array}$$

Thus $`U_{}(N,F)=U(N,F)T`$ and $`U(N,F)=P(N,F)R(N,F)`$.

Next we note that

$$A\left(T(N,F)\right)A(T)/C_0\left(P(N,F)\right).$$

For the map

$$V_T(u)\{\begin{array}{cc}V_{T(N,F)}(u),\hfill & \text{if }uT(N,F)^0\hfill \\ \mathrm{},\hfill & \text{if }uNR(N,F)\hfill \end{array}$$

extends to a Boolean ring homomorphism by Lemma 1.5. Then the kernel of the corresponding $``$-homomorphism of $`A(T)`$ onto $`A\left(T(N,F)\right)`$ is generated by the characteristic functions of $`\left\{\left[V_T(u)\right]\right|uNR(N,F)\}`$. Hence the kernel equals $`C_0\left(P(N,F)\right)`$.

Now,

$$\begin{array}{cc}\hfill \frac{C_0(T)}{C_0\left(U_{}(N,F)\right)}& =\frac{A(T)/C_0\left(\mathrm{\Sigma }(T)\right)}{C_0\left(U(N,F)T\right)}\hfill \\ & =\frac{A(T)/C_0\left(\mathrm{\Sigma }(T)\right)}{C_0\left(U(N,F)\right)/C_0\left(U(N,F)\mathrm{\Sigma }(T)\right)}\hfill \\ & \frac{A(T)}{C_0\left(U(N,F)\mathrm{\Sigma }(T)\right)}\hfill \\ & \frac{A(T)/C_0\left(P(N,F)\right)}{C_0\left(U(N,F)\mathrm{\Sigma }(T)\right)/C_0\left(P(N,F)\right)}.\hfill \end{array}$$

We have already noted that the numerator is $`A\left(T(N,F)\right)`$. As for the denominator, we have

$$\begin{array}{cc}\hfill C_0\left(U(N,F)\mathrm{\Sigma }(T)\right)/C_0\left(P(N,F)\right)& =C_0\left(R(N,F)\mathrm{\Sigma }(T)P(N,F)\right)/C_0\left(P(N,F)\right)\hfill \\ & C_0\left(\left(R(N,F)\mathrm{\Sigma }(T)\right)P(N,F)\right)\hfill \\ & =C_0\left(R(N,F)\left(\mathrm{\Sigma }(T)N\right)\right)\hfill \\ & =C_0\left(R(N,F)\left(\mathrm{\Sigma }(T)T(N,F)^0\right)\right)\hfill \\ & =C_0\left(S(N,F)\right).\hfill \end{array}$$

Hence $`C_0(T)/C_0\left(U_{}(N,F)\right)A(T(N,F),S(N,F))`$.

2. Groupoids and $`C^{}`$-algebras for Directed Graphs.

We now let $`E`$ be a directed graph. The set $`E^{}`$ of (undirected) finite paths has two structures that we will use.

Definition 2.1. We let $`G=G(E)`$ denote the set $`E^{}`$ with the following groupoid structure:

$$\begin{array}{c}\text{ }G^0=E^0\text{ }\hfill \\ \text{ }r(p)=o(p),s(p)=t(p),\text{ and }(e_1\mathrm{}e_n)^1=\overline{e_n}\mathrm{}\overline{e_1},\text{ for }p=e_1\mathrm{}e_nG\text{ }\hfill \\ \text{ }G^{(2)}=\left\{(p,q)G\times G\right|t(p)=o(q)\}\text{ }\hfill \\ \text{ }\text{multiplication is given by concatenation, followed by}\text{ }\hfill \\ \text{ }\text{the removal of pairs of the form }(e,\overline{e})\text{ }\hfill \end{array}$$

Definition 2.2. We let $`\stackrel{~}{E}`$ denote the following graph:

$$\begin{array}{c}\text{ }\stackrel{~}{E}^0=E^{}\text{ }\hfill \\ \text{ }\stackrel{~}{E}^1=\left\{(p,q)E^{}\times E^{}\right|(p^1,q)G^{(2)}\text{ and }p^1qE^1\}\text{ }\hfill \\ \text{ }\stackrel{~}{E}_+^1=\left\{(p,q)\stackrel{~}{E}^1\right|p^1qE_+^1\}\text{ }\hfill \\ \text{ }o(p,q)=p,t(p,q)=q,\overline{(p,q)}=(q,p)\text{ }\hfill \end{array}$$

Definition 2.3. The map $`\lambda :\stackrel{~}{E}^{}E^0`$ is defined by

$$\begin{array}{cc}\hfill \lambda (p)& =o(p),p\stackrel{~}{E}^0=E^{},\hfill \\ \hfill \lambda (\mu )& =\lambda (o(\mu )),\mu \stackrel{~}{E}^n\text{ for }1n\mathrm{}.\hfill \end{array}$$

Lemma 2.4. With $`\lambda `$ as fiber map, $`\stackrel{~}{E}`$ is a bundle of directed trees.

Proof. It is easy to check that $`p`$, $`q\stackrel{~}{E}^0`$ are connected by a path if and only if $`\lambda (p)=\lambda (q)`$, and that in this case the path connecting them is unique.

For $`x\stackrel{~}{E}_+^{\mathrm{}}/`$ we let $`\lambda (x)`$ denote the image under $`\lambda `$ of any representative of $`x`$. The groupoid $`G`$ acts on $`\stackrel{~}{E}`$ in the obvious way: if $`\alpha G`$ and $`p\stackrel{~}{E}^0`$ satisfy $`s(\alpha )=\lambda (p)`$ then $`\alpha p`$ is obtained by multiplication in $`G`$. If $`\alpha G`$ and $`(p,q)\stackrel{~}{E}^1`$ satisfy $`s(\alpha )=\lambda (p,q)`$ then $`\alpha (p,q)=(\alpha p,\alpha q)`$. It is clear that the action of $`G`$ on $`\stackrel{~}{E}`$ preserves the direction.

Definition 2.5. Let $`E`$ be a directed graph. We define $`i:I(E)I(\stackrel{~}{E})`$ as follows. For $`(N,F)I(E)`$, let $`i(N,F)=(\stackrel{~}{N},\stackrel{~}{F})`$, where

$$\begin{array}{cc}\hfill \stackrel{~}{N}& =t^1(N)\hfill \\ \hfill \stackrel{~}{F}_p& =\left\{(p,pe)\right|eF_{t(p)}\}.\hfill \end{array}$$

Remark 2.6. The map $`i`$ is clearly injective and order-preserving.

Lemma 2.7. Let $`E`$ be a directed graph, and let $`(\mathrm{\Lambda },\mathrm{\Phi })I(\stackrel{~}{E})`$. The following are equivalent:

(i) $`(\mathrm{\Lambda },\mathrm{\Phi })i\left(I(E)\right)`$.

(ii) $`U_{}(\mathrm{\Lambda },\mathrm{\Phi })`$ is $`G(E)`$-invariant.

(iii) $`\mathrm{\Lambda }=t^1\left(t(\mathrm{\Lambda })\right)`$, and for $`p\mathrm{\Lambda }`$, $`\mathrm{\Phi }_p=p\mathrm{\Phi }_{t(p)}`$.

Proof. $`\left(\text{(i)}\text{(ii)}\right):`$ Let $`(\mathrm{\Lambda },\mathrm{\Phi })=(\stackrel{~}{N},\stackrel{~}{F})`$ for some $`(N,F)I(E)`$. Note that

$$\stackrel{~}{F}_p=p\left\{(t(p),e)\right|eF_{t(p)}\},$$

(using the action of $`G(E)`$ on $`\stackrel{~}{E}`$), and hence that

$$\left[V_{\stackrel{~}{E}}(p;\stackrel{~}{F}_p)\right]_{}=p\left[V_{\stackrel{~}{E}}(t(p);\stackrel{~}{F}_{t(p)})\right]_{}.$$

Since $`\stackrel{~}{N}`$ is $`G(E)`$-invariant, it follows that $`U_{}(\stackrel{~}{N},\stackrel{~}{F})`$ is $`G(E)`$-invariant. $`\left(\text{(ii)}\text{(iii)}\right):`$ Let $`p\mathrm{\Lambda }`$. Then

$$\left[V_{\stackrel{~}{E}}(p;\mathrm{\Phi }_p)\right]_{}U_{}(\mathrm{\Lambda },\mathrm{\Phi }).$$

If $`t(q)=t(p)`$, then by $`G(E)`$-invariance we have

$$\left[V_{\stackrel{~}{E}}(q;qp^1\mathrm{\Phi }_p)\right]_{}U_{}(\mathrm{\Lambda },\mathrm{\Phi }).$$

By Theorem 1.28 we have

(1) $`q\mathrm{\Lambda }`$,

(2) $`qp^1\mathrm{\Phi }_p\mathrm{\Phi }_q`$.

It follows from (1) that $`\mathrm{\Lambda }=t^1\left(t(\mathrm{\Lambda })\right)`$. It follows from (2) and symmetry that $`p^1\mathrm{\Phi }_p=q^1\mathrm{\Phi }_q`$. In particular, $`p^1\mathrm{\Phi }_p=\mathrm{\Phi }_{t(p)}`$. $`\left(\text{(iii)}\text{(i)}\right):`$ Let $`N=t(\mathrm{\Lambda })`$. Then $`\mathrm{\Lambda }=t^1\left(t(\mathrm{\Lambda })\right)=t^1(N)=\stackrel{~}{N}`$. Since vertices of $`E`$ are paths of length zero, if $`p\mathrm{\Lambda }`$ then $`t\left(t(p)\right)=t(p)\mathrm{\Lambda }`$. Thus $`t(p)t^1\left(t(\mathrm{\Lambda })\right)=\mathrm{\Lambda }`$. Hence $`N\mathrm{\Lambda }`$. For $`uN`$ let

$$F_u=\left\{e\mathrm{\Delta }_{1,E}(u)\right|(u,e)\mathrm{\Phi }_u\}.$$

The conditions that $`(N,F)I(E)`$ follow from those that $`(\mathrm{\Lambda },\mathrm{\Phi })I(\stackrel{~}{E})`$. By hypothesis, then, if $`t(p)=u`$ we have

$$\begin{array}{cc}\hfill \mathrm{\Phi }_p& =p\mathrm{\Phi }_u\hfill \\ & =\left\{(p,pe)\right|eF_u\}\hfill \\ & =\stackrel{~}{F}_p.\hfill \end{array}$$

Thus $`(\mathrm{\Lambda },\mathrm{\Phi })=(\stackrel{~}{N},\stackrel{~}{F})=i(N,F)`$.

Theorem 2.8. Let $`E`$ be a directed graph. The map $`U_{}i`$ is an order-preserving one-to-one correspondence between $`I(E)`$ and the collection of open $`G(E)`$-invariant subsets of $`\stackrel{~}{E}`$.

Proof. This follows from Theorem 1.28 and Lemma 2.7.

We now prepare for the definition of the groupoids of a directed graph.

Definition 2.9. Let $`E`$ be a directed graph, and let $`xA(\stackrel{~}{E})\widehat{}`$. We define a function $`\underset{¯}{}:A(\stackrel{~}{E})\widehat{}E^{}`$ such that $`o(\underset{¯}{x})=\lambda (x)`$ as follows. If $`x\stackrel{~}{E}^0`$, then $`xE^{}`$ and we let $`\underset{¯}{x}=x`$. If $`x\stackrel{~}{E}_+^{\mathrm{}}/`$, then there is a unique $`\omega \stackrel{~}{E}^{\mathrm{}}`$ with $`o(\omega )=\lambda (x)`$ and such that some tail of $`\omega `$ is in (the equivalence class) $`x`$. Then we may write $`\omega `$ as

$$\omega =(p_0,p_1)(p_1,p_2)\mathrm{},$$

where $`p_0=\lambda (x)`$ and for each $`i`$, $`\mathrm{}(p_i)=i`$. We define $`\underset{¯}{x}=(p_0^1p_1)(p_1^1p_2)\mathrm{}E^{\mathrm{}}`$.

Lemma 2.10. The map

$$\underset{¯}{}:A(\stackrel{~}{E})\widehat{}E^{}$$

is one-to-one and has range $`\left\{pE^{}\right|\text{ some tail of }p\text{ is directed}\}`$. For $`(\alpha ,x)GA(\stackrel{~}{E})\widehat{}`$, $`\underset{¯}{\alpha x}=\alpha \underset{¯}{x}`$.

Proof. The map is a bijection from $`\stackrel{~}{E}^0E^{}`$. For $`x\stackrel{~}{E}_+^{\mathrm{}}/`$, if $`\underset{¯}{x}=f_1f_2\mathrm{}`$, then we may construct an infinite path in the equivalence class $`x`$ by letting $`p_i=f_1f_2\mathrm{}f_i`$ (and $`p_0=o(f_1)`$), and setting $`\omega =(p_0,p_1)(p_1,p_2)\mathrm{}`$. This defines a left inverse for the map $`\underset{¯}{}`$, proving it is one-to-one. The description of the range is clearly true. To check the equivariance of the $`G`$-action, let $`(\alpha ,x)GA(\stackrel{~}{E})\widehat{}`$. It is clear that equivariance holds if $`x\stackrel{~}{E}^0`$. So let $`x\stackrel{~}{E}_+^{\mathrm{}}/`$, and let $`\omega =(p_0,p_1)(p_1,p_2)\mathrm{}`$ be as in Definition 2.9. Let $`\alpha =e_1\mathrm{}e_n`$, and suppose that the product $`\alpha \underset{¯}{x}`$ involves $`k`$ cancellations. Then

$$\begin{array}{cc}\hfill \alpha \underset{¯}{x}& =(e_1\mathrm{}e_n)\left(p_1(p_1^1p_2)\mathrm{}\right)\hfill \\ & =e_1\mathrm{}e_{nk}(p_k^1p_{k+1})\mathrm{}.\hfill \end{array}$$

But the unique element of $`\stackrel{~}{E}^{\mathrm{}}`$ with origin equal to $`\lambda (\alpha x)`$ and with a tail representing $`\alpha x`$ is

$$\left((o(e_1),e_1)(e_1,e_1e_2)\mathrm{}(e_1\mathrm{}e_{nk},e_1\mathrm{}e_{nk}(p_k^1p_{k+1}))\mathrm{}\right)$$

Then it is clear that $`\underset{¯}{\alpha x}=\alpha \underset{¯}{x}`$.

Definition 2.11. For $`S\mathrm{\Sigma }(E)`$ we let $`\stackrel{~}{S}=t^1(S)=\{p\stackrel{~}{E}^0t(p)S\}`$.

Remark 2.12. If $`S\mathrm{\Sigma }(E)`$, then $`\stackrel{~}{S}`$ is open and $`G`$-invariant.

Let $`S\mathrm{\Sigma }(E)`$. We define

$$\begin{array}{cc}\hfill A(\stackrel{~}{E},\stackrel{~}{S})& =\underset{vE^0}{}A(\lambda ^1(v),\stackrel{~}{S}\lambda ^1(v))\hfill \\ \hfill (\stackrel{~}{E},\stackrel{~}{S})& =A(\stackrel{~}{E},\stackrel{~}{S})\widehat{}=\underset{vE^0}{}(\lambda ^1(v),\stackrel{~}{S}\lambda ^1(v))\hfill \end{array}$$

where the union is given the inductive topology.

Definition 2.13. Let $`E`$ be a directed graph. Let $`S\mathrm{\Sigma }(E)`$. The transformation groupoid $`G(\stackrel{~}{E},\stackrel{~}{S})`$ (with the relative product topology) is called an extended Toeplitz graph groupoid of $`E`$ (determined by the choice of $`S`$).

We recall the groupoid structure of $`G(\stackrel{~}{E},\stackrel{~}{S})`$:

$$\begin{array}{cc}\hfill \left(G(\stackrel{~}{E},\stackrel{~}{S})\right)^0& =(\stackrel{~}{E},\stackrel{~}{S})\hfill \\ \hfill s(\alpha ,x)& =x\hfill \\ \hfill r(\alpha ,x)& =\alpha x\hfill \\ \hfill (\alpha ,\beta x)(\beta ,x)& =(\alpha \beta ,x)\hfill \\ \hfill (\alpha ,x)^1& =(\alpha ^1,\alpha x).\hfill \end{array}$$

Since $`G`$ is discrete it is clear that $`s`$ and $`r`$ are local homeomorphisms, and hence that $`G(\stackrel{~}{E},\stackrel{~}{S})`$ is $`r`$-discrete. We call the $`C^{}`$-algebra of $`G(\stackrel{~}{E},\stackrel{~}{S})`$ an extended Toeplitz graph algebra.

Lemma 2.14. Let $`S\mathrm{\Sigma }(E)`$, and let $`D=G(\stackrel{~}{E},\stackrel{~}{S})`$. The nondegenerate $``$-representations of $`C_c(D)`$ are in one-to-one correspondence with the pairs $`(\pi ,U)`$, where $`\pi `$ is a nondegenerate representation of $`C_c((\stackrel{~}{E},\stackrel{~}{S}))`$ on a Hilbert space $`H`$, and $`U:GL(H)`$ is a representation of $`G`$ by partial isometries such that

$$\begin{array}{cc}\hfill U_\alpha ^{}U_\alpha & =\pi \left(\chi _{\lambda ^1(s(\alpha ))}\right),\hfill \\ \hfill U_\alpha U_\alpha ^{}& =\pi \left(\chi _{\lambda ^1(r(\alpha ))}\right),\hfill \\ \hfill U_\alpha \pi \left(\chi _{V(p)}\right)U_\alpha ^{}& =\pi \left(\chi _{V(\alpha p)}\right),\hfill \end{array}$$

where $`V(\alpha p)=\mathrm{}`$ if $`s(\alpha )\lambda (p)`$, and $`\pi `$ also denotes the extension of $`\pi `$ to the multiplier algebra of $`C_0\left((\stackrel{~}{E},\stackrel{~}{S})\right)`$.

Proof. If $`\sigma :C_c(D)L(H)`$ is a nondegenerate $``$-representation, then $`\sigma |C_c(D^0)`$ extends to a nondegenerate $``$-representation $`\pi :C_0\left((\stackrel{~}{E},\stackrel{~}{S})\right)L(H)`$. Since $`\lambda ^1(u)`$ is a clopen subset of $`(\stackrel{~}{E},\stackrel{~}{S})`$ for $`uE^0`$, the extension of $`\pi `$ to $`C_b((\stackrel{~}{E},\stackrel{~}{S}))`$ can be applied to $`\chi _{\lambda ^1(u)}`$. For $`\alpha G`$,

$$\left\{\sigma (\chi _{\{\alpha \}\times V})\right|V\lambda ^1\left(s(\alpha )\right)\text{ is compact-open}\}$$

is a coherent net of partial isometries, hence converges in the strong operator topology to a partial isometry $`U_\alpha L(H)`$. It is clear that $`U_\alpha ^{}U_\alpha `$ is orthogonal to $`\pi (\chi _{\lambda ^1(u)})`$ if $`us(\alpha )`$. By the nondegeneracy of $`\pi `$, it follows that $`U_\alpha ^{}U_\alpha =\pi (\chi _{\lambda ^1\left(s(\alpha )\right)})`$. Similarly, $`U_\alpha U_\alpha ^{}=\pi (\chi _{\lambda ^1\left(r(\alpha )\right)})`$. The remaining properties of the $`\{U_\alpha \}`$ follow from the definition. Conversely, if $`(\pi ,U)`$ are given, we define $`\sigma :C_c(D)L(H)`$ by

$$\sigma \left(\chi _{\{\alpha \}\times \lambda ^1\left(s(\alpha )\right)}f\right)=U_\alpha \pi (f)$$

whenever $`fC_c(D^0)`$ and $`\text{supp}(f)\lambda ^1\left(s(\alpha )\right)`$. Then $`\sigma `$ is a linear map, and it is easy to verify that $`\sigma `$ is multiplicative and $``$-preserving by checking on elements of the form $`\chi _{\{\alpha \}\times V}`$ for $`V\lambda ^1\left(s(\alpha )\right)`$ compact-open.

Corollary 2.15. Every $``$-representation of $`C_c\left(G(\stackrel{~}{E},\stackrel{~}{S})\right)`$ is bounded.

(This is true for any $`r`$-discrete groupoid — see , Proposition 3.2.)

To obtain more familiar objects we will define natural transversals in the extended Toeplitz graph groupoids. Let $`S\mathrm{\Sigma }(E)`$. We define $`X(E,S)(\stackrel{~}{E},\stackrel{~}{S})`$ by

$$X(E,S)=\left\{x(\stackrel{~}{E},\stackrel{~}{S})\right|\underset{¯}{x}E_+^{}\}.$$

(Thus $`X(E,S)`$ is the set of points in the spectrum of $`A(\stackrel{~}{E},\stackrel{~}{S})`$ that are represented by directed paths in $`E`$.) In the special case $`S=\mathrm{\Sigma }(E)`$ we let $`X(E)=X(E,\mathrm{\Sigma }(E))`$, the set of all points of $`\stackrel{~}{E}`$ represented by directed paths in $`E`$.

Lemma 2.16. $`X(E,S)`$ is a clopen transversal in $`G(\stackrel{~}{E},\stackrel{~}{S})`$.

Proof. Let $`xX(E,S)`$. Then $`\lambda (x)\stackrel{~}{E}^0`$, so we may consider the open set $`[V_{\stackrel{~}{E}}(\lambda (x))]`$ in $`A(\stackrel{~}{E})\widehat{}`$. Since $`xX(E,S)`$, $`x[V_{\stackrel{~}{E}}(\lambda (x))]`$. Moreover, for any $`y[V_{\stackrel{~}{E}}(\lambda (x))]`$, $`y`$ consists entirely of directed edges of $`\stackrel{~}{E}`$, and hence $`\underset{¯}{y}E_+^{}`$. Thus $`[V_{\stackrel{~}{E}}(\lambda (x))](\stackrel{~}{E},\stackrel{~}{S})X(E,S)`$, and so $`X(E,S)`$ is open. Now suppose that $`x(\stackrel{~}{E},\stackrel{~}{S})X(E,S)`$. Letting $`\underset{¯}{x}=e_1e_2\mathrm{}`$, then $`e_iE_+^1`$ for some $`i`$. Let $`p=e_1\mathrm{}e_i\stackrel{~}{E}^0`$. Then $`x[V(p)]`$ and $`[V(p)]X(E,S)=\mathrm{}`$. Thus the complement of $`X(E,S)`$ is open. To see that $`X(E,S)`$ is a transversal, let $`x(\stackrel{~}{E},\stackrel{~}{S})`$. Let $`\underset{¯}{x}=e_1e_2\mathrm{}`$. Then there is $`n`$ with $`e_iE_+^1`$ for $`in`$. Let $`\alpha =e_1\mathrm{}e_{n1}`$. Then $`(\alpha ^1,x)`$ has source $`x`$ and range in $`X(E,S)`$.

Definition 2.17. Let $`E`$ be a directed graph. The Toeplitz graph groupoids are the restrictions of the extended Toeplitz graph groupoids to the transversals $`X(E,S)`$, and the Toeplitz graph algebras are their $`C^{}`$-algebras:

$$\begin{array}{cc}\hfill 𝒯𝒢(E,S)& =G(E)(\stackrel{~}{E},\stackrel{~}{S})|X(E,S)\hfill \\ \hfill 𝒯𝒪(E,S)& =C^{}\left(𝒯𝒢(E,S)\right),\hfill \end{array}$$

for $`S\mathrm{\Sigma }(E)`$. (We let $`𝒯𝒪(E)𝒯𝒪(E,\mathrm{})`$.)

The graph groupoid and graph algebra of $`E`$ are special cases obtained when $`S=\mathrm{\Sigma }(E)`$:

$$\begin{array}{cc}\hfill 𝒢(E)& =𝒢(E,X(E))=G(E)\stackrel{~}{E}|X(E)\hfill \\ \hfill 𝒪(E)& =C^{}\left(𝒢(E)\right).\hfill \end{array}$$

Remark 2.18. In the case of a graph $`E`$ with no sinks, the graph groupoid defined above is exactly the usual notion of infinite directed paths “modulo shift-tail equivalence with lag”. In the case of a graph that is not row-finite, one must include the finite directed paths ending at vertices with infinite exit valence (as we have done). This idea was used in an ad-hoc way by previous authors ().

Next we will characterize representations of $`𝒯𝒪(E,S)`$ by means of generators and relations (cf. ).

Theorem 2.19. The nondegenerate representations of $`𝒯𝒪(E)`$ are in one-to-one correspondence with the families of operators $`\{S_e\}_{eE_+^1}`$ and $`\{P_u\}_{uE^0}`$ such that

(i) The $`\{S_e\}`$ are partial isometries and the $`\{P_u\}`$ are projections,

(ii) $`uvP_uP_v=0`$,

(iii) $`P_u=1`$ in the strong operator topology,

(iv) $`S_e^{}S_e=P_{t(e)}`$,

(v) $`P_u\{S_fS_f^{}o(f)=u\}`$.

Proof. If $`\pi :𝒯𝒪(E)L(H)`$ is nondegenerate, let

$$\begin{array}{cc}\hfill S_e& =\pi \left(\chi _{\{e\}\times V_{\stackrel{~}{E}}(t(e))}\right)\hfill \\ \hfill P_u& =\pi \left(\chi _{V_{\stackrel{~}{E}}(u)}\right).\hfill \end{array}$$

It is easy to verify properties (i) - (v).

Conversely, let $`\{S_e\}`$, $`\{P_e\}`$ satisfying (i) - (v) be given. For $`p=e_1e_2\mathrm{}e_nE_+^{}`$, let $`S_p=S_{e_1}S_{e_2}\mathrm{}S_{e_n}`$. We note the following elementary consequences of (i) - (v):

(a) $`efS_e^{}S_f=0`$,

(b) $`S_p^{}S_p=P_{t(p)}`$,

(c) $`S_p^{}S_q=0`$ if neither of $`p`$, $`q`$ extends the other. Let $`\theta _p=S_pS_p^{}`$ for $`pE_+^{}`$. We will verify the conditions of Lemma 1.5 for (the bundle of trees) $`\stackrel{~}{E}`$. If $`(p,q)\mathrm{\Delta }_{1,\stackrel{~}{E}}(p)`$, then $`q=pf`$ for some $`fE_+^1`$. Then

$$\begin{array}{cc}\hfill \theta _q& =S_qS_q^{}\hfill \\ & =S_pS_fS_f^{}S_p^{}\hfill \\ & S_pS_p^{}\hfill \\ & =\theta _p.\hfill \end{array}$$

Let $`(p,q_1)(p,q_2)\mathrm{\Delta }_{1,\stackrel{~}{E}}(p)`$. Then there are $`f_1f_2E_+^1`$, with $`o(f_1)=o(f_2)=t(p)`$, such that $`q_i=pf_i`$. Then

$$\begin{array}{cc}\hfill S_{q_1}^{}S_{q_2}& =S_{f_1}^{}S_p^{}S_pS_{f_2}\hfill \\ & =S_{f_1}^{}P_{t(p)}S_{f_2}\hfill \\ & =S_{f_1}^{}S_{f_2}\hfill \\ & =0.\hfill \end{array}$$

Thus by Lemma 1.5, there is a $``$-homomorphism $`\pi _0:C_0\left(X(E,\mathrm{})\right)L(H)`$ such that

$$\begin{array}{cc}\hfill \pi _0\left(\chi _{V(q)}\right)& =\theta _q,qE_+^{},\hfill \\ \hfill \pi _0\left(\chi _{V(u)}\right)& =P_u,uE^0.\hfill \end{array}$$

Then $`\pi _0`$ is nondegenerate, by (iii). Define $`\pi :C_c\left(𝒯𝒢(E)\right)L(H)`$ as follows. The elements of $`C_c\left(𝒯𝒢(E)\right)`$ can be written uniquely in the form

$$\chi _{\{\alpha _1\alpha _2^1\}\times V(\alpha _2)}f_{\alpha _1,\alpha _2},$$

where the sum is taken over pairs $`(\alpha _1,\alpha _2)E_+^{}\times E_+^{}`$ for which $`\alpha _1\alpha _2^1`$ involves no cancellations, and where $`f_{\alpha _1,\alpha _2}C_c\left(X(E,\mathrm{})\right)`$ is zero except for finitely many $`(\alpha _1,\alpha _2)`$. We define $`\pi `$ by

$$\pi \left(\chi _{\{\alpha _1\alpha _2^1\}\times V(\alpha _2)}f\right)=S_{\alpha _1}S_{\alpha _2}^{}\pi _0(f).$$

This is well-defined, since

$$\begin{array}{cc}\hfill \chi _{\{\alpha _1\alpha _2^1\}\times V(\alpha _2)}f=0& \text{supp}(f)V(\alpha _2)^c\hfill \\ & S_{\alpha _2}^{}\pi _0(f)=S_{\alpha _2}^{}\theta _{\alpha _2}(1\theta _{\alpha _2})\pi _0(f)=0.\hfill \end{array}$$

$`\pi `$ is clearly linear. It is straight-forward to verify that $`\pi `$ is multiplicative and adjoint-preserving by checking on elements of the form $`\chi _{\{\alpha _1\alpha _2^1\}\times V}`$ for $`V[V(\alpha _2)]`$ compact-open.

Theorem 2.20. Let $`S\mathrm{\Sigma }(E)`$. The nondegenerate representations of $`𝒯𝒪(E,S)`$ are in one-to-one correspondence with the families of operators $`\{S_e\}_{eE_+^1}`$ and $`\{P_u\}_{uE^0}`$ satisfying (i) - (v) of Theorem 2.19 such that equality holds in (v) whenever $`uS`$.

Proof. Note that equality in (v) for $`uS`$ means in particular that the sum in (v) is finitely nonzero. Let $`\pi `$ be a nondegenerate representation of $`𝒯𝒪(E)`$ corresponding to generators and relations as in Theorem 2.19. Then

$$\begin{array}{cc}\hfill \pi \text{ factors through }𝒯𝒪(E,S)& C_0\left(\stackrel{~}{S}X(E,S)\right)\mathrm{ker}\pi \hfill \\ & \left(uS\right)\left(F\mathrm{\Delta }_1(u)\text{ finite}\right)\left(P_u=\underset{eF}{}S_eS_e^{}\right)\hfill \\ & \text{ equality holds in (v) whenever }uS.\text{ }\hfill \end{array}$$

For reference elsewhere (), we give a slightly different form of the relations defining the algebra $`𝒪(E)`$. For this purpose we will let $`D`$ denote the set of vertices with infinite exit valence:

$$D=\left\{uE^0\right|\mathrm{\Delta }_1(u)\text{ is infinite}\}.$$

Theorem 2.21. Let $`E`$ be a directed graph. The nondegenerate representations of $`𝒪(E)`$ are in one-to-one correspondence with the families of operators $`\{S_e:eE_+^1\}`$ and $`\{P_u:uE^0\}`$ satisfying

(1) The $`\{S_e\}`$ are partial isometries and the $`\{P_u\}`$ are projections,

(2) $`uvP_uP_v=0`$,

(3) $`S_e^{}S_e=P_{t(e)}`$,

(4) $`P_{o(e)}S_e=S_e`$, if $`o(e)D`$,

(5) $`ef`$ and $`o(e)=o(f)DS_e^{}S_f=0`$,

(6) $`uDP_u=\{S_fS_f^{}o(f)=u\}`$,

(7) $`P_u=1`$ in the strong operator topology.

Proof. This follows easily from Theorems 2.19 and 2.20.

Next we will define the fundamental cocycle on the (extended) graph goupoids.

Lemma 2.22. Let $`(\alpha ,y)GA(\stackrel{~}{E})\widehat{}`$. Then there exist unique elements $`\beta _1,\beta _2G`$ and $`xA(\stackrel{~}{E})\widehat{}`$ such that   $`(i)`$ $`(\beta _1,x),(\beta _2,x)GA(\stackrel{~}{E})\widehat{}`$  $`(ii)`$ $`\alpha =\beta _1\beta _2^1`$  $`(iii)`$ $`y=\beta _2x`$  $`(iv)`$ The products $`\beta _1\underset{¯}{x}`$, $`\beta _2\underset{¯}{x}`$, $`\beta _1\beta _2^1`$ involve no cancellations.

Proof. For existence, let $`\alpha =e_1\mathrm{}e_k`$ and $`\underset{¯}{y}=f_1f_2\mathrm{}`$, and let $`rk`$ denote the number of cancellations occurring when $`\alpha `$ and $`\underset{¯}{y}`$ are multiplied. We have that

$$\begin{array}{cc}\hfill f_i& =\overline{e_{ki+1}},1ir\hfill \\ \hfill f_{r+1}& \overline{e_{kr}}.\hfill \end{array}$$

Then we may put

$$\begin{array}{cc}\hfill \beta _1& =e_1\mathrm{}e_{kr}\hfill \\ \hfill \beta _2& =f_1\mathrm{}f_r\hfill \\ \hfill \underset{¯}{x}& =f_{r+1}f_{r+2}\mathrm{}.\hfill \end{array}$$

For uniqueness, let $`\beta _1^{},\beta _2^{}`$, and $`x^{}`$ also satisfy conditions (i)-(iv) of the statement of the Lemma. Since $`\underset{¯}{y}=\beta ^{}\underset{¯}{x}^{}`$, there is $`s`$ such that

$$\begin{array}{cc}\hfill \beta _2^{}& =f_1\mathrm{}f_s\hfill \\ \hfill \underset{¯}{x}^{}& =f_{s+1}f_{s+2}\mathrm{}.\hfill \end{array}$$

If $`\beta _1^{}=e_1^{}\mathrm{}e_{\mathrm{}}^{}`$, then from $`\beta _1\underset{¯}{x}=\beta _1^{}\underset{¯}{x}^{}`$ we have

$$e_1\mathrm{}e_{kr}f_{r+1}f_{r+2}\mathrm{}=e_1^{}\mathrm{}e_{\mathrm{}}^{}f_{s+1}f_{s+2}\mathrm{}.$$

Suppose $`r<s`$. Since paths in a tree are unique (in this case, the path from $`o(e_1)=o(e_1^{})`$ to $`o(f_{s+1})`$), we must have

$$e_1\mathrm{}e_{kr}f_{r+1}\mathrm{}f_s=e_1^{}\mathrm{}e_{\mathrm{}}^{}=\beta _1^{}.$$

But then the product $`\beta _1^{}(\beta _2^{})^1`$ involves the cancellation of $`f_{r+1}\mathrm{}f_s`$, a contradiction. The assumption $`r>s`$ leads to a similar contradiction. Therefore $`r=s`$, and it follows that $`\beta _1^{}=\beta _1`$, $`\beta _2=\beta _2^{}`$, and $`x^{}=x`$.

Definition 2.23. Let $`(\alpha ,y)GA(\stackrel{~}{E})\widehat{}`$. The standard form of $`(\alpha ,y)`$ is the triple $`(\beta _1,\beta _2,x)`$ satisfying (i) - (iv) of Lemma 2.22.

Definition 2.24.$`c:GA(\stackrel{~}{E})\widehat{}𝐙`$ is defined by $`c(\alpha ,y)=\mathrm{}(\beta _1)\mathrm{}(\beta _2)`$, where $`(\beta _1,\beta _2,x)`$ is the standard form of $`(\alpha ,y)`$. For $`S\mathrm{\Sigma }(E)`$, we also let $`c`$ denote the restriction to $`G(\stackrel{~}{E},\stackrel{~}{S})`$.

Lemma 2.25. $`c`$ is a continuous homomorphism.

Proof. The continuity is clear. Note that it follows from the definition of $`c`$ that $`c`$ is zero on units, and that $`c(\alpha ,y)^1=c(\alpha ,y)`$. We will prove that $`c\left((\beta ,y)(\alpha ,y)^1\right)=c(\beta ,y)c(\alpha ,y)`$. Let $`y=g_1g_2\mathrm{}`$, $`\beta =e_1\mathrm{}e_j\overline{g_k}\mathrm{}\overline{g_1}`$, $`\alpha =f_1\mathrm{}f_p\overline{g_q}\mathrm{}\overline{g_1}`$, where $`e_j\overline{g_{k+1}},g_k`$, and $`f_p\overline{g_{q+1}},g_q`$. Then

$$\beta \alpha ^1=(e_1\mathrm{}e_j)(g_1\mathrm{}g_k)^1(g_1\mathrm{}g_q)(f_1\mathrm{}f_p)^1.$$

Suppose first that $`q>k`$. Then we have

$$\begin{array}{cc}\hfill \beta \alpha ^1& =e_1\mathrm{}e_jg_{k+1}\mathrm{}g_q\overline{f_p}\mathrm{}\overline{f_1}\hfill \\ & =(e_1\mathrm{}e_jg_{k+1}\mathrm{}g_q)(f_1\mathrm{}f_p)^1\hfill \\ \hfill \alpha y& =f_1\mathrm{}f_pg_{q+1}g_{q+2}\mathrm{}\hfill \\ & =(f_1\mathrm{}f_p)(g_{q+1}g_{q+2}\mathrm{}),\hfill \end{array}$$

and hence $`(\beta \alpha ^1,\alpha y)`$ has as standard form

$$(e_1\mathrm{}e_jg_{k+1}\mathrm{}g_q,f_1\mathrm{}f_p,g_{q+1}g_{q+2}\mathrm{}).$$

It follows that

$$\begin{array}{cc}\hfill c(\beta \alpha ^1,\alpha y)& =j+(qk)p\hfill \\ & =(jk)(pq)\hfill \\ & =c(\beta ,y)c(\alpha ,y).\hfill \end{array}$$

Next, if $`q<k`$, we may apply the above argument to $`c\left((\alpha ,y)(\beta ,y)^1\right)`$. Finally, if $`q=k`$, we have

$$\begin{array}{cc}\hfill \beta \alpha ^1& =e_1\mathrm{}e_j\overline{f_p}\mathrm{}\overline{f_1}\hfill \\ \hfill \alpha y& =f_1\mathrm{}f_pg_{k+1}g_{k+2}\mathrm{}.\hfill \end{array}$$

Let $`m`$ be the number of cancellations in the product $`(e_1\mathrm{}e_j)(\overline{f_p}\mathrm{}\overline{f_1})`$. Then

$$\begin{array}{cc}\hfill c(\beta \alpha ^1,\alpha y)& =(jm)(pm)\hfill \\ & =jp\hfill \\ & =(jk)(pq)\hfill \\ & =c(\beta ,y)c(\alpha ,y).\text{ }\hfill \end{array}$$

Remark 2.26. Note that $`c^1(0)`$ is an equivalence relation. For if $`(\beta _1,\beta _2,x)`$ is the standard form of the element $`(\beta _1\beta _2^1,\beta _2x)c^1(0)`$, then

$$\begin{array}{cc}\hfill r(\beta _1\beta _2^1,\beta _2x)=s(\beta _1\beta _2^1,\beta _2x)& \beta _1x=\beta _2x\hfill \\ & \beta _1=\beta _2,\text{ (since }\mathrm{}(\beta _1)=\mathrm{}(\beta _2)),\hfill \\ & (\beta _1\beta _2^1,\beta _2x)=(\lambda (x),x)c^1(0)^0.\text{ }\hfill \end{array}$$

Proposition 2.27. Let $`KA(\stackrel{~}{E})\widehat{}`$ be a closed $`G`$-invariant subset, and let $`c:GK𝐙`$ denote the restriction of the canonical cocycle to $`GK`$. Then $`c^1(0)`$ is an AF equivalence relation.

Proof. For $`FE`$ a finite subgraph, and $`n𝐍`$, let

$$\begin{array}{c}\text{ }H(F,n)=\{(\alpha ,y)c^1(0)|\beta _1,\beta _2F^{},\mathrm{}(\beta _1)=\mathrm{}(\beta _2)n,\underset{¯}{x}E_+^{},\text{ }\hfill \\ \text{ }\text{ (where }(\beta _1,\beta _2,x)\text{ is the standard form of }(\alpha ,y)\text{)}\}.\text{ }\hfill \end{array}$$

Then $`H(F,n)`$ is a compact-open subequivalence relation of $`c^1(0)`$. (Compactness follows from the requirement that $`\underset{¯}{x}`$ consist of directed edges.) If $`FF^{}`$ and $`nn^{}`$, then $`H(F,n)H(F^{},n^{})`$, and

$$\underset{F,n}{}H(F,n)=c^1(0).$$

We will show that $`H(F,n)`$ is an elementary groupoid (in the sense of  III.1.1). Since $`c^1(0)^0`$ is totally disconnected, it will follow that $`c^1(0)`$ is an AF groupoid. (In  an AF groupoid is defined to be the inductive limit of a sequence of elementary groupoids. However, since each $`H(F,n)`$ has totally disconnected unit space, $`C^{}\left(H(F,n)\right)`$ is an AF-algebra. Thus $`C^{}\left(c^1(0)\right)`$ is AF.)

For $`yH(F,n)^0`$, let $`M(F,n,y)`$ denote the set of ordered pairs $`(\beta _1,\beta _2)F^{}\times F^{}`$ such that

$``$$`xK`$ with $`(\beta _1,\beta _2,x)`$ equal to the standard form of an element of $`H(F,n)`$,

$``$$`y=\beta _2x`$. It is clear that $`M(F,n,y)`$ is finite. We claim that there is a (compact-open) neighborhood $`U`$ of $`y`$ in $`H(F,n)^0`$ such that for $`y^{}U`$, $`M(F,n,y^{})=M(F,n,y)`$. To see this, let $`\underset{¯}{y}=f_1f_2\mathrm{}`$. If $`\mathrm{}(\underset{¯}{y})>n`$, let $`U=[V(f_1\mathrm{}f_{n+1})]H(F,n)^0`$. Then for any $`y^{}U`$, $`\underset{¯}{y^{}}=f_1\mathrm{}f_{n+1}\mathrm{}`$, and the conclusion follows. If $`\mathrm{}(y)n`$, then $`\underset{¯}{y}\stackrel{~}{E}^0`$. Let $`R=\mathrm{\Delta }_{1,\stackrel{~}{F}}(y)`$. This is a finite subset of $`\mathrm{\Delta }_{1,\stackrel{~}{F}}(y)`$ since $`F`$ is a finite graph. We may now take $`U=[V(y;R)]H(F,n)`$. Then for any $`y^{}U`$, we must have $`y^{}=f_1^{}\mathrm{}`$, where $`f_i^{}=f_i`$ for $`i\mathrm{}(y)`$, and $`f_{\mathrm{}(y)+1}^{}F^1`$. The conclusion now follows because $`M(F,n,y)F^{}\times F^{}`$.

Now let $`yH(F,n)^0`$ and $`U`$ be as above. For $`(\beta _1,\beta _2)M(F,n,y)`$, let $`U(\beta _1,\beta _2)=\{\beta _1\beta _2^1\}\times U`$. Note that for any $`(\alpha ,z)H(F,n)`$ with $`zU`$, there exists $`(\beta _1,\beta _2)M(F,n,y)`$ with $`\alpha =\beta _1\beta _2^1`$, and thus such that $`(\alpha ,z)U(\beta _1,\beta _2)`$. Further, we note that for any $`(\beta _1,\beta _2)M(F,n,y)`$,

$``$$`U(\beta _1,\beta _2)`$ is a compact-open $`G`$-set in $`H(F,n)`$,

$``$$`s\left(U(\beta _1,\beta _2)\right)=U`$,

$``$For $`(\beta _1,\beta _2),(\beta _1^{},\beta _2^{})M(F,n,y)`$ distinct, $`r\left(U(\beta _1,\beta _2)\right)r\left(U(\beta _1^{},\beta _2^{})\right)=\mathrm{}`$. It follows that

$$\begin{array}{c}\text{ }H(F,n)|\left\{r\left(U(\beta _1,\beta _2)\right)\right|(\beta _1,\beta _2)M(F,n,y)\}M(F,n,y)^2\times U,\text{ }\hfill \end{array}$$

and that $`H(F,n)`$ is the disjoint union of finitely many such restrictions. Thus $`H(F,n)`$ is an elementary groupoid.

Corollary 2.28. $`C^{}(GK)`$ is nuclear, and coincides with $`C_r^{}(GK)`$.

Proof. Let $`D=GK`$. We obtain a circle action on $`C^{}(D)`$ in the usual way:

$$\alpha _z(f)(\zeta )=z^{c(\zeta )}f(\zeta ),fC_c(D).$$

(This extends to an automorphism of $`C^{}(D)`$ by Corollary 2.15.) Letting $`H=c^1(0)`$, the inclusion $`C_c(H)C_c(D)C^{}(D)`$ extends to an injective $``$-homomorphism $`C^{}(H)C^{}(D)`$ (injectivity follows easily since $`C^{}(H)`$ is an AF algebra). By approximating from within $`C_c(H)`$, it is easy to see that $`C^{}(H)=C^{}(D)^\alpha `$, the fixed-point algebra. Since $`C^{}(H)`$ is nuclear, it follows that $`C^{}(D)`$ is nuclear (see  for a more general result in the context of coactions).

It is easy to check that the above formula for $`\alpha _z`$ defines a circle action on $`C_r^{}(D)`$. Since $`C^{}(H)=C_r^{}(H)`$, it follows that $`C^{}(H)C_r^{}(D)`$. Hence if $`E`$ is the conditional expectation of $`C^{}(D)`$ onto $`C^{}(H)`$, and $`\lambda `$ is the canonical map of $`C^{}(D)`$ onto $`C_r^{}(D)`$, then $`E\lambda =E`$. It now follows that the canonical map is injective. (Alternatively, one may appeal to  6.2.14.ii and 6.1.7.)

We now require two simple facts about inclusions of $`r`$-discrete groupoids.

Lemma 2.29. (i) Let $`K`$ be an $`r`$-discrete groupoid and let $`H`$ be an open subgroupoid. Then $`C_c(H)C_c(K)`$ extends to an injective $``$-homomorphism $`C_r^{}(H)C_r^{}(K)`$. (ii) Let $`\pi :XY`$ be a continuous proper surjection of locally compact Hausdorff spaces. Let $`G`$ be a discrete groupoid acting equivariantly on $`X`$ and $`Y`$. Then $`\pi ^{}:C_c(Y)C_c(X)`$ extends to an injective $``$-homomorphism $`C_r^{}(GY)C_r^{}(GX)`$.

Proof. (i) Let $`uG^0`$, and let $`\sigma _u`$ denote the regular representation of $`C_c(GX)`$ induced from the point mass at $`u`$. Then $`\sigma _u`$ acts on $`\mathrm{}^2(G_u)`$ by the formula

$$\sigma _u(f)\xi (\alpha )=\underset{\beta G^{r(\alpha )}}{}f(\beta )\xi (\beta ^1\alpha ),fC_c(G),\xi \mathrm{}^2(G_u).$$

We have a partition of $`G_u`$ into sets invariant for left multiplication by $`H`$:

$$\left\{G_u^{G^0H^0}\right\}H\backslash G_u^{H^0}.$$

Choosing a cross-section $`FG_u^{H^0}`$ for $`H\backslash G_u^{H^0}`$, we have

$$\sigma _u|C_c(H)0\underset{xF}{}\tau _{r(x)},$$

where $`\tau _v`$ denotes the regular representation of $`C_c(H)`$ induced from the point mass at $`vH^0`$. Thus for $`fC_c(H)`$,

$$\begin{array}{cc}\hfill f_{C_r^{}(G)}& =\underset{uG^0}{sup}\sigma _u(f)\hfill \\ & \underset{vH^0}{sup}\tau _v(f)\hfill \\ & =f_{C_r^{}(H)}.\hfill \end{array}$$

But if $`vH^0`$, then $`\tau _v`$ is a subrepresentation of $`\sigma _v|C_c(H)`$. Hence $`f_{C_r^{}(G)}=f_{C_r^{}(H)}`$. (ii) Let $`\rho :XG^0`$ and $`\lambda :YG^0`$ be the fiber maps. Let $`yY`$, let $`x\pi ^1(y)`$, and let $`\sigma `$ (respectively $`\stackrel{~}{\sigma }`$) denote the regular representation of $`C_c(GY)`$ (respectively $`C_c(GX)`$) induced from the point mass at $`y`$ (respectively $`x`$). Then $`\sigma `$ (respectively $`\stackrel{~}{\sigma }`$) acts on $`\mathrm{}^2(G_{\lambda (y)})`$ (respectively $`\mathrm{}^2(G_{\rho (x)})`$). However $`\rho (x)=\lambda \pi (x)=\lambda (y)`$, and it is easy to see that $`\stackrel{~}{\sigma }\pi ^{}=\sigma `$. Thus for $`fC_c(GY)`$,

$$\begin{array}{cc}\hfill f_{C_r^{}(GY)}& =\underset{yY}{sup}\sigma _y(f)\hfill \\ & =\underset{yY}{sup}\stackrel{~}{\sigma }_x\pi ^{}(f),\text{ any }x\pi ^1(y),\hfill \\ & =\underset{xX}{sup}\stackrel{~}{\sigma }_x\pi ^{}(f)\hfill \\ & =\pi ^{}(f)_{C_r^{}(GX)}.\text{ }\hfill \end{array}$$

Corollary 2.30. Let $`E`$ be a directed graph, and let $`S\mathrm{\Sigma }(E)`$. Then $`C^{}\left(G(\stackrel{~}{E},\stackrel{~}{S})\right)`$ and $`𝒯𝒪(E,S)`$ are strongly Morita equivalent.

Proof. $`𝒯𝒢(E,S)`$ is an open subgroupoid of $`G(\stackrel{~}{E},\stackrel{~}{S})`$. By Lemma 2.29 (i),

$$C_r^{}\left(𝒯𝒢(E,S)\right)C_r^{}\left(G(\stackrel{~}{E},\stackrel{~}{S})\right).$$

But by Corollary 2.28, the full and reduced $`C^{}`$-algebras coincide for these groupoids. Therefore

$$𝒯𝒪(E,S)C^{}\left(G(\stackrel{~}{E},\stackrel{~}{S})\right).$$

$$\begin{array}{c}\text{ }\text{Let }p=\chi _{X(E,S)}M\left(C^{}\left(G(\stackrel{~}{E},\stackrel{~}{S})\right)\right).\text{Since}\text{ }\hfill \end{array}$$

$$pC_c\left(G(\stackrel{~}{E},\stackrel{~}{S})\right)p=C_c\left(𝒯𝒢(E,S)\right),$$

we have by continuity

$$pC^{}\left(G(\stackrel{~}{E},\stackrel{~}{S})\right)p=𝒯𝒪(E,S).$$

Moreover, $`p`$ is a full projection since $`X(E,S)`$ is a transversal in $`G(\stackrel{~}{E},\stackrel{~}{S})`$.

Remark 2.31. If the graph $`E`$ is countable, then all groupoids under discussion are second countable. In this case the previous result follows immediately from . Our aim, in proving Corollary 2.30 as we have done, was not only to establish the result for arbitrary graphs, but also to show that its proof is more elementary than would be implied by the use of .

Lemma 2.32. Let $`E`$ be a directed graph and let $`S\mathrm{\Sigma }`$. Then $`C^{}\left(G(\mathrm{\Sigma }S)\right)`$ is isomorphic to $`\left\{𝒦(H_u)\right|u\mathrm{\Sigma }S\}`$, where $`H_u=\mathrm{}^2\left(E^{}t^1(u)\right)`$.

Proof. Since $`\mathrm{\Sigma }S`$ is a discrete set, we have that $`G(\mathrm{\Sigma }S)`$ is the disjoint union of the (discrete) transitive groupoids $`G\left(E^{}t^1(u)\right)`$, $`u\mathrm{\Sigma }S`$. The lemma now follows from the fact that the $`C^{}`$-algebra of a discrete transitive groupoid is elementary.

Corollary 2.33. Let $`E`$ be a directed graph and let $`S\mathrm{\Sigma }`$. There is an exact sequence

$$0I_S𝒯𝒪(E,S)𝒪(E)0,$$

where $`I_S=\left\{𝒦_u\right|u\mathrm{\Sigma }S\}`$, and $`𝒦_u`$ is isomorphic to the algebra of compact operators on a Hilbert space of dimension $`\mathrm{\#}\left(E_+^{}t^1(u)\right)`$.

Proof. This follows from Corollary 2.30, Lemma 2.32 and , Proposition II.4.5.(i).

Now let $`E_1E_2`$ be an inclusion of directed graphs. We have an inclusion of bundles of directed trees $`\stackrel{~}{E}_1\stackrel{~}{E}_2`$, hence an injective $``$-homomorphism $`A(\stackrel{~}{E}_1)A(\stackrel{~}{E}_2)`$ (Remark 1.19). Let $`S_2\mathrm{\Sigma }(E_2)`$. We define $`S_1\mathrm{\Sigma }(E_1)`$ by

$$S_1=\left\{vE_1^0S_2\right|\mathrm{\Delta }_{1,E_2}(v)E_+^1\}.$$
$`()`$
Then $`\stackrel{~}{S_1}`$ is the set defined in Lemma 1.20 by the inclusion $`\stackrel{~}{E}_1\stackrel{~}{E}_2`$ and the set $`\stackrel{~}{S}_2\mathrm{\Sigma }(\stackrel{~}{E}_2)`$. Thus the following diagram commutes, has surjective columns and injective rows:

$$\begin{array}{ccc}A(\stackrel{~}{E}_1)& & A(\stackrel{~}{E}_2)\\ \\ & & \\ \\ A(\stackrel{~}{E}_1,\stackrel{~}{S}_1)& & A(\stackrel{~}{E}_2,\stackrel{~}{S}_2).\end{array}$$

From Lemma 2.29 we obtain a composition of injective $``$-homomorphisms:

$$C^{}\left(G(E_1)(\stackrel{~}{E}_1,\stackrel{~}{S}_1)\right)C^{}\left(G(E_1)(\stackrel{~}{E}_2,\stackrel{~}{S}_2)\right)C^{}\left(G(E_2)(\stackrel{~}{E}_2,\stackrel{~}{S}_2)\right).$$

We obtain a corresponding injective $``$-homomorphism of Toeplitz graph algebras, which we state as a theorem.

Theorem 2.34. Let $`E_1E_2`$ be an inclusion of directed graphs, and let $`S_2\mathrm{\Sigma }(E_2)`$. Let $`S_1\mathrm{\Sigma }(E_1)`$ be defined as in $`()`$. Then there is an injective $``$-homorphism

$$𝒯𝒪(E_1,S_1)𝒯𝒪(E_2,S_2).\text{ }$$

Theorem 2.35. Let $`E`$ be a directed graph. Let $`𝒲`$ be any collection of subgraphs which is directed by inclusion and for which

$$\begin{array}{cc}\hfill \underset{F𝒲}{}F^0& =E^0\hfill \\ \hfill \underset{F𝒲}{}F^1& =E^1.\hfill \end{array}$$

For $`S\mathrm{\Sigma }(E)`$, and $`F𝒲`$, let $`S_F\mathrm{\Sigma }(F)`$ be as above. Then

$$𝒯𝒪(E,S)=\underset{\genfrac{}{}{0pt}{}{}{𝒲}}{lim}𝒯𝒪(F,S_F).$$

Proof. The coherence of the system of $``$-homomorphisms follows from Remark 1.21. Note that $`{\displaystyle \genfrac{}{}{0pt}{}{lim}{\genfrac{}{}{0pt}{}{}{𝒲}}}`$$`A(\stackrel{~}{F},\stackrel{~}{S}_F)`$ is dense in $`A(\stackrel{~}{E},\stackrel{~}{S})`$ by the Stone-Weierstrass theorem, since each $`B𝒜(\stackrel{~}{E})`$ is the image of a set in $`𝒜(\stackrel{~}{F})`$ for all large enough $`F`$. Since $`G(E)=_𝒲G(F)`$, the equality stated in the theorem holds.

3. Structure of Graph $`C^{}`$-algebras.

The results in this section are parallel with similar results in other work (e.g. ). We show here that they follow easily in our general framework. Definition 3.1. Let $`E`$ be a directed graph. A cycle in $`E`$ is a path $`\alpha =e_1\mathrm{}e_nE_+^{}`$ such that $`o(\alpha )=t(\alpha )`$ and $`o(e_i)o(e_j)`$ for $`1i<jn`$. An exit of $`\alpha `$ is an edge in $`\mathrm{\Delta }_1\left(o(e_i)\right)\{e_i\}`$ for some $`i`$. The cycle $`\alpha `$ is terminal if $`\alpha `$ has no exit. The cycle $`\alpha `$ is transitory if it is not terminal, and if for each exit $`f`$ of $`\alpha `$ we have $`o(e_j)V\left(t(f)\right)`$ for all $`j`$; (in other words, $`\alpha `$ has an exit, but no exit from $`\alpha `$ leads back to $`\alpha `$).

Lemma 3.2. Let $`E`$ be a directed graph. Let $`uE^0`$, and suppose that $`E`$ has a non-terminal cycle (whose vertices are contained) in $`V(u)`$. Then the restriction of $`G(E)\stackrel{~}{E}`$ to $`\left[V_{\stackrel{~}{E}}(u)\right]_{}`$ contains an open $`G`$-set $`Z`$ with $`s(\overline{Z})\left[V_{\stackrel{~}{E}}(u)\right]_{}`$ and $`r(\overline{Z})s(Z)`$.

Proof. Let $`\alpha =e_1\mathrm{}e_n`$ be a non-terminal cycle with vertices in $`V(u)`$. We may assume that $`o(\alpha )`$ emits an exit from $`\alpha `$. Let $`U=\left[V_{\stackrel{~}{E}}\left(o(\alpha )\right)\right]_{}`$ and let $`Z=\{\alpha \}U`$. Then $`Z`$ is the required a $`G`$-set. (Any directed path that begins with an exit from $`\alpha `$ represents a point of $`U`$ that is not in the range of $`Z`$.)

Theorem 3.3. Let $`E`$ be a directed graph. Then $`𝒪(E)`$ is an AF algebra if and only if $`E`$ has no cycles.

Proof. Suppose first that $`E`$ has a cycle $`\alpha `$. If $`\alpha `$ is terminal, we may let $`N`$ be the set of vertices in $`\alpha `$ and take $`F`$ to be trivial. Then $`(N,F)(E)`$, and the corresponding ideal of $`𝒪(E)`$ is isomorphic to a matrix algebra over the continuous functions on the circle. Since $`𝒪(E)`$ has a non-AF ideal, $`𝒪(E)`$ is not AF. If $`\alpha `$ is not terminal, then let $`Z`$ be as in Lemma 3.2. Then $`\chi _Z`$ is a partial isometry in $`𝒪(E)`$ whose final projection is a proper subprojection of its initial projection. It follows that $`𝒪(E)`$ is not AF.

Now suppose that $`E`$ has no cycles. Then if $`F`$ is any finite subgraph of $`E`$, $`F^{}`$ is a finite set, and hence $`𝒯𝒪(F,S_F)`$ is finite dimensional. Then Theorem 2.35 implies that $`𝒪(E)`$ is AF.

We recall from  that an $`r`$-discrete groupoid is called locally contractive if for every nonempty open subset $`U`$ of the unit space there is an open $`G`$-set $`Z`$ with $`s(\overline{Z})U`$ and $`r(\overline{Z})s(Z)`$ (see also ).

Theorem 3.4. Let $`E`$ be a directed graph. Then $`G(E)\stackrel{~}{E}`$ is locally contractive if and only if there are no terminal cycles, and $`V(u)`$ contains a cycle for every $`uE^0`$.

Proof. We first suppose that $`E`$ has no terminal cycles and that $`V(u)`$ contains a cycle for every $`uE^0`$. Then Theorem 3.2 applies to every $`uE^0`$. Since every nonempty open subset of $`\stackrel{~}{E}`$ contains $`V(u)`$ for some $`uE^0`$, local contractivity follows from Theorem 3.2.

We now prove the converse. If $`\alpha `$ is a terminal cycle, then $`[\alpha ^{\mathrm{}}]`$ is an isolated point of $`\stackrel{~}{E}`$, and hence is an open set with no contracting subset. If $`uE^0`$ is such that $`V(u)`$ does not contain a cycle, consider the subgraph $`D`$ of $`E`$ with $`D^0=V(u)`$ and $`D^1=o^1(D^0)t^1(D^0)`$. By Theorem 3.3, $`𝒪(D)`$ is AF. Therefore the restriction of $`G(E)\stackrel{~}{E}`$ to (the open set) $`\left[V_{\stackrel{~}{E}}(u)\right]_{}`$ does not contain a $`G`$-set as in the definition of local contractivity. Hence $`G(E)\stackrel{~}{E}`$ is not locally contractive.

Definition 3.5. Let $`E`$ be a directed graph. We call $`E`$ cofinal if the following two properties hold.

(i) For every $`uE^0`$ and for every $`p=e_1e_2\mathrm{}E_+^{\mathrm{}}`$, there is $`\alpha E_+^{}`$ with $`o(\alpha )=u`$ and $`t(\alpha )=o(e_j)`$ for some $`j`$.

(ii) $`E^0\mathrm{\Sigma }(E)V(u)`$ for all $`uE^0`$. Remark 3.6. The first condition is the notion of cofinality (see e.g. ) used in the case of row-finite graphs. The second condition is necessary when there are vertices with infinite exit valence.

Theorem 3.7. Let $`E`$ be a directed graph. Then $`G(E)\stackrel{~}{E}`$ is minimal if and only if $`E`$ is cofinal.

Proof. Suppose first that $`E`$ is cofinal. Let $`U\stackrel{~}{E}`$ be a nonempty open invariant set. We will show that $`U=\stackrel{~}{E}`$. Let $`x\stackrel{~}{E}`$. By invariance of $`U`$ we may assume that $`x`$ is represented by a directed path $`pE_+^{}`$, where $`t(p)E^0\mathrm{\Sigma }(E)`$ if $`\mathrm{}(p)<\mathrm{}`$. Again by invariance, we may find $`uE^0`$ with $`\left[V_{\stackrel{~}{E}}(u)\right]_{}U`$. By cofinality there is $`\alpha E_+^{}`$ such that $`o(\alpha )=u`$, and $`t(\alpha )`$ is one of the vertices of $`p`$. But then $`\alpha ^1xU`$, so that $`xU`$ by invariance.

Now suppose that $`G(E)\stackrel{~}{E}`$ is minimal. Let $`uE^0`$. Put $`N_0=V(u)`$. Having defined $`N_i`$ for $`i<i_0`$, let

$$N_{i_0}=\left\{v\mathrm{\Sigma }(E)\right|t\left(\mathrm{\Delta }_1(v)\right)\underset{i<i_0}{}N_i\}.$$

Let $`N=_iN_i`$ and let $`F_v=\mathrm{}`$ for $`vN`$. Refering to Definition 1.23, all conditions are evidently true, so that $`(N,F)(E)`$. Since $`N\mathrm{}`$, minimality and Theorem 2.8 imply that $`N=E^0`$. Since $`NV(u)\mathrm{\Sigma }(E)`$, condition (ii) of cofinality holds.

It is easily shown by induction that if $`vN`$ and if $`e_1e_2\mathrm{}E_+^{\mathrm{}}`$ with $`o(e_1)=v`$, then $`t(e_n)V(u)`$ for all $`n`$ large enough. Now let $`pE_+^{\mathrm{}}`$. By minimality and Theorem 2.8 there exist $`vN`$, and $`\alpha E^{}`$ with $`t(\alpha )=v`$, such that $`[p]\alpha \left[V_{\stackrel{~}{E}}(v)\right]_{}`$. Hence there is $`q=e_1e_2\mathrm{}E_+^{\mathrm{}}`$ with $`o(q)=v`$ such that $`p=\alpha q`$. Since $`t(e_n)V(u)`$ for large $`n`$, condition (i) of cofinality holds.

We recall that an $`r`$-discrete groupoid is called essentially free if the set of units having trivial isotropy is dense in the space of units.

Theorem 3.8. Let $`E`$ be a directed graph. Then $`G(E)\stackrel{~}{E}`$ is essentially free if and only if $`E`$ has no terminal cycles.

Before proving Theorem 3.8 we need some lemmas. We will call a circuit any directed path of positive length whose origin and terminus coincide.

Lemma 3.9. Let $`E`$ be a directed graph and let $`x\stackrel{~}{E}`$. Then $`x`$ has nontrivial isotropy if and only if $`x=[\beta \gamma ^{\mathrm{}}]`$ for some circuit $`\gamma `$.

Proof. If $`x`$ has the indicated form, then $`\beta \gamma \beta ^1`$ fixes $`x`$. Conversely, suppose $`\alpha x=x`$ with $`\mathrm{}(\alpha )>0`$. Then necessarily $`\underset{¯}{x}`$ has infinite length. Let $`(\alpha ,\underset{¯}{x})G(E)\stackrel{~}{E}`$ have standard form $`(\beta _1,\beta _2,y)`$. If $`\mathrm{}(\beta _1)=\mathrm{}(\beta _2)`$, then since $`\beta _1y=x=\beta _2y`$ we must have $`\beta _1=\beta _2`$, contradicting the assumption on $`\alpha =\beta _1\beta _2^1`$. So we may assume $`\mathrm{}(\beta _1)<\mathrm{}(\beta _2)`$. But then from $`\beta _1y=\beta _2y`$ we find that $`\beta _2=\beta _1\gamma `$. Then $`y=\gamma y`$, so $`y=\gamma ^{\mathrm{}}`$. It follows that $`x=\beta _1\gamma ^{\mathrm{}}`$.

Lemma 3.10. Let $`E`$ be a directed graph and let $`\alpha E_+^{}`$ be a circuit. Then $`\alpha =\beta \gamma \delta `$ where $`\beta `$, $`\gamma `$, $`\delta E_+^{}`$ and $`\gamma `$ is a cycle.

Proof. Let $`\gamma `$ be the portion of $`\alpha `$ between two consecutive occurrences of a repeated vertex in $`\alpha `$.

Lemma 3.11. Let $`E`$ be a directed graph having no terminal cycles. Then for every $`uE^0`$ there is $`pE_+^{}`$ such that $`o(p)=u`$ and $`[p]\stackrel{~}{E}`$ has trivial isotropy.

Proof. Suppose first that $`V(u)`$ contains a non-transitory cycle. Then this cycle contains a vertex which emits an edge that is not in the cycle, but leads back to a vertex in the cycle. Thus there are $`\alpha `$, $`\beta `$, $`\gamma `$, $`\delta E_+^{}`$ such that

(i) $`\beta \gamma `$ is the chosen cycle,

(ii) $`o(\delta )=o(\beta `$, $`t(\delta )=t(\beta )`$, and the first edge of $`\delta `$ is not the first edge of $`\beta `$,

(iii) $`o(\alpha )=u`$ and $`t(\alpha )=o(\beta )`$.

Then the path $`p=\alpha \beta \gamma \delta \gamma (\beta \gamma )^2\delta \gamma (\beta \gamma )^3\mathrm{}`$ has the required properties.

Now suppose that $`u`$ leads only to transitory cycles. In this case there exists a path $`pE_+^{}`$ with $`o(p)=u`$, and $`t(p)E^0\mathrm{\Sigma }(E)`$ if $`\mathrm{}(p)<\mathrm{}`$, such that $`p`$ contains no cycles. Such a path can be constructed inductively by exiting any cycle encountered. By Lemma 3.10, such a path will contain no circuits. By Lemma 3.9, it will have the required properties.

Proof of Theorem 3.8. Suppose first that $`E`$ has no terminal cycles. If $`x\stackrel{~}{E}`$ has nontrivial isotropy, Lemma 3.9 implies that $`x=[\beta \gamma ^{\mathrm{}}]`$ for some circuit $`\gamma `$. Let $`u=o(\gamma )`$. Let $`p`$ be as in Lemma 3.11. Then $`x_n=[\beta \gamma ^np]`$ are points in $`\stackrel{~}{E}`$ with trivial isotropy that converge to $`x`$.

Conversely, suppose that $`E`$ has a terminal cycle, $`\alpha `$. Then $`[\alpha ^{\mathrm{}}]`$ is an isolated point in $`\stackrel{~}{E}`$, and has non-trivial isotropy.

Corollary 3.12. Let $`E`$ be a directed graph, and let $`S\mathrm{\Sigma }(E)`$. Then $`G(E)(\stackrel{~}{E},\stackrel{~}{S})`$ is essentially free if and only if $`E`$ has no terminal cycles.

Proof. Recall $`\mathrm{\Sigma }(\stackrel{~}{E})`$ is a discrete clopen subset of $`A(\stackrel{~}{E})\widehat{}`$. Moreover, every point of $`\mathrm{\Sigma }(\stackrel{~}{E})`$ has trivial isotropy. Therefore $`(\stackrel{~}{E},\stackrel{~}{S})=\stackrel{~}{E}\left(\mathrm{\Sigma }(\stackrel{~}{E})\stackrel{~}{S}\right)`$ has a dense set of points with trivial isotropy if and only if the same is true of $`\stackrel{~}{E}`$.

We next recall from , Definition II.4.3, that an $`r`$-discrete groupoid is called essentially principal if its restriction to each closed invariant subset of the unit space is essentially free. The characterization in graph terms rests on the following lemma.

Lemma 3.13. Let $`E`$ be a directed graph. Then there exists $`(N,F)(E)`$ such that $`E(N,F)`$ has a terminal cycle if and only if $`E`$ has a terminal or transitory cycle.

Proof. Suppose that $`E`$ has a transitory cycle, $`\alpha `$, and let $`C`$ denote the vertices of the edges in $`\alpha `$. Let $`D=\left\{eE_+^1\right|o(e)C,t(e)C\}`$. Then for every $`ut(D)`$ we have $`V(u)C=\mathrm{}`$. So we may let $`N=_{eD}V\left(t(e)\right)`$, and $`F_u=\mathrm{}`$ for $`uN`$. Then it is easy to see that $`(N,F)(E)`$, and $`\alpha `$ becomes a terminal cycle in $`E(N,F)`$.

Conversely, suppose $`(N,F)(E)`$ is such that $`E(N,F)`$ has a terminal cycle. Note that by Definition 1.23 (iia),

$$\underset{uNR(N,F)}{}V(u)NR(N,F),$$

and that $`NR(N,F)=E^0E(N,F)^0`$. Now let $`\alpha `$ be a terminal cycle in $`E(N,F)`$. With $`C`$ and $`D`$ as before, we must have

$$\underset{eD}{}V(u)E^0E(N,F)^0.$$

Therefore $`\alpha `$ is either terminal or transitory in $`E`$.

Theorem 3.14. Let $`E`$ be a directed graph. Then $`𝒢(E)`$ is essentially principal if and only if $`E`$ has no terminal or transitory cycles.

Proof. By Theorem 2.8 and Proposition 1.30, the closed invariant subsets of $`\stackrel{~}{E}`$ are of the form

$$(E(N,F)\stackrel{~}{},S(N,F)\stackrel{~}{}),$$

for $`(N,F)(E)`$. By Corollary 3.12, the restriction to such a set is essentially free if and only if $`E(N,F)`$ has no terminal cycles. By Lemma 3.13, no $`E(N,F)`$ has a terminal cycle if and only if $`E`$ has no terminal or transitory cycles.

We may assemble some of the above results as follows.

Theorem 3.15. Let $`E`$ be a directed graph.

(i) $`𝒪(E)`$ is a nuclear $`C^{}`$-algebra.

(ii) If $`E`$ has no terminal or transitory cycles, then the lattice of ideals in $`𝒪(E)`$ is isomorphic to the lattice of invariants $`(E)`$.

(iii) $`𝒪(E)`$ is simple if and only if $`E`$ is cofinal and has no terminal cycles.

(iv) $`𝒪(E)`$ is simple and purely infinite if and only if $`E`$ is cofinal, has no terminal cycles, and if $`V(u)`$ contains a cycle for every $`uE^0`$.

Proof. Statement (i) follows from Corollaries 2.28 and 2.30. Statement (ii) follows from Theorem 3.14 and , Theorem II.4.5(iii). Statement (iii) follows from (ii) and Theorems 3.7 and 3.8. Statement (iv) follows from (ii), Theorem 3.4, and  (or , whose argument adapts immediately to $`r`$-discrete groupoids).

References

C. Anantharaman-Delaroche, Purely infinite $`C^{}`$-algebras arising from dynamical systems, (preprint).

C. AnantharamanDelaroche and J. Renault, Amenable groupoids, (preprint).

R. Archbold and J. Spielberg, Topologically free actions and ideals in discrete dynamical systems, Proc. Edinburgh Math. Soc. 37 (1993), 119-124.

T. Bates, D. Pask, I. Raeburn and W. Szymanski, The $`C^{}`$-algebras of row-finite graphs, (preprint).

B. Brenken, $`C^{}`$-algebras of infinite graphs and Cuntz-Krieger algebras, (preprint).

J. Cuntz, A class of $`C^{}`$-algebras and topological Markov chains II: Reducible chains and the Ext-functor for $`C^{}`$-algebras, Invent. Math. 63 (1981), 25-40.

J. Cuntz and W. Krieger, A class of $`C^{}`$-algebras and topological Markov chains, Invent. Math. 56 (1980), 251-268.

D. Drinen and M. Tomforde, The $`C^{}`$-algebras of arbitrary graphs, preprint.

R. Exel and M. Laca, Cuntz-Krieger algebras for infinite matrices, J. reine angew. Math. 512 (1999), 119-172.

N. Fowler, M. Laca and I. Raeburn,The $`C^{}`$-algebras of infinite graphs, Proc. Amer. Math. Soc. 8 (2000), 2319-2327.

P.J. Higgins, The fundamental groupoid of a graph of groups, J. London Math. Soc. (2) 13 (1976), 145-149.

J.L. Kelley, General Topology van Nostrand, New York, 1955.

A. Kumjian, D. Pask, I. Raeburn and J. Renault, Graphs, groupoids and Cuntz-Krieger algebras, J. Funct. Anal. (), .

A. Kumjian, D. Pask and I. Raeburn, Cuntz-Krieger algebras of directed graphs, Pacific J. Math. 184 (1998), 161-174.

A. Kumjian and D. Pask, $`C^{}`$-algebras of directed graphs and group actions, Ergodic Theory & Dyn. Sys. 19 (1999), 1503-1519.

M. Laca and J. Spielberg, Purely infinite $`C^{}`$-algebras from boundary actions of discrete groups, J. reine angew. Math. 480 (1996), 125-139.

P. Muhly, J. Renault and D. Williams, Equivalence and isomorphism for groupoid $`C^{}`$-algebras, J. Operator Theory 17 (1987), 3-22.

J. Quigg, Discrete $`C^{}`$-coactions and $`C^{}`$-algebraic bundles, J. Austral. Math. Soc. (Series A) 60 (1996), 204-221.

J. Quigg and N. Sieben, $`C^{}`$-actions of $`r`$-discrete groupoids and inverse semigroups, (preprint).

I. Raeburn and W. Szymanski, Cuntz-Krieger algebras of infinite graphs and matrices, preprint.

J. Renault, A Groupoid Approach to $`C^{}`$-algebras, Lecture Notes in Mathematics 793, Springer-Verlag, Berlin, 1980.

J. Serre, Trees, Springer-Verlag, Berlin, 1980.

J. Spielberg, Semiprojectivity for certain purely infinite $`C^{}`$-algebras, (preprint, available at the Front for the Mathematics ArXiv, http://front.math.ucdavis.edu /math.OA/ 0102229).

W. Szymanski and S. Zhang, Infinite simple $`C^{}`$-algebras and reduced crossed products of abelian $`C^{}`$-algebras and free groups, Manuscripta Math. 92 (1997), 487-514.