2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ I think your graph-like structure is what's called a hypergraph, where "edges" (hyperedges) are allowed to encompass any number of vertices. $\endgroup$
    – pjs36
    Feb 21, 2016 at 7:58
  • $\begingroup$ @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)$. $\endgroup$
    – user10575
    Feb 21, 2016 at 8:04
  • $\begingroup$ Good point, @Shahab . I'd kind of assumed it would be functionally equivalent to a hypergraph, but this isn't necessarily the case. $\endgroup$
    – pjs36
    Feb 21, 2016 at 8:12

1 Answer 1

Reset to default
1
$\begingroup$

The question isn't well defined, of course, but it's hard for me to imagine a meaningful sense in which the answer is "no".

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.

The thing you're describing sounds very vaguely like a discrete version of a fibre bundle. I'd need to know a lot more about your motivation for considering such objects to do better than that, and you would need better than that to find anything. (In particular, your objects are very much more general than a fibre bundle on a discrete space...)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .