Is Hyper-graph Isomorphism preserve the size of edges or Rank of Hyper-graph?

441 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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!