Editing Hypergraph (section)

==Isomorphism, symmetry, 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 <math>H=(X,E)</math> is ''isomorphic'' to a hypergraph <math>G=(Y,F)</math>,  written as <math>H \simeq G</math> if there exists a [[bijection]]

:<math>\phi:X \to Y</math>

and a [[permutation]] <math>\pi</math> of <math>I</math> such that

:<math>\phi(e_i) = f_{\pi(i)}</math>

The bijection <math>\phi</math> is then called the [[isomorphism]] of the graphs.  Note that

:<math>H \simeq G</math> if and only if <math>H^* \simeq G^*</math>.

When the edges of a hypergraph are explicitly labeled, one has the additional notion of ''strong isomorphism''. One says that <math>H</math> is ''strongly isomorphic'' to <math>G</math> if the permutation is the identity. One then writes <math>H \cong G</math>.  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 <math>H</math> is ''equivalent'' to <math>G</math>, and writes <math>H\equiv G</math> if the isomorphism <math>\phi</math> has

:<math>\phi(x_n) = y_n</math>

and

:<math>\phi(e_i) = f_{\pi(i)}</math>

Note that

:<math>H\equiv G</math> if and only if <math>H^* \cong G^*</math>

If, in addition, the permutation <math>\pi</math> is the identity, one says that <math>H</math> equals <math>G</math>, and writes <math>H=G</math>.  Note that, with this definition of equality, graphs are self-dual:

:<math>\left(H^*\right) ^* = H</math>

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'',&nbsp;''E'')) is a [[group (mathematics)|group]] under composition, called the [[automorphism group]] of the hypergraph and written Aut(''H'').

===Examples===
Consider the hypergraph <math>H</math> with edges
:<math>H = \lbrace
e_1 = \lbrace a,b \rbrace,
e_2 = \lbrace b,c \rbrace,
e_3 = \lbrace c,d \rbrace,
e_4 = \lbrace d,a \rbrace,
e_5 = \lbrace b,d \rbrace,
e_6 = \lbrace a,c \rbrace
\rbrace</math>
and
:<math>G = \lbrace
f_1 = \lbrace \alpha,\beta \rbrace,
f_2 = \lbrace \beta,\gamma \rbrace,
f_3 = \lbrace \gamma,\delta \rbrace,
f_4 = \lbrace \delta,\alpha \rbrace,
f_5 = \lbrace \alpha,\gamma \rbrace,
f_6 = \lbrace \beta,\delta \rbrace
\rbrace</math>

Then clearly <math>H</math> and <math>G</math> are isomorphic (with <math>\phi(a)=\alpha</math>, ''etc.''), but they are not strongly isomorphic. So, for example, in <math>H</math>, vertex <math>a</math> meets edges 1, 4 and 6, so that,

:<math>e_1 \cap e_4 \cap e_6 = \lbrace a\rbrace</math>

In graph <math>G</math>, there does not exist any vertex that meets edges 1, 4 and 6:

:<math>f_1 \cap f_4 \cap f_6 = \varnothing</math>

In this example, <math>H</math> and <math>G</math> are equivalent, <math>H\equiv G</math>, and the duals are strongly isomorphic: <math>H^*\cong G^*</math>.

===Symmetry===
The ''{{visible anchor|rank}}'' <math>r(H)</math> of a hypergraph <math>H</math> is the maximum cardinality of any of the edges in the hypergraph.  If all edges have the same cardinality ''k'', the hypergraph is said to be ''uniform'' or ''k-uniform'', or is called a ''k-hypergraph''.  A graph is just a 2-uniform hypergraph.

The degree ''d(v)'' of a vertex ''v'' is the number of edges that contain it. ''H'' is ''k-regular'' if every vertex has degree ''k''.

The dual of a uniform hypergraph is regular and vice versa.

Two vertices ''x'' and ''y'' of ''H'' are called ''symmetric'' if there exists an automorphism such that <math>\phi(x)=y</math>.  Two edges <math>e_i</math> and <math>e_j</math> are said to be  ''symmetric'' if there exists an automorphism such that <math>\phi(e_i)=e_j</math>.

A hypergraph is said to be ''vertex-transitive'' (or ''vertex-symmetric'') if all of its vertices are symmetric. Similarly, a hypergraph is ''edge-transitive'' if all edges are symmetric. If a hypergraph is both edge- and vertex-symmetric, then the hypergraph is simply ''transitive''.

Because of hypergraph duality, the study of edge-transitivity is identical to the study of vertex-transitivity.