Groupoids and Graphs

From CanisiusmathWiki

I found this article about Graphs, Groupoids, and Cuntz-Krieger Algebras by Kumjian, et al: [1] (http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJJ-45M2WD1-30&_user=604742&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000031198&_version=1&_urlVersion=0&_userid=604742&md5=52f806e7386b6be6197411081ab591d0)

It gives some nice, mathy definitions on the construction of a groupoid from a directed graph, and goes on to do many more impressive things.

Table of contents

1 Elementary Necessary Background Definitions

2 Group Actions on Graphs

3 Cayley Graphs and Groupoid Graphs

4 Constructing Graphs From Transformation Groupoids of Non-Abelian Groups Under The Action of Conjugation - A Picture Gallery

5 Further Thoughts

6 Papers Resulting From This Project

[edit]

Elementary Necessary Background Definitions

Hilbert Space (http://en.wikipedia.org/wiki/Hilbert_space) - an inner product space that is complete under the norm defined by the inner product. A finite-dimensional inner product space is a Euclidean space, and it is a Hilbert space.

Banach Space (http://en.wikipedia.org/wiki/Banach_space) - a complete, normed vector space. Every Hilbert space is a Banach space, but not every Banach space is a Hilbert space, since a Banach space need not have an inner product.

Algebra (http://en.wikipedia.org/wiki/Algebra_over_a_field) - a vector space with a multiplication operation, under which distributive properties hold, as well multiplication by scalars.

Associative Algebra (http://en.wikipedia.org/wiki/Associative_algebra) - an algebra in which the multiplication operation is associative.

Banach Algebra (http://en.wikipedia.org/wiki/Banach_algebra)- an associative algebra over the real or complex numbers that is also a Banach space. The vector multiplication operation and the Banach space norm must satisfy the property: $\forall x, y \in A , \|x \, y\| \ \leq \|x \| \, \| y\|$ .

*-ring and *-algebra (http://en.wikipedia.org/wiki/Star-algebra) - a *-ring is an associative ring with an involution map (http://en.wikipedia.org/wiki/Involution) denoted by *. A *-algebra is a *-ring that is an associative algebra over another *-ring.

Banach *-algebra - a Banach algebra over $\mathbb{C}$ that is a *-algebra.

B*-algebra (http://en.wikipedia.org/wiki/B%2A-algebra) - a B*-algebra is a Banach algebra over $\mathbb{C}$ , with the involution map * satisfying $| | x * | | = | | x | |$ . Another definition is that a B*-algebra is a Banach *-algebra for which the above property relating the norm to the involution map holds.

C*-algebra (http://en.wikipedia.org/wiki/C%2A-algebra) - a B*-algebra with the added condition that $\|x^* x \| = \|x\|^2$ for all x in the algebra. Some simple examples of C*-algebras include $C (X)$ (the set of continuous functions on a compact space $X$ with pointwise multiplication) and $M_n(\mathbb{C})$ (the set of all $n\times n$ complex-valued matrices).

Separable space (http://en.wikipedia.org/wiki/Separable_space) - a topological space that contains a countable dense subset; i.e., a set with a countable number of elements whose closure is the entire space. A Hilbert space is separable if and only if it has a countable orthonormal basis.

Simple algebra (http://en.wikipedia.org/wiki/Simple_algebra) - an algebra with no non-trivial two-sided ideals, and in which the set of products of elements in the algebra is non-trivial.

Purely infinite - (taken from Blanchard and Kirchberg, who took it from Kirchberg and Rordam) A C*-algebra A is said to be purely infinite if and only if:

(i) for every pair of positive elements $a,b\in A_+$ such that b lies in the closed two-sided ideal span (AaA) generated by a and every $ε > 0$ there exists an element $d\in A$ such that $| | b - d * a d | | < ε$ , and

(ii) there is no non-zero character on A.

(iii) There are other characterizations available, but this is a rather nontrivial concept.

Cuntz algebra (http://en.wikipedia.org/wiki/Cuntz_algebra) - is a kind of a separable, simple, purely infinite C*-algebra. It is defined by certain generators and relations. I will come back to define this more carefully at a future instance.

[edit]

Group Actions on Graphs

I found this article. It seems to contain some nice, basic information on how groups could act on graphs, and it seems very readable (at least the parts I've read): Group Actions on Graphs, Maps, and Surface with Maximum Symmetry (http://www.math.auckland.ac.nz/~conder/preprints/GroupActions.pdf).

The author of this article has done a lot of work with 1/2-transitive group actions: Finite Graphs of Valency 4 and Girth 4 Admitting Half-Transitive Group Actions, by Dragan Marusic (http://www.austms.org.au/Publ/Jamsa/V73P2/pdf/y15.pdf)

Definitions:

Vertex-Transitive Graph (http://mathworld.wolfram.com/Vertex-TransitiveGraph.html) - A graph such that every pair of vertices is equivalent under some element of the automorphism group of the vertex set. More explicitly, a vertex-transitive graph is a graph whose automorphism group is transitive. Informally speaking, a graph is vertex-transitive if every vertex has the same local environment, so that no vertex can be distinguished from any other based on the vertices and edges surrounding it.

Edge-Transitive Graph (http://mathworld.wolfram.com/Edge-TransitiveGraph.html) - A graph such that any two edges are equivalent under some element of its automorphism group. More precisely, a graph is edge-transitive if for all pairs of edges $(e 1, e 2)$ there exists an element $γ$ of the edge automorphism group $A u t * (G)$ such that $γ(e 1) = e 2$ . Informally speaking, a graph is edge-transitive if every edge has the same local environment, so that no edge can be distinguished from any other based on the vertices and edges surrounding it.

Arc-Transitive Graph (http://en.wikipedia.org/wiki/Arc-transitive_graph) - A graph G such that, given any two edges e₁ = u₁v₁ and e₂ = u₂v₂ of G, there are two automorphisms

f : G → G, g : G → G

such that

f (e₁) = e₂, g (e₁) = e₂

and

f (u₁) = u₂, f (v₁) = v₂,

g (u₁) = v₂, g (v₁) = u₂.

In other words, a graph is arc-transitive if its automorphism group acts transitively upon its arcs.

More generally, a graph is called s-arc-transitive (or sometimes simply "s-transitive") with $s\geq 1$ if it has an s-route and if there is always a graph automorphism of G sending each s-route onto any other s-route.

A graph is half-transitive if its automorphism group acts transitively on its vertex set and edge set, but not on its arc set.

[edit]

Cayley Graphs and Groupoid Graphs

I was unable to find a published manner of creating a graph out of a groupoid, except in the natural way of using the base set as the vertices and using the source and target maps on the morphisms to make them directed edges. This will often create a multigraph with multiple loops.

Using this idea of creating a graph from a groupoid, you can show that given a group $G$ and an alphabet $A$ of generators, it is possible to create a groupoid that yields a graph isomorphic to the Cayley graph $C a y (G, A)$ .

Recall that $C a y (G, A)$ has vertex set $V = G$ and edge set $E=\{(x,ax):x\in G, a\in A\}$ .

Consider the transformation groupoid $\mathcal{G}$ formed by $G$ acting on itself by left multiplication.

That is, $\mathcal{G} = G\times G$ , with source map s $(g 1, g 2) = g 2$ and target map t $(g_1,g_2) = g_1\cdot g_2 = g_1g_2$ , since in this case the group action is left multiplication.

Construct the graph with vertex set $V_{\mathcal{G}}=\mathcal{G}^{(0)}$ and whose edge set is a subset of the groupoid, namely $E_{\mathcal{G}}=\{(a,g)\in \mathcal{G} : a\in A\}$ .

Claim: The resulting graph, $U(\mathcal{G}, A)$ , is isomorphic to $C a y (G, A)$ .

Proof: Fairly obvious. The graphs have the same vertex set, since $\mathcal{G}^{(0)}=G$ . It is left to show that they have the same edge set. Let $(x, y)$ be an edge in $C a y (G, A)$ . Then $\exists a\in A$ such that $y = a x$ . Hence, the edge has source $x$ and target $a x$ . This describes a groupoid element $(g 1, g 2)$ with s $(g 1, g 2) = x$ and t $(g 1, g 2) = a x$ . But this implies that $g 2 = x$ and $g 1 = a$ , by the aforementioned definitions of the source and target maps for the groupoid. So the edge $(x, y)$ in $C a y (G, A)$ corresponds to the morphism $(a, x)$ in $\mathcal{G}$ . But $(a,x)\in E_{\mathcal{G}}$ . Hence the edges in $C a y (G, A)$ are in $U(\mathcal{G}, A)$ .

Now suppose $(a,x)\in E_{\mathcal{G}}$ . Then since t $(a, x) = a x$ and s $(a, x) = x$ , the edge directs from the element $x$ to the element $a x$ , which describes the edge $(x, a x)$ , which is an edge in $C a y (G, A)$ .

Therefore, the graphs are isomorphic.

Possible generalizations: Instead of constructing a graph on all of $G$ , we may only want to use a subset $S\subseteq G$ and an alphabet $A\subseteq S$ . Then we construct the edge set $E = \{(s,as) : a\in A, s,as\in S\}$ . Then we still construct $\mathcal{G}$ as the transformation groupoid of $G$ acting on $G$ by left multiplication, but we construct $U(\mathcal{G}, S, A)$ with vertex set $S$ , and edge set $E_{\mathcal{G}}=\{(a,s) : a\in A, s,as\in S\}$ . Then again, $Cay(G,S,A) \cong U(\mathcal{G}, S, A)$ .

[edit]

Constructing Graphs From Transformation Groupoids of Non-Abelian Groups Under The Action of Conjugation - A Picture Gallery

Note: Loops are directed, all other edges are directed in both ways, in order to cut down on the number of directed edges I would have to draw.

The underlying graph of the groupoid of the symmetric group S_3 under conjugation.

The underlying graph of the groupoid of the dihedral group D_4 under conjugation.

The underlying graph of the groupoid of the quaternion group Q_8 under conjugation. Notice that it is isomorphic to D_4, but it is drawn differently to distinguish between the different subgroup structures of the two groups.

[edit]

Further Thoughts

There is a notion of an action in category theory that gives a semi-direct product category. In particular, when both categories are groupoids, the semi-direct product is also a groupoid. These notions are defined in this paper by Ng: Some remarks on groupoids and small categories (http://arxiv.org/abs/0710.3426).

Question for further thought: If we choose groups and construct a semi-direct group product, then make a Cayley graph, is it isomorphic to a graph yielded by creating a semi-direct product of the left regular transformation groupoids of the chosen groups?

To answer this question, it's necessary to figure out whether you can always pick a groupoid action that "mirrors" the group action. In the cases of some group actions this is true. In Ng's examples, he says that a groupoid action by conjugation (inner automorphism) is parallel to the same group action. In what other cases is there a natural correspondence?

Let's look at a couple examples where we can work with the definitions. We are using $α$ and $φ$ as in Definition 4 of Ng.

Example 1: We let $\mathcal{H}$ be the left multiplication transformation groupoid of $\mathbb{Z}_3$ for now, but any $\mathbb{Z}_n$ will work. We let $\mathcal{G}$ be the groupoid of two morphisms on one element. That is, $\mathcal{G}^{(1)}=\{1,T\}$ and $\mathcal{G}^{(0)}=\{\star\}$ . Since $\mathcal{G}$ has only one object, $φ$ is trivial. Hence, $\mathcal{G}\times^{\phi}\mathcal{H} = \mathcal{H}$ .

Let $\alpha_T: (j,i) \mapsto (-j,-i)$ and $\alpha_1: (j,i)\mapsto (j,i)$ . Exercise -- see if this satisfies the 7 conditions listed in Definition 4! Spoiler alert: it does.

Then $\mathcal{H}\times_{\alpha} \mathcal{G} = \{((j,i),a): (j,i)\in \mathcal{H}, a\in\mathcal{G}\}$ . Hence, there are 18 morphisms in $\mathcal{H}\times_{\alpha} \mathcal{G}$ , but just 3 objects in the base set. The new groupoid looks like $\mathcal{H}$ with twice as many arrows.

Example 2: Since Ng already states that conjugation is a groupoid action, we will use it in order to inspect whether it "works" with the group action of conjugation. That is, if we form a group semi-direct product under conjugation, will it correspond to the underlying graph of a semi-direct product groupoid under conjugation?

I computed the simple case of $\mathbb{Z}_2$ acting on $\mathbb{Z}_2$ by conjugation. Obviously in the group setting, the action will be trivial since $\mathbb{Z}_2$ is abelian. Hence, the group semi-direct product simply yields the direct product $\mathbb{Z}_2\times \mathbb{Z}_2$ .

In the groupoid setting, we form $\mathcal{G}$ as the full left multiplication transformation groupoid of $\mathbb{Z}_2$ . The action is accompanied by the trivial map $φ(i) = i$ . Then $\mathcal{G}\times^{\phi}\mathcal{G}=\{(g,h)\in \mathcal{G}\times\mathcal{G}: \bold{s}(g)=\bold{t}(h)=\bold{s}(h)\} = \{((1,1),(0,1)), ((1,0),(0,0)), ((0,0),(0,0)), ((0,1),(0,1))\}$ .

Next, we compute the action:

$α (0,0) (0,0) = (0,0)$ , $α (0,1) (0,1) = (0,1)$ , $α (1,1) (0,1) = (0,0)$ , and $α (1,0) (0,0) = (0,1)$ .

Thus, $\mathcal{G}\times_{\alpha}\mathcal{G} = \{(h,g): \bold{t}(g)=\bold{s}(h)=\bold{t}(h)\} = \{((0,0),(0,0)), ((0,0),(1,1)), ((0,1),(0,1)), ((0,1),(1,0))\}$ .

This means there are only 4 morphisms, 2 of which are identity morphisms. Hence, $\mathcal{G}\times_{\alpha}\mathcal{G}$ is the connected groupoid on 2 elements, and we see that $\mathcal{G}\times_{\alpha}\mathcal{G} \cong \mathcal{G}$ .

Thus, conjugation in the group setting and groupoid setting do not work together well in this case to form semi-direct products.

[edit]

Papers Resulting From This Project

I (Brian) wrote up a short little 5 page job describing the results and possible implications of my work at this REU. Here it is for your viewing pleasure: [2] (http://upload.wikimedia.org/wikipedia/commons/c/c1/Blearygroupoids.pdf)

Retrieved from "http://wiki.canisiusmath.net/index.php?title=Groupoids_and_Graphs"

Groupoids and Graphs

From CanisiusmathWiki

Elementary Necessary Background Definitions

Group Actions on Graphs

Cayley Graphs and Groupoid Graphs

Constructing Graphs From Transformation Groupoids of Non-Abelian Groups Under The Action of Conjugation - A Picture Gallery

Further Thoughts

Papers Resulting From This Project

Views

Personal tools

Navigation

Search

Toolbox