4
$\begingroup$

Informally, hypergraph is a generalization of a graph in which an edge can join any number of vertices.

A hypergraph $G=(V, E)$ is a two tuple, where $V$ is the set of vertices and $E$ is a set contain subsets of the vertex set of $V$. An example of hyper-graph is given below and for example edge $e_3$ is a subset contain $v_3,v_5,v_6$ and similarly for other edges.

enter image description here

Isomorphism : Two hyper graphs $G(V,E)$ and $H(V,E')$ are isomorphic if there is a permutation $g$ on $V$ such that, $\forall $ $e \in E$, $$e\in E \iff g(e) \in E'$$

Question : Is the hypergraph isomorphism preserve the size of edge (edge is a subset of vertex set here) i.e. an edge $e$ that contain say $l$ vertices will be mapped to edge $g(e)$ whose size is also $l$ or it is not required.

Reference: https://en.wikipedia.org/wiki/Hypergraph

$\endgroup$
4
$\begingroup$

Whether it's expressly stated or not, it must be the case that hypergraph automorphisms send an edge containing $\ell$ points to another edge containing $\ell$ points.

This follows from the fact that $g: V \to V$ is a permutation (i.e., bijection). The very definition of two sets having the same size is that there is a bijective map from one to the other. Here, $g$ restricted to any subset of $V$ (say, $E$) is a bijective map from $E$ to $g(E)$, hence $E$ and $g(E)$ contain the same number of vertices.

And hopefully this agrees with your intuition about isomorphisms; isomorphic objects should be "the same" in every essential way, and the number of vertices contained in a given edge seems pretty essential, when it comes to hypergraphs!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy