# isomorphism of graph-like structures

Consider graph-like structures $S=(N,E)$ with $N$ a finite set and $E\subseteq N\times \mathcal{P}(N)$. Two such structures $(N,E)$ and $(N',E')$ are isomorphic if there is a bijection $\lambda$ between $N$ and $N'$ such that $(a,B)\in E$ iff $(\lambda(a),\lambda(B))\in E'$, where $\lambda(B)=\{\lambda(b)\mid b\in B\}$, for all $a\in N$ and $B\in\mathcal{P}(N)$.

My question is if and how isomorphisms over such structures can be reduced to graph isomorphism? As a side question, do you have pointers to the literature where such structures have been studied?

• I think your graph-like structure is what's called a hypergraph, where "edges" (hyperedges) are allowed to encompass any number of vertices. Feb 21, 2016 at 7:58
• @pjs36: I don't think it is a hypergraph as the OP requires $E\subset N\times\mathcal P(N)$ and not $E\subset\mathcal P(N)$.
– user10575
Feb 21, 2016 at 8:04
• Good point, @Shahab . I'd kind of assumed it would be functionally equivalent to a hypergraph, but this isn't necessarily the case. Feb 21, 2016 at 8:12

One can imagine such structures by splitting $E$ into the union of $E_a$ based on the first coordinate, and then creating a $|N|$-dimensional array, with side lengths $|E_a|$, and finally inserting a digraph into each cell in this array. The idea is that, if you put a linear ordering on the sets $E_a$, then the cell in the $(k_a,k_b,\cdots, k_z)$ position of the array is filled with the digraph that has edges from $n$ to $m$ iff $m$ is in the second coordinate of the ${k_n}^\text{th}$ element of $E_n$ (that is, if $E_n=\{(n,A_1),(n,A_2),\dots (n,A_q)\}$, then we want $m\in A_{k_n}$)
With this picture in mind, we can see that $S$-isomorphism is an extremely strong condition to place on a function $N\to N'$. The most basic restriction we can imagine is that $\phi$ must send each of the digraphs in the $N$ array bijectively to one digraph in the $N'$ array. So each such function is, in particular, a digraph isomorphism.