\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*{hypergraph category}

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

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

[[!include category theory - contents]]

\hypertarget{graph_theory}{}\paragraph*{{Graph theory}}\label{graph_theory}

[[!include graph theory - contents]]

\hypertarget{hypergraph_categories}{}\section*{{Hypergraph categories}}\label{hypergraph_categories}

\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{remarks}{Remarks}\dotfill \pageref*{remarks} \linebreak
\noindent\hyperlink{properties}{Properties}\dotfill \pageref*{properties} \linebreak
\noindent\hyperlink{as_monoids_in_a_presheaf_category}{As monoids in a presheaf category}\dotfill \pageref*{as_monoids_in_a_presheaf_category} \linebreak
\noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak


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

A \emph{hypergraph category} is a [[monoidal category]] whose [[string diagrams]] are [[hypergraphs]]. Recall that in general the [[vertices]] of a string diagram correspond to [[morphisms]] in a [[category]], and its [[edges]] to [[objects]]. An ordinary string diagram is a [[directed graph]], where the inputs and outputs of a vertex describe objects appearing in a [[tensor product]]-decomposition of the [[domain]] and [[codomain]] of a morphism; each edge is connected to only one vertex as input and one vertex as output because of how morphisms in a category are composed. A hypergraph category allows edges to connect to many vertices as input and many vertices as output, which [[category theory|category theoretically]] means that we may [[composition|compose]] many morphisms containing an object in their [[codomain]] with many morphisms containing that object in their [[domain]].

Hypergraph categories have been reinvented many times and given many different names, such as ``well-supported compact closed categories'' (\hyperlink{Carboni}{Carboni} and \hyperlink{RSW}{RSW}), ``dgs-monoidal categories'' (\hyperlink{GH}{GH}), and ``spidered/dungeon categories'' (\hyperlink{Morton}{Morton}). The name ``hypergraph category'' is more recent (\hyperlink{Kissinger}{Kissinger} and \hyperlink{FongDC}{Fong}).

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

A \textbf{hypergraph category} is:

\begin{itemize}%
\item a [[symmetric monoidal category]] in which
\item each object is equipped with the structure of a special commutative [[Frobenius algebra]], such that
\item the Frobenius algebra structure of any tensor product $X\otimes Y$ is induced in the canonical way from those of $X$ and $Y$.

\end{itemize}
Note in particular that we do \emph{not} require the morphisms of the category to be Frobenius algebra morphisms.

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

\begin{itemize}%
\item The category [[Rel]] of sets and relations (with cartesian product of sets as the monoidal product) is a hypergraph category, with the Frobenius algebra on $X$ given by the ``deleting and copying'' [[comonoid]] $\{ (x, *) \mid x \in X \}$, $\{ (x, (x, x)) | x \in X \}$ together with its [[opposite relation|opposite]].


\item More generally, categories of [[span|spans]], [[cospan|cospans]], [[relation|relations]] and [[corelation|corelations]] in any category (with the appropriate structure) are hypergraph categories.


\item Categories of [[decorated cospan|decorated cospans]] and decorated corelations are hypergraph categories.



\end{itemize}
\hypertarget{remarks}{}\subsection*{{Remarks}}\label{remarks}

\begin{itemize}%
\item The reason for the definition is that if $X$ is a special commutative Frobenius algebra, then there is a unique morphism $X^{\otimes m}\to X^{\otimes n}$ induced by the Frobenius algebra structure. It can of course be defined as the $m$-ary multiplication followed by the $n$-ary comultiplication; the real point is that the special commutative Frobenius axioms ensure that any composite of two such morphisms is again another such morphism. This is what enables the hypergraph string diagrams described informally above. (Some authors refer to these morphisms as ``spiders'' due to their appearance in [[string diagram|string diagrams]], as a black node with $m + n$ legs.)


\item The free hypergraph category on one object is the category of finite sets and isomorphism classes of cospans. This is a decategorification of the fact that the free monoidal category containing a (non-special) commutative Frobenius algebra is the category of 1-dimensional [[manifolds]] and isomorphism classes of 2-dimensional [[cobordisms]]. More general free hypergraph categories can be constructed using labeled cospans.


\item Note that the special commutative Frobenius algebras are not required to be ``extra-special'', meaning that the morphism $I = X^{\otimes 0} \to X^{\otimes 0} = I$ need not be the identity. Thus, the relevant sort of ``hypergraphs'' can contain ``edges not incident to any vertices''. If we add the extra-special condition, the cospans are replaced by ``co-relations'', i.e. jointly surjective cospans.



\end{itemize}
\hypertarget{properties}{}\subsection*{{Properties}}\label{properties}

\hypertarget{as_monoids_in_a_presheaf_category}{}\subsubsection*{{As monoids in a presheaf category}}\label{as_monoids_in_a_presheaf_category}

Let $\mathbf{Cospan}_\Delta$ be the free hypergraph category on [[generators and relations|generators]] $\Delta$. The objects are [[lists]] of [[elements]] of $\Delta$, or equivalently [[pairs]] $(m,l)$ of a [[natural number]] $m$ and a labelling $l\colon \big[ m \big] \to \Delta$. The morphisms are compatible [[cospans]] of [[functions]] (up to [[isomorphism]]).

\begin{uprop}
\hyperlink{FongSpivak}{Fong, Spivak}. To give a hypergraph category with chosen objects $\Delta$ that generate it is to give a lax monoidal functor $\mathbf{Cospan}_\Delta\to \mathbf{Set}$.

\end{uprop}
(Formally, this can be made into an equivalence between the category of objectwise-free hypergraph categories and the lax monoidal functors; and every hypergraph category is in some sense equivalent to an objectwise-free one.)

A hypergraph category is thus a \href{https://ncatlab.org/nlab/show/presheaf}{presheaf} $H\colon \mathbf{Cospan}_\Delta\to \mathbf{Set}$ that has lax monoidal structure

\begin{displaymath}
1\to H()\qquad H(\vec a)\times H(\vec b)\to H(\vec a,\vec b)
\end{displaymath}
which is strongly reminiscent of the \href{https://ncatlab.org/nlab/show/mix%20rule}{mix rule}. A lax monoidal functor is the same thing as a \href{https://ncatlab.org/nlab/show/Day+convolution#Monoids}{monoid for the Day convolution}. Thus hypergraph categories are monoids in the presheaf category $[\mathbf{Cospan}_\Delta, \mathbf{Set}]$.

\hypertarget{references}{}\subsection*{{References}}\label{references}

\begin{itemize}%
\item [[Aleks Kissinger]], \emph{Finite matrices are complete for (dagger-)hypergraph categories} (\href{https://arxiv.org/abs/1406.5942}{arxiv:1406.5942})


\item [[Brendan Fong]], \emph{Decorated Cospans}, Theory and Applications of Categories, Vol. 30, 2015, No. 33, pp 1096-1120 (\href{https://arxiv.org/abs/1502.00872}{arxiv:1502.00872})


\item [[Brendan Fong]], \emph{The Algebra of Open and Interconnected Systems}, Ph.D. Thesis (\href{https://arxiv.org/abs/1609.05382}{arxiv:1609.05382})


\item [[Aurelio Carboni]], \emph{Matrices, relations and group representations} J. Algebra, 138(2):497--529, 1991


\item [[Robert Rosebrugh]], N. Sabadini, and R. F. C. Walters. \emph{Generic commutative separable algebras and cospans of graphs}. Th. App. Cat. 15(6):164--177, 2005. \href{http://www.tac.mta.ca/tac/volumes/15/6/15-06abs.html}{online}.


\item F. Gadducci, R. Heckel. \emph{An inductive view of graph transformation}. In ``Recent Trends in Algebraic Development Techniques'', Lecture Notes in Computer Science 1376:223--237. Springer--Verlag, Berlin Heidelberg, 1998.


\item [[Jeffrey Morton]], \emph{Belief propagation in monoidal categories} In [[Bob Coecke]], I. Hasuo, P. Panangaden (eds.) \emph{Quantum Physics and Logic} 2014 (QPL 2014), EPTCS 172:262--269.


\item [[Brendan Fong]] and [[David Spivak]], \emph{Hypergraph Categories} (\href{https://arxiv.org/abs/1806.08304}{arxiv:1806.08304})



\end{itemize}
[[!redirects hypergraph categories]] [[!redirects well-supported compact closed category]] [[!redirects well-supported compact closed categories]] [[!redirects dgs-monoidal category]] [[!redirects dgs-monoidal categories]] [[!redirects spidered category]] [[!redirects spidered categories]] [[!redirects dungeon category]] [[!redirects dungeon categories]]



\end{document}