3 Quivers

A quiver Q is a set derived from a labeled directed multigraph with loops \Gamma. An element of Q is called a *path*, and falls into one of three classes. The first class is the set of *vertices* of \Gamma. The second class is the set of *walks* in \Gamma of length at least one, each of which is represented by the corresponding sequence of *arrows* in \Gamma. The third class is the singleton set containing the distinguished *zero path*, usually denoted 0. An associative multiplication is defined on Q.

This chapter describes the functions in **QPA** that deal with paths and quivers. The functions for constructing paths in Section 4.2 are normally not useful in isolation; typically, they are invoked by the functions for constructing quivers in Section 3.2.

`‣ InfoQuiver` | ( info class ) |

is the info class for functions dealing with quivers.

`‣ Quiver` ( N, arrows ) | ( function ) |

`‣ Quiver` ( vertices, arrows ) | ( function ) |

`‣ Quiver` ( adjacencymatrix ) | ( function ) |

Arguments: First construction: `N` -- number of vertices, `arrows` -- a list of arrows to specify the graph \Gamma. Second construction: `vertices` -- a list of vertex names, `arrows` -- a list of arrows. Third construction: takes an adjacency matrix for the graph \Gamma.

Returns: a quiver, which is an object from the category `IsQuiver`

(3.3-1).

In the first and third constructions, the vertices are named `v1, v2, ...'. In the second construction, unique vertex names are given as strings in the list that is the first parameter. Each arrow is a list consisting of a source vertex and a target vertex, followed optionally by an arrow name as a string.

Vertices and arrows are referenced as record components using the dot (`.') operator.

gap> q1 := Quiver(["u","v"],[["u","u","a"],["u","v","b"], > ["v","u","c"],["v","v","d"]]); <quiver with 2 vertices and 4 arrows> gap> VerticesOfQuiver(q1); [ u, v ] gap> ArrowsOfQuiver(q1); [ a, b, c, d ] gap> q2 := Quiver(2,[[1,1],[2,1],[1,2]]); <quiver with 2 vertices and 3 arrows> gap> ArrowsOfQuiver(q2); [ a1, a2, a3 ] gap> VerticesOfQuiver(q2); [ v1, v2 ] gap> q3 := Quiver(2,[[1,1,"a"],[2,1,"b"],[1,2,"c"]]); <quiver with 2 vertices and 3 arrows> gap> ArrowsOfQuiver(q3); [ a, b, c ] gap> q4 := Quiver([[1,1],[2,1]]); <quiver with 2 vertices and 5 arrows> gap> VerticesOfQuiver(q4); [ v1, v2 ] gap> ArrowsOfQuiver(q4); [ a1, a2, a3, a4, a5 ] gap> SourceOfPath(q4.a2); v1 gap> TargetOfPath(q4.a2); v2

`‣ DynkinQuiver` ( Delta, n, orientation ) | ( operation ) |

Arguments: `Delta`, `n`, `orientation` -- a character (A,D,E), a positive integer, and a list giving the orientation.

Returns: a Dynkin quiver of type `Delta` ("A", "D", or "E") with index `n` and orientation of the arrows given by the list `orientation`.

If `Delta` is equal to "A" with index `n`, then the list `orientation` is of the form `["r", "l", "l", ...,"r", "l"]`

of length `n-1`, where "l" or "r" in coordinate i means that the arrow a_i is oriented to the left or to the right, respectively. The vertices and the arrows are named as in the following diagram xymatrix1ar@-[r]^-a_1 & 2ar@-[r]^-a_2 & ar@--[r] & ar@-[r]^-a_n-2} & n - 1 ar@-[r]^-a_n-1} & n

If `Delta` is equal to "D" with index `n` and `n` greater or equal to 4, then the list `orientation` is of the form `["r", "l", "l", ...,"r", "l"]`

of length `n-1`, where "l" or "r" in coordinate i means that the arrow a_i is oriented to the left or to the right, respectively. The vertices and the arrows are named as in the following diagram xymatrix1ar@-[dr]^-a_1 & & & & & & 3ar@-[r]^a_3 & ar@--[r] & ar@-[r]^-a_n-2} & n - 1 ar@-[r]^-a_n-1} & n 2ar@-[ur]_-a_2 & & & & &

If `Delta` is equal to "E" with index `n` and `n` in [6,7,8], then the list `orientation` is of the form `["r", "l", "l", ...,"r", "l","d"]`

of length `n-1`, where "l" or "r" in the `n - 2` first coordinates and at coordinate i means that the arrow a_i is oriented to the left or to the right, respectively, and the last orientation parameter is "d" or "u" indicating if the arrow a_n-1 is oriented down or up. The vertices and the arrows are named as in the following diagram xymatrix & & nar@-[d]^a_n-1} & & & & & 1ar@-[r]^a_1 & 2ar@-[r]^a_2 & 3ar@-[r]^-a_3 & ar@--[r] &ar@-[r] & n - 2 ar@-[r]^-a_n-2} & n - 1

`‣ OrderedBy` ( quiver, ordering ) | ( function ) |

Returns: a copy of `quiver` whose elements are ordered by `ordering`. The default ordering of a quiver is length left lexicographic. See Section 3.4 for more information.

`‣ IsQuiver` ( object ) | ( category ) |

Returns: true when `object` is a quiver.

`‣ IsAcyclicQuiver` ( quiver ) | ( property ) |

Returns: true when `quiver` is a quiver with no oriented cycles.

`‣ IsUAcyclicQuiver` ( quiver ) | ( property ) |

Returns: true when `quiver` is a quiver with no unoriented cycles. Note: an oriented cycle is also an unoriented cycle!

`‣ IsConnectedQuiver` ( quiver ) | ( property ) |

Returns: true when `quiver` is a connected quiver (i.e. each pair of vertices is connected by an unoriented path in `quiver`).

`‣ IsTreeQuiver` ( quiver ) | ( property ) |

Returns: true when `quiver` is a tree as a graph (i.e. it is connected and contains no unoriented cycles).

gap> q1 := Quiver(2,[[1,2]]); <quiver with 2 vertices and 1 arrows> gap> IsQuiver("v1"); false gap> IsQuiver(q1); true gap> IsAcyclicQuiver(q1); IsUAcyclicQuiver(q1); true true gap> IsConnectedQuiver(q1); IsTreeQuiver(q1); true true gap> q2 := Quiver(["u","v"],[["u","v"],["v","u"]]); <quiver with 2 vertices and 2 arrows> gap> IsAcyclicQuiver(q2); IsUAcyclicQuiver(q2); false false gap> IsConnectedQuiver(q2); IsTreeQuiver(q2); true false gap> q3 := Quiver(["u","v"],[["u","v"],["u","v"]]); <quiver with 2 vertices and 2 arrows> gap> IsAcyclicQuiver(q3); IsUAcyclicQuiver(q3); true false gap> IsConnectedQuiver(q3); IsTreeQuiver(q3); true false gap> q4 := Quiver(2, []); <quiver with 2 vertices and 0 arrows> gap> IsAcyclicQuiver(q4); IsUAcyclicQuiver(q4); true true gap> IsConnectedQuiver(q4); IsTreeQuiver(q4); false false

`‣ IsDynkinQuiver` ( quiver ) | ( property ) |

Returns: true when `quiver` is a Dynkin quiver (more precisely, when underlying undirected graph of `quiver` is a Dynkin diagram).

This function prints an additional information. If it returns true, it prints the Dynkin type of `quiver`, i.e. A_n, D_m, E_6, E_7 or E_8. Moreover, in case `quiver` is not connected or contains an unoriented cycle, the function also prints a respective info.

gap> q1 := Quiver(4,[[1,4],[4,2],[3,4]]); <quiver with 4 vertices and 3 arrows> gap> IsDynkinQuiver(q1); D_4 true gap> q2 := Quiver(2,[[1,2],[1,2]]); <quiver with 2 vertices and 2 arrows> gap> IsDynkinQuiver(q2); Quiver contains an (un)oriented cycle. false gap> q3 := Quiver(5,[[1,5],[2,5],[3,5],[4,5]]); <quiver with 5 vertices and 4 arrows>

The only supported ordering on the paths in a quiver is length left lexicographic ordering. The reason for this is that **QPA** does not have its own functions for computing Groebner basis. Instead they are computed using the **GAP**-package **GBNP**. The interface with this package, which is provided by the **QPA**, only supports the length left lexicographic ordering, even though **GBNP** supports more orderings.

For constructing a quiver, there are three different methods. TODO: Explain how the vertices and arrows are ordered.

`‣ .` ( Q, element ) | ( operation ) |

Arguments: `Q` -- a quiver, and `element` -- a vertex or an arrow.

The operation `.`

allows access to generators of the quiver. If you have named your vertices and arrows then the access looks like ``Q`.`name of element`'. If you have not named the elements of the quiver, then the default names are v1, v2, ... and a1, a2, ... in the order they are created.

`‣ VerticesOfQuiver` ( quiver ) | ( attribute ) |

Returns: a list of paths that are vertices in `quiver`.

`‣ ArrowsOfQuiver` ( quiver ) | ( attribute ) |

Returns: a list of paths that are arrows in `quiver`.

`‣ AdjacencyMatrixOfQuiver` ( quiver ) | ( attribute ) |

Returns: the adjacency matrix of `quiver`.

`‣ GeneratorsOfQuiver` ( quiver ) | ( attribute ) |

Returns: a list of the vertices and the arrows in `quiver`.

`‣ NumberOfVertices` ( quiver ) | ( attribute ) |

Returns: the number of vertices in `quiver`.

`‣ NumberOfArrows` ( quiver ) | ( attribute ) |

Returns: the number of arrows in `quiver`.

`‣ OrderingOfQuiver` ( quiver ) | ( attribute ) |

Returns: the ordering used to order elements in `quiver`. See Section 3.4 for more information.

`‣ OppositeQuiver` ( quiver ) | ( attribute ) |

Returns: the opposite quiver of `quiver`, where the vertices are labelled "name in original quiver" + "_op" and the arrows are labelled "name in orginal quiver" + "_op".

This attribute contains the opposite quiver of a quiver, that is, a quiver which is the same except that every arrow goes in the opposite direction.

The operation `OppositePath`

(4.16-1) takes a path in a quiver to the corresponding path in the opposite quiver.

The opposite of the opposite of a quiver Q is isomorphic to Q. In QPA, we regard these two quivers to be the same, so the call `OppositeQuiver(OppositeQuiver(Q))`

returns the object `Q`

.

gap> q1 := Quiver(["u","v"],[["u","u","a"],["u","v","b"], > ["v","u","c"],["v","v","d"]]); <quiver with 2 vertices and 4 arrows> gap> q1.a; a gap> q1.v; v gap> VerticesOfQuiver(q1); [ u, v ] gap> ArrowsOfQuiver(q1); [ a, b, c, d ] gap> AdjacencyMatrixOfQuiver(q1); [ [ 1, 1 ], [ 1, 1 ] ] gap> GeneratorsOfQuiver(q1); [ u, v, a, b, c, d ] gap> NumberOfVertices(q1); 2 gap> NumberOfArrows(q1); 4 gap> OrderingOfQuiver(q1); <length left lexicographic ordering> gap> q1_op := OppositeQuiver(q1); <quiver with 2 vertices and 4 arrows> gap> VerticesOfQuiver(q1_op); [ u_op, v_op ] gap> ArrowsOfQuiver(q1_op); [ a_op, b_op, c_op, d_op ]

`‣ FullSubquiver` ( quiver, list ) | ( operation ) |

Returns: This function returns a quiver which is a full subquiver of a `quiver` induced by the `list` of its vertices.

The names of vertices and arrows in resulting (sub)quiver remain the same as in original one. The function checks if `list` consists of vertices of `quiver`.

`‣ ConnectedComponentsOfQuiver` ( quiver ) | ( operation ) |

Returns: This function returns a list of quivers which are all connected components of a `quiver`.

The names of vertices and arrows in resulting (sub)quiver remain the same as in original one. The function sets the property `IsConnectedQuiver`

(3.3-4) to true for all the components.

gap> Q := Quiver(6, [ [1,2],[1,1],[3,2],[4,5],[4,5] ]); <quiver with 6 vertices and 5 arrows> gap> VerticesOfQuiver(Q); [ v1, v2, v3, v4, v5, v6 ] gap> FullSubquiver(Q, [Q.v1, Q.v2]); <quiver with 2 vertices and 2 arrows> gap> ConnectedComponentsOfQuiver(Q); [ <quiver with 3 vertices and 3 arrows>, <quiver with 2 vertices and 2 arrows>, <quiver with 1 vertices and 0 arrows> ]

`‣ DoubleQuiver` ( quiver ) | ( attribute ) |

Arguments: `quiver` -- a quiver.

Returns: the double quiver of `quiver`.

The vertices in the double quiver are labelled by the same labels as in the original quiver. The "old" arrows in the double quiver are labelled by the same labels as in the original, and the "new" arrows in the double quiver are labelled by the same labels as in the original quiver with the string "bar" added.

`‣ SeparatedQuiver` ( quiver ) | ( attribute ) |

Arguments: `quiver` -- a quiver.

Returns: the separated quiver of `quiver`.

The vertices in the separated quiver are labelled v and v' for each vertex v in `quiver`, and for each arrow a: v -> w in `quiver` the arrow v-> w' is labelled a.

`‣ IsPath` ( object ) | ( category ) |

All path objects are in this category.

`‣ IsQuiverVertex` ( object ) | ( category ) |

All vertices are in this category.

`‣ IsArrow` ( object ) | ( category ) |

All arrows are in this category.

`‣ IsZeroPath` ( object ) | ( property ) |

is true when `object` is the zero path.

gap> q1 := Quiver(["u","v"],[["u","u","a"],["u","v","b"], > ["v","u","c"],["v","v","d"]]); <quiver with 2 vertices and 4 arrows> gap> IsPath(q1.b); true gap> IsPath(q1.u); true gap> IsQuiverVertex(q1.c); false gap> IsZeroPath(q1.d); false

`‣ SourceOfPath` ( path ) | ( attribute ) |

Returns: the source (first) vertex of `path`.

`‣ TargetOfPath` ( path ) | ( attribute ) |

Returns: the target (last) vertex of `path`.

`‣ LengthOfPath` ( path ) | ( attribute ) |

Returns: the length of `path`.

`‣ WalkOfPath` ( path ) | ( attribute ) |

Returns: a list of the arrows that constitute `path` in order.

`‣ *` ( p, q ) | ( operation ) |

Arguments: `p` and `q` -- two paths in the same quiver.

Returns: the multiplication of the paths. If the paths are not in the same quiver an error is returned. If the target of `p` differs from the source of `q`, then the result is the zero path. Otherwise, if either path is a vertex, then the result is the other path. Finally, if both are paths of length at least 1, then the result is the concatenation of the walks of the two paths.

gap> q1 := Quiver(["u","v"],[["u","u","a"],["u","v","b"], > ["v","u","c"],["v","v","d"]]); <quiver with 2 vertices and 4 arrows> gap> SourceOfPath(q1.v); v gap> p1:=q1.a*q1.b*q1.d*q1.d; a*b*d^2 gap> TargetOfPath(p1); v gap> p2:=q1.b*q1.b; 0 gap> WalkOfPath(p1); [ a, b, d, d ] gap> WalkOfPath(q1.a); [ a ] gap> LengthOfPath(p1); 4 gap> LengthOfPath(q1.v); 0

`‣ =` ( p, q ) | ( operation ) |

Arguments: `p` and `q` -- two paths in the same quiver.

Returns: true if the two paths are equal. Two paths are equal if they have the same source and the same target and if they have the same walks.

`‣ <` ( p, q ) | ( operation ) |

Arguments: `p` and `q` -- two paths in the same quiver.

Returns: a comparison of the two paths with respect to the ordering of the quiver.

`‣ IncomingArrowsOfVertex` ( vertex ) | ( attribute ) |

Returns: a list of arrows having `vertex` as target. Only meaningful if `vertex` is in a quiver.

`‣ OutgoingArrowsOfVertex` ( vertex ) | ( attribute ) |

Returns: a list of arrows having `vertex` as source.

`‣ InDegreeOfVertex` ( vertex ) | ( attribute ) |

Returns: the number of arrows having `vertex` as target. Only meaningful if `vertex` is in a quiver.

`‣ OutDegreeOfVertex` ( vertex ) | ( attribute ) |

Returns: the number of arrows having `vertex` as source.

`‣ NeighborsOfVertex` ( vertex ) | ( attribute ) |

Returns: a list of neighbors of `vertex`, that is, vertices that are targets of arrows having `vertex` as source.

gap> q1 := Quiver(["u","v"],[["u","u","a"],["u","v","b"], > ["v","u","c"],["v","v","d"]]); <quiver with 2 vertices and 4 arrows> gap> OutgoingArrowsOfVertex(q1.u); [ a, b ] gap> InDegreeOfVertex(q1.u); 2 gap> NeighborsOfVertex(q1.v); [ u, v ]

This implementation of posets was done by the HomAlg-project.

`‣ Poset` ( P, rel ) | ( operation ) |

Arguments: `P` a list and `rel` -- a list of pairs from `P`.

Returns: the poset defined on the points `P` and the relations generated by `rel`.

The elements in `P` is given as a list, and for example `["a", "b", "c", "d"]`

and the relations are given as a list of lists, for instance in the above case: `[ ["a", "b", "c"], ["b", "d"], ["c", "d"]].`

The first list means that a < b and a < c, and the second one means b < d and finally the last one means c < d.

`‣ Size` ( P ) | ( attribute ) |

Returns: the number of elements of the poset `P`.

`‣ UnderlyingSet` ( P ) | ( operation ) |

Arguments: `P` -- poset.

Returns: the underlying set of the poset `P`.

`‣ PartialOrderOfPoset` ( P ) | ( operation ) |

Arguments: `P` -- poset.

Returns: the partial order of the poset `P` as a function.

generated by GAPDoc2HTML