Graph operators on Discrete Groups

Let $G$ be a group and let $S \subset G$ be a set of group elements such that the identity element $I \notin S$ . The Cayley graph associated with $(G,S)$ is the directed graph with one vertex associated to each group element and directed edges $(g,h)$ whenever $g h^{-1} \in S$ .

Consider the graph generated from a group denoted by $G_0$ .

Consider the line graph of it, $L(G_0)$ .

This takes the edges of the original graph and forms vertices from the edges. Then, new edges are added to the vertices given that the intersection of the original edges include shared vertices between the original edges.

We analyze the meaning of $L(G_0)$ in terms of the Cayley graph $G_0$ , and its group operations.

It in effect switches the representations by vertices and edges.

Vertices are given by a pair $(g, h) \text{ s.t. } gh^{-1} \in S$ , and edges represent group elements.

The application of this in data science may be shown when dealing with data that is operated on by operations $g$ within a “group” such as operations that increase the value, decrease the value, etc.

Next: clique operator on Cayley graph $G_0$

We discuss embedding graphs in Cayley graphs.

Let X be a graph with vertex set {1,…,v} and G be a finite group. Consider the construction given by the following. Let $h: V(X) \rightarrow G$ be an assignment of vertices to group elements and let us denote $h(i) = g_i$ . The $g_i$ are not necessarily distinct. Take Y to be the Cayley graph

$Y = X(G, C)$

where

$C = \{ g_i g_j^{-1}: i,j \text{ adjacent in } X \}$ .

Y is connected if and only if each $g \in G$ can be expressed as a product of elements of $C$ or if $C$ is a generating set for $G$ .

Cayley graphs have three distinguishing properties.

(1) Regularity

(2) Connectedness

(3) Homogeneity

Consider constructing a Cayley graph based on a dynamic discrete group, with generators given by moves made by a Markov chain.

Let $\{ P_1, \cdots, P_n \}$ be various transition matrices of markov chains $M_1, \cdots, M_n$ . We can form a group representation of these by letting each $P_i$ be a group operator $g \in G$ .