nLab quiver

Redirected from "directed pseudograph".
Contents

This entry is about the mathematical notion. For the commutative diagram editor, see quiver (editor).

Context

Graph theory

Representation theory

Contents

Idea

A quiver (Gabriel 72) is a collection of edges which may stretch between (ordered) pairs of “points”, called vertices. Hence a quiver is a kind of graph.

The term “quiver” (German: Köcher) — for what in graph theory is (and was) known as directed graphs (directed pseudo-multigraphs, to be precise) — is due to Gabriel 1972, where it says on the first page:

For such a 4-tuple [\big[ EtsVE \underoverset{\underset{t}{\longrightarrow}}{\overset{s}{\longrightarrow}}{} V ]\big] we propose the term quiver, and not graph, since there are already too many notions attached to the latter word.

Hence the notion “quiver” is a concept with an attitude, indicating that one is interested in certain special constructions with these graphs, distinct from what graph theory typically cares about: Namely one is interested in their quiver representations. In this way, “quiver” is really a term in representation theory; see also Derksen & Weyman 2005, ftn 1:

The underlying motivations of quiver theory are quite different from those in the traditional graph theory. To emphasize this distinction, it is common in our context to use the word “quivers” instead of “graphs”.

A key result in quiver representation-theory is Gabriel's theorem, also form Gabriel 1972.

Definitions

Slick definition

The walking quiver1 XX is the category with

  • one object X 0X_0, called the object of vertices;

  • one object X 1X_1, called the object of edges;

  • two morphisms s,t:X 1X 0s, t\colon X_1 \to X_0, called the source and target;

  • together with identity morphisms.

A quiver is a functor G:XG\colon X \to Set.

More generally, a quiver in a category CC is a functor G:XCG\colon X \to C.

The category of quivers in CC, Quiv(C)(C), is the functor category C XC^{X}, where:

In the basic case where CC is Set, the category Quiv(Set) is equivalent to the category of presheaves on X opX^{op}. So: the category of quivers, Quiv, is the category of presheaves on the category X opX^{op}.

Nuts-and-bolts definitions

A quiver GG consists of two sets EE (the set of edges of GG), VV (the set of vertices of GG) and two functions

s,t:EVs, t\colon E \rightrightarrows V

(the source and target functions). More generally, a quiver internal to a category (more simply, in a category) CC consists of two objects EE, VV and two morphisms s,t:EVs, t\colon E \rightrightarrows V.

If G=(E,V,s,t)G = (E, V, s, t) and G=(E,V,s,t)G' = (E', V', s', t') are two quivers in a category CC, a morphism g:GGg\colon G \to G' is a pair of morphisms g 0:VVg_0\colon V \to V', g 1:EEg_1\colon E \to E' such that sg 1=g 0ss' \circ g_1 = g_0 \circ s and tg 1=g 0tt' \circ g_1 = g_0 \circ t.

In graph theory, a quiver is often (cf. p. 4 or Figure 2-2) called a directed pseudograph (or some variation on that theme), but category theorists often just call them directed graphs.

Remarks

Let G 0=G(X 0)G_0 = G(X_0) and G 1=G(X 1)G_1 = G(X_1).

  • A quiver in CC is a presheaf on X opX^{op} with values in CC.

  • A quiver is a globular set which is concentrated in the first two degrees.

  • A quiver can have distinct edges e,eG 1e,e'\in G_1 such that s(e)=s(e)s(e) = s(e') and t(e)=t(e)t(e) = t(e'). A quiver can also have loops, namely, edges with s(e)=t(e)s(e) = t(e).

  • A quiver is complete if for any pair of vertices v,vG 0v,v'\in G_0, there exists a unique directed edge eG 1e\in G_1 with s(e)=v,t(e)=vs(e) = v, t(e) = v'.

Terminology

Saying quiver instead of directed (multi)graph indicates focus on a certain set of operation intended on that graph. Notably there is the notion of a quiver representation.

Now, one sees that a representation of a graph GG in the sense of quiver representation is nothing but a functor ρ:Q:=F(G)Vect\rho\colon Q := F(G) \to Vect from the free category F(G)F(G) on the quiver GG:

Given a graph GG with collection of vertices G 0G_0 and collection of edges G 1G_1, there is the free category F(G)F(G) on the graph whose collection of objects coincides with the collection of vertices, and whose collection of morphisms consists of finite sequences of edges in GG that fit together head-to-tail (also known as paths). The composition operation in this free category is the concatenation of sequences of edges.

Here we are taking advantage of the adjunction between Cat (the category of small categories) and Quiv (the category of directed graphs). Namely, any category has an underlying directed graph:

U:CatQuivU\colon Cat \to Quiv

and the left adjoint of this functor gives the free category on a directed graph:

F:QuivCatF\colon Quiv\to Cat

Since this is the central operation on quivers that justifies their distinction from the plain concept of directed graph, we may adopt here the point of view that quiver is synonymous with free category.

So a representation of a quiver Q=F(G)Q = F(G) is a functor

R:QVectR\colon Q \to Vect

Concretely, such a thing assigns a vector space to each vertex of the graph GG, and a linear operator to each edge. Representations of quivers are fascinating things, with connections to ADE theory, quantum groups, string theory, and more.

Properties

Relation to free categories

It may be handy to identify a quiver with its free category. This can be justified in the sense that the functor F:QuivCatF\colon Quiv \to Cat is an embedding (kk-surjective for all k>0k \gt 0) on the cores. In other words, isomorphisms between quivers may be identified with equivalences between free categories with no ambiguity.

However, at the level of noninvertible morphisms, this doesn't work; while UU is faithful, it is not full. In other words, there are many functors between free categories that are not morphisms of quivers.

Nevertheless, if we fix a quiver GG and a category DD, then a representation of GG in DD is precisely a functor from F(G)F(G) to DD (or equivalently a quiver morphism from GG to U(D)U(D)), and we may well want to think of this as being a morphism (a heteromorphism) from GG to DD. As long as DD is not itself a free category, this is unlikely to cause confusion.

Relation to representation theory of algebras

For QQ a quiver, write kQk Q for the path algebra of QQ over a ground field kk. That is, kQk Q is an algebra with kk-basis given by finite composable sequences of arrows in QQ, including a “lazy path” of length zero at each vertex. The product of two paths composable paths is their composite, and the product of non-composable paths is zero.

A module over kQk Q is the same thing as a representation of QQ, so the theory of representations of quivers can be viewed within the broader context of representation theory of (associative) algebras.

If QQ is acyclic, then kQk Q is finite-dimensional as a vector space, so in studying representations of QQ, we are really studying representations of a finite dimensional algebra, for which many interesting tools exist (Auslander-Reiten theory, tilting, etc.).

Classification

Gabriel's theorem (Gabriel 72) says that connected quivers with a finite number of indecomposable quiver representations over an algebraically closed fieldare precisely the Dynkin quivers: those whose underlying undirected graph is a Dynkin diagram in the ADE series, and that the indecomposable quiver representations are in bijection with the positive roots in the root system of the Dynkin diagram. (Gabriel 72).

Generalizations

Enriched quivers

Let VV be a category (or a (infinity,1)-category). A quiver QQ is a VV-enriched quiver if it has a collection of objects Ob(Q)Ob(Q) and a VV-valued functor Mor:Ob(Q)×Ob(Q)VMor: Ob(Q) \times Ob(Q) \to V for all objects a,bOb(Q)a, b \in Ob(Q). Quivers in the usual sense are enriched in Set, while loop directed graphs/binary endorelations are quivers enriched in the category of truth values Ω\Omega. n n -quivers are quivers enriched in the category of (n1)(n-1)-quivers.

In dependent type theory with universes, a type equipped with an identity type is a quiver type enriched in a universe Type.

algebraic structureoidification
magmamagmoid
pointed magma with an endofunctionsetoid/Bishop set
unital magmaunital magmoid
quasigroupquasigroupoid
looploopoid
semigroupsemicategory
monoidcategory
anti-involutive monoiddagger category
associative quasigroupassociative quasigroupoid
groupgroupoid
flexible magmaflexible magmoid
alternative magmaalternative magmoid
absorption monoidabsorption category
cancellative monoidcancellative category
rigCMon-enriched category
nonunital ringAb-enriched semicategory
nonassociative ringAb-enriched unital magmoid
ringringoid
nonassociative algebralinear magmoid
nonassociative unital algebraunital linear magmoid
nonunital algebralinear semicategory
associative unital algebralinear category
C-star algebraC-star category
differential algebradifferential algebroid
flexible algebraflexible linear magmoid
alternative algebraalternative linear magmoid
Lie algebraLie algebroid
monoidal poset2-poset
strict monoidal groupoid?strict (2,1)-category
strict 2-groupstrict 2-groupoid
strict monoidal categorystrict 2-category
monoidal groupoid(2,1)-category
2-group2-groupoid/bigroupoid
monoidal category2-category/bicategory

References

The concept of quiver in the context of quiver representation (and their classification in Gabriel's theorem) originates with

Some general-purpose references include

  • Harm Derksen, Jerzy Weyman, Quiver representations, Notices of the AMS (Feb 2005) [pdf, full:pdf]

  • William Crawley-Boevey, Lectures on quiver representations (pdf).

  • Alistair Savage, Finite-dimensional algebras and quivers (arXiv:math/0505082), Encyclopedia of Mathematical Physics, eds. J.-P. Françoise, G.L. Naber and Tsou S.T., Oxford, Elsevier, 2006, volume 2, pp. 313-320.

Quivers (referred to as directed pseudographs) were a tool in parts of the work of Ringel and Youngs in the second half the twentieth century to prove Heawood’s formula for every finite genus, cf. e.g. Fig. 2.3 the monograph

  • Gerhard Ringel: Map Color Theorem. Springer. Grundlehren Band 209. 1974

Beware that, strictly speaking, for Ringel, “quiver” means “embedded quiver” (into a given surface); in particular the author distinguishes between the two possible orientations of an embedded loop.

Quivers embedded in surfaces are studied in:

  • Arthur T. White: Graphs, Groups and Surfaces. North Holland. Completely revised and enlarged edition (1985)

A special kind of quiver (finite, no loops, no parallel arcs) is treated in

  • Gregory Gutin, Jørgen Bang-Jensen: Digraphs: Theory, Algorithms and Applications. Springer Monographs in Mathematics. Second Edition (2009)

  • William Lawvere: Qualitative Distinctions Between Some Toposes of Generalized Graphs, Contemporary Mathematics 92 (1989)

Some introductory material on the relation between quivers (there called multigraphs) and categories can be found in


  1. Also called “the elementary ”parallel process“ ” by Lawvere in p. 272, “a category that has no compositions in it” by Lawvere, in his lecture at Como.

Last revised on November 14, 2023 at 09:29:54. See the history of this page for a list of all contributions to it.