5
$\begingroup$

If $H_i = (V_i, E_i)$ for $i=1,2$ are hypergraphs then a map $f:V_1\to V_2$ is said to be a hypergraph homomorphism if $f(e_1)\in E_2$ for all $e_1\in E_1$. Hypergraphs together with hypergraph homomorphisms form a category. Is this category cartesian closed?

$\endgroup$
6
  • 1
    $\begingroup$ Do you have a hypergraph structure on $Hom(G_1,G_2)$ in mind? Maybe something drawn from category theory (since graphs are kinda like categories)? $\endgroup$ Commented Jan 26, 2019 at 16:26
  • $\begingroup$ Good point. How is it done in the category of graphs? Maybe for the category of graphs we could say that $f,g\in \text{Hom}(G,H)$ form an edge if $\{f(v),g(v)\}\in E(H)$ for all $v\in V(G)$. Analogously for hypergraphs, how about ${\cal S}\subseteq\text{Hom}(H_1, H_2)$ is a hyperedge in $\text{Hom}(H_1,H_2)$, iff $\{f(v): f\in {\cal S}\} \in E(H_2)$ for all $v\in V(H_1)$? $\endgroup$ Commented Jan 26, 2019 at 21:27
  • $\begingroup$ In this link it says Cat is cartesian closed, with functor categories as the internal hom. It says directed graphs are cartesian closed, probably using the same idea. en.wikipedia.org/wiki/Cartesian_closed_category $\endgroup$ Commented Jan 27, 2019 at 15:29
  • 1
    $\begingroup$ I take that previous link to suggest that the cartesian product on directed graphs makes it cartesian closed. There's also a cartesian product on graphs (link below) but I do not know if hom-tensor duality is satisfied. There's also a tensor product on graphs (link below): en.wikipedia.org/wiki/Cartesian_product_of_graphs, math.stackexchange.com/questions/302147/… $\endgroup$ Commented Jan 27, 2019 at 15:31
  • 1
    $\begingroup$ I remember from a course in grad school that there are 4 monoidal products on Graph, but I don't remember all of them. $\endgroup$ Commented Jan 27, 2019 at 17:36

1 Answer 1

4
$\begingroup$

I think the answer is yes, although the internal-hom may be a little surprising.

First let's describe the cartesian product. I believe the category $\rm HyGph$ is a topological concrete category over $\rm Set$, in the following way. Suppose $X$ is a set and $\{S_i\}$ is a family of hypergraphs, with functions $f_i : X \to V_{S_i}$ to their vertex sets. Then there is a "largest hypergraph" on $X$ rendering the $f_i$ homomorphisms, where $E_X$ consists of all subsets $e\subseteq X$ such that $f_i(e)\in E_{S_i}$ for all $i$. In particular, given hypergraphs $Y,Z$, if we take $X = V_Y \times V_Z$ with the $f$'s the projections, we obtain the product hypergraph structure on $V_Y\times V_Z = V_{Y\times Z}$: thus $E_{Y\times Z}$ consists of all subsets $e\subseteq V_Y\times V_Z$ such that $\pi_1(e)\in E_Y$ and $\pi_2(e)\in E_Z$. Put differently, each edge of $Y\times Z$ is obtained by choosing an edge $e_Y\in E_Y$ and an edge $e_Z\in E_Z$, and then choosing a subset of the rectangle $e_Y \times e_Z \subseteq V_Y \times V_Z$ that projects onto both $e_Y$ and $e_Z$, i.e. contains at least one ordered pair with each possible first coordinate and at least one ordered pair with each possible second component.

Now there is a standard way to discover what an internal-hom must look like if it exists, by mapping out of small objects. To start with, let $I$ be the hypergraph with one vertex and no edges. Then for any hypergraph $X=(V_X,E_X)$, a homomorphism $I\to X$ simply picks out a vertex of $X$. Thus, if there is an internal-hom $Y^X$, the vertices of $Y^X$ are in bijection with the homomorphisms $I\to Y^X$, which must in turn be in bijection with the homomorphisms $I\times X\to Y$. But since $I$ has no edges, the above description of the product means that $I\times X$ has no edges either (in fact we could see this simply because any edge of $I\times X$ must project to an edge of $I$). Thus every set-function from $V_{I\times X} \cong V_X$ to $V_Y$ determines a vertex of $Y^X$, whether or not it is a homomorphism.

The information about homomorphisms is instead carried by the unary edges (edges containing only one vertex). The terminal hypergraph $1$ is a one-element set with the unique possible (unary) edge. A homomorphism $1\to X$ picks out a vertex of $X$ that belong to a unary edge. Thus, a homomorphism $1\to Y^X$ picks out such a vertex of $Y^X$, but such homomorphisms must be bijective to homomorphisms $1\times X \to Y$, i.e. $X\to Y$ since $1\times X \cong X$. So the vertices of $Y^X$ are the arbitrary set-functions $V_X\to V_Y$, while the homomorphisms are the set-functions that belong to unary edges. This is similar to some other examples of cartesian closed categories, such as $G\text{-}\rm Set$ in which the elements of $Y^X$ are arbitrary functions $X\to Y$, with $G$ acting by conjugation, so that the actual $G$-equivariant maps $X\to Y$ (the "real morphisms" in the category) are instead the $G$-fixed-points of the $G$-set $Y^X$.

We can detect all the other edges of $Y^X$ in a similar way. For any nonempty set $A$, let $J_A$ be the hypergraph with vertices $A$ and the only edge being the whole set $A$. Then a homomorphism $J_A\to X$ is a function $A\to X$ whose image is an edge. Thus, an edge of $Y^X$ must be uniquely determined by picking a subset $A\subseteq V_{Y^X}$ of functions $V_X\to V_Y$ such that the corresponding function $A\times V_X \to V_Y$ is a homomorphism $J_A \times X\to Y$, which is to say such that for any edge $e_X\in E_X$, if a subset $e\subseteq A\times e_X$ projects onto both $A$ and $e_X$, then $\{ f(x) \mid (f,x)\in e \}$ is an edge of $Y$.

This defines a hypergraph $Y^X$ which must be the cartesian-closed exponential if such exists. It remains to prove that it actually is, but I think this is fairly straightforward. The evaluation map $Y^X\times X\to Y$ is a homomorphism, essentially by definition of the edges of $Y^X$. And if $Z\times X\to Y$ is a homomorphism, then there is a unique induced function $V_Z\to V_{Y^X} = (V_Y)^{V_X}$, which is a homomorphism again essentially by definition of the edges of $Y^X$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.