Hypergraph - Isomorphism and Equality

Isomorphism and Equality

A hypergraph homomorphism is a map from the vertex set of one hypergraph to another such that each edge maps to one other edge.

A hypergraph is isomorphic to a hypergraph, written as if there exists a bijection

and a permutation of such that

The bijection is then called the isomorphism of the graphs. Note that

if and only if .

When the edges of a hypergraph are explicitly labeled, one has the additional notion of strong isomorphism. One says that is strongly isomorphic to if the permutation is the identity. One then writes . Note that all strongly isomorphic graphs are isomorphic, but not vice-versa.

When the vertices of a hypergraph are explicitly labeled, one has the notions of equivalence, and also of equality. One says that is equivalent to, and writes if the isomorphism has

and

Note that

if and only if

If, in addition, the permutation is the identity, one says that equals, and writes . Note that, with this definition of equality, graphs are self-dual:

A hypergraph automorphism is an isomorphism from a vertex set into itself, that is a relabeling of vertices. The set of automorphisms of a hypergraph H (= (X, E)) is a group under composition, called the automorphism group of the hypergraph and written Aut(H).