Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

3 Quivers
 3.1 Information class, Quivers
 3.2 Constructing Quivers
 3.3 Categories and Properties of Quivers
 3.4 Orderings of paths in a quiver
 3.5 Attributes and Operations for Quivers
 3.6 Categories and Properties of Paths
 3.7 Attributes and Operations of Paths
 3.8 Attributes of Vertices
 3.9 Posets

3 Quivers

3.1 Information class, 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.

3.1-1 InfoQuiver
‣ InfoQuiver( info class )

is the info class for functions dealing with quivers.

3.2 Constructing Quivers

3.2-1 Quiver
‣ 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

3.2-2 DynkinQuiver
‣ 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

3.2-3 OrderedBy
‣ 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.

3.3 Categories and Properties of Quivers

3.3-1 IsQuiver
‣ IsQuiver( object )( category )

Returns: true when object is a quiver.

3.3-2 IsAcyclicQuiver
‣ IsAcyclicQuiver( quiver )( property )

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

3.3-3 IsUAcyclicQuiver
‣ IsUAcyclicQuiver( quiver )( property )

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

3.3-4 IsConnectedQuiver
‣ 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).

3.3-5 IsTreeQuiver
‣ 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

3.3-6 IsDynkinQuiver
‣ 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>

3.4 Orderings of paths in a quiver

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.

3.5 Attributes and Operations for Quivers

3.5-1 .
‣ .( 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.

3.5-2 VerticesOfQuiver
‣ VerticesOfQuiver( quiver )( attribute )

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

3.5-3 ArrowsOfQuiver
‣ ArrowsOfQuiver( quiver )( attribute )

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

3.5-4 AdjacencyMatrixOfQuiver
‣ AdjacencyMatrixOfQuiver( quiver )( attribute )

Returns: the adjacency matrix of quiver.

3.5-5 GeneratorsOfQuiver
‣ GeneratorsOfQuiver( quiver )( attribute )

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

3.5-6 NumberOfVertices
‣ NumberOfVertices( quiver )( attribute )

Returns: the number of vertices in quiver.

3.5-7 NumberOfArrows
‣ NumberOfArrows( quiver )( attribute )

Returns: the number of arrows in quiver.

3.5-8 OrderingOfQuiver
‣ OrderingOfQuiver( quiver )( attribute )

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

3.5-9 OppositeQuiver
‣ 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 original 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 ]

3.5-10 FullSubquiver
‣ 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.

3.5-11 ConnectedComponentsOfQuiver
‣ 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> ]

3.5-12 DoubleQuiver
‣ 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.

3.5-13 SeparatedQuiver
‣ 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.

3.6 Categories and Properties of Paths

3.6-1 IsPath
‣ IsPath( object )( category )

All path objects are in this category.

3.6-2 IsQuiverVertex
‣ IsQuiverVertex( object )( category )

All vertices are in this category.

3.6-3 IsArrow
‣ IsArrow( object )( category )

All arrows are in this category.

3.6-4 IsZeroPath
‣ 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

3.7 Attributes and Operations of Paths

3.7-1 SourceOfPath
‣ SourceOfPath( path )( attribute )

Returns: the source (first) vertex of path.

3.7-2 TargetOfPath
‣ TargetOfPath( path )( attribute )

Returns: the target (last) vertex of path.

3.7-3 LengthOfPath
‣ LengthOfPath( path )( attribute )

Returns: the length of path.

3.7-4 WalkOfPath
‣ WalkOfPath( path )( attribute )

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

3.7-5 *
‣ *( 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

3.7-6 =
‣ =( 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.

3.7-7 <
‣ <( 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.

3.8 Attributes of Vertices

3.8-1 IncomingArrowsOfVertex
‣ IncomingArrowsOfVertex( vertex )( attribute )

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

3.8-2 OutgoingArrowsOfVertex
‣ OutgoingArrowsOfVertex( vertex )( attribute )

Returns: a list of arrows having vertex as source.

3.8-3 InDegreeOfVertex
‣ InDegreeOfVertex( vertex )( attribute )

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

3.8-4 OutDegreeOfVertex
‣ OutDegreeOfVertex( vertex )( attribute )

Returns: the number of arrows having vertex as source.

3.8-5 NeighborsOfVertex
‣ 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 ]

3.9 Posets

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

3.9-1 Poset
‣ 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.

3.9-2 Size
‣ Size( P )( attribute )

Returns: the number of elements of the poset P.

3.9-3 UnderlyingSet
‣ UnderlyingSet( P )( operation )

Arguments: P -- poset.

Returns: the underlying set of the poset P.

3.9-4 PartialOrderOfPoset
‣ PartialOrderOfPoset( P )( operation )

Arguments: P -- poset.

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

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 Bib Ind

generated by GAPDoc2HTML