Polygraph (mathematics)

A polygraph with 0-cells (vertices), 1-cells (gray edges), 2-cells (red edges), and 3-cells (blue edges). The red shading indicates a path of two 1-cells (a, b) that together form the source of a 2-cell. This can be done for the source and/or target of any dimension (where applicable, 0-cells can't be connected, and so 0 and 1-cells can't show this property), as long as the set is a path (tip-to-tail) such as cells a and b.

This article is about a notion of higher-dimensional directed graph. For the forensic instrument, see Polygraph. For the dual pen device that produces a simultaneous copy of an original while it is written in cursive writing, see Polygraph (duplicating device). For an author that can write on a variety of different subjects, see Polygraph (author).

In mathematics, and particularly in category theory, a polygraph is a generalisation of a directed graph. It is also known as a computad. They were introduced as "polygraphs" by Albert Burroni ^[1] and as "computads" by Ross Street. ^[2]

In the same way that a directed multigraph can freely generate a category, an n-computad is the "most general" structure which can generate a free n-category. ^[3]

In the context of a graph, each dimension is represented as a set of ${\displaystyle k}$-cells. Vertices would make up the 0-cells, edges connecting vertices would be 1-cells, and then each dimension higher connects groups of the dimension beneath it. For 2-cells and up, which connect edges themselves, a source or target may consist of multiple edges of the dimension below it, as long as each set of elements are composites, i.e., are paths connected tip-to-tail. ^[3]

A globular set can be seen as a specific instance of a polygraph. In a polygraph, a source or target of a ${\displaystyle k}$-cell may consist of an entire path of elements of (${\displaystyle k}$-1)-cells, but a globular set restricts this to singular elements of (${\displaystyle k}$-1)-cells. ^{[3] [4]}

References

1. A. Burroni. Higher-dimensional word problems with applications to equational logic. TCS, 115(1):43--62, 1993.
2. R. Street. Limits indexed by category-valued 2-functors. Journal of Pure and Applied Algebra, 8(2):149--181, 1976.
3. computad at the nLab
4. globular+set at the nLab