CINXE.COM

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0 plus SVG 1.1//EN" "http://www.w3.org/2002/04/xhtml-math-svg/xhtml-math-svg-flat.dtd" > <html xmlns="http://www.w3.org/1999/xhtml"> <head> <title> hypergraph in nLab </title> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> <meta name="robots" content="index,follow" /> <meta name="viewport" content="width=device-width, initial-scale=1" /> <link href="/stylesheets/instiki.css?1676280126" media="all" rel="stylesheet" type="text/css" /> <link href="/stylesheets/mathematics.css?1660229990" media="all" rel="stylesheet" type="text/css" /> <link href="/stylesheets/syntax.css?1660229990" media="all" rel="stylesheet" type="text/css" /> <link href="/stylesheets/nlab.css?1676280126" media="all" rel="stylesheet" type="text/css" /> <link rel="stylesheet" type="text/css" href="https://cdn.jsdelivr.net/gh/dreampulse/computer-modern-web-font@master/fonts.css"/> <style type="text/css"> h1#pageName, div.info, .newWikiWord a, a.existingWikiWord, .newWikiWord a:hover, [actiontype="toggle"]:hover, #TextileHelp h3 { color: #226622; } a:visited.existingWikiWord { color: #164416; } </style> <style type="text/css"><![CDATA[/*></style> <script src="/javascripts/prototype.js?1660229990" type="text/javascript"></script> <script src="/javascripts/effects.js?1660229990" type="text/javascript"></script> <script src="/javascripts/dragdrop.js?1660229990" type="text/javascript"></script> <script src="/javascripts/controls.js?1660229990" type="text/javascript"></script> <script src="/javascripts/application.js?1660229990" type="text/javascript"></script> <script src="/javascripts/page_helper.js?1660229990" type="text/javascript"></script> <script src="/javascripts/thm_numbering.js?1660229990" type="text/javascript"></script> <script type="text/x-mathjax-config"> <![CDATA[//><!]]> </script> <script type="text/javascript"> <![CDATA[//><!]]> </script> <link href="https://ncatlab.org/nlab/atom_with_headlines" rel="alternate" title="Atom with headlines" type="application/atom+xml" /> <link href="https://ncatlab.org/nlab/atom_with_content" rel="alternate" title="Atom with full content" type="application/atom+xml" /> <script type="text/javascript"> document.observe("dom:loaded", function() { generateThmNumbers(); }); </script> </head> <body> <div id="Container"> <div id="Content"> <h1 id="pageName"> <span style="float: left; margin: 0.5em 0.25em -0.25em 0"> <svg xmlns="http://www.w3.org/2000/svg" width="1.872em" height="1.8em" viewBox="0 0 190 181"> <path fill="#226622" d="M72.8 145c-1.6 17.3-15.7 10-23.6 20.2-5.6 7.3 4.8 15 11.4 15 11.5-.2 19-13.4 26.4-20.3 3.3-3 8.2-4 11.2-7.2a14 14 0 0 0 2.9-11.1c-1.4-9.6-12.4-18.6-16.9-27.2-5-9.6-10.7-27.4-24.1-27.7-17.4-.3-.4 26 4.7 30.7 2.4 2.3 5.4 4.1 7.3 6.9 1.6 2.3 2.1 5.8-1 7.2-5.9 2.6-12.4-6.3-15.5-10-8.8-10.6-15.5-23-26.2-31.8-5.2-4.3-11.8-8-18-3.7-7.3 4.9-4.2 12.9.2 18.5a81 81 0 0 0 30.7 23c3.3 1.5 12.8 5.6 10 10.7-2.5 5.2-11.7 3-15.6 1.1-8.4-3.8-24.3-21.3-34.4-13.7-3.5 2.6-2.3 7.6-1.2 11.1 2.8 9 12.2 17.2 20.9 20.5 17.3 6.7 34.3-8 50.8-12.1z"/> <path fill="#a41e32" d="M145.9 121.3c-.2-7.5 0-19.6-4.5-26-5.4-7.5-12.9-1-14.1 5.8-1.4 7.8 2.7 14.1 4.8 21.3 3.4 12 5.8 29-.8 40.1-3.6-6.7-5.2-13-7-20.4-2.1-8.2-12.8-13.2-15.1-1.9-2 9.7 9 21.2 12 30.1 1.2 4 2 8.8 6.4 10.3 6.9 2.3 13.3-4.7 17.7-8.8 12.2-11.5 36.6-20.7 43.4-36.4 6.7-15.7-13.7-14-21.3-7.2-9.1 8-11.9 20.5-23.6 25.1 7.5-23.7 31.8-37.6 38.4-61.4 2-7.3-.8-29.6-13-19.8-14.5 11.6-6.6 37.6-23.3 49.2z"/> <path fill="#193c78" d="M86.3 47.5c0-13-10.2-27.6-5.8-40.4 2.8-8.4 14.1-10.1 17-1 3.8 11.6-.3 26.3-1.8 38 11.7-.7 10.5-16 14.8-24.3 2.1-4.2 5.7-9.1 11-6.7 6 2.7 7.4 9.2 6.6 15.1-2.2 14-12.2 18.8-22.4 27-3.4 2.7-8 6.6-5.9 11.6 2 4.4 7 4.5 10.7 2.8 7.4-3.3 13.4-16.5 21.7-16 14.6.7 12 21.9.9 26.2-5 1.9-10.2 2.3-15.2 3.9-5.8 1.8-9.4 8.7-15.7 8.9-6.1.1-9-6.9-14.3-9-14.4-6-33.3-2-44.7-14.7-3.7-4.2-9.6-12-4.9-17.4 9.3-10.7 28 7.2 35.7 12 2 1.1 11 6.9 11.4 1.1.4-5.2-10-8.2-13.5-10-11.1-5.2-30-15.3-35-27.3-2.5-6 2.8-13.8 9.4-13.6 6.9.2 13.4 7 17.5 12C70.9 34 75 43.8 86.3 47.4z"/> </svg> </span> <span class="webName">nLab</span> hypergraph </h1> <div class="navigation"> <span class="skipNav"><a href='#navEnd'>Skip the Navigation Links</a> | </span> <span style="display:inline-block; width: 0.3em;"></span> <a href="/nlab/show/HomePage" accesskey="H" title="Home page">Home Page</a> | <a href="/nlab/all_pages" accesskey="A" title="List of all pages">All Pages</a> | <a href="/nlab/latest_revisions" accesskey="U" title="Latest edits and page creations">Latest Revisions</a> | <a href="https://nforum.ncatlab.org/discussion/10098/#Item_1" title="Discuss this page in its dedicated thread on the nForum" style="color: black">Discuss this page</a> | <form accept-charset="utf-8" action="/nlab/search" id="navigationSearchForm" method="get"> <fieldset class="search"><input type="text" id="searchField" name="query" value="Search" style="display:inline-block; float: left;" onfocus="this.value == 'Search' ? this.value = '' : true" onblur="this.value == '' ? this.value = 'Search' : true" /></fieldset> </form> <span id='navEnd'></span> </div> <div id="revision"> <html xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xml:lang="en" lang="en"> <head><meta http-equiv="Content-type" content="application/xhtml+xml;charset=utf-8" /><title>Contents</title></head> <body> <div class="rightHandSide"> <div class="toc clickDown" tabindex="0"> <h3 id="context">Context</h3> <h4 id="graph_theory">Graph theory</h4> <div class="hide"><div> <p><strong><a class="existingWikiWord" href="/nlab/show/graph+theory">graph theory</a></strong></p> <p><a class="existingWikiWord" href="/nlab/show/graph">graph</a></p> <ul> <li> <p><a class="existingWikiWord" href="/nlab/show/vertex">vertex</a>, <a class="existingWikiWord" href="/nlab/show/edge">edge</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/omega-graph">omega-graph</a>, <a class="existingWikiWord" href="/nlab/show/hypergraph">hypergraph</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/quiver">quiver</a>, <a class="existingWikiWord" href="/nlab/show/n-quiver">n-quiver</a></p> </li> </ul> <p><a class="existingWikiWord" href="/nlab/show/category+of+simple+graphs">category of simple graphs</a></p> <h3 id="properties">Properties</h3> <ul> <li><a class="existingWikiWord" href="/nlab/show/graph+distance">graph distance</a></li> </ul> <h3 id="extra_properties">Extra properties</h3> <ul> <li> <p><a class="existingWikiWord" href="/nlab/show/reflexive+graph">reflexive</a>, <a class="existingWikiWord" href="/nlab/show/directed+graph">directed</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/bipartite+graph">bipartite</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/planar+graph">planar</a></p> </li> </ul> <h3 id="extra_structure">Extra structure</h3> <ul> <li> <p><a class="existingWikiWord" href="/nlab/show/reflexive+graph">reflexive</a><a class="existingWikiWord" href="/nlab/show/directed+graph">directed graph</a> + <a class="existingWikiWord" href="/nlab/show/unit+law">unital</a> <a class="existingWikiWord" href="/nlab/show/associative">associative</a> <a class="existingWikiWord" href="/nlab/show/composition">composition</a> = <a class="existingWikiWord" href="/nlab/show/category">category</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/ribbon+graph">ribbon graph</a>, <a class="existingWikiWord" href="/nlab/show/combinatorial+map">combinatorial map</a>, <a class="existingWikiWord" href="/nlab/show/topological+map">topological map</a>, <a class="existingWikiWord" href="/nlab/show/child%27s+drawing">child's drawing</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/vertex+coloring">vertex coloring</a>, <a class="existingWikiWord" href="/nlab/show/clique">clique</a></p> </li> </ul> </div></div> </div> </div> <h1 id="contents">Contents</h1> <div class='maruku_toc'> <ul> <li><a href='#idea'>Idea</a></li> <li><a href='#categories_of_hypergraphs_definition'>Categories of hypergraphs: Definition</a></li> <li><a href='#hypergraphs_from_a_topostheoretic_perspective'>Hypergraphs from a topos-theoretic perspective</a></li> <li><a href='#hypergraphs_as_2colored_graphs'>Hypergraphs as 2-colored graphs</a></li> <li><a href='#related_concepts'>Related concepts</a></li> <li><a href='#references'>References</a></li> </ul> </div> <h2 id="idea">Idea</h2> <p>In an ordinary undirected <a class="existingWikiWord" href="/nlab/show/graph">graph</a>, each edge <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>e</mi></mrow><annotation encoding="application/x-tex">e</annotation></semantics></math> links an <a class="existingWikiWord" href="/nlab/show/unordered+pair">unordered pair</a> of vertices <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>y</mi></mrow><annotation encoding="application/x-tex">y</annotation></semantics></math> (perhaps allowing for the possibility that <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>x</mi><mo>=</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x = y</annotation></semantics></math>, as in the case of a loop). Hypergraphs generalize this, allowing a “hyperedge” to link any set of “hypervertices”. Abstracting everything away but the <em>incidence</em> relation between hypervertices and hyperedges, a hypergraph can be modelled as an arbitrary heterogenous <a class="existingWikiWord" href="/nlab/show/relation">relation</a>, or more generally as a <a class="existingWikiWord" href="/nlab/show/span">span</a>.</p> <h2 id="categories_of_hypergraphs_definition">Categories of hypergraphs: Definition</h2> <p>As with “<a class="existingWikiWord" href="/nlab/show/graph">graph</a>”, the word “hypergraph” does not have an entirely standardized meaning. We take as our starting point <a href="#SchmidtStroehlein">(Schmidt & Ströhlein)</a>, 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.</p> <div class="num_defn"> <h6 id="definition">Definition</h6> <p>The <strong>category of simple hypergraphs</strong> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>SimpHGrph</mi></mrow><annotation encoding="application/x-tex">SimpHGrph</annotation></semantics></math> has objects consisting of a pair of sets <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(V,E)</annotation></semantics></math> equipped with a relation <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>R</mi><mo>⊆</mo><mi>V</mi><mo>×</mo><mi>E</mi></mrow><annotation encoding="application/x-tex">R \subseteq V \times E</annotation></semantics></math>, and morphisms <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>R</mi><mo>⊆</mo><mi>V</mi><mo>×</mo><mi>E</mi><mo stretchy="false">)</mo><mo>→</mo><mo stretchy="false">(</mo><mi>R</mi><mo>′</mo><mo>⊆</mo><mi>V</mi><mo>′</mo><mo>×</mo><mi>E</mi><mo>′</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(R \subseteq V \times E) \to (R' \subseteq V' \times E')</annotation></semantics></math> consisting of pairs of functions <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>f</mi><mo>:</mo><mi>V</mi><mo>→</mo><mi>V</mi><mo>′</mo><mo>,</mo><mi>g</mi><mo>:</mo><mi>E</mi><mo>→</mo><mi>E</mi><mo>′</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(f : V \to V', g : E \to E')</annotation></semantics></math> which preserve the relation, i.e., such that for all <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>v</mi><mo>∈</mo><mi>V</mi><mo>,</mo><mi>e</mi><mo>∈</mo><mi>E</mi></mrow><annotation encoding="application/x-tex">v\in V, e \in E</annotation></semantics></math>, if <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>v</mi><mo>,</mo><mi>e</mi><mo stretchy="false">)</mo><mo>∈</mo><mi>R</mi></mrow><annotation encoding="application/x-tex">(v,e) \in R</annotation></semantics></math> then <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>f</mi><mi>v</mi><mo>,</mo><mi>g</mi><mi>e</mi><mo stretchy="false">)</mo><mo>∈</mo><mi>R</mi><mo>′</mo></mrow><annotation encoding="application/x-tex">(f v,g e) \in R'</annotation></semantics></math>.</p> </div> <p>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 <a class="existingWikiWord" href="/nlab/show/Rel">Rel</a> (whose <em>morphisms</em> are binary relations).</p> <p>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.</p> <div class="num_defn"> <h6 id="definition_2">Definition</h6> <p>The <strong>category of hypergraphs</strong> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>HGrph</mi></mrow><annotation encoding="application/x-tex">HGrph</annotation></semantics></math> has objects consisting of a pair of sets <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(V,E)</annotation></semantics></math> equipped with a span <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi><mover><mo>←</mo><mi>v</mi></mover><mi>R</mi><mover><mo>→</mo><mi>e</mi></mover><mi>E</mi></mrow><annotation encoding="application/x-tex">V \overset{v}\leftarrow R \overset{e}\rightarrow E</annotation></semantics></math>, and morphisms <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>V</mi><mover><mo>←</mo><mi>v</mi></mover><mi>R</mi><mover><mo>→</mo><mi>e</mi></mover><mi>E</mi><mo stretchy="false">)</mo><mo>→</mo><mo stretchy="false">(</mo><mi>V</mi><mo>′</mo><mover><mo>←</mo><mrow><mi>v</mi><mo>′</mo></mrow></mover><mi>R</mi><mo>′</mo><mover><mo>→</mo><mrow><mi>e</mi><mo>′</mo></mrow></mover><mi>E</mi><mo>′</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(V \overset{v}\leftarrow R \overset{e}\rightarrow E) \to (V' \overset{v'}\leftarrow R' \overset{e'}\rightarrow E')</annotation></semantics></math> consisting of triples of functions <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>f</mi><mo>:</mo><mi>V</mi><mo>→</mo><mi>V</mi><mo>′</mo><mo>,</mo><mi>g</mi><mo>:</mo><mi>E</mi><mo>→</mo><mi>E</mi><mo>′</mo><mo>,</mo><mi>h</mi><mo>:</mo><mi>R</mi><mo>→</mo><mi>R</mi><mo>′</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(f : V \to V', g : E \to E', h:R \to R')</annotation></semantics></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>v</mi><mo>′</mo><mo>∘</mo><mi>h</mi><mo>=</mo><mi>f</mi><mo>∘</mo><mi>v</mi></mrow><annotation encoding="application/x-tex">v'\circ h = f\circ v</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>e</mi><mo>′</mo><mo>∘</mo><mi>h</mi><mo>=</mo><mi>g</mi><mo>∘</mo><mi>e</mi></mrow><annotation encoding="application/x-tex">e'\circ h = g\circ e</annotation></semantics></math>.</p> </div> <p>Note that <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>HGrph</mi></mrow><annotation encoding="application/x-tex">HGrph</annotation></semantics></math> is just the <a class="existingWikiWord" href="/nlab/show/category+of+presheaves">category of presheaves</a> over the “<a class="existingWikiWord" href="/nlab/show/walking+structure">walking</a> cospan” <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo>•</mo><mo>→</mo><mo>•</mo><mo>←</mo><mo>•</mo></mrow><annotation encoding="application/x-tex">\bullet \rightarrow \bullet \leftarrow \bullet</annotation></semantics></math>, and that <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>SimpHGrph</mi></mrow><annotation encoding="application/x-tex">SimpHGrph</annotation></semantics></math> is a <a class="existingWikiWord" href="/nlab/show/full+subcategory">full subcategory</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>HGrph</mi></mrow><annotation encoding="application/x-tex">HGrph</annotation></semantics></math>.</p> <h2 id="hypergraphs_from_a_topostheoretic_perspective">Hypergraphs from a topos-theoretic perspective</h2> <p>In Lawvere (<a href="#Law86">1986</a> p.6, <a href="#Law89">1989</a> pp.283-4) it is pointed out that <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>Set</mi> <mrow><mo>•</mo><mo>←</mo><mo>•</mo><mo>→</mo><mo>•</mo></mrow></msup></mrow><annotation encoding="application/x-tex">Set^{\bullet\leftarrow\bullet\rightarrow\bullet}</annotation></semantics></math> is a <a class="existingWikiWord" href="/nlab/show/spatial+topos">spatial topos</a> since it is equivalent to the topos of sheaves on the space <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>X</mi><mo>=</mo><mo stretchy="false">{</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">X=\{a,b,c\}</annotation></semantics></math> with topology <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>τ</mi><mo>=</mo><mo stretchy="false">{</mo><mi>∅</mi><mo>,</mo><mo stretchy="false">{</mo><mi>a</mi><mo stretchy="false">}</mo><mo>,</mo><mo stretchy="false">{</mo><mi>b</mi><mo stretchy="false">}</mo><mo>,</mo><mo stretchy="false">{</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo stretchy="false">}</mo><mo>,</mo><mo stretchy="false">{</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo stretchy="false">}</mo><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">\tau=\{\emptyset,\{a\},\{b\},\{a,b\},\{a,b,c\}\}</annotation></semantics></math> i.e. <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>X</mi></mrow><annotation encoding="application/x-tex">X</annotation></semantics></math> has two isolated points <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>a</mi><mo>,</mo><mi>b</mi></mrow><annotation encoding="application/x-tex">a,b</annotation></semantics></math> and a <a class="existingWikiWord" href="/nlab/show/focal+point">focal</a> one <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>c</mi></mrow><annotation encoding="application/x-tex">c</annotation></semantics></math> whose only neighborhood is the whole space.</p> <p>The <a class="existingWikiWord" href="/nlab/show/lattice+of+subtoposes">lattice of subtoposes</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>Set</mi> <mrow><mo>•</mo><mo>←</mo><mo>•</mo><mo>→</mo><mo>•</mo></mrow></msup></mrow><annotation encoding="application/x-tex">Set^{\bullet\leftarrow\bullet\rightarrow\bullet}</annotation></semantics></math> consists (besides the two obvious subtoposes) of one <a class="existingWikiWord" href="/nlab/show/closed+subtopos">closed</a> and two <a class="existingWikiWord" href="/nlab/show/open+subtopos">open</a> copies of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Set</mi></mrow><annotation encoding="application/x-tex">Set</annotation></semantics></math>, two closed copies of the <a class="existingWikiWord" href="/nlab/show/Sierpinski+topos">Sierpinski topos</a> complementing the open copies of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Set</mi></mrow><annotation encoding="application/x-tex">Set</annotation></semantics></math> respectively and an open <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Set</mi><mo>×</mo><mi>Set</mi><mo>=</mo><mi>Sh</mi><mo stretchy="false">(</mo><mo stretchy="false">{</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo stretchy="false">}</mo><mo stretchy="false">)</mo><mo>=</mo><msub><mi>Sh</mi> <mrow><mo>¬</mo><mo>¬</mo></mrow></msub><mo stretchy="false">(</mo><msup><mi>Set</mi> <mrow><mo>•</mo><mo>←</mo><mo>•</mo><mo>→</mo><mo>•</mo></mrow></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">Set\times Set=Sh(\{a,b\})=Sh_{\neg\neg}(Set^{\bullet\leftarrow\bullet\rightarrow\bullet})</annotation></semantics></math> complementing the closed copy of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Set</mi></mrow><annotation encoding="application/x-tex">Set</annotation></semantics></math>. In particular, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>Set</mi> <mrow><mo>•</mo><mo>←</mo><mo>•</mo><mo>→</mo><mo>•</mo></mrow></msup></mrow><annotation encoding="application/x-tex">Set^{\bullet\leftarrow\bullet\rightarrow\bullet}</annotation></semantics></math> is a <a class="existingWikiWord" href="/nlab/show/scattered+topos">scattered topos</a>.</p> <p>The complementary open-closed pairs of the subtopos lattice correspond precisely to analyses of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>Set</mi> <mrow><mo>•</mo><mo>←</mo><mo>•</mo><mo>→</mo><mo>•</mo></mrow></msup></mrow><annotation encoding="application/x-tex">Set^{\bullet\leftarrow\bullet\rightarrow\bullet}</annotation></semantics></math> by <a class="existingWikiWord" href="/nlab/show/Artin+gluing">Artin gluing</a>.</p> <p>For instance, take the product functor <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo>⊓</mo><mo lspace="verythinmathspace">:</mo><mi>Set</mi><mo>×</mo><mi>Set</mi><mo>→</mo><mi>Set</mi></mrow><annotation encoding="application/x-tex">\sqcap\colon Set\times Set\to Set</annotation></semantics></math> with <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo stretchy="false">)</mo><mo>↦</mo><mi>X</mi><mo>×</mo><mi>Y</mi></mrow><annotation encoding="application/x-tex">(X,Y)\mapsto X\times Y</annotation></semantics></math>. <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo>⊓</mo></mrow><annotation encoding="application/x-tex">\sqcap</annotation></semantics></math> is left exact since it forms an adjoint string with the <a class="existingWikiWord" href="/nlab/show/diagonal+functor">diagonal functor</a> and the coproduct functor: <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo>⊔</mo><mo>⊣</mo><mo>▵</mo><mo>⊣</mo><mo>⊓</mo></mrow><annotation encoding="application/x-tex">\sqcup\dashv \triangle\dashv\sqcap</annotation></semantics></math> .</p> <p>Then <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mstyle mathvariant="bold"><mi>Gl</mi></mstyle><mo stretchy="false">(</mo><mo>⊓</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\mathbf{Gl}(\sqcap)</annotation></semantics></math> has objects <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo stretchy="false">)</mo><mo>,</mo><mi>Z</mi><mo>,</mo><mi>u</mi><mo lspace="verythinmathspace">:</mo><mi>Z</mi><mo>→</mo><mi>X</mi><mo>×</mo><mi>Y</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">((X,Y),Z, u\colon Z\to X\times Y)</annotation></semantics></math> where <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo stretchy="false">)</mo><mo>∈</mo><mi>Set</mi><mo>×</mo><mi>Set</mi></mrow><annotation encoding="application/x-tex">(X,Y)\in Set\times Set</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Z</mi><mo>∈</mo><mi>Set</mi></mrow><annotation encoding="application/x-tex">Z\in Set</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>u</mi></mrow><annotation encoding="application/x-tex">u</annotation></semantics></math> is a morphism in <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Set</mi></mrow><annotation encoding="application/x-tex">Set</annotation></semantics></math>. Since by the universal property of products <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>u</mi><mo lspace="verythinmathspace">:</mo><mi>Z</mi><mover><mo>→</mo><mrow><mo stretchy="false">⟨</mo><msub><mi>u</mi> <mn>0</mn></msub><mo>,</mo><msub><mi>u</mi> <mn>1</mn></msub><mo stretchy="false">⟩</mo></mrow></mover><mi>X</mi><mo>×</mo><mi>Y</mi></mrow><annotation encoding="application/x-tex">u\colon Z\overset{\langle u_0, u_1\rangle}{\rightarrow} X\times Y</annotation></semantics></math> corresponds to a pair of maps <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>u</mi> <mn>0</mn></msub></mrow><annotation encoding="application/x-tex">u_0</annotation></semantics></math>, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>u</mi> <mn>1</mn></msub></mrow><annotation encoding="application/x-tex">u_1</annotation></semantics></math>, one sees that the objects in <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mstyle mathvariant="bold"><mi>Gl</mi></mstyle><mo stretchy="false">(</mo><mo>⊓</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\mathbf{Gl}(\sqcap)</annotation></semantics></math> really correspond to spans in <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Set</mi></mrow><annotation encoding="application/x-tex">Set</annotation></semantics></math>.</p> <p>The open inclusion of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Set</mi><mo>×</mo><mi>Set</mi></mrow><annotation encoding="application/x-tex">Set\times Set</annotation></semantics></math> into <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mstyle mathvariant="bold"><mi>Gl</mi></mstyle><mo stretchy="false">(</mo><mo>⊓</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\mathbf{Gl}(\sqcap)</annotation></semantics></math> is given by the <a class="existingWikiWord" href="/nlab/show/geometric+morphism">geometric morphism</a></p> <div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><msub><mi>i</mi> <mo>*</mo></msub><mo lspace="verythinmathspace">:</mo><mi>Set</mi><mo>×</mo><mi>Set</mi><mo>→</mo><mstyle mathvariant="bold"><mi>Gl</mi></mstyle><mo stretchy="false">(</mo><mo>⊓</mo><mo stretchy="false">)</mo><mspace width="2em"></mspace><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo stretchy="false">)</mo><mo>↦</mo><mo stretchy="false">(</mo><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo stretchy="false">)</mo><mo>,</mo><mi>X</mi><mo>×</mo><mi>Y</mi><mo>,</mo><msub><mi>id</mi> <mrow><mi>X</mi><mo>×</mo><mi>Y</mi></mrow></msub><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex"> i_\ast \colon Set\times Set\to \mathbf{Gl}(\sqcap) \qquad (X,Y)\mapsto ((X,Y),X\times Y,id_{X\times Y})</annotation></semantics></math></div><div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><msup><mi>i</mi> <mo>*</mo></msup><mo lspace="verythinmathspace">:</mo><mstyle mathvariant="bold"><mi>Gl</mi></mstyle><mo stretchy="false">(</mo><mo>⊓</mo><mo stretchy="false">)</mo><mo>→</mo><mi>Set</mi><mo>×</mo><mi>Set</mi><mspace width="2em"></mspace><mo stretchy="false">(</mo><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo stretchy="false">)</mo><mo>,</mo><mi>Z</mi><mo>,</mo><mi>u</mi><mo stretchy="false">)</mo><mo>↦</mo><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex"> i^\ast\colon \mathbf{Gl}(\sqcap)\to Set\times Set \qquad ((X,Y),Z,u)\mapsto (X,Y)</annotation></semantics></math></div><div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><msub><mi>i</mi> <mo>!</mo></msub><mo lspace="verythinmathspace">:</mo><mi>Set</mi><mo>×</mo><mi>Set</mi><mo>→</mo><mstyle mathvariant="bold"><mi>Gl</mi></mstyle><mo stretchy="false">(</mo><mo>⊓</mo><mo stretchy="false">)</mo><mspace width="2em"></mspace><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo stretchy="false">)</mo><mo>↦</mo><mo stretchy="false">(</mo><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo stretchy="false">)</mo><mo>,</mo><mn>0</mn><mo>,</mo><mn>0</mn><mo>→</mo><mi>X</mi><mo>×</mo><mi>Y</mi><mo stretchy="false">)</mo><mspace width="1em"></mspace><mo>,</mo></mrow><annotation encoding="application/x-tex"> i_{!} \colon Set\times Set\to \mathbf{Gl}(\sqcap) \qquad (X,Y)\mapsto ((X,Y),0,0\to X\times Y) \quad ,</annotation></semantics></math></div> <p>and the closed inclusion of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Set</mi></mrow><annotation encoding="application/x-tex">Set</annotation></semantics></math> by</p> <div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><msub><mi>j</mi> <mo>*</mo></msub><mo lspace="verythinmathspace">:</mo><mi>Set</mi><mo>→</mo><mstyle mathvariant="bold"><mi>Gl</mi></mstyle><mo stretchy="false">(</mo><mo>⊓</mo><mo stretchy="false">)</mo><mspace width="2em"></mspace><mi>X</mi><mo>↦</mo><mo stretchy="false">(</mo><mo stretchy="false">(</mo><mn>1</mn><mo>,</mo><mn>1</mn><mo stretchy="false">)</mo><mo>,</mo><mi>X</mi><mo>,</mo><mi>X</mi><mo>→</mo><mn>1</mn><mo>×</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex"> j_\ast \colon Set\to \mathbf{Gl}(\sqcap) \qquad X\mapsto ((1,1),X,X\to 1\times 1)</annotation></semantics></math></div><div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><msup><mi>j</mi> <mo>*</mo></msup><mo lspace="verythinmathspace">:</mo><mstyle mathvariant="bold"><mi>Gl</mi></mstyle><mo stretchy="false">(</mo><mo>⊓</mo><mo stretchy="false">)</mo><mo>→</mo><mi>Set</mi><mspace width="2em"></mspace><mo stretchy="false">(</mo><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo stretchy="false">)</mo><mo>,</mo><mi>Z</mi><mo>,</mo><mi>u</mi><mo stretchy="false">)</mo><mo>↦</mo><mi>Z</mi><mspace width="1em"></mspace><mo>.</mo></mrow><annotation encoding="application/x-tex"> j^\ast\colon\mathbf{Gl}(\sqcap)\to Set \qquad ((X,Y),Z,u)\mapsto Z\quad .</annotation></semantics></math></div> <p>Since <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo>▵</mo><mo>⊣</mo><mo>⊓</mo></mrow><annotation encoding="application/x-tex">\triangle\dashv\sqcap</annotation></semantics></math> the closed inclusion is <a class="existingWikiWord" href="/nlab/show/essential+geometric+morphism">essential</a>:</p> <div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><msub><mi>j</mi> <mo>!</mo></msub><mo lspace="verythinmathspace">:</mo><mi>Set</mi><mo>→</mo><mstyle mathvariant="bold"><mi>Gl</mi></mstyle><mo stretchy="false">(</mo><mo>⊓</mo><mo stretchy="false">)</mo><mspace width="2em"></mspace><mi>X</mi><mo>↦</mo><mo stretchy="false">(</mo><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>X</mi><mo stretchy="false">)</mo><mo>,</mo><mi>X</mi><mo>,</mo><mi>X</mi><mover><mo>→</mo><mrow><mo stretchy="false">⟨</mo><msub><mi>id</mi> <mi>X</mi></msub><mo>,</mo><msub><mi>id</mi> <mi>X</mi></msub><mo stretchy="false">⟩</mo></mrow></mover><mi>X</mi><mo>×</mo><mi>X</mi><mo stretchy="false">)</mo><mspace width="1em"></mspace><mo>.</mo></mrow><annotation encoding="application/x-tex"> 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 .</annotation></semantics></math></div> <p>Since <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo>⊔</mo><mo>⊣</mo><mo>▵</mo></mrow><annotation encoding="application/x-tex">\sqcup\dashv \triangle</annotation></semantics></math> there is a somewhat surprising further left adjoint:</p> <div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><msup><mi>j</mi> <mo>∘</mo></msup><mo lspace="verythinmathspace">:</mo><mstyle mathvariant="bold"><mi>Gl</mi></mstyle><mo stretchy="false">(</mo><mo>⊓</mo><mo stretchy="false">)</mo><mo>→</mo><mi>Set</mi><mspace width="2em"></mspace><mo stretchy="false">(</mo><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo stretchy="false">)</mo><mo>,</mo><mi>Z</mi><mo>,</mo><mi>u</mi><mo stretchy="false">)</mo><mo>↦</mo><mi>X</mi><msub><mo>⊔</mo> <mi>u</mi></msub><mi>Y</mi><mspace width="1em"></mspace><mo>.</mo></mrow><annotation encoding="application/x-tex"> j^\circ\colon\mathbf{Gl}(\sqcap)\to Set \qquad ((X,Y),Z,u)\mapsto X\sqcup_u Y\quad .</annotation></semantics></math></div> <p>Here <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>X</mi><msub><mo>⊔</mo> <mi>u</mi></msub><mi>Y</mi></mrow><annotation encoding="application/x-tex"> X\sqcup_u Y</annotation></semantics></math> denotes the <a class="existingWikiWord" href="/nlab/show/pushout">pushout</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>X</mi><mover><mo>←</mo><mrow><msub><mi>u</mi> <mn>0</mn></msub></mrow></mover><mi>Z</mi><mover><mo>→</mo><mrow><msub><mi>u</mi> <mn>1</mn></msub></mrow></mover><mi>Y</mi></mrow><annotation encoding="application/x-tex">X\overset{u_0}{\leftarrow} Z\overset{u_1}{\rightarrow} Y</annotation></semantics></math> where <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>u</mi> <mn>0</mn></msub></mrow><annotation encoding="application/x-tex">u_0</annotation></semantics></math>, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>u</mi> <mn>1</mn></msub></mrow><annotation encoding="application/x-tex">u_1</annotation></semantics></math> are the pair of maps provided by <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>u</mi><mo lspace="verythinmathspace">:</mo><mi>Z</mi><mover><mo>→</mo><mrow><mo stretchy="false">⟨</mo><msub><mi>u</mi> <mn>0</mn></msub><mo>,</mo><msub><mi>u</mi> <mn>1</mn></msub><mo stretchy="false">⟩</mo></mrow></mover><mi>X</mi><mo>×</mo><mi>Y</mi></mrow><annotation encoding="application/x-tex">u\colon Z\overset{\langle u_0, u_1\rangle}{\rightarrow} X\times Y</annotation></semantics></math> . Since a map from <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo stretchy="false">)</mo><mo>,</mo><mi>Z</mi><mo>,</mo><mi>u</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">((X,Y),Z,u)</annotation></semantics></math> to <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>j</mi> <mo>!</mo></msub><mo stretchy="false">(</mo><mi>W</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">j_!(W)</annotation></semantics></math> is a triple <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><msub><mi>f</mi> <mn>0</mn></msub><mo>,</mo><msub><mi>f</mi> <mn>1</mn></msub><mo>,</mo><msub><mi>f</mi> <mn>2</mn></msub><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(f_0,f_1,f_2)</annotation></semantics></math> such that the following diagram commutes:</p> <div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><mrow><mtable><mtr><mtd><mi>Z</mi></mtd> <mtd><mover><mo>→</mo><mrow><mo stretchy="false">⟨</mo><msub><mi>u</mi> <mn>0</mn></msub><mo>,</mo><msub><mi>u</mi> <mn>1</mn></msub><mo stretchy="false">⟩</mo></mrow></mover></mtd> <mtd><mi>X</mi><mo>×</mo><mi>Y</mi></mtd></mtr> <mtr><mtd><msub><mi>f</mi> <mn>2</mn></msub><mo stretchy="false">↓</mo></mtd> <mtd></mtd> <mtd><msub><mi>f</mi> <mn>0</mn></msub><mo stretchy="false">↓</mo><mo stretchy="false">↓</mo><msub><mi>f</mi> <mn>1</mn></msub></mtd></mtr> <mtr><mtd><mi>W</mi></mtd> <mtd><mover><mo>→</mo><mrow><mo stretchy="false">⟨</mo><msub><mi>id</mi> <mi>W</mi></msub><mo>,</mo><msub><mi>id</mi> <mi>W</mi></msub><mo stretchy="false">⟩</mo></mrow></mover></mtd> <mtd><mi>W</mi><mo>×</mo><mi>W</mi></mtd></mtr></mtable></mrow></mrow><annotation encoding="application/x-tex"> \array{ 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 } </annotation></semantics></math></div> <p><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><msub><mi>f</mi> <mn>0</mn></msub><mo>,</mo><msub><mi>f</mi> <mn>1</mn></msub><mo>,</mo><msub><mi>f</mi> <mn>2</mn></msub><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(f_0,f_1,f_2)</annotation></semantics></math> has to satisfy the two conditions <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>f</mi> <mn>0</mn></msub><msub><mi>u</mi> <mn>0</mn></msub><mo>=</mo><msub><mi>f</mi> <mn>2</mn></msub></mrow><annotation encoding="application/x-tex">f_0 u_0= f_2</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>f</mi> <mn>1</mn></msub><msub><mi>u</mi> <mn>1</mn></msub><mo>=</mo><msub><mi>f</mi> <mn>2</mn></msub></mrow><annotation encoding="application/x-tex">f_1 u_1=f_2</annotation></semantics></math>, or equivalently, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>f</mi> <mn>0</mn></msub><msub><mi>u</mi> <mn>0</mn></msub><mo>=</mo><msub><mi>f</mi> <mn>1</mn></msub><msub><mi>u</mi> <mn>1</mn></msub></mrow><annotation encoding="application/x-tex">f_0 u_0=f_1 u_1</annotation></semantics></math> . But this is the same as giving a map from <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>j</mi> <mo>∘</mo></msup><mo stretchy="false">(</mo><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo stretchy="false">)</mo><mo>,</mo><mi>Z</mi><mo>,</mo><mi>u</mi><mo stretchy="false">)</mo><mo>=</mo><mi>X</mi><msub><mo>⊔</mo> <mi>u</mi></msub><mi>Y</mi></mrow><annotation encoding="application/x-tex">j^\circ ((X,Y),Z,u)= X\sqcup_u Y</annotation></semantics></math> to <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>W</mi></mrow><annotation encoding="application/x-tex">W</annotation></semantics></math> by the universal property of the pushout.</p> <p>Whence we get an adjoint string:</p> <div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><msup><mi>j</mi> <mo>∘</mo></msup><mo>⊣</mo><msub><mi>j</mi> <mo>!</mo></msub><mo>⊣</mo><msup><mi>j</mi> <mo>*</mo></msup><mo>⊣</mo><msub><mi>j</mi> <mo>*</mo></msub><mo lspace="verythinmathspace">:</mo><mi>Set</mi><mo>→</mo><mi>𝔾𝕝</mi><mo stretchy="false">(</mo><mo>⊓</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">j^\circ\dashv j_!\dashv j^\ast \dashv j_\ast \colon Set\to \mathbb{Gl}(\sqcap)</annotation></semantics></math></div> <p>with <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>j</mi> <mo>!</mo></msub></mrow><annotation encoding="application/x-tex">j_!</annotation></semantics></math>, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>j</mi> <mo>*</mo></msub></mrow><annotation encoding="application/x-tex">j_\ast</annotation></semantics></math> <a class="existingWikiWord" href="/nlab/show/fully+faithful">fully faithful</a>, exhibiting <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mstyle mathvariant="bold"><mi>Gl</mi></mstyle><mo stretchy="false">(</mo><mo>⊓</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\mathbf{Gl}(\sqcap)</annotation></semantics></math> almost as a <a class="existingWikiWord" href="/nlab/show/cohesive+topos">cohesive topos</a> over <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Set</mi></mrow><annotation encoding="application/x-tex">Set</annotation></semantics></math>. Of course, since <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>Set</mi> <mrow><mo>•</mo><mo>←</mo><mo>•</mo><mo>→</mo><mo>•</mo></mrow></msup></mrow><annotation encoding="application/x-tex">Set^{\bullet\leftarrow\bullet\rightarrow\bullet}</annotation></semantics></math> is spatial it is not expected to satisfy all of Lawvere’s axioms. In particular, the <a class="existingWikiWord" href="/nlab/show/Nullstellensatz">Nullstellensatz</a> is violated since none of the copies of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Set</mi></mrow><annotation encoding="application/x-tex">Set</annotation></semantics></math> is <a class="existingWikiWord" href="/nlab/show/dense+subtopos">dense</a> in <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>Set</mi> <mrow><mo>•</mo><mo>←</mo><mo>•</mo><mo>→</mo><mo>•</mo></mrow></msup></mrow><annotation encoding="application/x-tex">Set^{\bullet\leftarrow\bullet\rightarrow\bullet}</annotation></semantics></math>.</p> <p>Let <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Q</mi></mrow><annotation encoding="application/x-tex">Q</annotation></semantics></math> be the diagram category <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>N</mi><mover><munder><mo>⇉</mo><mi>t</mi></munder><mi>s</mi></mover><mi>A</mi></mrow><annotation encoding="application/x-tex">N\overset{s}{\underset{t}{\rightrightarrows}} A</annotation></semantics></math> underlying the topos <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>Set</mi> <mrow><msup><mi>Q</mi> <mi>op</mi></msup></mrow></msup></mrow><annotation encoding="application/x-tex">Set^{Q^{op}}</annotation></semantics></math> of directed graphs or <a class="existingWikiWord" href="/nlab/show/quiver">quivers</a>. Consider the <a class="existingWikiWord" href="/nlab/show/Yoneda+embedding">Yoneda embedding</a> of the object <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>A</mi></mrow><annotation encoding="application/x-tex">A</annotation></semantics></math> into the presheaves: <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Y</mi><mo stretchy="false">(</mo><mi>A</mi><mo stretchy="false">)</mo><mo>=</mo><msub><mi>Hom</mi> <mi>Q</mi></msub><mo stretchy="false">(</mo><mo lspace="verythinmathspace" rspace="0em">−</mo><mo>,</mo><mi>A</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">Y(A)=Hom_Q(-,A)</annotation></semantics></math>. Viewed as a graph this gives the basic figure type of an <em>a</em>rrow <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>K</mi> <mn>2</mn></msub><mo>=</mo><mo>•</mo><mo>→</mo><mo>•</mo></mrow><annotation encoding="application/x-tex">K_2=\bullet\to\bullet</annotation></semantics></math> , the other basic figure being the <em>n</em>ode <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo>•</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math> given by <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Y</mi><mo stretchy="false">(</mo><mi>N</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">Y(N)</annotation></semantics></math> .</p> <p>The <a class="existingWikiWord" href="/nlab/show/category+of+elements">category of elements</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mo>∫</mo> <mi>Q</mi></msub><mi>Y</mi><mo stretchy="false">(</mo><mi>A</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\int_Q Y(A)</annotation></semantics></math> is just the category <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo>•</mo><mo>→</mo><mo>•</mo><mo>←</mo><mo>•</mo></mrow><annotation encoding="application/x-tex">\bullet\rightarrow \bullet\leftarrow\bullet</annotation></semantics></math> underlying the hypergraphs. Since <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Y</mi><mo stretchy="false">(</mo><mi>A</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">Y(A)</annotation></semantics></math> is the representable presheaf corresponding to <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>A</mi></mrow><annotation encoding="application/x-tex">A</annotation></semantics></math> this is equivalent to the <a class="existingWikiWord" href="/nlab/show/slice+category">slice category</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Q</mi><mo stretchy="false">/</mo><mi>A</mi></mrow><annotation encoding="application/x-tex">Q/A</annotation></semantics></math>. Then the following equivalence exhibits <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>Set</mi> <mrow><msup><mi>Q</mi> <mi>op</mi></msup></mrow></msup></mrow><annotation encoding="application/x-tex">Set^{Q^{op}}</annotation></semantics></math> as an <a class="existingWikiWord" href="/nlab/show/%C3%A9tendue">étendue topos</a> using a general formula for <a class="existingWikiWord" href="/nlab/show/slice+topos">slices</a> of <a class="existingWikiWord" href="/nlab/show/presheaf+topos">presheaf toposes</a> and suggesting to view a quiver as a ‘foliated’ hypergraph:</p> <div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><msup><mi>Set</mi> <mrow><msup><mi>Q</mi> <mi>op</mi></msup></mrow></msup><mo stretchy="false">/</mo><mi>Y</mi><mo stretchy="false">(</mo><mi>A</mi><mo stretchy="false">)</mo><mo>≃</mo><msup><mi>Set</mi> <mrow><mo stretchy="false">(</mo><mi>Q</mi><mo stretchy="false">/</mo><mi>A</mi><msup><mo stretchy="false">)</mo> <mi>op</mi></msup></mrow></msup><mo>≃</mo><msup><mi>Set</mi> <mrow><mo stretchy="false">(</mo><msub><mo>∫</mo> <mi>Q</mi></msub><mi>Y</mi><mo stretchy="false">(</mo><mi>A</mi><mo stretchy="false">)</mo><msup><mo stretchy="false">)</mo> <mi>op</mi></msup></mrow></msup><mo>≃</mo><msup><mi>Set</mi> <mrow><mo>•</mo><mo>←</mo><mo>•</mo><mo>→</mo><mo>•</mo></mrow></msup><mspace width="1em"></mspace><mo>.</mo></mrow><annotation encoding="application/x-tex">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 .</annotation></semantics></math></div> <p>This equivalence will be further explained in terms of graph colorings in the next section.</p> <h2 id="hypergraphs_as_2colored_graphs">Hypergraphs as 2-colored graphs</h2> <p>There is a classical equivalence between hypergraphs and <a class="existingWikiWord" href="/nlab/show/vertex+coloring">2-colored</a> (hence <a class="existingWikiWord" href="/nlab/show/bipartite+graph">bipartite</a>) graphs. Given a hypergraph <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>H</mi></mrow><annotation encoding="application/x-tex">H</annotation></semantics></math>, define a graph <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi><mo stretchy="false">(</mo><mi>H</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">G(H)</annotation></semantics></math> whose vertex set is the <a class="existingWikiWord" href="/nlab/show/disjoint+union">disjoint union</a> of the hypervertices and the hyperedges of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>H</mi></mrow><annotation encoding="application/x-tex">H</annotation></semantics></math>, and with an edge <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>x</mi> <mi>v</mi></msub><mo>∼</mo><msub><mi>x</mi> <mi>e</mi></msub></mrow><annotation encoding="application/x-tex">x_v \sim x_e</annotation></semantics></math> in <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi><mo stretchy="false">(</mo><mi>H</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">G(H)</annotation></semantics></math> whenever the corresponding pair <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>v</mi><mo>,</mo><mi>e</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(v,e)</annotation></semantics></math> are incident in <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>H</mi></mrow><annotation encoding="application/x-tex">H</annotation></semantics></math> (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 <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math> determines a hypergraph <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>H</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">H(G)</annotation></semantics></math> by interpreting black vertices as hypervertices and white vertices as hyperedges that connect all of their (black vertex) neighbors.</p> <p>Giving a <a class="existingWikiWord" href="/nlab/show/vertex+coloring">vertex coloring</a> of a graph <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math> with <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math> colors is equivalent to building a graph homomorphism <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi><mo>→</mo><msub><mi>K</mi> <mi>n</mi></msub></mrow><annotation encoding="application/x-tex">G \to K_n</annotation></semantics></math> into the complete graph on <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math> vertices, and so graphs equipped with a <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mn>2</mn></mrow><annotation encoding="application/x-tex">2</annotation></semantics></math>-coloring are naturally organized as a <a class="existingWikiWord" href="/nlab/show/slice">slice</a> category over <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>K</mi> <mn>2</mn></msub></mrow><annotation encoding="application/x-tex">K_2</annotation></semantics></math>. The classical equivalence between hypergraphs and 2-colored graphs can then be expressed formally as an <a class="existingWikiWord" href="/nlab/show/equivalence+of+categories">equivalence of categories</a></p> <div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><mi>HGrph</mi><mo>≅</mo><mi>Grph</mi><mo stretchy="false">/</mo><msub><mi>K</mi> <mn>2</mn></msub></mrow><annotation encoding="application/x-tex"> HGrph \cong Grph/K_2 </annotation></semantics></math></div> <p>between the category of hypergraphs and the slice over <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>K</mi> <mn>2</mn></msub></mrow><annotation encoding="application/x-tex">K_2</annotation></semantics></math> 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 <a class="existingWikiWord" href="/nlab/show/graph#definition_in_terms_of_action_on_a_set_of_halfedges">this definition</a>). Moreover, this equivalence restricts to an equivalence</p> <div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><mi>SimpHGrph</mi><mo>≅</mo><mi>LoopGrph</mi><mo stretchy="false">/</mo><msub><mi>K</mi> <mn>2</mn></msub></mrow><annotation encoding="application/x-tex"> SimpHGrph \cong LoopGrph/K_2 </annotation></semantics></math></div> <p>where <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>LoopGraph</mi></mrow><annotation encoding="application/x-tex">LoopGraph</annotation></semantics></math> is the category of “loop graphs”, i.e., the full subcategory of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Grph</mi></mrow><annotation encoding="application/x-tex">Grph</annotation></semantics></math> whose objects are symmetric relations.</p> <h2 id="related_concepts">Related concepts</h2> <ul> <li> <p><a class="existingWikiWord" href="/nlab/show/hypermap">hypermap</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/hyperstructure">hyperstructure</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/hypergraph+category">hypergraph category</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/quiver">quiver</a></p> </li> </ul> <h2 id="references">References</h2> <ul> <li> <p>W. Dörfler and D. A. Waller, <em>A category-theoretical approach to hypergraphs</em>, Archiv der Mathematik <strong>34</strong> no.1 (1980) pp.185-192. DOI: 10.1007/BF01224952</p> </li> <li> <p>W. Grilliette, <em>A Functorial Link between Hypergraphs and Quivers</em> , Electronic J. of Combinatorics <strong>22</strong> (2015). (<a href="http://arxiv.org/abs/1608.00058">arXiv:1608:00058</a>)</p> </li> <li id="Law86"> <p><a class="existingWikiWord" href="/nlab/show/F.+William+Lawvere">F. William Lawvere</a>, <em>Categories of Spaces may not be Generalized Spaces as Exemplified by Directed Graphs</em>, Revista Colombiana de Matemáticas <strong>XX</strong> (1986) pp.179-186. Reprinted with commentary in TAC <strong>9</strong> (2005) pp.1-7. (<a href="http://www.tac.mta.ca/tac/reprints/articles/9/tr9.pdf">pdf</a>)</p> </li> <li id="Law89"> <p><a class="existingWikiWord" href="/nlab/show/F.+William+Lawvere">F. William Lawvere</a>, <em>Qualitative Distinctions between some Toposes of Generalized Graphs</em> , Cont. Math. <strong>92</strong> (1989) pp.261-299.</p> </li> <li> <p>T. R. S. Walsh, <em>Hypermaps Versus Bipartite Maps</em>, Journal of Combinatorial Theory (B) <strong>18</strong> (1975) pp.155-163.</p> </li> <li> <p>Martin Schmidt, <em>Functorial Approach to Graph and Hypergraph Theory</em>, (<a href="https://arxiv.org/abs/1907.02574">arXiv:1907.02574</a>)</p> </li> </ul> </body></html> </div> <div class="revisedby"> <p> Last revised on July 8, 2019 at 12:14:07. See the <a href="/nlab/history/hypergraph" style="color: #005c19">history</a> of this page for a list of all contributions to it. </p> </div> <div class="navigation navfoot"> <a href="/nlab/edit/hypergraph" accesskey="E" class="navlink" id="edit" rel="nofollow">Edit</a><a href="https://nforum.ncatlab.org/discussion/10098/#Item_1">Discuss</a><span class="backintime"><a href="/nlab/revision/hypergraph/24" accesskey="B" class="navlinkbackintime" id="to_previous_revision" rel="nofollow">Previous revision</a></span><a href="/nlab/show/diff/hypergraph" accesskey="C" class="navlink" id="see_changes" rel="nofollow">Changes from previous revision</a><a href="/nlab/history/hypergraph" accesskey="S" class="navlink" id="history" rel="nofollow">History (24 revisions)</a> <a href="/nlab/show/hypergraph/cite" style="color: black">Cite</a> <a href="/nlab/print/hypergraph" accesskey="p" id="view_print" rel="nofollow">Print</a> <a href="/nlab/source/hypergraph" id="view_source" rel="nofollow">Source</a> </div> </div>  </div>  </body> </html>