\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{mathbbol}
\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}

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

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

[[!include graph theory - contents]]

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

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{categories_of_hypergraphs_definition}{Categories of hypergraphs: Definition}\dotfill \pageref*{categories_of_hypergraphs_definition} \linebreak
\noindent\hyperlink{hypergraphs_from_a_topostheoretic_perspective}{Hypergraphs from a topos-theoretic perspective}\dotfill \pageref*{hypergraphs_from_a_topostheoretic_perspective} \linebreak
\noindent\hyperlink{hypergraphs_as_2colored_graphs}{Hypergraphs as 2-colored graphs}\dotfill \pageref*{hypergraphs_as_2colored_graphs} \linebreak
\noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak
\noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak


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

In an ordinary undirected [[graph]], each edge $e$ links an [[unordered pair]] of vertices $x$ and $y$ (perhaps allowing for the possibility that $x = y$, as in the case of a loop). Hypergraphs generalize this, allowing a ``hyperedge'' to link any set of ``hypervertices''. Abstracting everything away but the \emph{incidence} relation between hypervertices and hyperedges, a hypergraph can be modelled as an arbitrary heterogenous [[relation]], or more generally as a [[span]].

\hypertarget{categories_of_hypergraphs_definition}{}\subsection*{{Categories of hypergraphs: Definition}}\label{categories_of_hypergraphs_definition}

As with ``[[graph]]'', the word ``hypergraph'' does not have an entirely standardized meaning. We take as our starting point \hyperlink{SchmidtStroehlein}{(Schmidt \& Str\"o{}hlein)}, who define hypergraphs as heterogenous relations (usually presented as boolean-valued matrices) and give an appropriate notion of morphism. We call these ``simple'' hypergraphs, since they are a special case of a more general definition given below.

\begin{defn}
\label{}\hypertarget{}{}
The \textbf{category of simple hypergraphs} $SimpHGrph$ has objects consisting of a pair of sets $(V,E)$ equipped with a relation $R \subseteq V \times E$, and morphisms $(R \subseteq V \times E) \to (R' \subseteq V' \times E')$ consisting of pairs of functions $(f : V \to V', g : E \to E')$ which preserve the relation, i.e., such that for all $v\in V, e \in E$, if $(v,e) \in R$ then $(f v,g e) \in R'$.

\end{defn}
The category of simple hypergraphs could also be referred to more dryly as ``the category of binary relations'', although this has potential for confusion with [[Rel]] (whose \emph{morphisms} are binary relations).

In a simple hypergraph, a hypervertex can be incident to a hyperedge at most once, but in some situations one wants to allow a hypervertex to be incident to a hyperedge multiple times. To define hypergraphs in this more general sense, we keep the intuition of hypergraphs-as-heterogenous-relations, but generalize relations to spans.

\begin{defn}
\label{}\hypertarget{}{}
The \textbf{category of hypergraphs} $HGrph$ has objects consisting of a pair of sets $(V,E)$ equipped with a span $V \overset{v}\leftarrow R \overset{e}\rightarrow E$, and morphisms $(V \overset{v}\leftarrow R \overset{e}\rightarrow E) \to (V' \overset{v'}\leftarrow R' \overset{e'}\rightarrow E')$ consisting of triples of functions $(f : V \to V', g : E \to E', h:R \to R')$ such that $v'\circ h = f\circ v$ and $e'\circ h = g\circ e$.

\end{defn}
Note that $HGrph$ is just the [[category of presheaves]] over the ``[[walking structure|walking]] cospan'' $\bullet \rightarrow \bullet \leftarrow \bullet$, and that $SimpHGrph$ is a [[full subcategory]] of $HGrph$.

\hypertarget{hypergraphs_from_a_topostheoretic_perspective}{}\subsection*{{Hypergraphs from a topos-theoretic perspective}}\label{hypergraphs_from_a_topostheoretic_perspective}

In Lawvere (\hyperlink{Law86}{1986} p.6, \hyperlink{Law89}{1989} pp.283-4) it is pointed out that $Set^{\bullet\leftarrow\bullet\rightarrow\bullet}$ is a [[spatial topos]] since it is equivalent to the topos of sheaves on the space $X=\{a,b,c\}$ with topology $\tau=\{\emptyset,\{a\},\{b\},\{a,b\},\{a,b,c\}\}$ i.e. $X$ has two isolated points $a,b$ and a [[focal point|focal]] one $c$ whose only neighborhood is the whole space.

The [[lattice of subtoposes]] of $Set^{\bullet\leftarrow\bullet\rightarrow\bullet}$ consists (besides the two obvious subtoposes) of one [[closed subtopos|closed]] and two [[open subtopos|open]] copies of $Set$, two closed copies of the [[Sierpinski topos]] complementing the open copies of $Set$ respectively and an open $Set\times Set=Sh(\{a,b\})=Sh_{\neg\neg}(Set^{\bullet\leftarrow\bullet\rightarrow\bullet})$ complementing the closed copy of $Set$. In particular, $Set^{\bullet\leftarrow\bullet\rightarrow\bullet}$ is a [[scattered topos]].

The complementary open-closed pairs of the subtopos lattice correspond precisely to analyses of $Set^{\bullet\leftarrow\bullet\rightarrow\bullet}$ by [[Artin gluing]].

For instance, take the product functor $\sqcap\colon Set\times Set\to Set$ with $(X,Y)\mapsto X\times  Y$. $\sqcap$ is left exact since it forms an adjoint string with the [[diagonal functor]] and the coproduct functor: $\sqcup\dashv \triangle\dashv\sqcap$ .

Then $\mathbf{Gl}(\sqcap)$ has objects $((X,Y),Z, u\colon Z\to X\times Y)$ where $(X,Y)\in Set\times Set$ and $Z\in Set$ and $u$ is a morphism in $Set$. Since by the universal property of products $u\colon Z\overset{\langle u_0, u_1\rangle}{\rightarrow} X\times Y$ corresponds to a pair of maps $u_0$, $u_1$, one sees that the objects in $\mathbf{Gl}(\sqcap)$ really correspond to spans in $Set$.

The open inclusion of $Set\times Set$ into $\mathbf{Gl}(\sqcap)$ is given by the [[geometric morphism]]

\begin{displaymath}
i_\ast \colon Set\times Set\to \mathbf{Gl}(\sqcap) \qquad (X,Y)\mapsto ((X,Y),X\times Y,id_{X\times Y})
\end{displaymath}
\begin{displaymath}
i^\ast\colon \mathbf{Gl}(\sqcap)\to Set\times Set \qquad ((X,Y),Z,u)\mapsto (X,Y)
\end{displaymath}
\begin{displaymath}
i_{!} \colon Set\times Set\to \mathbf{Gl}(\sqcap) \qquad (X,Y)\mapsto ((X,Y),0,0\to X\times Y) \quad ,
\end{displaymath}
and the closed inclusion of $Set$ by

\begin{displaymath}
j_\ast \colon Set\to \mathbf{Gl}(\sqcap) \qquad X\mapsto ((1,1),X,X\to 1\times 1)
\end{displaymath}
\begin{displaymath}
j^\ast\colon\mathbf{Gl}(\sqcap)\to Set \qquad ((X,Y),Z,u)\mapsto Z\quad .
\end{displaymath}
Since $\triangle\dashv\sqcap$ the closed inclusion is [[essential geometric morphism|essential]]:

\begin{displaymath}
j_!\colon Set \to \mathbf{Gl}(\sqcap)\qquad X\mapsto ((X,X), X,  X\overset{\langle id_X,id_X\rangle}{\to} X\times X)\quad .
\end{displaymath}
Since $\sqcup\dashv \triangle$ there is a somewhat surprising further left adjoint:

\begin{displaymath}
j^\circ\colon\mathbf{Gl}(\sqcap)\to Set \qquad ((X,Y),Z,u)\mapsto X\sqcup_u Y\quad .
\end{displaymath}
Here $X\sqcup_u Y$ denotes the [[pushout]] of $X\overset{u_0}{\leftarrow} Z\overset{u_1}{\rightarrow} Y$ where $u_0$, $u_1$ are the pair of maps provided by $u\colon Z\overset{\langle u_0, u_1\rangle}{\rightarrow} X\times Y$ . Since a map from $((X,Y),Z,u)$ to $j_!(W)$ is a triple $(f_0,f_1,f_2)$ such that the following diagram commutes:

\begin{displaymath}
\itexarray{
Z & \overset{\langle u_0, u_1\rangle}{\rightarrow} & X\times Y 
\\
f_2\downarrow &  &f_0\downarrow \downarrow f_1 
\\
W & \overset{\langle id_W, id_W\rangle}{\rightarrow} & W\times W
}
\end{displaymath}
$(f_0,f_1,f_2)$ has to satisfy the two conditions $f_0 u_0= f_2$ and $f_1 u_1=f_2$, or equivalently, $f_0 u_0=f_1 u_1$ . But this is the same as giving a map from $j^\circ ((X,Y),Z,u)= X\sqcup_u Y$ to $W$ by the universal property of the pushout.

Whence we get an adjoint string:

\begin{displaymath}
j^\circ\dashv j_!\dashv j^\ast \dashv j_\ast \colon Set\to \mathbb{Gl}(\sqcap)
\end{displaymath}
with $j_!$, $j_\ast$ [[fully faithful]], exhibiting $\mathbf{Gl}(\sqcap)$ almost as a [[cohesive topos]] over $Set$. Of course, since $Set^{\bullet\leftarrow\bullet\rightarrow\bullet}$ is spatial it is not expected to satisfy all of Lawvere's axioms. In particular, the [[Nullstellensatz]] is violated since none of the copies of $Set$ is [[dense subtopos|dense]] in $Set^{\bullet\leftarrow\bullet\rightarrow\bullet}$.

Let $Q$ be the diagram category $N\overset{s}{\underset{t}{\rightrightarrows}} A$ underlying the topos $Set^{Q^{op}}$ of directed graphs or [[quiver|quivers]]. Consider the [[Yoneda embedding]] of the object $A$ into the presheaves: $Y(A)=Hom_Q(-,A)$. Viewed as a graph this gives the basic figure type of an \emph{a}rrow $K_2=\bullet\to\bullet$ , the other basic figure being the \emph{n}ode $\bullet$ given by $Y(N)$ .

The [[category of elements]] $\int_Q Y(A)$ is just the category $\bullet\rightarrow \bullet\leftarrow\bullet$ underlying the hypergraphs. Since $Y(A)$ is the representable presheaf corresponding to $A$ this is equivalent to the [[slice category]] $Q/A$. Then the following equivalence exhibits $Set^{Q^{op}}$ as an [[étendue|étendue topos]] using a general formula for [[slice topos|slices]] of [[presheaf topos|presheaf toposes]] and suggesting to view a quiver as a `foliated' hypergraph:

\begin{displaymath}
Set^{Q^{op}}/Y(A)\simeq Set^{(Q/A)^{op}}\simeq Set^{(\int_Q Y(A))^{op}}\simeq Set^{\bullet\leftarrow\bullet\rightarrow\bullet}\quad .
\end{displaymath}
This equivalence will be further explained in terms of graph colorings in the next section.

\hypertarget{hypergraphs_as_2colored_graphs}{}\subsection*{{Hypergraphs as 2-colored graphs}}\label{hypergraphs_as_2colored_graphs}

There is a classical equivalence between hypergraphs and [[vertex coloring|2-colored]] (hence [[bipartite graph|bipartite]]) graphs. Given a hypergraph $H$, define a graph $G(H)$ whose vertex set is the [[disjoint union]] of the hypervertices and the hyperedges of $H$, and with an edge $x_v \sim x_e$ in $G(H)$ whenever the corresponding pair $(v,e)$ are incident in $H$ (creating multiple edges in the case of multiple incidence). By coloring vertices corresponding to hypervertices in black and vertices corresponding to hyperedges in white, we satisfy the requirement that no pair of vertices sharing an edge have the same color. Conversely, this construction is clearly reversible: any 2-colored graph $G$ determines a hypergraph $H(G)$ by interpreting black vertices as hypervertices and white vertices as hyperedges that connect all of their (black vertex) neighbors.

Giving a [[vertex coloring]] of a graph $G$ with $n$ colors is equivalent to building a graph homomorphism $G \to K_n$ into the complete graph on $n$ vertices, and so graphs equipped with a $2$-coloring are naturally organized as a [[slice]] category over $K_2$. The classical equivalence between hypergraphs and 2-colored graphs can then be expressed formally as an [[equivalence of categories]]

\begin{displaymath}
HGrph \cong Grph/K_2
\end{displaymath}
between the category of hypergraphs and the slice over $K_2$ of the category of graphs, where by the latter we mean ``pseudographs'' in the greatest level of generality, allowing for loops, multiple edges between vertices, and dangling half-edges (as described in [[graph\#definition\_in\_terms\_of\_action\_on\_a\_set\_of\_halfedges|this definition]]). Moreover, this equivalence restricts to an equivalence

\begin{displaymath}
SimpHGrph \cong LoopGrph/K_2
\end{displaymath}
where $LoopGraph$ is the category of ``loop graphs'', i.e., the full subcategory of $Grph$ whose objects are symmetric relations.

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

\begin{itemize}%
\item [[hypermap]]


\item [[hyperstructure]]


\item [[hypergraph category]]


\item [[quiver]]



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

\begin{itemize}%
\item W. D\"o{}rfler and D. A. Waller, \emph{A category-theoretical approach to hypergraphs}, Archiv der Mathematik \textbf{34} no.1 (1980) pp.185-192. DOI: 10.1007/BF01224952


\item W. Grilliette, \emph{A Functorial Link between Hypergraphs and Quivers} , Electronic J. of Combinatorics \textbf{22} (2015). (\href{http://arxiv.org/abs/1608.00058}{arXiv:1608:00058})


\item [[F. William Lawvere]], \emph{Categories of Spaces may not be Generalized Spaces as Exemplified by Directed Graphs}, Revista Colombiana de Matem\'a{}ticas \textbf{XX} (1986) pp.179-186. Reprinted with commentary in TAC \textbf{9} (2005) pp.1-7. (\href{http://www.tac.mta.ca/tac/reprints/articles/9/tr9.pdf}{pdf})


\item [[F. William Lawvere]], \emph{Qualitative Distinctions between some Toposes of Generalized Graphs} , Cont. Math. \textbf{92} (1989) pp.261-299.


\item T. R. S. Walsh, \emph{Hypermaps Versus Bipartite Maps}, Journal of Combinatorial Theory (B) \textbf{18} (1975) pp.155-163.


\item Martin Schmidt, \emph{Functorial Approach to Graph and Hypergraph Theory}, (\href{https://arxiv.org/abs/1907.02574}{arXiv:1907.02574})



\end{itemize}
[[!redirects hypergraphs]]



\end{document}