# Abelian factors in 2-step nilpotent Lie algebras constructed from graphs

Rachelle DeCoste  Rachelle DeCoste, Wheaton College, Norton, MA
<EMAIL_ADDRESS>,  Lisa DeMeyer  Lisa DeMeyer, Central
Michigan University, Mount Pleasant, MI<EMAIL_ADDRESS>,  Meera Mainkar
Meera Mainkar, Central Michigan University, Mount Pleasant, MI
<EMAIL_ADDRESS>and  Allie Ray  Allie Ray, Birmingham-Southern College,
Birmingham, AL<EMAIL_ADDRESS>
###### Abstract.

We consider real 2-step metric nilpotent Lie algebras associated to graphs
with possibly repeated edge labels as constructed by Ray in 2016. We determine
how the structure of the edge labeling within the graph contributes to the
abelian factor in these Lie algebras. Furthermore, we explicitly compute the
abelian factor of the 2-step nilpotent Lie algebras associated with some
families of graphs such as star graphs, cycles, Schreier graphs, and properly
edge-colored graphs. We also study the singularity properties of these Lie
algebras in certain cases.

MSC 2020: Primary: 17B30; Secondary: 05C15, 05C99, 22E25.
Key Words: Nilpotent Lie algebra, Edge-labeled graph, Abelian factor

##  1\. Background

A 2-step nilpotent Lie algebra ${\mathfrak{n}}$ is a Lie algebra where each
Lie bracket $[X,[Y,Z]]=0$ for all elements $X,Y,Z$ of ${\mathfrak{n}}$.
Investigating a 2-step nilpotent Lie algebra with inner product has become the
main tool to study the associated 2-step nilpotent Lie group with left
invariant metric. This research was initiated by Eberlein [9, 10] and Kaplan
[17, 18]. Recently, there has been a lot of interest in investigating the
structure of 2-step nilpotent Lie algebras associated with various type of
graphs. Due to the associated combinatorial structure, these 2-step nilpotent
Lie algebras have proven to be an interesting source of examples in the study
of geometry and dynamics of nilpotent Lie groups, nilmanifolds, infra-
nilmanifolds, solvmanifolds, etc. See, for example [1, 2, 4, 5, 6, 7, 8, 12,
13, 15, 20, 22, 23, 24, 25, 26, 27].

In this paper, we study the structure of real 2-step nilpotent Lie algebras
constructed from connected directed edge-labeled graphs. A first construction
on simple graphs with no repeated edge labels was introduced by S. Dani and
the third author in [6] in order to study Anosov diffeomorphisms of
nilmanifolds. In [7], the first three authors further investigated the
geometry of these constructed Lie algebras with a specific metric. More
specifically, the authors studied the properties of singularity, Heisenberg-
like Lie algebras and closed geodesic density properties on the associated
nilmanifolds.

The construction from [6] was generalized by the fourth author in [27]. They
defined a new 2-step nilpotent Lie algebra construction associated with graphs
(simple or non-simple) with possibly repeated edge labels. These Lie algebras
can be thought of as a quotient of the 2-step nilpotent Lie algebras
associated with simple graphs as in [6]. They also studied the Lie algebras
constructed from Schreier graphs, which are a generalization of Cayley graphs.
This generalized construction was also used in [25] where the authors study
Lie algebras associated with uniform graphs.

One issue that arises with the construction of 2-step nilpotent Lie algebras
from graphs with repeated edge labels is the presence of an abelian factor. By
definition, the center of any 2-step nilpotent Lie algebra contains its
derived algebra. For the Lie algebras constructed from simple graphs with non-
repeated edge labels, the center is equal to its derived algebra. However, if
we allow repeated edge labels, this is not always the case and the size of the
center compared with the size of its derived algebra depends on the structure
of edge labels within the associated graph. The vector space complement of the
derived algebra in the center is called an abelian factor of the 2-step
nilpotent Lie algebra.

In this paper, we consider certain families of graphs with repeated edge
labels and then determine the existence or absence of abelian factors in the
associated 2-step nilpotent Lie algebras. Furthermore, we explicitly describe
their non-trivial abelian factors in terms of the associated graphs. We also
find a basis for the orthogonal complement of the center with respect to the
natural inner product on the 2-step nilpotent Lie algebra arising from certain
families of graphs.

This paper is organized as follows. In Section 2, we introduce and recall the
basic terminology and notation in graph theory and Lie algebras. We also give
a sufficient condition in terms of a graph for the associated 2-step nilpotent
Lie algebra to have a trivial abelian factor. We then consider the families of
star graphs, cycles, and Schreier graphs in Sections 3-5, respectively.
Section 6 includes some applications related to graph coloring. We end with a
discussion of open questions and further research directions, and we would
like to thank the referee for the suggestion of adding this conclusion
section.

##  2\. Preliminaries

Let $G=(V,E,C)$ denote a connected, directed graph with vertex set $V(G)$,
edge set $E(G)$, and edge labeling given by a surjective map
$c:E(G)\rightarrow C(G)=\\{Z_{1},Z_{2},\ldots,Z_{p}\\}$. Note that we will
suppress $G$ if it is understood in context. If the direction of an edge from
a vertex $v$ to a vertex $w$ is relevant, we denote the edge by $(v,w)$.
Otherwise we denote it by $vw$.

######  Definition 2.1.

([27] Remark 3.2-3.3) Given a directed edge-labeled graph $G=(V,E,C)$, we
define a metric 2-step nilpotent Lie algebra ${\mathfrak{n}}_{G}$ in the
following way. First, define the real vector space
${\mathfrak{n}}_{G}={\mathfrak{v}}\oplus{\mathfrak{w}}$ where ${\mathfrak{v}}$
is the span of the vertex set $V(G)$ and ${\mathfrak{w}}$ is the span of the
edge labels $C(G)$. The metric is defined so that $V\cup C$ is an orthonormal
basis for ${\mathfrak{n}}_{G}$. Define the Lie bracket on ${\mathfrak{n}}_{G}$
by:

$[v_{i},v_{j}]=\sum_{\ell=1}^{|C|}(\epsilon_{\ell}-\epsilon^{\prime}_{\ell})Z_{\ell}$

where

$\epsilon_{\ell}=\begin{cases}1&\text{if }c(v_{i},v_{j})=Z_{\ell}\\\
0&otherwise,\end{cases}$

and

$\epsilon^{\prime}_{\ell}=\begin{cases}1&\text{if }c(v_{j},v_{i})=Z_{\ell}\\\
0&otherwise.\end{cases}$

All other brackets not defined by linearity or skew symmetry are zero.

######  Remark 2.2.

Note that with this definition, the derived algebra
$[{\mathfrak{n}}_{G},{\mathfrak{n}}_{G}]={\mathfrak{w}}$. Also note that this
Lie algebra will be 2-step nilpotent as
$[{\mathfrak{n}}_{G},{\mathfrak{n}}_{G}]\subseteq{\mbox{span}}\\{C(G)\\}$ and
thus $[{\mathfrak{n}}_{G},[{\mathfrak{n}}_{G},{\mathfrak{n}}_{G}]]=0$.

######  Example 2.3.

For the graph in Figure 1, the orthonormal basis for the Lie algebra
${\mathfrak{n}}$ using Definition 2.1 would be
$\\{v_{1},v_{2},v_{3},Z_{1},Z_{2}\\}$ with brackets $[v_{1},v_{2}]=Z_{1}$,
$[v_{1},v_{3}]=Z_{2}$, and $[v_{2},v_{3}]=Z_{1}-Z_{2}$. All other brackets not
defined by linearity or skew symmetry are zero.

$v_{3}$$v_{1}$$v_{2}$$Z_{1}$$Z_{1}$$Z_{2}$$Z_{2}$ Figure 1. Directed graph on
3 vertices

To study these 2-step nilpotent metric Lie algebras, we follow the approach in
[9, 17]. Let ${\mathfrak{n}}$ denote a real 2-step nilpotent Lie algebra and
$[{\mathfrak{n}},{\mathfrak{n}}]$ denote its derived algebra. Let
${\mathfrak{v}}$ denote a linear direct summand of
$[{\mathfrak{n}},{\mathfrak{n}}]$ in ${\mathfrak{n}}$, i.e.
${\mathfrak{n}}={\mathfrak{v}}\oplus[{\mathfrak{n}},{\mathfrak{n}}]$. Choose
an inner product $\langle\,,\,\rangle$ on ${\mathfrak{n}}$ such that a basis
of ${\mathfrak{v}}$ together with a basis of $[{\mathfrak{n}},{\mathfrak{n}}]$
forms an orthonormal basis of ${\mathfrak{n}}$. For
$Z\in[{\mathfrak{n}},{\mathfrak{n}}]$, the skew-symmetric operator $j(Z)$ on
${\mathfrak{v}}$ is defined such that for each $X\in{\mathfrak{v}}$, $j(Z)(X)$
is the unique element satisfying

(1) $\displaystyle\langle j(Z)(X),Y\rangle=\langle Z,[X,Y]\rangle\,\,\text{
for all }Y\in{\mathfrak{v}}.$

Note that some authors, such as [9, 17], have defined this operator based on
the center, $\mathcal{Z}({\mathfrak{n}})$. In this case,
${\mathfrak{n}}=\mathcal{V}\oplus\mathcal{Z}({\mathfrak{n}})$ where
$\mathcal{V}=\mathcal{Z}({\mathfrak{n}})^{\perp}$. We instead choose to use
the derived algebra for ease of calculations since the edge labels form a
basis for the derived algebra in our construction.

Let ${\mathfrak{n}}={\mathfrak{v}}\oplus[{\mathfrak{n}},{\mathfrak{n}}]$ as
above. Since ${\mathfrak{n}}$ is 2-step nilpotent,
$[{\mathfrak{n}},{\mathfrak{n}}]$ is contained in the center
$\mathcal{Z}({\mathfrak{n}})$. Then there exists a unique subspace
$\mathfrak{a}$ of ${\mathfrak{v}}$ such that
$\mathcal{Z}({\mathfrak{n}})=[{\mathfrak{n}},{\mathfrak{n}}]\oplus\mathfrak{a}$.
This subspace $\mathfrak{a}$ is known as a _maximal abelian factor of
${\mathfrak{n}}$_ (see [19] for example). We note that $\mathfrak{a}$ depends
on a choice of the direct summand ${\mathfrak{v}}$. Hence,
${\mathfrak{n}}=\mathcal{Z}({\mathfrak{n}})^{\perp}\oplus\mathfrak{a}\oplus[{\mathfrak{n}},{\mathfrak{n}}]$
and
${\mathfrak{v}}=[{\mathfrak{n}},{\mathfrak{n}}]^{\perp}=\mathcal{Z}({\mathfrak{n}})^{\perp}\oplus\mathfrak{a}$.

######  Definition 2.4.

If ${\mathfrak{n}}_{G}$ is a 2-step nilpotent Lie algebra associated with a
directed edge-labeled graph $G=(V,E,C)$ by Definition 2.1, then we have a
canonical choice for ${\mathfrak{v}}$, i.e. ${\mathfrak{v}}$ is the span of
the vertex set $V$. Therefore the corresponding abelian factor $\mathfrak{a}$
is canonically determined to be the unique subspace of ${\mathfrak{v}}$ such
that the center
$\mathcal{Z}({\mathfrak{n}})=[{\mathfrak{n}}_{G},{\mathfrak{n}}_{G}]\oplus\mathfrak{a}$.
We call $\mathfrak{a}$ the _abelian factor of ${\mathfrak{n}}_{G}$_. If
$\mathfrak{a}$ is trivial, we will say ${\mathfrak{n}}_{G}$ has _no abelian
factor_.

The abelian factor is a Lie algebraic notion and is not metric dependent.
However, as shown in the Lemma below, it is often useful to compute the
abelian factor using a specific metric.

######  Lemma 2.5.

Let $G=(V,E,C)$ denote a directed, edge-labeled graph. Then the abelian factor
$\mathfrak{a}$ of ${\mathfrak{n}}_{G}$ is equal to
${\displaystyle\bigcap_{Z\in C}\ker(j(Z))}.$

###### Proof.

Let $X$ be an element of $\mathfrak{a}$ and let $Z\in C$. Then for all
$Y\in{\mathfrak{v}}$, we have $[X,Y]=0$ and hence $\langle Z,[X,Y]\rangle=0$.
This implies that $\langle j(Z)(X),Y\rangle=0$ for all $Y\in{\mathfrak{v}}$.
Therefore $j(Z)(X)=0$ and hence
$\mathfrak{a}\subseteq{\displaystyle\bigcap_{Z\in C}\ker(j(Z))}.$

Now assume that $X^{\prime}\in{\mathfrak{v}}$ and $j(Z)(X^{\prime})=0$ for
each $Z\in C$. Let $Y\in{\mathfrak{v}}$ be arbitrary. Then $\langle
j(Z)(X^{\prime}),Y\rangle=0$ for all $Z\in C$. Hence $\langle
Z,[X^{\prime},Y]\rangle=0$ for all $Z\in C$. Since $C$ is an orthonormal basis
for $[{\mathfrak{n}}_{G},{\mathfrak{n}}_{G}]$, we have $[X^{\prime},Y]=0$.
Therefore $X^{\prime}\in\mathfrak{a}$ as $Y\in{\mathfrak{v}}$ is arbitrary. We
have proved that ${\displaystyle\bigcap_{Z\in
C}\ker(j(Z))}\subseteq\mathfrak{a}$. ∎

When each edge has a unique label, as in the construction in [6], the
resulting 2-step nilpotent Lie algebra has no abelian factor. This is often
not the case if repeated edge labels are allowed. The next results illustrate
how common the presence of an abelian factor is in the case when repeated edge
labels are allowed and give us some basic tools for which to investigate the
presence or lack of an abelian factor in the resulting Lie algebras.

######  Proposition 2.6.

If $G$ is a directed edge-labeled graph on an odd number of vertices with one
edge label, then ${\mathfrak{n}}_{G}$ has a nontrivial abelian factor.

###### Proof.

Let every edge in $G$ be labeled by $Z$ and let $|V(G)|=n$, where $n$ is odd.
Since ${\mathfrak{v}}$ is odd dimensional and
$j(Z):{\mathfrak{v}}\rightarrow{\mathfrak{v}}$ is a skew symmetric linear map,
there exists some nonzero $X\in{\mathfrak{v}}$ with $X\in\ker(j(Z))$. Since
$[{\mathfrak{n}},{\mathfrak{n}}]$ is 1 dimensional,
$[{\mathfrak{n}},{\mathfrak{n}}]=\\{aZ|a\in{\mathbb{R}}\\}$, so by linearity
of $j$, $X$ is in the kernel of $j(Z^{\prime})$ for any
$Z^{\prime}\in[{\mathfrak{n}},{\mathfrak{n}}]$. Hence, ${\mathfrak{n}}_{G}$
has a nontrivial abelian factor by Lemma 2.5. ∎

To determine the abelian factor from graph properties, we must look at how
edges with the same label are connected to each other. For the rest of this
section, we assume that our graph $G$ is simple.

The neighborhood of a vertex $v$, denoted by $N(v)$, is defined as the set of
all vertices in graph $G$ which are adjacent to $v$ without considering edge
direction.

######  Definition 2.7.

For a vertex $v$ and an edge label $Z$, we define a _$Z$ -neighborhood_ of $v$
as follows: $N_{Z}(v)=\\{w\in N(x)\,|\,c(vw)=Z\\}.$

######  Definition 2.8.

Let $v$ be a vertex in graph $G$. Define the _edge-label degree_ of $v$ by
$deg_{Z}(v)=|N_{Z}(v)|$, ie. the number of edges incident to vertex $v$ with
label $Z$.

######  Definition 2.9.

For a graph $G$, we define the following set:

${\mathcal{A}}(G)=\\{v\in V(G)\,|\,\mbox{ every }y\in N(v)\mbox{ has
}deg_{c(vy)}(y)>1\\}.$

Note that we will suppress $G$ if it is understood in context.

######  Example 2.10.

Given the graphs in Figure 2,
${\mathcal{A}}(G_{1})=\\{v_{1},v_{2},v_{3},v_{4}\\}$ and
${\mathcal{A}}(G_{2})=\\{v_{1},v_{5}\\}$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$Z_{1}$$Z_{1}$$Z_{1}$$Z_{1}$

$v_{3}$$v_{1}$$v_{2}$$v_{4}$$v_{5}$$v_{6}$$Z_{1}$$Z_{2}$$Z_{1}$$Z_{1}$$Z_{2}$

Figure 2. Graphs $G_{1}$ and $G_{2}$, respectively

######  Theorem 2.11.

Let ${\mathfrak{n}}_{G}$ denote the 2-step nilpotent Lie algebra associated to
a simple graph $G$. Then, the abelian factor $\mathfrak{a}$ of
${\mathfrak{n}}_{G}$ is contained in the span of ${\mathcal{A}}$.

###### Proof.

Label the vertices in $V(G)$ as ${\mathcal{A}}=\\{v_{1},\dots,v_{m}\\}$ and
${\mathcal{A}}^{c}=V(G)-{\mathcal{A}}=\\{v_{m+1},\ldots,v_{n}\\}$.

For $k=m+1,\ldots,n$, there exists a vertex $y_{k}$ in $N(v_{k})$ such that
$deg_{c(v_{k}y_{k})}(y_{k})\leq 1$ since $v_{k}\in{\mathcal{A}}^{c}$.

Let $\displaystyle X=\sum_{i=1}^{m}a_{i}v_{i}+\sum_{j=m+1}^{n}a_{j}v_{j}$ be
an element of the abelian factor. Hence, we have the bracket $[X,y_{k}]=0$ for
all $y_{k}$ obtained in the previous step.

This implies that for each $k=m+1,\ldots,n$:

$\displaystyle a_{k}[v_{k},y_{k}]+\sum_{1\leq\ell\neq k\leq
n}a_{k}[v_{\ell},y_{k}]$ $\displaystyle=0.$

Recall that $y_{k}\in{\mathcal{A}}^{c}$ means that the label
$c(v_{k}y_{k})\neq c(v_{\ell}y_{k}),\forall\ell\neq k$. Hence
$[v_{k},y_{k}]\not\in\operatorname{span}\\{[v_{\ell},y_{k}]\,|\,\ell\neq
k\\}$. Thus, $[v_{k},y_{k}]$ is linearly independent from
$\\{[v_{\ell},y_{k}]\,|\,\ell\neq k\\}$. Hence $a_{k}=0$ for all
$k=m+1,\ldots,n$.

Thus,
$X\in\operatorname{span}\\{v_{1},\ldots,v_{m}\\}=\operatorname{span}{\mathcal{A}}$.
∎

The next examples illustrate the necessity and insufficiency of Theorem 2.11.

######  Example 2.12.

For $G_{1}$ in Figure 2, a straightforward calculation shows that the
associated 2-step nilpotent Lie algebra ${\mathfrak{n}}_{G_{1}}$ will have a
two dimensional abelian factor with basis $\\{v_{1}+v_{3},v_{2}+v_{4}\\}$. For
$G_{2}$, the associated Lie algebra has no abelian factor even though
${\mathcal{A}}=\\{v_{1},v_{5}\\}$. If it did, it would necessarily be
contained in the span of $\\{v_{1},v_{5}\\}$. A straightforward check shows
that ${\mathfrak{n}}_{G_{2}}$ has no abelian factor. This is also verified in
Proposition 3.11. We note that for this graph, the orientation of the labels
$Z_{1}$ and $Z_{2}$ does not affect the abelian factor of
${\mathfrak{n}}_{G_{2}}$.

######  Example 2.13.

Let ${G_{1}^{\prime}}$ be the graph in Figure 3. Note this is the same graph
as $G_{1}$ in Figure 2 except the direction of $v_{4}v_{1}$ has switched. We
get the same set ${\mathcal{A}}=\\{v_{1},v_{2},v_{3},v_{4}\\}$ as in Example
2.10 because the definition of ${\mathcal{A}}$ does not depend on the
direction of the edges. However, ${\mathfrak{n}}_{G_{1}^{\prime}}$ has no
abelian factor. This is verified in part 1 of Proposition 4.3.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$Z_{1}$$Z_{1}$$Z_{1}$$Z_{1}$ Figure 3. Graph
$G_{1}^{\prime}$

Sometimes it is advantageous to instead consider what vertices do not
contribute to the abelian factor. The next Proposition gives us criteria for
that.

######  Proposition 2.14.

Let ${\mathfrak{n}}_{G}$ denote the 2-step nilpotent Lie algebra associated to
a simple graph $G$. The following are equivalent:

  1. (1)

The abelian factor of ${\mathfrak{n}}_{G}$ is contained in the span of
${\mathcal{A}}$.

  2. (2)

If $\displaystyle\sum_{i=1}^{|V|}a_{i}v_{i}$ is in the abelian factor and
$v_{j}\in N(v_{k})$ such that $deg_{c(v_{j}v_{k})}(v_{k})=1$, then $a_{j}=0$.

###### Proof.

(1) $\Rightarrow$ (2): If $v_{j}\in N(v_{k})$ such that
$deg_{c(v_{j}v_{k})}(v_{k})=1$, then by Definition 2.9,
$v_{j}\not\in{\mathcal{A}}$ and therefore $a_{j}=0$.

(2) $\Rightarrow$ (1): Let $\sum a_{i}v_{i}$ be in the abelian factor. We need
to show if some $a_{j}\neq 0$ then $v_{j}\in{\mathcal{A}}$. Assume $a_{j}\neq
0$ and $v_{j}\not\in{\mathcal{A}}$. By Definition 2.9, there is some $v_{k}\in
N(v_{j})$ with $deg_{c(v_{k}v_{j})}(v_{k})=1$. Hence assumption (2) holds and
$a_{j}=0$, which is a contradiction. Hence, $v_{j}\in{\mathcal{A}}$. ∎

######  Corollary 2.15.

Let ${\mathfrak{n}}_{G}$ denote the 2-step nilpotent Lie algebra associated to
a simple graph $G$. If ${\mathcal{A}}=\emptyset$, then ${\mathfrak{n}}_{G}$
has no abelian factor. Also, if ${\mathcal{A}}$ only contains one vertex, then
${\mathfrak{n}}_{G}$ has no abelian factor.

###### Proof.

If ${\mathcal{A}}=\emptyset$, the proof follows directly from Proposition
2.14. Letting ${\mathcal{A}}=\\{v_{i}\\}$, by Proposition 2.14, the abelian
factor will be of the form $a_{i}v_{i}$. Then for some $v_{k}\in N(v_{i})$,
$[a_{i}v_{i},v_{k}]=0$, which implies that $a_{i}Z=0$. Thus, $a_{i}=0$, and
${\mathfrak{n}}_{G}$ has no abelian factor. ∎

Note that when ${\mathcal{A}}$ contains more than one vertex, there may or may
not be an abelian factor. See Example 2.12.

##  3\. Star graphs

In the following section, we determine what properties of star graphs lead to
an abelian factor in the associated Lie algebra and compute a nice basis for
the orthogonal complement of the center.

Let $K_{1,n}$ denote a star graph. The vertex of degree $n$ is called often
called the _center vertex_ of a star graph in graph theory work. To avoid
confusion with the Lie Algebra term, we will call the vertex of degree $n$ in
$K_{1,n}$ the _central vertex_ and label this vertex $v_{0}$. A vertex of
degree 1 is called an _end_ or a _leaf_.

######  Notation 3.1.

For a star graph, $K_{1,n}$, label the central vertex as $v_{0}$. Let
$Z_{1},\ldots,Z_{k}$ denote the edge labels in the graph, and let $m_{i}$
denote the multiplicity of edge label $Z_{i}$ for $1\leq i\leq k$. Label the
end vertices in graph $K_{1,n}$ as $v_{i,j}$ so that edges with label $Z_{i}$
connect the central vertex $v_{0}$ to vertices $v_{i,j}$ for $1\leq j\leq
m_{i}$ for each $1\leq i\leq k$. Denote the direction of each edge via a map
$\delta:\\{v_{i,j}\\}\rightarrow\\{+1,-1\\}$ where $\delta(v_{i,j})=+1$ if the
edge $Z_{i}$ is oriented from $v_{0}$ to $v_{i,j}$ and $-1$ if edge $Z_{i}$ is
oriented from $v_{i,j}$ to $v_{0}$. Hence in the Lie algebra
${\mathfrak{n}}_{K_{1,n}}$, we have $[v_{0},v_{i,j}]=\delta(v_{i,j})Z_{i}$ for
all $1\leq j\leq m_{i}$ and $1\leq i\leq k$.

######  Theorem 3.2.

Let $K_{1,n}$ be a star graph with $k$ distinct edge labels. Then the
associated Lie algebra ${\mathfrak{n}}_{K_{1,n}}$ has abelian factor of
dimension $\displaystyle n-k$.

###### Proof.

Label the edges of $K_{1,n}$ by $Z_{1},\ldots,Z_{k}$ with multiplicities
$m_{1}\geq\cdots\geq m_{k}$ respectively and let $p$ denote the largest index
with $m_{p}>1$. Then $m_{p+1},\ldots,m_{k}=1$ and $m_{i}>1$ for $1\leq i\leq
p$. Observe by Definition 2.9 that the only vertices in ${\mathcal{A}}$ are
the ends whose incident edge label has multiplicity strictly greater than 1.

Thus, the abelian factor factor is contained in the span of the set
${\mathcal{A}}=\\{v_{i,j}\,|1\leq i\leq p,1\leq j\leq m_{i}\\}$.

Let $\displaystyle X=\sum_{i=1}^{p}\sum_{j=1}^{m_{i}}a_{i,j}v_{i,j}$. Observe
that $[X,v_{i,j}]=0$ for all $i,j$ since no two distinct ends $v_{i,j}$ are
adjacent and $[v_{i,j},v_{i,j}]=0$. So $X$ is in the abelian factor if and
only if $\displaystyle
0=[X,v_{0}]=\sum_{i=1}^{p}\sum_{j=1}^{m_{i}}-\delta(v_{i,j})a_{i,j}Z_{i}$.
Since $\\{Z_{i}|1\leq i\leq k\\}$ is a linearly independent set, this occurs
precisely when $\displaystyle\sum_{j=1}^{m_{i}}\delta(v_{i,j})a_{i,j}=0$, for
each $i$. For each $i$ we have a linear equation with $m_{i}$ variables;
hence, the solution set for each $i$ has dimension $m_{i}-1$. Thus, the
dimension $D$ of the abelian factor is given by the following computation:

$\begin{split}D&=\sum_{i=1}^{p}(m_{i}-1)\\\
&=\left(\sum_{i=1}^{p}m_{i}\right)-p\\\ &=\sum_{i=1}^{p}m_{i}+(k-p)-(k-p)-p\\\
&=\sum_{i=1}^{p}m_{i}+\sum_{j=p+1}^{k}m_{j}-k+p-p\\\
&=\sum_{i=1}^{k}m_{i}-k.\end{split}$

Note that $m_{i}=1$ for $p+1\leq i\leq k$ so $\sum_{i=p+1}^{k}m_{i}=k-p$.

Finally, observe that $\displaystyle\sum_{i=1}^{k}m_{i}=n$ since this sum is
precisely the number of ends on the star, and thus $D=n-k$. ∎

######  Corollary 3.3.

Let $K_{1,n}$ be a star graph with vertex and edge labeling as in Notation
3.1. Then a basis of the abelian factor in ${\mathfrak{n}}_{K_{1,n}}$ is given
by the set

$A=\bigcup_{i=1}^{p}\bigcup_{j=1}^{m_{i}-1}\left\\{\delta(v_{i,m_{i}})v_{i,j}-\delta(v_{i,j})v_{i,m_{i}}\right\\},$

and an orthonormal basis for the orthogonal complement of the center,
$\mathcal{Z}({\mathfrak{n}}_{K_{1,n}})^{\perp}$, is given by

$S=\\{v_{0}\\}\bigcup_{i=1}^{k}\left\\{\frac{1}{\sqrt{m_{i}}}\left(\delta(v_{i,1})v_{i,1}+\delta(v_{i,2})v_{i,2}+\ldots+\delta(v_{i,m_{i}})v_{i,m_{i}}\right)\right\\},$

.

###### Proof.

A straightforward linear algebra computation to compute the basis for the
nullspace of $\displaystyle{\sum_{j=1}^{m_{i}}\delta(v_{i,j})a_{i,j}}$ gives
that a basis for the abelian factor is given by
$\displaystyle\bigcup_{i=1}^{p}\bigcup_{j=1}^{m_{i}-1}\\{\delta(v_{i,m_{i}})v_{i,j}-\delta(v_{i,j})v_{i,m_{i}}\\}$.
Note that if $1\leq i\leq p$ then $m_{i}>1$, so
$\delta(v_{i,m_{i}})v_{i,j}-\delta(v_{i,j})v_{i,m_{i}}\neq 0$.

Next, we show that $S$ is a basis of
$\mathcal{Z}({\mathfrak{n}}_{K_{1,n}})^{\perp}$. First, observe that for each
$i$,

$\left\langle\frac{1}{\sqrt{m_{i}}}\left(\delta(v_{i,1})v_{i,1}+\ldots+\delta(v_{i,j})v_{i,j}+\ldots+\delta(v_{i,m_{i}})v_{i,m_{i}}\right),\delta(v_{i,m_{i}})v_{i,j}-\delta(v_{i,j})v_{i,m_{i}}\right\rangle$
$=\frac{1}{\sqrt{m_{i}}}\delta(v_{i,j})\delta(v_{i,m_{i}})-\frac{1}{\sqrt{m_{i}}}\delta(v_{i,m_{i}})\delta(v_{i,j})=0,$

for all $j=1,\dots,m_{i-1}$. Also, $\langle
v_{0},\delta(v_{i,j})v_{i,j}-\delta(v_{i,m_{i}})v_{i,m_{i}}\rangle=0$ for all
$i,j$. This shows that
$S\subseteq\mathcal{Z}({\mathfrak{n}}_{K_{1,n}})^{\perp}$. Next, it is clear
that $S$ is a linearly independent set since the set $V(K_{1,n})$ is linearly
independent. Finally,
$\dim\mathcal{Z}({\mathfrak{n}}_{K_{1,n}})^{\perp}=\dim{\mathfrak{n}}_{K_{1,n}}-\dim\mathcal{Z}({\mathfrak{n}}_{K_{1,n}})=(1+n+k)-(k+(n-k))=k+1=|S|$.
Therefore, $S$ is a basis for $\mathcal{Z}({\mathfrak{n}}_{K_{1,n}})^{\perp}$.
∎

######  Example 3.4.

The star graph $G$ in Figure 4 is associated to a 10 dimensional nilpotent Lie
Algebra, which has a 3 dimensional abelian factor with basis
$\\{v_{1,1}-v_{1,3},v_{1,2}+v_{1,3},-v_{2,1}-v_{2,2}\\}$ and a 4 dimensional
$\mathcal{Z}({\mathfrak{n}}_{G})^{\perp}$ with orthonormal basis
$\\{v_{0},\frac{1}{\sqrt{3}}(v_{1,1}-v_{1,2}+v_{1,3}),\frac{1}{\sqrt{2}}(v_{2,1}-v_{2,2}),v_{3,1}\\}$.

$v_{0}$$v_{1,1}$$v_{1,2}$$v_{1,3}$$v_{2,1}$$v_{2,2}$$v_{3,1}$$Z_{1}$$Z_{1}$$Z_{1}$$Z_{2}$$Z_{2}$$Z_{3}$
Figure 4. Example of a star graph

There are three types of 2-step nilpotent Lie algebras, which depend on the
singularity of the $j(Z)$ operator defined in (1).

######  Definition 3.5.

Let
${\mathfrak{n}}=(\mathcal{Z}({\mathfrak{n}})^{\perp}\oplus\mathfrak{a})\oplus[{\mathfrak{n}},{\mathfrak{n}}]$
be a 2-step nilpotent metric Lie algebra. Then, ${\mathfrak{n}}$ is _singular_
if the $j(Z)$ operator restricted to $\mathcal{Z}({\mathfrak{n}})^{\perp}$ is
singular for all $Z$ in $[{\mathfrak{n}},{\mathfrak{n}}]$. ${\mathfrak{n}}$ is
_nonsingular_ if the abelian factor $\mathfrak{a}$ of ${\mathfrak{n}}$ is
trivial and the $j(Z)$ operator is nonsingular for all nonzero $Z$ in
$[{\mathfrak{n}},{\mathfrak{n}}]$. By [14, 21], if ${\mathfrak{n}}$ is neither
singular nor nonsingular, it is _almost nonsingular_.

Note that $j(Z)X=0$ for all $X\in\mathfrak{a}$. This would result in any
2-step nilpotent Lie algebra with an abelian factor being singular unless we
restrict the domain of $j(Z)$ to $\mathcal{Z}({\mathfrak{n}})^{\perp}$ as in
Definition 3.5.

We now recall a result of [7] where the authors found that if a star graph had
unique edge labels, then the resulting Lie algebra was always singular. We
then generalize this result when we allow repeated edge labels.

######  Proposition 3.6.

([7] Ex. 3.4) Let $K_{1,n}$ denote the directed star graph with edge labels
$Z_{1},\ldots,Z_{n}$, each with multiplicity 1. Then the resulting Lie algebra
${\mathfrak{n}}_{K_{1,n}}$ is singular. Moreover, if
$Z\in[{\mathfrak{n}}_{K_{1,n}},{\mathfrak{n}}_{K_{1,n}}]$ is given by
$\sum_{i=1}^{n}a_{i}Z_{i}$, then the eigenvalues of $j(Z)$ are $0,\pm
i\sqrt{a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}}$.

######  Theorem 3.7.

Let $K_{1,n}$ have edges labeled by $Z_{1},\ldots,Z_{k}$ with multiplicities
$m_{1},\ldots,m_{k}$ respectively, and let $Z=\sum_{i=1}^{k}a_{i}Z_{i}$ be an
arbitrary element of the derived algebra of ${\mathfrak{n}}_{K_{1,n}}$. Then
the eigenvalues of $j(Z)$ are $\displaystyle 0,\pm
i\sqrt{\sum_{\ell=1}^{k}m_{\ell}a_{\ell}^{2}}$.

###### Proof.

We have $j(Z):{\mathfrak{v}}\rightarrow{\mathfrak{v}}$ where
${\mathfrak{v}}=[{\mathfrak{n}}_{K_{1,n}},{\mathfrak{n}}_{K_{1,n}}]^{\perp}=\mathcal{Z}({\mathfrak{n}}_{K_{1,n}})^{\perp}\oplus\mathfrak{a}$.
The matrix of $j(Z)$ is identically $0$ when restricted to $\mathfrak{a}$. The
matrix of $j(Z)$ restricted to $\mathcal{Z}({\mathfrak{n}}_{K_{1,n}})^{\perp}$
with respect to the orthonormal basis from Corollary 3.3 is given by

$\begin{bmatrix}0&a_{1}\sqrt{m_{1}}&\dots&a_{k}\sqrt{m_{k}}\\\
-a_{1}\sqrt{m_{1}}&0&\dots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
-a_{k}\sqrt{m_{k}}&0&\dots&0\end{bmatrix}.$

The characteristic polynomial of this matrix is
$(-\lambda)^{k-1}(\lambda^{2}+\sum_{\ell=1}^{k}m_{\ell}a_{\ell}^{2}$). ∎

######  Corollary 3.8.

Let $K_{1,n}$ be a star graph with possibly repeated edge labels. Then
${\mathfrak{n}}_{K_{1,n}}$ is singular.

###### Proof.

The proof follows directly from the proof of Theorem 3.7 and Definition 3.5. ∎

We now show that the Lie algebra associated to a star graph with repeated edge
labels has a Lie subalgebra with no abelian factor which corresponds to a
different star graph with unique weighted edge labels.

Let
${\mathfrak{n}}_{G}=(\mathcal{Z}({\mathfrak{n}}_{G})^{\perp}\oplus\mathfrak{a})\oplus[{\mathfrak{n}}_{G},{\mathfrak{n}}_{G}]$
be a 2-step nilpotent Lie algebra associated to a star graph $G$. Then define
${\mathfrak{n}}_{G}^{*}$ to be the Lie algebra given by
${\mathfrak{n}}_{G}^{*}=\mathfrak{a}\backslash{\mathfrak{n}}_{G}$. Thus
${\mathfrak{n}}_{G}^{*}\cong\mathcal{Z}({\mathfrak{n}}_{G})^{\perp}\oplus[{\mathfrak{n}}_{G},{\mathfrak{n}}_{G}]$,
and ${\mathfrak{n}}_{G}^{*}$ is a Lie algebra which has no abelian factor.
Using a slightly modified construction, the Lie algebra
${\mathfrak{n}}_{G}^{*}$ can be constructed from graph $K_{1,k}$ where $k$ is
the number of distinct edge labels in the original graph $G$. In the new
graph, all $k$ edges have distinct edge labels $Z_{1},\ldots,Z_{k}$, where
each $|Z_{i}|=1$, and each edge is weighted according to the square root of
its multiplicity in the original graph $G$.

######  Example 3.9.

Let $G$ be the graph given in Example 3.4 and let ${\mathfrak{n}}_{G}$ denote
the resulting Lie algebra. Let
${\mathfrak{n}}_{G}^{*}=\mathcal{Z}({\mathfrak{n}}_{G})^{\perp}\oplus[{\mathfrak{n}}_{G},{\mathfrak{n}}_{G}]$,
which is the Lie algebra resulting from the modified construction described
above using directed graph with edge labels of multiplicity one and where each
edge label is weighted according to the square root of its multiplicity in
graph $G$, as shown in Figure 5 . The vectors $\\{Z_{1},Z_{2},Z_{3}\\}$ form
an orthonormal basis for the derived algebra of ${\mathfrak{n}}_{G}^{*}$,
which in this case is equal to the center of the Lie algebra in
${\mathfrak{n}}_{G}^{*}$. The vectors $\\{X_{0},X_{1},X_{2},X_{3}\\}$ are
given by the basis for $\mathcal{Z}({\mathfrak{n}}_{G})^{\perp}$ in Corollary
3.3. So in this example, $X_{0}=v_{0}$,
$X_{1}=\frac{1}{\sqrt{3}}(v_{1,1}-v_{1,2}+v_{1,3})$,
$X_{2}=\frac{1}{\sqrt{2}}(v_{2,1}-v_{2,2})$, and $X_{3}=v_{1,3}$.

$X_{0}$$X_{1}$$X_{2}$$X_{3}$$\sqrt{3}Z_{1}$$\sqrt{2}Z_{2}$$Z_{3}$ Figure 5.
Graph for modified construction used in Example 3.9

Next we consider a graph $G$ which is the union of two star graphs whose
central vertices are connected by a single edge.

######  Example 3.10.

The graph in Figure 6 is associated to a nilpotent Lie algebra which has 3
dimensional abelian factor with basis
$\\{v_{1,1}-v_{1,2},v_{2,1}-v_{2,2},w_{1,1}-w_{1,2}\\}$.

$v_{0}$$v_{1,1}$$v_{2,2}$$v_{1,2}$$v_{2,1}$$w_{0}$$w_{1,1}$$w_{1,2}$$Z_{1}$$Z_{2}$$Z_{1}$$Z_{2}$$Z_{1}$$Z_{1}$$Z_{1}$
Figure 6. Union of two star graphs with adjacent central vertices

######  Proposition 3.11.

Let $G$ be the graph which is constructed from two directed, edge-labeled,
star graphs $G_{1}=K_{1,n}$ and $G_{2}=K_{1,m}$ where the central vertex of
each $G_{1}$ and $G_{2}$ is adjacent by a labeled, directed edge. Let
$\mathfrak{a}_{i}$ denote the abelian factor of ${\mathfrak{n}}_{G_{i}}$ for
$i=1,2$. Then the abelian factor $\mathfrak{a}$ of ${\mathfrak{n}}_{G}$ is
given by ${\mbox{span}}(\mathfrak{a}_{1}\cup\mathfrak{a}_{2})$.

###### Proof.

Let $G$ be a graph constructed from two star graphs, as described, with
vertices labeled as shown in Figure 7. Edge labels and edge directions not
pictured.

$v_{0}$$v_{1}$$v_{n}$$v_{2}$$\ddots$$w_{0}$$w_{1}$$\vdots$$w_{m}$ Figure 7.
Vertex labeling for the proof of Proposition 3.11

Let $X\in\mathfrak{a}_{1}\cup\mathfrak{a}_{2}$. Assume that
$X\in\mathfrak{a}_{1}$ and write $X=\sum_{i=0}^{n}a_{i}v_{i}$. By Corollary
3.3, $a_{0}=0$. Since $X$ is in $\mathfrak{a}_{1}$, we have $[X,v_{i}]=0$ for
all $v_{i}$ in $G_{1}$. It is also true that $[X,w_{j}]=0$ for all $w_{j}$ in
$G_{2}$ because there are no adjacent edges between $v_{1},\ldots,v_{n}$ and
vertices in $G_{2}$. A similar result holds if $X\in\mathfrak{a}_{2}$.
Therefore $X\in\mathfrak{a}$. Since $\mathfrak{a}$ is a vector space
containing $\mathfrak{a}_{1}\cup\mathfrak{a}_{2}$, we have
${\mbox{span}}(\mathfrak{a}_{1}\cup\mathfrak{a}_{2})\subseteq\mathfrak{a}$.

To show equality, suppose $\displaystyle
X=\sum_{i=0}^{n}a_{i}v_{i}+\sum_{j=0}^{m}b_{j}w_{j}\in\mathfrak{a}$. For
$1\leq i\leq n$, $0=[X,v_{i}]=[a_{0}v_{0},v_{i}]=a_{0}[v_{0},v_{i}]$, hence
$a_{0}=0$. Similarly, for $1\leq j\leq m$,
$0=[X,w_{j}]=[b_{0}w_{0},w_{j}]=b_{0}[w_{0},w_{j}]$, and hence $b_{0}=0$.
Therefore, $\displaystyle
X=\sum_{i=1}^{n}a_{i}v_{i}+\sum_{j=1}^{m}b_{j}w_{j}$.

We will now show that
$\displaystyle\sum_{i=1}^{n}a_{i}v_{i}\in\mathfrak{a}_{1}$ and
$\displaystyle\sum_{j=1}^{m}b_{j}w_{j}\in\mathfrak{a}_{2}$. Since
$X\in\mathfrak{a}$, we have $[X,v_{0}]=0$. Hence,
$[\sum_{i=1}^{n}a_{i}v_{i},v_{0}]=0$ as $[w_{j},v_{0}]=0$ for all
$j=1,\ldots,m$. Also $[\sum_{i=1}^{n}a_{i}v_{i},v_{k}]=0$ for all
$k=1,\ldots,n$ and therefore $\sum_{i=1}^{n}a_{i}v_{i}\in\mathfrak{a}_{1}$.
Similarly, we can show that $\sum_{j=1}^{m}b_{j}w_{j}\in\mathfrak{a}_{2}$.
Thus, ${\mbox{span}}(\mathfrak{a}_{1}\cup\mathfrak{a}_{2})=\mathfrak{a}$. ∎

######  Corollary 3.12.

Let $G_{1}=K_{1,n}$ be a directed, edge-labeled star graph with $k_{1}$ edge
labels and $G_{2}=K_{1,m}$ a directed edge-labeled star graph with $k_{2}$
edge labels. Let $G$ be the graph constructed from $G_{1}$ and $G_{2}$ where
the central vertex of each $G_{1}$ and $G_{2}$ is adjacent by a labeled,
directed edge. Then the dimension of the abelian factor of $G$ is
$(n+m)-(k_{1}+k_{2})$.

###### Proof.

The dimension of the span of $E_{1}\cup E_{2}$ is given by the sum of
$dim(E_{1})=n-k_{1}$ and $dim(E_{2})=m-k_{2}$. ∎

Note that the quantity $k_{1}+k_{2}$ in Corollary 3.12 is not necessarily the
number of distinct edge labels in the graph $G$. Edge labels in $G_{1}$ and
$G_{2}$ are not necessarily distinct and the label of the edge connecting the
central vertices is irrelevant for this result.

Observe that the result on the double star graphs cannot be extended to trees
in general. As we see from the next example, there are trees with an internal
vertex that is involved in the abelian factor.

######  Example 3.13.

Let ${\mathfrak{n}}_{G}$ be the Lie algebra constructed from the graph $G$ in
Figure 8. In this graph, ${\mathcal{A}}=\\{w_{0},v_{1},v_{2},u_{1},u_{2}\\}$.
The corresponding ${\mathfrak{n}}_{G}$ has a three dimensional abelian factor
with basis $\\{v_{1}-v_{2},v_{2}+w_{0}+u_{2},u_{1}-u_{2}\\}$.

$v_{0}$$v_{1}$$v_{2}$$w_{0}$$u_{0}$$u_{1}$$u_{2}$$Z_{1}$$Z_{1}$$Z_{1}$$Z_{2}$$Z_{2}$$Z_{2}$
Figure 8. Example of a tree that is not a star graph

##  4\. Cycles

Let $C_{n}$ be a cycle with $n$ vertices and $n$ edges, where we label the
vertices $\\{v_{1},v_{2},\dots,v_{n}\\}$, with $v_{i}$ adjacent to $v_{i+1}$
for $1\leq i\leq n-1$ and $v_{n}$ adjacent to $v_{1}$, without specifying the
direction of the edges. Denote the edge labels by $Z_{j}$ for $1\leq j\leq p$
for some positive integer $p$.

######  Definition 4.1.

In the cycle $C_{n}$, define an edge to have standard orientation if it is
directed as $(v_{i},v_{i+1})$ for $1\leq i\leq n-1$ or $(v_{n},v_{1})$. An
edge has opposite standard orientation if it is directed as $(v_{i+1},v_{i})$
for $1\leq i\leq n-1$ or $(v_{1},v_{n})$. We define the graph $C_{n}$ to have
standard orientation if all edges have standard orientation.

The cycle in Example 2.13 has three edges with standard orientation and one
with opposite standard orientation. The cycle in Example 2.10 has standard
orientation.

######  Theorem 4.2.

Let $C_{n}$ be a cycle with standard orientation and all edge labels the same.
Let $\mathfrak{a}$ denote the abelian factor of the associated Lie algebra
${\mathfrak{n}}_{C_{n}}$.

  1. (1)

If $n$ is even, the dimension of $\mathfrak{a}$ is 2 with basis
$\displaystyle\left\\{\sum_{i=1}^{k}v_{2i-1},\sum_{i=1}^{k}v_{2i}\right\\}$,
where $n=2k$.

  2. (2)

If $n$ is odd, the dimension of $\mathfrak{a}$ is 1 with basis
$\displaystyle\left\\{\sum_{i=1}^{n}v_{i}\right\\}$.

###### Proof.

Assume $C_{n}$ has the standard orientation and all edges have the same label,
$Z$. Then the brackets in the Lie algebra ${\mathfrak{n}}_{C_{n}}$ are given
by $[v_{i},v_{i+1}]=[v_{n},v_{1}]=Z$ for $i=1,\dots,n-1$, with skew symmetry
and linearity, and all other brackets are zero. Let
$X=\sum_{i=1}^{n}a_{i}v_{i}$ be an element in the abelian factor of
${\mathfrak{n}}_{C_{n}}$. Consider $[X,v_{i}]$ for each $i=1,\dots,n$. By the
adjacency and directions of edges in the graph $C_{n}$, we have
$[X,v_{i}]=(a_{i-1}-a_{i+1})Z$ for $i=2,\dots,n-1$,
$[X,v_{1}]=(a_{n}-a_{2})Z$, and $[X,v_{n}]=(a_{n-1}-a_{1})Z$. Since
$[X,v_{i}]=0$ for all $i=1,\ldots,n$, we have the following coefficient
relationships: $a_{i-1}=a_{i+1}$ for $i=2,\dots,n-1$, $a_{2}=a_{n}$ and
$a_{1}=a_{n-1}$.

If $n$ is even, the above computation shows that the abelian factor is spanned
by two vectors, one is the sum of the even indexed vertices and the other is
the sum of the odd indexed vertices. This results in a 2-dimensional abelian
factor with the basis given above.

If $n$ is odd, then using $a_{2}=a_{n}$, we obtain that each even indexed term
is equal to each odd indexed term. Therefore, all $a_{i}$ are equal. Thus
there is a 1-dimensional abelian factor with the basis given above. ∎

######  Proposition 4.3.

Let $C_{n}$ be a cycle with all edge labels the same. Let $m$ be the number of
edges which have opposite standard orientation. Let $\mathfrak{a}$ denote the
abelian factor of the associated Lie algebra ${\mathfrak{n}}_{C_{n}}$.

  1. (1)

If $n=2k$ is even and $m$ is odd, the dimension of $\mathfrak{a}$ is zero.

  2. (2)

If $n=2k$ is even and $m$ is even, the dimension of $\mathfrak{a}$ is 2. The
basis is

$\displaystyle\left\\{\sum_{i=1}^{k}\epsilon_{2i-1}v_{2i-1},\sum_{i=1}^{k}\epsilon_{2i}v_{2i}\right\\},$

where $\epsilon_{j}=\pm 1$.

  3. (3)

If $n=2k+1$ is odd, the dimension of $\mathfrak{a}$ is 1 with basis
$\displaystyle\left\\{\sum_{i=1}^{n}\epsilon_{i}v_{i}\right\\}$ where
$\epsilon_{i}=\pm 1$.

###### Proof.

For $1\leq i\leq n-1,$ define $\delta_{i}=1$ if the edge $v_{i}v_{i+1}$ has
standard orientation and $-1$ if the edge has opposite standard orientation.
Similarly, define $\delta_{n}=1$ if the edges $v_{n}v_{1}$ has standard
orientation and $-1$ if the edge has opposite standard orientation. In this
more general case, the bracket relations are given by
$[v_{i},v_{i+1}]=\delta_{i}Z$ for $1\leq i\leq n-1$ and
$[v_{n},v_{1}]=\delta_{n}Z$. Let $X=\sum_{i=1}^{n}a_{i}v_{i}$ be an element in
the abelian factor of ${\mathfrak{n}}_{C_{n}}$. Following the same
calculations as in the proof of Theorem 4.2, we get the following relations
between the coefficients of $X$: $a_{i}=\delta_{i}\delta_{i+1}a_{i+2}$ for
$1\leq i\leq n-2$, $a_{n-1}=\delta_{n-1}\delta_{n}a_{1}$, and
$a_{n}=\delta_{n}\delta_{1}a_{2}$.

Note that for every change in orientation of an edge, two of these relations
will change signs, one for coefficients with even index and one for
coefficients with odd index. In the case where $n$ is even and $m$ is odd,
this means that an odd number of coefficient relations will change signs in
both the odd indexed coefficients and even indexed coefficients. This will
result in the equations $a_{2}=\pm a_{4}=\ldots=\pm a_{n}=-a_{2}$ and
$a_{1}=\pm a_{3}=\ldots=\pm a_{n-1}=-a_{1}$, which means $a_{i}=0$ for all
$1\leq i\leq n$ and hence there is no abelian factor. In the other two cases,
these relations give us the basis given in the corollary. ∎

Example 2.13 illustrates case 1 in Proposition 4.3.

In the next results, we investigate the case where $C_{n}$ has at least two
distinct edge labels. We will need the following terminology.

A path is a sequence of distinct adjacent edges within a graph, disregarding
the direction of the edges. The length of a path is equal to the number of
edges in the path.

######  Definition 4.4.

A _same-labeled path_ is a path where the label on each edge is the same and
there are exactly two vertices in the path of edge-label degree 1 for that
label, i.e. the path is of maximal length.

######  Proposition 4.5.

If $C_{n}$ is a cycle with at least two distinct edge labels and at most one
same-labeled path on 2 or more edges, then ${\mathfrak{n}}_{C_{n}}$ has no
abelian factor.

###### Proof.

Let $v_{1}-v_{2}-\cdots-v_{k+1}$ be the only same-labeled path in $C_{n}$ of
length 2 or more.

Note that if $k<4$, the path has length 3 or less, and then by Definition 2.9,
${\mathcal{A}}=\emptyset$, hence by Corollary 2.15, there is no abelian
factor.

If $k\geq 4$ then ${\mathcal{A}}=\\{v_{3},v_{4},\ldots,v_{k-1}\\}$. Solving

$0=\left[a_{3}v_{3}+a_{4}v_{4}+\ldots+a_{k-1}v_{k-1},v_{\ell}\right]$

for each $\ell=1,2,\ldots,k+1$ yields $a_{i}=0$ for all $3\leq i\leq k-1$.
Therefore, by Proposition 2.14, ${\mathfrak{n}}_{C_{n}}$ has no abelian
factor. ∎

######  Lemma 4.6.

Let $P_{n}$ be the path on $n\geq 3$ vertices labeled $v_{1},\ldots,v_{n}$
with directed edges $(v_{i},v_{i+1})$ for $i=1,\ldots,n-1$ and all having the
same edge label $Z$. Then an element of the abelian factor
$X=\sum_{i=1}^{n}a_{i}v_{i}$ of the associated Lie algebra
${\mathfrak{n}}_{P_{n}}$ will have $a_{i-1}=a_{i+1}$, for $2\leq i\leq n-1$.

###### Proof.

For $2\leq i\leq n-1$, $[X,v_{i}]=0$ since $X$ is in the abelian factor. Then
since $N(v_{i})=\\{v_{i-1},v_{i+1}\\}$ and all edges have label $Z$, we have
$[X,v_{i}]=a_{i-1}Z-a_{i+1}Z=0$. Therefore, $a_{i-1}=a_{i+1}$ for $2\leq i\leq
n-1$. ∎

######  Proposition 4.7.

Let $C_{n}$ be a cycle with standard orientation and at least two distinct
edge labels. The Lie algebra ${\mathfrak{n}}_{C_{n}}$ has a nontrivial abelian
factor if and only if the induced subgraph of $C_{n}$ on each edge label
consists of the disjoint union of paths each with an even edge-length.

###### Proof.

Let $p$ denote the number of edge labels. Since there are two or more edge
labels, $n\geq p\geq 2$. Since $C_{n}$ is a cycle, the induced subgraph on any
edge label consists of the finite disjoint union of paths.

$(\Rightarrow$) Assume that ${\mathfrak{n}}_{C_{n}}$ has a nontrivial abelian
factor and suppose that for some edge label $Z_{0}$, the induced subgraph on
that edge label includes a connected component that is a path on an odd number
of edges. Denote this odd length path by $v_{1}-v_{2}-\cdots-v_{k}$. Since
there are an odd number of edges in this path, the index $k$ is even. Suppose
$X=\sum_{i=1}^{k}a_{i}v_{i}+Y$ is in the abelian factor of
${\mathfrak{n}}_{C_{n}}$ where the expansion of $Y$ in terms of the vertex
labels will have no terms from the odd path made up by the vertices
$v_{i},1\leq i\leq k$. By Proposition 2.14 Part (2), $a_{2}=a_{k-1}=0$, and by
Lemma 4.6, we have $a_{1}=a_{3}=\cdots=a_{k-1}$ and
$a_{2}=a_{4}=\cdots=a_{k}$. Since $a_{2}=0$, we have
$a_{2}=a_{4}=\cdots=a_{k}=0$, and $a_{k-1}=0$ implies
$a_{1}=a_{3}=\cdots=a_{k-1}=0$. Thus, any element $X$ in the abelian factor
has no nonzero terms from vertices in any odd path.

Then for a same-labeled path in $C_{n}$ incident to an odd path, we can again
use Proposition 2.14 Part (2) and Lemma 4.6 in the same manner as above. In
addition, we have the fact that the coefficient of the term corresponding to
the vertex where the two paths are incident is zero. Thus, the terms of an
element in the abelian factor will have coefficient zero for any term
associated with vertex labels from that path. Since $C_{n}$ is decomposed into
finitely many paths, each incident to another path at both the initial and
final vertex, we get that any element $X$ in the abelian factor is zero. Hence
${\mathfrak{n}}_{C_{n}}$ has no abelian factor.

($\Leftarrow$) Assume the induced subgraph of $C_{n}$ on each edge label
consists of the finite disjoint union of paths each with an even edge-length.
This condition implies that $n$ is even. Decompose $C_{n}$ into these paths,
where each subgraph is a same-labeled path and incident paths are of distinct
edge labels. Denote the vertices of $C_{n}$ by $\\{v_{1},\ldots,v_{n}\\}$ and
denote the edge labels of each same-labeled path by $Z_{1},\ldots,Z_{p}$ where
$Z_{1}$ is the edge label of $(v_{1},v_{2})$ and the edge labels are indexed
in the order they appear in standard orientation. Note that not all $Z_{i}$’s
are necessarily distinct, but because we are decomposing on induced graphs for
each edge label, we do assume that $Z_{\ell}\neq Z_{\ell+1}$ for
$1\leq\ell\leq p-1$ and $Z_{1}\neq Z_{p}$. Then a straightforward computation
shows that $X=\sum_{i=1}^{n/2}v_{2i-1}$ is in the abelian factor. To see this,
first observe that $[X,v_{2j-1}]=0$ for each $1\leq j\leq n/2$ since
$[v_{2j-1},v_{2j-1}]=0$ and there are no adjacency relations among distinct
odd indexed vertices so $[v_{2i-1},v_{2j-1}]=0$ for $i\neq j$. Observe that
the edge labels of the two edges incident to an even indexed vertex are the
same since each same-labeled path is of even length and starts at a vertex
with odd index. Thus, $[v_{2i-1},v_{2i}]=[v_{2i},v_{2i+1}]$. Hence for any
$1\leq i\leq n/2$, we obtain
$[X,v_{2i}]=[v_{2i-1},v_{2i}]+[v_{2i+1},v_{2i}]=0$ by skew symmetry of the
bracket. Thus, ${\mathfrak{n}}_{C_{n}}$ has a nontrivial abelian factor. ∎

######  Corollary 4.8.

Let $n$ be odd and let $C_{n}$ be a cycle with standard orientation and at
least two distinct edge labels. Then ${\mathfrak{n}}_{C_{n}}$ has trivial
abelian factor.

###### Proof.

This follows directly from Proposition 4.7, as the decomposition into even
paths required for a nontrivial abelian factor is impossible in a cycle with
an odd number of edges. ∎

##  5\. Schreier graphs

The next family of graphs that we will consider are Schreier graphs, which are
a generalization of Cayley graphs. In general, Schreier graphs are not simple,
so multiple edges between vertices as well as loops on a vertex are allowed.

######  Definition 5.1.

A _$k$ -regular graph_ is a graph such that every vertex has degree $k$. We
will say a graph is _even-regular_ if $k$ is even.

######  Definition 5.2.

A _Schreier graph_ $G=(V,E,C)$ is an even-regular directed edge-labeled graph,
where for each vertex $v\in V(G)$ and for each label $Z\in C(G)$, there is one
edge starting at $v$ with edge label $Z$ and one edge terminating at $v$ with
same edge label $Z$. Note that this could be the same edge, forming a loop at
vertex $v$.

$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{4}$$Z_{2}$$Z_{1}$$Z_{1}$$Z_{2}$$Z_{2}$$Z_{1}$$Z_{2}$$Z_{1}$$Z_{2}$$Z_{1}$
Figure 9. Example of a Schreier graph

The technical definition of a Schreier graph comes from a group, subgroup, and
a set of generators for the group. The vertices are the right cosets and the
edges are formed by right inverse multiplication of the cosets by each of the
group generators. For details on the group theoretic motivation for this
construction, see [27, Definition 2.1]. By [16, Theorem 2], every connected
even-regular graph, is a Schreier graph for a certain selection of group,
subgroup, and generating set. This paper is focused on the graph theoretic
structure of the Schreier graphs rather than which groups and subgroups create
these graphs.

One important property of a Schreier graph $G$ that we are utilizing is a
group action on the vertices of the graph. This group action $\alpha$ on the
vertices of $G$ is defined such that

$\alpha(Z)v=w\mbox{ if and only if $(v,w)\in E(G)$ with edge-label $Z$.}$

This group action is then expanded to the entire group by writing each element
in the group as a product of the generators in the edge-label set. We have

$\alpha(Z_{1}Z_{2})v=\alpha(Z_{1})(\alpha(Z_{2})v).$

From this we can see that

$\alpha(Z^{-1})w=v\mbox{ if and only if }\alpha(Z)v=w.$

######  Example 5.3.

Given the Schreier graph in Figure 9, we have the following:

$\displaystyle\alpha(Z_{1})v_{1}$ $\displaystyle=$ $\displaystyle v_{1}\mbox{
since there is a $Z_{1}$ loop from $v_{1}$ to $v_{1}$,}$
$\displaystyle\alpha(Z_{2})v_{1}$ $\displaystyle=$ $\displaystyle v_{2}\mbox{
since there is a $Z_{2}$ edge from $v_{1}$ to $v_{2}$,}$
$\displaystyle\alpha(Z_{2}^{-1})v_{1}$ $\displaystyle=$ $\displaystyle
v_{5}\mbox{ since there is $Z_{2}$ edge from $v_{5}$ to $v_{1}$, and}$
$\displaystyle\alpha(Z_{1}^{2})v_{2}$ $\displaystyle=$ $\displaystyle
v_{5}\mbox{ since there are $Z_{1}$ edges from $v_{2}$ to $v_{3}$ and from
$v_{3}$ to $v_{5}$.}$

######  Proposition 5.4.

([27] Theorem 4.2) Let $G$ be a Schreier graph and ${\mathfrak{n}}_{G}$ the
associated Lie algebra constructed by Definition 2.1. Then the $j$-operator on
${\mathfrak{n}}_{G}$ is given by

$j(Z)v=\alpha(Z)v-\alpha(Z^{-1})v,$

for all $Z$ in $[{\mathfrak{n}}_{G},{\mathfrak{n}}_{G}]$ and for all
$v\in{\mathfrak{v}}$.

Given a Schreier graph $G$ and the Lie algebra ${\mathfrak{n}}_{G}$ associated
to it as constructed in Definition 2.1, we wish to find a basis for the
abelian factor of ${\mathfrak{n}}_{G}$. We begin by adapting Definition 2.9 of
${\mathcal{A}}$ to a sequence of paths of length two with the same label and
then define an equivalence relation on the vertices of $G$ based on these
sequences.

######  Definition 5.5.

Let $G=(V,E,C)$ be a Schreier graph.

  1. (1)

We define a relation $\sim$ on $V(G)$: $v_{i}\sim v_{j}$ if there exists a
sequence of edge labels $\\{Z_{1},\dots,Z_{\ell}\\}\subseteq C$ (edge labels
not necessarily distinct) such that

$v_{j}=\alpha\Big{(}(Z_{\ell}^{\pm 1})^{2}\cdots(Z_{2}^{\pm 1})^{2}(Z_{1}^{\pm
1})^{2}\Big{)}v_{i}.$

  2. (2)

We call this product $(Z_{\ell}^{\pm 1})^{2}\cdots(Z_{2}^{\pm
1})^{2}(Z_{1}^{\pm 1})^{2}$ a 2-path sequence. We will denote the set of all
2-path sequences by $\mathcal{T}$. In other words $v_{i}\sim v_{j}$ if and
only if there exists a 2-path sequence $T\in\mathcal{T}$ such that
$v_{j}=\alpha(T)v_{i},$ i.e., if there exists a 2-path sequence connecting
$v_{i}$ to $v_{j}$.

######  Example 5.6.

In Figure 9, $v_{1}\sim v_{2}$ because
$v_{2}=\alpha(Z_{2}^{2}Z_{2}^{2})(v_{1})$. We also note that
$v_{2}=\alpha((Z_{2}^{-1})^{2})v_{1}$. Hence the 2-path sequence connecting
the vertices is not necessarily unique.

######  Lemma 5.7.

Let $G=(V,E,C)$ be a Schreier graph. Then the relation $\sim$ from Definition
5.5 is an equivalence relation.

###### Proof.

(Reflexive): Since $G$ is a Schreier graph, for each vertex $v_{i}\in V$,
there is an edge labeled $Z$ starting at $v_{i}$ and terminating at some
vertex $v_{j}$, for some $Z\in C$. Vertex $v_{j}$ will also have an edge
labeled $Z$ starting at $v_{j}$ and ending at some vertex $v_{k}$ (Note that
these vertices and edges may not be unique).

$v_{i}$$v_{j}$$v_{k}$$Z$$Z$

Consider $T=(Z^{-1})^{2}Z^{2}\in\mathcal{T}$. Then $\alpha(T)v_{i}=v_{i}$.
Thus $v_{i}\sim v_{i}$.

(Symmetric): Assume that $v_{i}\sim v_{j}$. Therefore, there exists a 2-path
sequence $T=(Z_{\ell}^{\pm 1})^{2}\cdots(Z_{2}^{\pm 1})^{2}(Z_{1}^{\pm
1})^{2}$ such that $v_{j}=\alpha\Big{(}(Z_{\ell}^{\pm 1})^{2}\cdots(Z_{2}^{\pm
1})^{2}(Z_{1}^{\pm 1})^{2}\Big{)}v_{i}$. It follows that
$v_{i}=\alpha\Big{(}(Z_{1}^{\mp 1})^{2}(Z_{2}^{\mp 1})^{2}\cdots(Z_{\ell}^{\mp
1})^{2}\Big{)}v_{j}$, where the inverse of $(Z_{i})^{\pm}$ is $Z_{i}^{\mp}$.
Therefore $v_{j}\sim v_{i}$.

(Transitive): Assume that $v_{i}\sim v_{j}$ and $v_{j}\sim v_{k}$. Then there
exists 2-path sequences $T_{1},T_{2}\in\mathcal{T}$ such that
$v_{j}=\alpha(T_{1})v_{i}\mbox{ and }v_{k}=\alpha(T_{2})v_{j}.$ Thus,
$v_{k}=\alpha(T_{2})\Big{(}\alpha(T_{1})v_{i}\Big{)}=\alpha(T_{2}T_{1})v_{i}$.
Since $T_{2}T_{1}\in\mathcal{T}$, $v_{i}\sim v_{k}$.
Therefore $\sim$ is an equivalence relation. ∎

Next, we take the partition of $V(G)$ into equivalence classes with respect to
the equivalence relation $\sim$ from Definition 5.5. We will denote the
equivalence class containing $v_{i}$ by $[v_{i}]$.

For the Schreier graph in Figure 9 above, the equivalence relation would
partition the vertices into two equivalence classes:
$[v_{1}]=\\{v_{1},v_{2},v_{5}\\}$ and $[v_{3}]=\\{v_{3},v_{4}\\}$. The sum of
the vertices in each equivalence class will form basis elements for the
abelian factor of the associated Lie algebra as detailed below.

######  Theorem 5.8.

Let ${\mathfrak{n}}_{G}$ be the Lie algebra associated with the Schreier graph
$G=(V,E,C)$ as defined above. Let $\beta$ be the the number of distinct
equivalence classes in the partition of $V(G)$ with respect to $\sim$ from
Definition 5.5. For ease of notation, we will relabel vertices if necessary in
order that the vertices $v_{1},v_{2},\ldots,v_{\beta}$ represent the distinct
equivalence classes. Define
$\displaystyle\xi_{i}=\sum_{v_{j}\in[v_{i}]}v_{j}$, for each $i$. Then the set
$\\{\xi_{i}\\}_{i=1}^{\beta}$ forms a basis for the abelian factor of
${\mathfrak{n}}_{G}$.

The following lemmas will lead us to the proof of this theorem.

######  Lemma 5.9.

For each $Z\in C$, $\alpha(Z^{2})$ permutes the vertices in each equivalence
class $[v]$. Consequently, $\alpha(Z^{2})\xi_{i}=\xi_{i}$ for all
$i=1,\ldots,\beta$ and $Z\in C$.

###### Proof.

Let $Z\in C$ and $v\in V(G)$. Let $w\in[v]$. Then there exists a 2-path
sequence $T$ such that $w=\alpha(T)v$. Therefore
$\alpha(Z^{2})w=\alpha(Z^{2})(\alpha(T)v)=\alpha(Z^{2}T)v\in[v]$ as $Z^{2}T$
is also a 2-path sequence. Also, if $w\in[v]$, then
$\alpha(Z^{-1})^{2}w\in[v]$ since $(Z^{-1})^{2}\in\mathcal{T}$. Then we see
that $\alpha(Z^{2})\Big{(}\alpha(Z^{-1})^{2}w\Big{)}=w$.

Now,

$\displaystyle\alpha(Z^{2})\xi_{i}$ $\displaystyle=$
$\displaystyle\alpha(Z^{2})\sum_{v_{j}\in[v_{i}]}v_{j}$ $\displaystyle=$
$\displaystyle\sum_{v_{j}\in[v_{i}]}\alpha(Z^{2})v_{j}$ $\displaystyle=$
$\displaystyle\sum_{v_{k}\in[v_{i}]}v_{k},$

because $\alpha(Z^{2})$ permutes the vertices in $[v_{i}]$. Thus
$\alpha(Z^{2})\xi_{i}=\xi_{i}$ for each $i=1,\ldots,\beta$. ∎

######  Lemma 5.10.

For each $i=1,\ldots,\beta$, $\xi_{i}$ is in the abelian factor of
${\mathfrak{n}}_{G}$.

###### Proof.

By Lemma 5.9, we know $\alpha(Z^{2})\xi_{i}=\xi_{i}$ for each $i$ and for all
$Z\in C$. By applying $\alpha(Z^{-1})$ to both sides of this equation, we get
$\alpha(Z)\xi_{i}=\alpha(Z^{-1})\xi_{i}$, which means
$\alpha(Z)\xi_{i}-\alpha(Z^{-1})\xi_{i}=0$. By Proposition 5.4,
$j(Z)\xi_{i}=0$ for each $i$ and for all $Z\in C$. Hence by Lemma 2.5,
$\xi_{i}$ is in the abelian factor for all $i=1,\dots,\beta$. ∎

######  Lemma 5.11.

Let $X$ be in the abelian factor of ${\mathfrak{n}}_{G}$. Then $\alpha(T)X=X$
for all 2-path sequences $T\in\mathcal{T}$. Consequently, $X$ is in the span
of $\\{\xi_{i}\\}_{i=1}^{\beta}$, using the notation of Theorem 5.8.

###### Proof.

Let $X$ be in the abelian factor of ${\mathfrak{n}}_{G}$. Then by Lemma 2.5,
it implies that $j(Z)X=0$ for all $Z\in C$. By Proposition 5.4, this means
that $\alpha(Z)X-\alpha(Z^{-1})X=0$. Hence $\alpha(Z)X=\alpha(Z^{-1})X$ and
$\alpha((Z^{\pm 1})^{2})X=X$ for all $Z\in C$. By induction, we get
$\alpha(T)X=X$ for all 2-path sequences $T\in\mathcal{T}$.

Let the vertex set $V=\\{v_{1},\ldots,v_{n}\\}$. Assume that
$X=\sum_{k=1}^{n}b_{k}v_{k}$ is in the abelian factor of ${\mathfrak{n}}_{G}$.
We will prove that $b_{i}=b_{j}$ whenever $v_{i}\sim v_{j}$. Suppose that
$v_{i}\sim v_{j}$ for some $i$ and $j$. By definition of $\sim$, there exists
a 2-path sequence $T$ such that $\alpha(T)(v_{i})=v_{j}$. We just proved that
$X$ is invariant under $\alpha(T)$ and hence

$\sum_{k=1}^{n}b_{k}\alpha(T)v_{k}=\sum_{k=1}^{n}b_{k}v_{k}.$

Since $\alpha(T)(v_{i})=v_{j}$, we can rewrite the above equation as follows:

$b_{i}v_{j}+\sum_{k\neq i}b_{k}\alpha(T)v_{k}=b_{j}v_{j}+\sum_{k\neq
j}b_{k}v_{k}.$

Using the fact that $\alpha(T)$ permutes the set of all vertices
$\\{v_{k}\\}$, there does not exist $k\neq i$ such that
$\alpha(T)v_{k}=v_{j}$. Also the set $\\{v_{k}\\}$ is linearly independent.
Hence $b_{i}=b_{j}$. Therefore, we have proved that if $v_{j}$ is in the
equivalence class $[v_{i}]$, then $b_{j}=b_{i}$. Thus

$\displaystyle
X=\sum_{i=1}^{\beta}\sum_{v_{j}\in[v_{i}]}b_{i}v_{j}=\sum_{i=1}^{\beta}b_{i}\sum_{v_{j}\in[v_{i}]}v_{j}=\sum_{i=1}^{\beta}b_{i}\xi_{i}.$

This proves that $X$ is in the span of $\\{\xi_{i}\\}_{i=1}^{\beta}$. ∎

Proof of Theorem 5.8. Let the vertex set $V=\\{v_{1},\ldots,v_{n}\\}$. Since
$V$ is a linearly independent set and $\\{[v_{i}]\\}_{i=1}^{\beta}$ is a
partition of $V(G)$, it follows directly that $\\{\xi_{i}\\}_{i=1}^{\beta}$ is
a linearly independent set. Also the set $\\{\xi_{i}\\}_{i=1}^{\beta}$ is a
subset of the abelian factor by Lemma 5.10. Moreover, by Lemma 5.11, the
abelian factor is the span of $\\{\xi_{i}\\}_{i=1}^{\beta}$ . Therefore
$\\{\xi_{i}\\}_{i=1}^{\beta}$ forms a basis for the abelian factor of
${\mathfrak{n}}_{G}$. ∎

######  Example 5.12.

For the Schreier graph $G$ in Figure 9, the resulting Lie algebra
${\mathfrak{n}}$ would have a two-dimensional abelian factor with basis
$\\{v_{1}+v_{2}+v_{5},v_{3}+v_{4}\\}$.

######  Example 5.13.

Consider the cycle $C_{n}$ with standard orientation and all edge labels the
same. Because $C_{n}$ can be considered a Schreier graph, we can use Theorem
5.8 to compute a basis for the abelian factor of ${\mathfrak{n}}_{C_{n}}$.

  1. (1)

If $n=2k$ is even, there will be two distinct equivalence classes:
$[v_{1}]=\\{v_{2i-1}\\}_{i=1}^{k}$ and $[v_{2}]=\\{v_{2i}\\}_{i=1}^{k}$.

  2. (2)

If $n$ is odd, there will be one equivalence class
$[v_{1}]=\\{v_{i}\\}_{i=1}^{n}$.

This will result in the same basis for the abelian factor of
${\mathfrak{n}}_{C_{n}}$ as in Theorem 4.2.

##  6\. Graph coloring

One area of interest in graph theory is edge-colored graphs. This is
equivalent to edge-labeled graphs by defining the set of edge labels to be the
set of colors. We can then use results from Section 2 to study the associated
2-step nilpotent Lie algebras. We assume that all graphs in this section are
simple.

###  6.1. Proper edge coloring

######  Definition 6.1.

An edge coloring on a graph $G$ is called a proper edge coloring if no two
incident edges have the same color.

######  Proposition 6.2.

Let $G$ be a simple graph with proper edge coloring. Then the associated
2-step nilpotent Lie algebra ${\mathfrak{n}}_{G}$ has no abelian factor.

###### Proof.

Since no edge label is repeated among the edges incident at any single vertex,
${\mathcal{A}}=\emptyset$. Thus, by Corollary 2.15, ${\mathfrak{n}}_{G}$ has
no abelian factor. ∎

######  Definition 6.3.

For a graph $G$, the _chromatic index_ of $G$ is denoted $\chi^{\prime}(G)$
and is the minimum number of colors required for a proper edge coloring of
$G$.

Observe that if $G$ has a proper edge coloring using $k$ colors, then a proper
edge coloring using more colors, up to the number of edges, can be obtained
from a proper $k$ coloring by introducing a new color on one edge whose label
appears more than one time in $G$.

Recall the following well-known result from Graph Theory, see [3] for example.
Denote the maximum degree of a vertex in $G$ by $\Delta(G)$.

######  Theorem 6.4 (Vizing’s Theorem).

For any finite simple graph $G$,

$\Delta(G)\leq\chi^{\prime}(G)\leq\Delta(G)+1.$

If $G$ is bipartite, then $\chi^{\prime}(G)=\Delta(G)$. If $G$ is a regular
graph (recall Definition 5.1) on an odd number of vertices, then
$\chi^{\prime}(G)=\Delta(G)+1$ [3]. Generally speaking, Paul Erdős proved that
almost all graphs have $\chi^{\prime}(G)=\Delta(G)$ [11].

######  Proposition 6.5.

Let $C_{n}$ be a cycle on $n$ vertices where $n$ is even. Then there exists an
edge labeling so that ${\mathfrak{n}}_{C_{n}}$ has no abelian factor and
$dim([{\mathfrak{n}}_{C_{n}},{\mathfrak{n}}_{C_{n}}])=k$ for each $2\leq k\leq
n$.

###### Proof.

For $n$ even, the cycle $C_{n}$ is bipartite, so,
$\chi^{\prime}({C_{n}})=\Delta({C_{n}})=2$. Thus a proper edge coloring exists
with $k$ colors where $2\leq k\leq n$. ∎

For every simple connected directed graph $G$, there exists an edge coloring
of $G$ that is proper. Thus, for every graph with $\chi^{\prime}(G)<|E(G)|$,
there is an edge coloring with multiple edges having the same label that the
resulting 2-step nilpotent Lie algebra ${\mathfrak{n}}_{G}$ has no abelian
factor. In fact, for each $k$ with $\chi^{\prime}(G)\leq k\leq|E(G)|$, we can
find an edge coloring of $G$ so that the resulting Lie algebra
${\mathfrak{n}}_{G}$ has no abelian factor and has
$dim([{\mathfrak{n}}_{G},{\mathfrak{n}}_{G}])=k$.

These results are consistent with the results of sections 3 and 4. We
illustrate with the following examples:

######  Example 6.6.

  1. (1)

Let $K_{1,n}$ be a star graph. Then $\chi^{\prime}(K_{1,n})=|E(K_{1,n})|=n$,
so there is only one proper coloring of $K_{1,n}$. If we color the edges so
that the coloring is not proper, then by Theorem 3.2 the corresponding Lie
algebra will have a nontrivial abelian factor.

  2. (2)

Let $C_{2n}$ be a cycle on an even number of vertices. We have
$\chi^{\prime}({C_{n}})=2$, and any proper coloring by $k$ colors for $2\leq
k\leq 2n$ will result in ${\mathfrak{n}}_{C_{n}}$ with no abelian factor.
However, there are non-proper edge colorings which also result in
${\mathfrak{n}}_{C_{n}}$ with trivial abelian factor. See Proposition 4.7 for
a precise description.

###  6.2. An application to uniformly colored graphs

We now consider a family of properly edge-colored graphs known as uniformly
colored graphs. In [25], the authors give a correspondence between uniform Lie
algebras and the 2-step nilpotent Lie algebras associated with uniformly
colored graphs.

######  Definition 6.7.

Let $G$ be a a regular graph where every vertex has degree $s>0$. A proper
edge coloring of the graph $G$ is called a _uniform coloring_ using $p$ colors
if each label is used $r$ times. If $G$ has $q$ vertices and if each label is
used $r$ times, then $G$ is called a $(p,q,r)$ uniform graph.

Since a uniform coloring is a proper coloring, we have that a graph with a
uniform coloring also results in the associated Lie algebra
${\mathfrak{n}}_{G}$ having no abelian factor. Hence the derived algebra of
${\mathfrak{n}}_{G}$ will be equal to the center of ${\mathfrak{n}}_{G}$.

We now give an application to the singularity properties of Lie algebras
arising from a graph $G$ with a uniform edge coloring. Refer back to
Definition 3.5 for the definition of singularity.

######  Proposition 6.8.

Let $G$ be a simple $(p,q,r)$ uniformly colored graph with an even number of
vertices such that the degree of each vertex, $s$, coincides with the number
of edge colors, $p$. Then the associated 2-step nilpotent Lie algebra
${\mathfrak{n}}_{G}$ is either nonsingular or almost nonsingular.

###### Proof.

Let $G$ be uniformly colored by edge labels $\\{Z_{1},\ldots,Z_{s}\\}$. Then
each edge label appears $r$ times in $G$ where $r=2q$. Consider the subgraph
of $G$ which is induced on the edges labeled $Z_{i}$, and denote this subgraph
by $G_{i}$. Observe since $G$ is uniformly colored and since each vertex has
precisely one incident edge with each edge label, the graph $G_{i}$ forms a
vertex covering of $G$ by disjoint copies of $K_{2}$. For each $i$, $1\leq
i\leq s$, there exists a permutation $\sigma_{i}$ of the set
$\\{1,\ldots,q=2r\\}$ so that in the ordered basis $\\{X_{\sigma_{i}(k)}\\}$
for ${\mathfrak{v}}\subset{\mathfrak{n}}_{G}$, the map $j(Z_{i})$ has matrix
of size $2r\times 2r$ in block diagonal form which has $r$ copies of the
$2\times 2$ block $\bigl{(}\begin{smallmatrix}0&-1\\\
1&0\end{smallmatrix}\bigr{)}$ on the diagonal. It is now apparent that
$j(Z_{i})$ has eigenvalues $\pm i$. Thus, $j(Z_{i})$ is nonsingular for all
$1\leq i\leq s$. Hence, the Lie algebra ${\mathfrak{n}}_{G}$ is either
nonsingular or almost nonsingular. ∎

######  Example 6.9.

Let $G$ be the $(3,6,3)$ uniformly colored graph in Figure 10.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$Z_{1}$$Z_{3}$$Z_{2}$$Z_{3}$$Z_{2}$$Z_{2}$$Z_{1}$$Z_{1}$$Z_{3}$
Figure 10. Example of a $(3,6,3)$ uniformly colored graph

Then a direct computation shows that for $Z_{0}=aZ_{1}+bZ_{2}+cZ_{3}$, the map
$j(Z_{0})$ has the following matrix in the basis for
${\mathfrak{v}}\subset{\mathfrak{n}}_{G}$ given by the vertices of $G$.

$\left(\begin{matrix}0&-a&0&-c&0&-b\\\ a&0&-c&0&-b&0\\\ 0&c&0&-b&0&-a\\\
c&0&b&0&-a&0\\\ 0&b&0&a&0&-c\\\ b&0&a&0&c&0\end{matrix}\right)$

The map $j(Z_{0})$ is nonsingular.

######  Example 6.10.

Let $C_{8}$ be a cycle on 8 vertices with standard orientation and edge labels
$Z_{1},Z_{2},Z_{3},Z_{4}$ repeated in that order around the cycle twice. This
graph is a $(4,8,2)$ uniformly colored graph. For each $1\leq i\leq 4$ we have
$j(Z_{i})$ singular. This is evident from the graph because each edge is not
incident on 4 of the vertices, giving each $j(Z_{i})$ a nontrivial nullspace.
However, a direct computation shows $j(Z_{1}+Z_{3})$ is nonsingular. Hence the
resulting Lie algebra ${\mathfrak{n}}_{C_{n}}$ is almost nonsingular.

##  7\. Conclusion

This article provides several results in the study of how edge-labeling
patterns in the graph can affect the algebraic structure of the resulting Lie
algebra. These results are primarily on the existence and description of an
abelian factor and singularity of nilpotent Lie algebras. While the results
stand on their own, there are several open questions that the authors suggest
for further research.

Open Question 1.  Is there a necessary and sufficient condition on a labeled
graph $G$ to determine the existence of a nontrivial abelian factor in
${\mathfrak{n}}_{G}$? Currently no such condition has been found, even in the
case where $G$ is a simple graph, leaving much left to investigate. We have
shown that changing the label or direction of a single edge can alter the
structure of the Lie algebra and its abelian factor. From the results
presented here, it is evident that the same-labeled paths of length two and
their incidence in the graph $G$ will play a significant role in determining
the algebraic properties of ${\mathfrak{n}}_{G}$.

Open Question 2. For a given Lie algebra ${\mathfrak{n}}$, can either the
graph labeling or construction method of the Lie algebra be adapted in such a
way that would result in an isomorphic Lie algebra ${\mathfrak{n}}^{\prime}$
that could be used more effectively to study these Lie algebras further? The
results in this article suggest that the study of Lie algebras associated to
graphs using different or adapted constructions may prove fruitful. For star
graphs, we describe a weighted graph with fewer edges that still encoded the
same information about the Lie algebra (Example 3.9). For any Schreier graph
$G$, it is possible to construct a new graph whose vertices are the
equivalence classes from Definition 5.5. This construction is useful for
determining the abelian factor of ${\mathfrak{n}}_{G}$, but does not
immediately generalize to non-Schreier graphs.

Open Question 3. Given that a labeled graph gives rise to a natural inner
product on the associated Lie algebra ${\mathfrak{n}}_{G}$, to what extent are
the geometric properties of these constructed Lie algebras determined by the
graph theoretic structure? We discussed singularity in Sections 3 and 6. A
particular topic of interest to the authors is which Lie algebras admit
metrics that are Heisenberg-like. In [7, Corollary 4.3], the first three
authors found that the Lie algebras constructed from simple graphs would be
Heisenberg-like if and only if the graph is either a star graph or a complete
graph on three vertices. It is unknown if a similar result can be obtained
when the graphs are allowed to have repeated edge labels. In the case of
repeated edge labels, it may be desirable to take the Lie algebra quotient
with the abelian factor. One obstacle to further geometric computation,
including geodesic properties, is finding a suitable basis so the computation
of the eigenvectors of the $j(Z)$ map is accessible.

## References

  * [1] A. Alfaro, M. Alvarez, Y. Anza, Degenerations of graph Lie algebras, Linear Multilinear Algebra. 70 (1): 91-100 (2022).
  * [2] A. Andrada, I. Dotti, Killing-Yano 2-forms on 2-step nilpotent Lie groups, Geom. Dedicata. 212: 415-424 (2021).
  * [3] J.A. Bondy, U.S.R. Murty, Graph Theory. Springer (2008).
  * [4] D. Chakrabarti, M. Mainkar, S. Swiatlowski, Automorphism groups of nilpotent Lie algebras associated to certain graphs, Comm. Algebra. 48 (1): 263-273 (2020).
  * [5] D. Conti, V. del Barco, F. Rossi, Diagram involutions and homogeneous Ricci-flat metrics, Manuscripta Math. 165 (3-4): 381-413 (2021).
  * [6] S. G. Dani, M. G. Mainkar, Anosov automorphisms on compact nilmanifolds associated with graphs, Trans. Amer. Math. Soc. 357: 2235-2251 (2005).
  * [7] R. DeCoste, L. DeMeyer, M. G. Mainkar, Graphs and metric 2-step nilpotent Lie algebras, Adv. Geom. 18 (3): 265-284 (2018).
  * [8] J. Deré, M. Mainkar, Anosov diffeomorphisms on infra-nilmanifolds associated to graphs, to appear in Math. Nachr., https://arxiv.org/pdf/2008.09717.pdf (2021).
  * [9] P. Eberlein, Geometry of 2-step nilpotent groups with a left invariant metric, I, Ann. Scient. École Normale Sup. (4) 27 (5): 611-660 (1994).
  * [10] P. Eberlein, Geometry of 2-step nilpotent groups with a left invariant metric II, Trans. Amer. Math. Soc. 343: 805-828 (1994).
  * [11] P. Erdős, On the chromatic index of almost all graphs, J. Combin. Theory Ser. B. 23: 225-257 (1977).
  * [12] H. Fanai̋, Einstein solvmanifolds and graphs, C. R. Math. 344 (1): 37-39 (2007).
  * [13] M. Farinati, A. Jancsa, Lie bialgebra structures on 2-step nilpotent graph algebras, J. Algebra. 505: 70-91, (2018).
  * [14] R. Gornet, M. Mast, The length spectrum of Riemannian two-step nilmanifolds, Ann. Scient. École Normale Sup. (4) 33 (2): 181-209 (2000).
  * [15] G. Grantcharov, V. Grantcharov, P. Iliev, Solvable Lie algebras and graphs, J. Algebra. 491: 474-489 (2017).
  * [16] J.L. Gross, Every connected regular graph of even degree is a Schreier coset graph, J. Combinatorial Theory. 22: 227-232 (1977).
  * [17] A. Kaplan, Riemannian nilmanifolds attached to Clifford modules, Geom. Dedicata. 11: 127-136 (1981).
  * [18] A. Kaplan, On the geometry of groups of Heisenberg type, Bull. London Math. Soc. 15 (1): 35-42 (1983).
  * [19] J. Lauret, C. Will, On Anosov automorphisms of nilmanifolds, J. Pure Appl. Algebra. 212 (7): 1747-1755 (2008).
  * [20] J. Lauret, C. Will, Einstein solvmanifolds: Existence and non-existence questions, Math. Ann. 350 (1): 199-225 (2011).
  * [21] K. Lee, K. Park, Smoothly closed geodesics in 2-step nilmanifolds, Indiana Univ. Math. J. 45: 1-14 (1996).
  * [22] M. Mainkar, Graphs and two-Step nilpotent Lie algebras, Groups Geom. Dyn. 9 (1): 55-65 (2015).
  * [23] Y. Nikolayevsky, Geodesic orbit and naturally reductive nilmanifolds associated with graphs, Math. Nachr. 293 (4): 754-760 (2020).
  * [24] G. Ovando, The geodesic flow on nilmanifolds associated to graphs, Rev. Un. Mat. Argentina. 61 (2): 315-338 (2020).
  * [25] T. L. Payne, M. Schroeder, Uniform Lie algebras and uniformly colored graphs, Adv. Geom. 17 (4): 507-524 (2017).
  * [26] H. Pouseele, P. Tirao, Compact symplectic nilmanifolds associated with graphs, J. Pure Appl. Algebra. 213 (9): 1788-1794 (2009).
  * [27] A. Ray, Two-step and three-step nilpotent Lie algebras constructed from Schreier graphs, J. Lie Theory. 26 (2): 479-495 (2016).