\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{graph of a functor}

\hypertarget{context}{}\subsubsection*{{Context}}\label{context}

\hypertarget{category_theory}{}\paragraph*{{Category theory}}\label{category_theory}

[[!include category theory - contents]]

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{definition}{Definition}\dotfill \pageref*{definition} \linebreak
\noindent\hyperlink{examples}{Examples}\dotfill \pageref*{examples} \linebreak
\noindent\hyperlink{graphs_of_0functors}{Graphs of 0-functors}\dotfill \pageref*{graphs_of_0functors} \linebreak
\noindent\hyperlink{graphs_of_1functors}{Graphs of 1-functors}\dotfill \pageref*{graphs_of_1functors} \linebreak
\noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak


\hypertarget{idea}{}\subsection*{{Idea}}\label{idea}

In as far as the notion of [[functor]] generalizes that of [[function]] and that of [[profunctor]] generalizes that of [[relation]], the notion of \emph{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 Set = 0 Cat$ is nothing but the [[category of elements]] of the corresponding characteristic function $\chi_R : X \times Y \to (-1)Cat = \{0,1\}$, so the graph of a functor $F\colon C \to D$, or more generally that of a [[profunctor]] $\chi : C^{op} \times D \to 0 Cat = Set$, is nothing but its [[category of elements]].

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

\begin{displaymath}
\itexarray{
    Graph(f) &\to& {*}
    \\
    \downarrow && \downarrow
    \\
    C^{op} \times D &\stackrel{\chi_f}{\to}& (n-1,r-1)Cat
  }
\end{displaymath}
whenever this makes sense. For instance in the context of $(\infty,1)$-[[Higher Topos Theory|category theory]] the graph may be taken to be the fibration classified by $\chi_f : C \times D^{op} \to (\infty,0)$ as described at [[universal fibration of (∞,1)-categories]].

\hypertarget{definition}{}\subsection*{{Definition}}\label{definition}

For $n \leq \infty$ let $(n-1) Cat$ and $n 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]].

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

By the general logic of [[distributor]]s this defines an $n$-correspondence

\begin{displaymath}
\chi_f : C^{op} \times D \stackrel{f^{op} \times Id}{\to} D^{op} 
     \times D \stackrel{Func(-,-)}{\to} (n-1) Cat
\end{displaymath}
The \textbf{graph} of $f$ is the fibration $Graph(f) \to C^{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^{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 \emph{other} profunctor induced by $f$, which gives a fibration over $C\times D^{op}$, an opfibration over $C^{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^{op} : C^{op} \to D^{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^{op}$ just a functor which effectively is the functor $F$ doesn't do much harm.

[[Colin Zwanziger]]: Aren't we better off defining [[graph of a function]] as a span to avoid an arbitrary choice of $\langle 1, f\rangle$ or $\langle f, 1\rangle$ and then treating the two-sided fibration as the graph of a functor?Edit: Actually, we would still have to choose whether we were taking the graph of the representable or corepresentable profunctor induced by the functor, since these yield different spans. But we have that two functors F and G are adjoint iff ([[adjoint functors\#In\_terms\_of\_graphs2sided\_discrete\_fibrations|Lawvere's definition]]) the (graph of F)\_A and (graph of G)\_B agree. One level down we would have two functions f and g are adjoint (=inverse) iff (graph of f)\_A and (graph of g)\_B agree, but the two notions of graph turn out to be the same at this level.

\hypertarget{examples}{}\subsection*{{Examples}}\label{examples}

\hypertarget{graphs_of_0functors}{}\subsubsection*{{Graphs of 0-functors}}\label{graphs_of_0functors}

To reproduce the ordinary notion of [[graph of a function]] let $(n,r) = (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) = (-1,0)$-categories is the set $\{0,1\}$ of truth values, as described at [[(-1)-category]]. The [[profunctor]] corresponding to $f : X \to Y$ is therefore the characteristic function

\begin{displaymath}
\chi_f : X \times Y \to \{0,1\}
\end{displaymath}
that maps

\begin{displaymath}
\chi_f(x,y) = 
    \left\lbrace
      \itexarray{
        1 & if f(x) = y
        \\
        0 & otherwise
      }
    \right.
    \,.
\end{displaymath}
(Notice that in this case $X^{op} = X$.)

The [[2-pullback]] of ${*} = {1} \to \{0,1\}$ along $\chi_f$ is just the ordinary [[pullback]]

\begin{displaymath}
\itexarray{
  Graph(f) &\to& {*}
  \\
  \downarrow && \downarrow
  \\
  X \times Y
  &\stackrel{\chi_f}{\to}&
  \{0,1\}
}
\end{displaymath}
which identifies $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]].

\hypertarget{graphs_of_1functors}{}\subsubsection*{{Graphs of 1-functors}}\label{graphs_of_1functors}

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

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

\hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts}

\begin{itemize}%
\item \textbf{graph of a functor}, [[cograph of a functor]]
\item [[cograph of a profunctor]]

\end{itemize}
[[!redirects graph of a profunctor]]



\end{document}