nLab
graph of a functor

Idea

In as far as the notion of functor generalizes that of function and that of profunctor generalizes that of relation, the notion of graph of a (pro)functor generalizes that of graph of a function.

Just as the graph of a function $f:X\to Y$, or more generally that of a relation $R\subset X\times Y$ for $X,Y\in \mathrm{Set}=0\mathrm{Cat}$ is nothing but the category of elements of the corresponding characteristic function ${\chi }_R:X\times Y\to (-1)\mathrm{Cat}=\{\mathrm{0,1}\}$, so the graph of a functor $F:C\to D$, or more generally that of a profunctor $\chi :C^{\mathrm{op}}\times D\to 0\mathrm{Cat}=\mathrm{Set}$, is nothing but its category of elements.

Generally, the graph of a functor $f:C\to D$ between $(n,r)$-categories is the Grothendieck construction of the corresponding correspondence: the fibration classified by the correspondence, i.e. the comma object

$$\begin{array}{ccc}\mathrm{Graph}(f)& \to & *\\ \downarrow & & \downarrow \\ C^{\mathrm{op}}\times D& \stackrel{{\chi }_f}{\to }& (n-1,r-1)\mathrm{Cat}\end{array}$$\array{ Graph(f) &\to& {*} \\ \downarrow && \downarrow \\ C^{op} \times D &\stackrel{\chi_f}{\to}& (n-1,r-1)Cat }

whenever this makes sense. For instance in the context of $(\mathrm{\infty }\mathrm{,1})$-category theory the graph may be taken to be the fibration classified by ${\chi }_f:C\times D^{\mathrm{op}}\to (\mathrm{\infty }\mathrm{,0})$ as described at universal fibration of (∞,1)-categories.

Definition

For $n\le \mathrm{\infty }$ let $(n-1)\mathrm{Cat}$ and $n\mathrm{Cat}$ be a realization of the notions of $n$-category of $(n-1)$-categories and of the $(n+1)$-category of $n$-categories, respectively, such that standard constructions of category theory work, in particular a version of the Yoneda lemma. See higher category theory.

Eric: Is it really necessary to restrict $n$ to $0\le n\le \mathrm{\infty }$? In principle, couldn’t you have a graph of a (-1)-functor and/or (-2)-functor?

Toby: Sure. There's not much to them, but why not?

Then with $C,D\in n\mathrm{Cat}$ let $f:C\to D$ be a ($n$-)functor.

By the general logic of distributors this defines an $n$-correspondence

$${\chi }_f:C^{\mathrm{op}}\times D\stackrel{f^{\mathrm{op}}\times \mathrm{Id}}{\to }{D}^{\mathrm{op}}\times D\stackrel{\mathrm{Func}(-,-)}{\to }(n-1)\mathrm{Cat}$$\chi_f : C^{op} \times D \stackrel{f^{op} \times Id}{\to} D^{op} \times D \stackrel{Func(-,-)}{\to} (n-1) Cat

The graph of $f$ is the fibration $\mathrm{Graph}(f)\to C^{\mathrm{op}}\times D$ classified by ${\chi }_f$.

Mike Shulman: It’s not obvious to me that this is the best thing to call the graph of a functor; there are lots of other graphy things one can construct from a functor that all reduce to the usual notion of the graph of a function. To start with, there is of course also the induced opfibration oven $C\times D^{\mathrm{op}}$, would you call that the “opgraph”? But actually, the two-sided fibration $D\leftarrow P\to C$ (an opfibration over $C$ and a fibration over $D$) looks to me more like a graph. And then there is of course the other profunctor induced by $f$, which gives a fibration over $C\times D^{\mathrm{op}}$, an opfibration over $C^{\mathrm{op}}\times D$, and a two-sided fibration from $C$ to $D$.

Urs Schreiber: I would be inclined to loosely say “graph” for all of these and to introduce terminology like “opgraph” when it really matters which specific realization we mean. Because all these seem to be so similar to me that I am not sure if it is worth distinguishing them a lot. For instance, wouldn’t an analogous discussion be possible concerning what we call $F^{\mathrm{op}}:C^{\mathrm{op}}\to D^{\mathrm{op}}$ given a functor $F:C\to D$? I don’t actually know what a standard term is, does one say “opfunctor” for this? But I’d say it doesn’t matter much either way, calling $F^{\mathrm{op}}$ just a functor which effectively is the functor $F$ doesn’t do much harm.

Examples

Graphs of 0-functors

To reproduce the ordinary notion of graph of a function let $(n,r)=(\mathrm{0,0})$. then $(n,r)$-categories $X,Y$ are just sets and a functor $f:X\to Y$ is just a function between sets. Moreover, the category of $(n-1,r)=(-\mathrm{1,0})$-categories is the set $\{\mathrm{0,1}\}$ of truth values, as described at (-1)-category. The profunctor corresponding to $f:X\to Y$ is therefore the characteristic function

$${\chi }_f:X\times Y\to \{\mathrm{0,1}\}$$\chi_f : X \times Y \to \{0,1\}

that maps

$${\chi }_f(x,y)=\{\begin{array}{cc}1& \mathrm{if}f(x)=y\\ 0& \mathrm{otherwise}\end{array}.$$\chi_f(x,y) = \left\lbrace \array{ 1 & if f(x) = y \\ 0 & otherwise } \right. \,.

(Notice that in this case $X^{\mathrm{op}}=X$.)

The 2-pullback of $*=1\to \{\mathrm{0,1}\}$ along ${\chi }_f$ is just the ordinary pullback

$$\begin{array}{ccc}\mathrm{Graph}(f)& \to & *\\ \downarrow & & \downarrow \\ X\times Y& \stackrel{{\chi }_f}{\to }& \{\mathrm{0,1}\}\end{array}$$\array{ Graph(f) &\to& {*} \\ \downarrow && \downarrow \\ X \times Y &\stackrel{\chi_f}{\to}& \{0,1\} }

which identifies $\mathrm{Graph}(f)\hookrightarrow X\times Y$ with the subset of pairs $(x,y)$ for which $f(x)=y$. This is the ordinary notion of graph of a function.

Graphs of 1-functors

For $f:C\to D$ an ordinary functor, with corresponding profunctor ${\chi }_f:C^{\mathrm{op}}\times D\to \mathrm{Set}$, the category $\mathrm{Graph}(f)$ is the category of elements $\int {\chi }_f$ of ${\chi }_f$.

If we regard $C$ and $D$ as 2-categories under the embedding $1\mathrm{Cat}\hookrightarrow 2\mathrm{Cat}$ then the profunctor ${\chi }_f$ corresponding to $f$ is of the form ${\chi }_f:C^{\mathrm{op}}\times D\to \mathrm{Cat}$ and in this context $\mathrm{Graph}(f)\to C^{\mathrm{op}}\times D$ is the Grothendieck construction on ${\chi }_f$.

Related concepts

Closely related is the notion of cograph of a functor.