¹

1 Introduction↩︎

Higher-rank graphs (or \(k\)-graphs) were first described by the author and Kumjian in [3] as a graphical model for the higher-rank Cuntz-Krieger algebras of [4]. The \(C^*\)-algebra associated to a higher-rank graph has attracted wide attention from researchers in operator algebras (see [5]–[10] for example) as they are highly tractable and provide examples of classifiable \(C^*\)-algebras. There is now a growing interest in higher-rank graphs from researchers in algebra (see [11]–[14] amongst others). Lately there has been an interesting investigation of higher-rank graphs from a combinatorial/topological point of view (see [15]–[19] for instance). From this work we now know that a higher-rank graph has a well-defined fundamental groupoid and a topological realisation which has the same fundamental group. The results in the most recent paper [15], has opened many subtle questions about the relationship between ordinary (rank-one) graphs and higher-rank graphs.

For example, the major question addressed in [15] was the embedabilty of a higher-rank graph in its fundamental groupoid. This is always true for ordinary (rank-one) graphs but not for rank-two and higher. The embedability property has an impact on an important structure theorem for the \(C^*\)-algebra of a higher-rank graph: If a connected higher-rank graph \(\Lambda\) embeds in its fundamental groupoid, then the \(C^*\)-algebra \(C^* ( \Sigma )\) of its universal cover \(\Sigma\) is type \(I_0\). Then, under a further technical condition (which holds for rank-one) \(C^* ( \Sigma)\) is Morita equivalent to an abelian \(C^*\)-algebra (see [15]).

As a higher-rank graph with a single vertex is a monoid, it was natural to look for solutions to the embedding problem in the study of monoids embedding in their enveloping group. The author happened upon the work of Mal’cev in [20] and Lambek in [1]. Lambek comes up with a geometric condition called the polyhedral condition (P), see [1]. Condition (P) involves a system of equations derived from a polyhedral graph. See [21] for a good survey of this work. In [2] Johnstone provides a similar construction when looking for more general results for embedding a category in a groupoid. The authors of [15] tried to refine the techniques of [1], [2] to apply them to the embedabilty problem for higher-rank graphs in their fundamental groupoid but ran into technical difficulties, and this work was put aside.

This paper arose from solo work the author undertook after the project [15] was completed. The author took interest in the combinatorial object which parameterises the system of equations used in the work of [1], [2]. In particular, the system of equations (as appears in Lambek’s condition (P)) is reminiscent of the equations for bi-coloured commuting squares in a higher-rank graph. Many examples provided by [1], [22] turn out to define higher-rank graphs of rank \(2\) or \(3\). Not only that, they have trivial fundamental group.

Hence these examples are new instances of higher-rank trees. The main purpose of the first part of this paper is to investigate their graphical properties, as there are relatively few examples of higher-rank trees available (other than standard constructions involving known rank-\(1\) graphs). In the first two-thirds of this paper we produce a new class \(\mathcal{L}_{\mathfrak{P}}\) of higher-rank trees from polyhedral graphs whose properties we can readily compute:

Theorem A: To each non-degenerate polyhedral graph \(\mathfrak{P}=(P,A)\) we construct a higher-rank tree \(T \in \mathcal{L}_{\mathfrak{P}}\) which

1. has a \(1\)-skeleton \(\operatorname{Sk}_T\) which is is planar and satisfies \(| \operatorname{Sk}_T^1 | - 2 | \operatorname{Sk}_T^0 | +4 = 0\);

2. is connected, singly connected, locally convex and acyclic, that is \(H_i (T)=0\) for \(i \ge 1\);

3. embeds in its fundamental groupoid and up to quasi-isomorphism, has rank \(2,3,4\).

A long-term reason for wanting to find out more about such objects lies in the study of totally disconnected locally compact (tdlc) simple groups, where automorphism groups of (one-dimensional, homogeneous) trees play an important role (see [23]). This paper therefore is part of an ambition to produce new examples of simple tdlc. We begin to explore this possiblility, with a potential example, in section 7.

In this manuscript we begin in section 2 by accumulating some background material and notation for higher-rank graphs, in particular their description in terms of coloured directed graphs with a collection of bi-coloured commuting squares describing their defining relations.

In section 3 we begin the construction of the combinatorial object used in [1], [2]. In particular, for each polyhedral graph appearing in their methods, they parameterise a system of equations indexed by half-lines. Johnstone then constructs a directed graph \(E\), called a quadrangle club, so-called as it is built out of directed squares. The system of equations (the Lambek half-arc equations) in question is then parameterised by subgraphs with four vertices and edges, called quadrangles. In section 4 we show that this system of equations could be coloured in the same way that the bi-coloured commuting squares in the 1-skeleton associated to a higher-rank graph are coloured. This computation is facilitated by the fact quadrangle club graph consists of bi-coloured square subgraphs and so is bipartite. Furthermore, this set of bi-coloured commuting squares \(\mathcal{C}\) coming from a convex polyhedron is complete, and so gives rise to a higher-rank graph \(\Lambda_{E,\mathcal{C}}\), see Theorem 27. Since the convex polyhedron is planar, this means that the dimension of resulting the higher-rank graph lies between two and four by the celebrated four-color theorem (see [24]–[26]). Furthermore, some basic graph theory allows us to characterise which polyhedral graphs give rise to rank-\(2\) graphs (see Proposition 24).

The results in [16] show that higher-rank graphs have a topological realisation which is consistent with their fundamental group, as defined in [18]. Since the higher-rank graphs we have constructed begin their life as a graph embedded in a sphere, it would then be natural to suppose that the fundamental group of these new higher-rank graphs is trivial. We conjecture that, under a certain non-degeneracy condition, all planar higher-rank trees we have constructed have dimension less than or equal to four.

In section 5 we address the question of computing the fundamental group of \(\Lambda_{E,\mathcal{C}}\). To compute the fundamental group of a higher-rank graphs, we use the techniques of [27] which begins with the computation of a maximal spanning tree of the underlying \(1\)-skeleton \(E\). In section 5.1 we produce an algorithm for doing this which is weighted towards edges appearing on the left of the bi-coloured commuting squares (for demonstrative reasons only, see Examples 8). We then apply [27] to produce a presentation of the fundamental group and argue that it is trivial by systematically showing all the generators of the group are trivial (see Theorem 31). This computation is facilitated by the fact that all paths in the quadrangle club are at most length two. Finally, we use the results of [15], to show in Corollary 34 that these new planar higher-rank graphs embed in their fundamental groupoid.

Finally, moving away from the class \(\mathcal{L}_{\mathfrak{P}}\), we provide what the author believes are three good reasons for studying finite higher-rank trees from a purely graphical perspective. These reasons are interesting because they are examples where the higher dimensional behaviour varies from the familiar one dimensional behaviour.

First, a rank-\(1\) tree is planar, however is is possible to find (in dimension greater than three) a higher rank tree which is not planar.

Second, it is well-known that a rank-\(1\) tree does not admit a (fixed-point) free automorphism of order three. However, for a higher-rank tree of higher dimension, the underlying category is not a free category, so there can be cycles (albeit trivial in the fundamental group). We give an example of a rank-\(2\) planar tree which admits a (fixed-point) free automorphism of order \(3\).

Third, it is well-known that a rank-\(1\) tree with an odd number of vertices always has a (fixed-point free) automorphism. We give an example of a planar higher-rank tree with an odd number of vertices which has no automorphisms.

We finish by giving classes of examples of higher-rank trees which are already in the literature. The most important of which are the \(\Omega_{k,m}\) graphs whose properties we summarise:

Theorem B: To each integer \(k \ge 1\) and number \(0 \neq m \in \mathbb{N}^k\) there is a higher rank tree \(\Omega_{k,m}\) which

1. is planar if \(k=2\), or \(k=3\) and \(m=(1,1,1)\);

2. does not belong to \(\mathcal{L}_{\mathfrak{P}}\);

3. is connected, singly connected, locally convex and acyclic, that is \(H_i ( \Omega_{k,m} ) =0\) for \(i \ge 1\);

4. has rank \(k\) and embeds in its fundamental groupoid.

The author would like to thank the other authors of [15] for stimulating conversations about the embedding of higher-rank graphs in their fundamental groupoid, in particular the examples which stimulated his interest in studying them more deeply in this manuscript.

2 Background↩︎

Let \(k \ge 1\) and \(\mathbb{N}^k\) denote the free abelian monoid with generators \(\{ \varepsilon_i : 1 \le i \le k \}\). Let \(\le\) be the usual coordinatewise order on \(\mathbb{N}^k\). For \(m,n\in \mathbb{N}^k\), we write \(m \vee n\) for their coordinate-wise maximum and \(m \wedge n\) for their coordinatewise minimum. We write \(\mathbf{1}_k\) or just \(\mathbf{1}\) for \((1, \ldots , 1) \in \mathbb{N}^k\). A directed graph is a quadruple \(E=(E^0,E^1,r,s)\) consisting of finitely many vertices \(E^0\) and edges \(E^1\) whose direction is given by the maps \(r,s : E^1 \to E^0\). The sets \(E^n\), \(n \ge 0\) denote the collection of paths of length \(n\) in \(E\). The set of finite paths, \(E^* = \cup_{n \ge 0} E^n\) forms a category with the roles of the range and source maps interchanged.

2.1 Coloured graphs↩︎

We briefly review the definitions given in [28] which themselves have been tailored for connections with higher-rank graphs: For \(k \ge 1\), a \(k\)-coloured graph \(E=(E^0,E^1,r,s)\) is a directed graph along with a colour map \(c_E : E^1 \to \{c_1,\dots,c_k\}\). By considering \(\{c_1,\dots , c_k\}\) as generators of the free group \(\mathbb{F}_k\), we extend \(c_E:E^* \setminus E^0 \to \mathbb{F}_k^+\) by \(c_E (\mu_1 \cdots \mu_n)=c_E (\mu_1)c_E (\mu_2) \cdots c_E (\mu_n)\). We will drop the subscript from \(c_E\) if there is no risk of confusion. For \(k\)-coloured directed graphs \(E\) and \(F\), a coloured-graph morphism \(\phi: F \to E\) is a graph morphism satisfying \(c_E \circ \phi^1 = c_F\).

One may represent a square \(\phi\) as a labelled version of \((E_{2,(\varepsilon_i+\varepsilon_j)},c_E)\). For instance the \(2\)-coloured graph below on the left has only one square \(\phi\), shown to its right, given by \(\phi(n) = v\) for all \(n \in E_{2,{(\varepsilon_1+\varepsilon_2)}}^0\), \(\phi( f_1^0) = \phi( f_1^{\varepsilon_2}) = e\) and \(\phi( f_2^0 ) = \phi( f_2^{\varepsilon_1} ) = f\). \[\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/shuoyqdn.png}\label{epqfjgyz}\end{figure}\tag{1}\]

Let \(\mathcal{C}_E = \{ \phi : (E_{k,\varepsilon_i+\varepsilon_j} ,c_E)\to (E,c_E') : 1 \le i \neq j \le k \}\) denote the collection of squares in a \(k\)-coloured graph \((E,c_E)\).

2.2 Higher-rank graphs↩︎

A higher-rank graph (or a rank-\(k\) graph) is a countable category \(\Lambda\) with a degree functor \(d:\Lambda \to \mathbb{N}^k\), \(k \ge 1\), satisfying the factorisation property: if \(\lambda\in\Lambda\) and \(m,n\in\mathbb{N}^k\) are such that \(d(\lambda)=m+n\), then there are unique \(\mu,\nu \in \Lambda\) with \(d(\mu)=m\), \(d(\nu)=n\) and \(\lambda=\mu\nu\).

Given \(m \in \mathbb{N}^k\) we define \(\Lambda^m := d^{-1}(m)\). Following [18], for \(v,w \in \Lambda^0\) and \(F \subseteq \Lambda\) define \(vF := r^{-1}(v) \cap F\), \(Fw := s^{-1}(w) \cap F\), and \(vFw := vF \cap Fw\). If \(V \subset \Lambda^0\), then \(V\Lambda = r^{-1} (V)\) and \(\Lambda V = s^{-1} (V)\).

The factorisation property allows us to identify \(\Lambda^0\) with \(\operatorname{Obj}(\Lambda)\), and we call its elements vertices. A vertex \(v \in \Lambda^0\) is a sink if \(s^{-1} (v) = \emptyset\), a vertex \(w \in \Lambda^0\) is a source if \(r^{-1} (w) = \emptyset\). By the factorisation property, for each \(\lambda\in\Lambda\) and \(m \leq n \leq d(\lambda)\), we may write \(\lambda=\lambda'\lambda''\lambda'''\), where \(d(\lambda')=m, d(\lambda'') = n-m\) and \(d(\lambda'')=d(\lambda)-n\); then \(\lambda (m,n) :=\lambda''\). For more information about higher-rank graphs see [29], [30] for example.

We define the \(1\)-skeleton of a \(k\)-graph \(\Lambda\) to be the \(k\)-coloured graph \((\operatorname{Sk}_\Lambda,c)\) given by \(\operatorname{Sk}_\Lambda^0 = \operatorname{Obj}(\Lambda)\), \(\operatorname{Sk}_\Lambda^1 = \bigcup_{i\leq k}\Lambda^{\varepsilon_i}\), with range and source as in \(\Lambda\). The colouring map \(c : \operatorname{Sk}_\Lambda^1 \to \{c_1,\dots,c_k\}\) is given by \(c(f) = c_i\) if and only if \(f \in \Lambda^{\varepsilon_i}\). The \(1\)-skeleton \((\operatorname{Sk}_\Lambda,c)\) comes with a canonical set of squares \(\mathcal{C}_\Lambda := \{\phi_\lambda : \lambda \in \Lambda^{\varepsilon_i+\varepsilon_j}: i \neq j \leq k \}\), where \(\phi_\lambda : E_{k,\varepsilon_i+\varepsilon_j} \to \operatorname{Sk}_\Lambda\) is given by \(\phi_\lambda(\varepsilon_\ell^{n}) = \lambda(n,n+\varepsilon_\ell)\) for each \(n \leq \varepsilon_i+\varepsilon_j\) and \(\ell = i,j\). The collection \(\mathcal{C}_\Lambda\) is complete by [28].

A quasi-morphism from a rank-\(k\) graph \(( \Omega , d_\Omega )\) to a rank-\(\ell\) graph \(( \Lambda , d_\Lambda )\) is a pair \(( \phi , f)\) consisting of a functor \(\phi : \Omega \to \Lambda\) and a homomorphism \(f: \mathbb{N}^k \to \mathbb{N}^\ell\) such that \(d_\Lambda \circ \phi = f \circ d_\Omega\).

The locally convex condition ensures that the range of the degree map \(d : \Lambda \to \mathbb{N}^k\) is a convex set of \(\mathbb{N}^k\).

Standing assumption: We shall assume that all \(k\)-graphs in this manuscript are locally convex.

For a locally convex \(k\)-graph \(\Lambda\) and \(m \in \mathbb{N}^k\), we write \[\Lambda^{\leq m} := \{ \lambda \in \Lambda : d(\lambda) \leq m \text{ and } s ( \lambda ) \Lambda^{\varepsilon_i} = \emptyset \text{ whenever } d (\lambda ) + \varepsilon_i \leq m \} .\]

Note that \(\Lambda^{\le 0} = \Lambda^0\).

Every rank-\(k\) graph \(\Lambda\) has a fundamental groupoid, defined as follows (see [31] or [18]). The following definitions come from [15]:

The assignment \(\Lambda \mapsto \Pi (\Lambda)\) is a functor from \(k\)-graphs to groupoids. Note that \(\Pi(\Lambda)\) is denoted \(\mathcal{G}(\Lambda)\) in [18]. Each \(k\)-graph also has a fundamental group; the standard definition, for connected rank-\(k\) graphs, is as any one of the isotropy groups of its fundamental groupoid, as follows.

2.3 Gluing higher-rank graphs↩︎

There are results about gluing higher-rank graphs in written in categorical terminology in [17]. Since we are using coloured graphs with bi-coloured commuting squares to model higher-rank graphs exclusively here, we pause briefly here to give these results from a coloured graph perspective.

Let \((E,c)\) be a \(k\)-coloured graph with squares \(\mathcal{C}\). Suppose that \(\sim_1\) is an equivalence relation on \(E^0 \sqcup E^1\) with the following property:

The following is an analogue of [17].

Conversely we may “cut-off" hereditary and cohereditary locally convex subgraphs from a \(k\)-coloured graph.

3 Quadrangle clubs built from polyhedral graphs↩︎

3.1 Convex polyhedra and polyhedral graphs↩︎

Roughly speaking, a convex polyhedron and a polyhedral graph are one and the same thing, but in a different place. The first of which is an undirected graph embedded in the sphere and the second is a planar graph derived from the former by stereographic projection (clearly this process is reversible). If the graph embedded in the sphere is a tiling of the sphere, then it is called a spherical polyhedron.

In the diagram below we have the convex polyhedron with points \(v_1,v_2\) on the equator together with arcs \(a_0\) round the left equator, \(a_2\) round the right equator and \(a_1\) round the south pole. This is a spherical polyhedron and maps via stereographic projection to the polyhedral graph, \(C_2\), shown on the right. \[\tag{7} \begin{array}{l} \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/ixuftmhc.png}\tag{8}\end{figure} \end{array}\]

Our starting point is, as in [1], a convex polyhedron \(\mathfrak{P}=(P,A)\) (called Eulerian in [1]) described by finite sets of points and arcs \((P, A)\), inscribed on the sphere \(S^2\). Since the graph is embedded on a sphere there is no distinction between the bounded faces and the unbounded face of the graph. So the set \(P\) is a finite set \(p\) of points on the sphere, and \(A\) is a collection of mutually disjoint subsets \(a\) of \(S^2 \setminus P\), called arcs. Each arc is homeomorphic to the interval \((0,1)\) such that for each \(a \in A\) there are distinct \(r(a), s(a) \in P\) such that \(\overline{a} = a \cup \{r(a), s(a)\}\) (that is \(\mathfrak{P}\) has no loops/cycles), and no other arc \(b \neq a\) satisfies \(\overline{b}=b \cup \{r(a), s(a)\}\) (that is \(\mathfrak{P}\) has no parallel edges). Hence we may identify \(A\) with \(\{ (v,w) \in P^2 : r(a) =v \neq w=s(a) \text{ some } a \in A \}\). For each \(a \in A\) the points \(r(a), s(a) \in P\) are said to be neighbours. The interior of each arc contains no vertex and no point of an other arc (that is \(\mathfrak{P}\) is planar). The valency (or degree) \(d_{\mathfrak{P}} (v)\) of a point \(v \in P\) in the graph \(\mathfrak{P}=(P,A)\) is the number of neighbours of \(v\).

The complement of \(\cup_{p\in P} p \cup \bigcup_{a \in A} a\) on the sphere then consists of \(|A| - |P| + 2\) distinct open sets which we call the faces. We write \(F\) for the set of faces and typically denote its elements by \(f\). By hypothesis we have the following three adjacencies: an arc \(a\) is adjacent to a face \(f\) if \(a \subseteq \overline{f}\), an arc \(a\) is adjacent to a point \(p\) if \(p \in \overline{a}\), and a point \(p\) is adjacent to a face \(f\) if \(p \in \overline{f}\).

Standing assumption: We assume that \(\mathfrak{P}\) is connected, and that every point is adjacent to two arcs (that is \(\mathfrak{P}\) has no sinks/sources). For more information on planar graphs see [32].

We shall need to use some of the methods of Johnstone [2] found in his paper on embeddings of categories in a groupoid. Since we will not require the full generality of Johnstone’s set up, we describe a specific arrangement which he calls a quadrangle club, which arises from a Lambek diagram as in [1]. The specific quadrangle clubs we consider are the ones described in [2].

3.2 Quadrangle clubs and half-arc Lambek conditions↩︎

Johnstone’s method for constructing a quadrangle club involves placing a vertex in the middle of each arc to produce two half-arcs: For each arc \(a\) in the convex polyhedron, this produces two half arcs called \((r(a),a)\) and \((a,s(a))\) by dividing the arc \(a\) in two, with “midpoint" labelled \(a\). Each half-arc maintains the face-adjacency (\(L=\) Left,\(R=\) right) of \(a\), that is \(L((r(a),a) = L(a)= L((a,s(a))\) and \(R((r(a),a) = R(a) = R((a,s(a))\)(see 10 ).

Note that \(E\) is a directed graph with \(E^3 = \emptyset\), that is there are no paths of length three in \(E\). Our standing assumption entails that \(E\) has no cycles/loops, parallel edges or sources/sinks.

Following [2] we have:

Each arc \(a \in A\) gives rise to two quadrangles \(q_{ar}\) and \(q_{al}\), from its two half-arcs as follows:

• Consists of the vertices \(r(a), a , L(a), R(a)\), where \(L(a)\) and \(R(a)\) are the two faces to which the arc \(a\) is adjacent. Here we let \(L(a), R(a)\) be determined by the orientation of the sphere. Another choice would give different directions. The four edges in the quadrangle connect these vertices as shown to the right below.

• Consists of the vertices \(s(a), a, L(a), R(a)\). The four edges in the quadrangle connect these vertices as shown to the left below.

\[\tag{10} \begin{array}{ll} &\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/kcwfhjuy.png}\tag{11}\end{figure} \\ \end{array}\]

4 The higher-rank graph \(\Lambda_{E,\mathcal{C}}\) built from the Lambek quadrangle club \(E\) defined from a polyhedral graph \(\mathfrak{P}=(P,A)\)↩︎

In the last section we showed how to associate a Lambek quadrangle club, a directed graph \(E\), to a polyhedral graph \(\mathfrak{P}=(P,A)\). Then we showed how to colour the natural equations coming from the quadrangles so that \(E\) becomes a coloured graph \((E,c)\). In this section we show that this coloured graph has all the requisite properties to become a higher-rank graph \(\Lambda_{E,\mathcal{C}}\) where \(\mathcal{C}\) are the commuting squares given by the coloured quadrangles.

4.1 Colouring the Lambek quadrangle club↩︎

Here the idea is to colour the edges of Lambek quadrangle club \(E\) so that the Lambek half-arc equations 12 , 13 colour the squares of \(E\) to form a coloured graph with a complete set of squares in the sense of Definition 2. This will enable us to produce a higher-rank graph using [28] as we had set out to do.

To create the necessary complete set of squares in \(E\), we colour the edges occurring in the half arc Lambek conditions 12 13 . Thus creating coloured commuting squares in the sense of [28]. In particular, we must assign edges on opposite sides of the square in 12 , 13 the same colour. For certain types of polyhedral graph, this turns out to be particularly easy:

We thank the contributors to Math.Stackexchange for directing us to a proof which otherwise we could not cite (see [35]).

General colouring algorithm:↩︎

First check if every vertex in the polyhedral graph has even degree, then by Proposition 24 we know that the plane can be coloured by two colours, and proceed by the method suggested there. It is known that there is no polynomial-time algorithm for determining if a planar graph is \(3\)-colourable. Observe that if a planar polyhedral graph is \(2\)-colourable, then its dual is not necessarily \(2\)-colourable, see 7 .

Since \(\mathfrak{P}= (P,A)\) is planar we know by [24]–[26] that we need at most \(4\) colours. Let \(R = \{ r_1 , \ldots , r_n \}\) be the regions within \(\mathfrak{P}\) and fix a colouring function \(c : R \to \{ c_1 , c_2 , c_3 , c_4 \}\) such that for each region/face \(f_k\) of \(\mathfrak{P}\) such that no two adjacent regions have the same colour.

4.2 The coloured Lambek quadrangle club \((E,c)\)↩︎

Following section ¿sec:sec:coloring-alg?, we know that \((E,c)\) is a \(k\)-coloured graph, \(2 \le k \le 4\). Let \(Q = \{ q_{ar} , q_{al} : a \in A \}\) be the collection of quadrangles in \(E\), with associated bi-coloured commuting squares given by the half-arc Lambek conditions. Each quadrangle gives rise to a bi-coloured square in the coloured graph \((E,c)\): For instance, fix \(a \in A\) and consider the quadrangle \[q_{al} = \big( (a,R(a)) , (R(a),r(a)) , (a,L(a)) , (L(a),r(a)) \big)\]

where \((a,R(a)),(L(a),r(a))\) have colour \(c_i\) and \((a,L(a)), (R(a),r(a))\) have colour \(c_j\). Then following section 2.1 and consulting 10 we construct a square \(\phi_{al}\) in \((E,c)\) by defining \(\phi_{al} : ( E_{k,(\varepsilon_i+\varepsilon_j)} , c_E) \to (E,c)\) by \[\begin{align} \phi_{al} (0) &= r(a) , \;\phi_{al} ( \varepsilon_i ) = R(a) , \;\phi_{al} ( \varepsilon_j) = L(a) \text{ and } \phi_{al} ( \varepsilon_i + \varepsilon_j ) = s(a) , \\ \phi_{al} ( f^0_i ) &= (a,R(a)), \;\phi_{al} ( f^{\varepsilon_i}_j ) = (r(a),L(a)), \;\phi_{al} ( f_0^j ) = (a,L(a)) , \;\phi_{al} ( f^{\varepsilon_j}_i ) = (r(a),R(a)) , \end{align}\]

and similarly for a square \(\phi_{ar}\) for the quadrangle \(q_{ar}\). The the set \(\mathcal{C}\) of \(2 |A|\) commuting squares in \((E,c)\) is then \[\label{eq:cs} \mathcal{C}= \{ \phi_{al} , \phi_{ar} : a \in A \} .\tag{23}\]

Recall from Definitions 2, a collection of bi-coloured squares \(\mathcal{C}\) in \((E,c)\) is complete if for each \(i \neq j \leq k\) and \(c_ic_j\)-coloured path \(fg \in E^2\) there is a unique \(c_jc_i\)-coloured path \(g'f'\) with the same range and source such that \((fg, g'f') \in \mathcal{C}\).

5 Computing the Fundamental Group of \(\Lambda_{(E,\mathcal{C})}\)↩︎

We claim that each \(\Lambda_{E,\mathcal{C}}\) is a tree. In order to show that each \(\Lambda_{E,\mathcal{C}}\) is a tree, we must compute its findamentsl group. To do this we plan to apply the results of [27]. In order to use these results, we must first chose a maximal spanning tree for the planar \(1\)-skeleton \(\operatorname{Sk}_{\Lambda_{(E,\mathcal{C})}}=E\) of \(\Lambda_{(E,\mathcal{C})}\). We do this as follows: Let \(\mathfrak{P}=(P,A)\) be a polyhedral graph where \(P=\{ v_1 , \ldots , v_{m} \}\), \(R= \{ r_1 , \ldots , r_{n} \}\), and \(A= \{ a_1 \ldots , a_{m+n-2} \}\), for \(m,n \ge 2\). Let \(E\) its Lambek quadrangle club graph which has \(N=2 |A|+2\) vertices. Fix a colouring \(c : E^1 \to \{ c_1 , \ldots , c_k \}\), \(2 \le k \le 4\). Let \(Q = \{ q_{ar} , q_{al} : a \in A \}\) be the collection of quadrangles, with \(2 |A|\) associated commuting squares \(\mathcal{C}\). Let \(\Lambda_{(E,\mathcal{C})}\) be the associated higher-rank graph. Recall, in a graph with \(n\) vertices, a spanning tree will have \(n-1\) edges. We use a variant of the usual maximal spanning tree algorithm which is greedy for edges on the left side of each Lambek half-arc equation.

5.1 Left-greedy maximal spanning tree algorithm↩︎

1. Assign weights to the edges of \(E\) in such a way that edges of the form \((a,f)\) where \(f=R(a)\) have weight \(2\), edges of the form \((a,f)\) some \(a \in A\) where \(f=R(a)\) have weight \(1\). Edges of the form \((r,v)\) where \(v=r(a)\) some \(a \in A\) where \(r=R(a)\) have weight \(2\) otherwise \((r,v)\) has weight \(1\). Order the edges in \(E^1\) with those of weight \(2\) first and those of weight \(1\) next. Let \(T\) be the set of edges comprising the maximum weight spanning tree. Set \(T = \emptyset\).

2. Add the first edge, in \(E^1\) with weight \(2\) to \(T\).

3. Add the next edge with weight \(2\) to \(T\) if and only if it does not form a cycle in \(T\). If there are no remaining edges of weight \(2\) add the first edge of weight \(1\) which does not form a (n undirected) cycle in \(T\).

4. If \(T\) has \(N-1\) edges stop and output \(T\). Otherwise go to step 3.

Finally, we seek an analog of the formula \(| T^1 | - | T^0| +1 =0\) for \(T\) a finite rank-\(1\) tree. We can get such a formula for members of \(\mathcal{L}_{\mathfrak{P}}\)

6 Differences from one-dimensional trees↩︎

The purpose of this section is to show that, since higher-rank graphs are not free categories, then it is possible to have a higher-rank tree with properties different to a rank-\(1\) tree.

Fact 1. A rank-\(1\) tree is bipartite with no cycles, so by the \(4\)-colour theorem it is planar.

The same is not true of higher-rank trees.

Fact 2. Let \(\Lambda\) be a rank-\(1\) tree. Then \(\Lambda\) does not admit a fixed point free automorphism of order three.

The same is not true of higher-rank trees.

Using the techniques developed in section 2.3 one may glue three locally convex, planar rank-\(2\) trees together to produce a new locally convex, planar rank-\(2\) tree which has an automorphism of order three which admits no fixed points. Indeed, the reader will see that the construction given easily generalises.

Fact 3. Let \(\Lambda\) be a rank-\(1\) tree with an odd number of vertices. The \(\Lambda\) admits a fixed point free automorphism.

The same is not true of higher-rank trees.

7 Tailpiece↩︎

Many examples of higher-rank trees we have covered in the above text have sources and/or sinks on the outside of the main body of their skeleton. See 31 , 29 , 27 , 25 , 21 . Some of these graphs may be glued together at sources as we saw with 29 , 27 ; here we glued them together in a circuit using the two sources on the outside of 29 . Some of these graphs, typically members of \(\mathcal{L}_{\mathfrak{P}}\) which have sinks on the outside as with 21 . Again, we can glue them together in a circuit, however we can also glue them in place of the edges in a 2-regular tree \(T_2\) as shown below. \[\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/byxuetdn.png}\label{abvglwny}\end{figure}\tag{33}\]

The automorphism group of the above graph contains the automorphism group of \(T_2\), plus an internal symmetry \(\mathbb{Z} / 2 \mathbb{Z}\) for each of the diamonds substituted for each edge.

Let \(\gamma,\delta \in \Lambda^{\le n}\) and consider \(\Sigma_{\alpha,\beta} \cap \Sigma_{\gamma,\delta}\). If \(n \le m\) then is nonempty unless \(\gamma = \alpha \alpha'\) and \(\delta = \beta \beta'\) in which case \(\Sigma={\alpha,\beta} \cap \Sigma_{\alpha\alpha',\beta\beta'} = \Sigma_{\alpha,\beta}\). Conversely, in the case \(m \le n\) we have \(\alpha = \gamma \gamma'\) and \(\beta = \delta \delta'\) we have \(\Sigma_{\gamma \gamma',\beta \beta'} \cap \Sigma_{\gamma ,\delta} = \Sigma_{\gamma,\delta}\). Suppose \(m,n\) are incomparable and \(g \in \Sigma_{\alpha,\beta} \cap \Sigma_{\gamma,\delta}\). Let \(t = m \wedge n\) then by the factorisation property we have \[g ( \alpha (0,t) ) = g ( \beta (0,t) ) \text{ from } \Sigma_{\alpha,\beta} \text{ and } g ( \gamma (0,t) ) = g ( \delta (0,t) ) \text{ from } \Sigma_{\gamma,\delta} .\]

Hence \(g \in \Sigma_{\alpha(0,t),\beta(0,t)}\) and \(g \in \Sigma_{\gamma(0,t),\delta(0,t)}\). Arguing as before, we can only have a nonempty intersection if \(\gamma (0,t) = \mu \nu\) and \(\alpha (0,t) = \mu \nu'\), similarly \(\delta (0,t) = \kappa \nu''\) and \(\beta (0,t) = \kappa \nu'''\), so \(\Sigma_{\alpha,\beta} \cap \Sigma_{\gamma,\delta} = \Sigma_{\mu,\kappa}\). The above calculations show that \(\{ \Sigma_{\alpha,\beta} : \alpha ,\beta \in \Lambda^{\le m} \}\) form a basis for a topology on \(\Gamma\).

References↩︎

---

1. This research was supported by ARC Discovery Projects Grant 200100155↩︎