DualHypergraph - Maple Help

Hypergraphs

 DualHypergraph
 Return the dual of an hypergraph

 Calling Sequence DualHypergraph(H)

Parameters

 H -

Description

 • The command DualHypergraph(H) returns the dual hypergraph of H. ##

Terminology

 • Dual hypergraph : If H :=(X, Y) is a hypergraph, then the dual hypergraph of H is the hypergraph whose vertex set is Y and where  {y1, y2, ...} is a hyperedge if y1, y2, ... intersect at a single vertex of H and {y1, y2, ...} is inclusion-maximal with that property.
 • In broad terms, if H :=(X, Y) is a hypergraph without isolated vertices (that is, without vertices of degree zero) then the dual hypergraph of H is essentially (Y, X) and, thus, H  and the dual of its dual isomorphic.

Examples

 > $\mathrm{with}\left(\mathrm{Hypergraphs}\right):$$\mathrm{with}\left(\mathrm{ExampleHypergraphs}\right):$

Consider the Lovasz hypergraph of rank 3.

 > $\mathrm{L3}≔\mathrm{Lovasz}\left(3\right);$$\mathrm{Vertices}\left(\mathrm{L3}\right);$$\mathrm{Hyperedges}\left(\mathrm{L3}\right)$
 ${\mathrm{L3}}{≔}{\mathrm{< a hypergraph on 6 vertices with 10 hyperedges >}}$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}\right]$
 $\left[\left\{{1}{,}{2}{,}{4}\right\}{,}\left\{{1}{,}{3}{,}{4}\right\}{,}\left\{{2}{,}{3}{,}{4}\right\}{,}\left\{{1}{,}{2}{,}{5}\right\}{,}\left\{{1}{,}{3}{,}{5}\right\}{,}\left\{{2}{,}{3}{,}{5}\right\}{,}\left\{{1}{,}{2}{,}{6}\right\}{,}\left\{{1}{,}{3}{,}{6}\right\}{,}\left\{{2}{,}{3}{,}{6}\right\}{,}\left\{{4}{,}{5}{,}{6}\right\}\right]$ (1)

Draw a graphical representation of L3.

 > $\mathrm{Draw}\left(\mathrm{L3}\right)$

Compute the dual hypergraph DL3 of of L3.

 > $\mathrm{DL3}≔\mathrm{DualHypergraph}\left(\mathrm{L3}\right);$$\mathrm{Vertices}\left(\mathrm{DL3}\right);$$\mathrm{Hyperedges}\left(\mathrm{DL3}\right)$
 ${\mathrm{DL3}}{≔}{\mathrm{< a hypergraph on 10 vertices with 6 hyperedges >}}$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}{,}{7}{,}{8}{,}{9}{,}{10}\right]$
 $\left[\left\{{1}{,}{2}{,}{3}{,}{10}\right\}{,}\left\{{4}{,}{5}{,}{6}{,}{10}\right\}{,}\left\{{7}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{4}{,}{5}{,}{7}{,}{8}\right\}{,}\left\{{1}{,}{3}{,}{4}{,}{6}{,}{7}{,}{9}\right\}{,}\left\{{2}{,}{3}{,}{5}{,}{6}{,}{8}{,}{9}\right\}\right]$ (2)

Draw a graphical representation of DF4.

 > $\mathrm{Draw}\left(\mathrm{DL3}\right)$

Check whether L3 and DL3 are isomorphic or not.

 > $\mathrm{AreIsomorphic}\left(\mathrm{L3},\mathrm{DL3}\right)$
 ${\mathrm{false}}$ (3)

Check that L3 and the dual of DL3 are isomorphic.

 > $\mathrm{AreIsomorphic}\left(\mathrm{L3},\mathrm{DualHypergraph}\left(\mathrm{DL3}\right)\right)$
 ${\mathrm{true}}$ (4)

Consider the Fan hypergraph of rank 4.

 > $\mathrm{F4}≔\mathrm{Fan}\left(4\right);$$\mathrm{Vertices}\left(\mathrm{F4}\right);$$\mathrm{Hyperedges}\left(\mathrm{F4}\right)$
 ${\mathrm{F4}}{≔}{\mathrm{< a hypergraph on 5 vertices with 5 hyperedges >}}$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}\right]$
 $\left[\left\{{1}{,}{5}\right\}{,}\left\{{2}{,}{5}\right\}{,}\left\{{3}{,}{5}\right\}{,}\left\{{4}{,}{5}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{4}\right\}\right]$ (5)

Draw a graphical representation of F4.

 > $\mathrm{Draw}\left(\mathrm{F4}\right)$

Compute the dual hypergraph DF4 of of F4.

 > $\mathrm{DF4}≔\mathrm{DualHypergraph}\left(\mathrm{F4}\right);$$\mathrm{Vertices}\left(\mathrm{DF4}\right);$$\mathrm{Hyperedges}\left(\mathrm{DF4}\right)$
 ${\mathrm{DF4}}{≔}{\mathrm{< a hypergraph on 5 vertices with 5 hyperedges >}}$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}\right]$
 $\left[\left\{{1}{,}{5}\right\}{,}\left\{{2}{,}{5}\right\}{,}\left\{{3}{,}{5}\right\}{,}\left\{{4}{,}{5}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{4}\right\}\right]$ (6)

Draw a graphical representation of DF4.

 > $\mathrm{Draw}\left(\mathrm{DF4}\right)$

Check that F4 and DF4 are isomorphic.

 > $\mathrm{AreIsomorphic}\left(\mathrm{F4},\mathrm{DF4}\right)$
 ${\mathrm{true}}$ (7)

References

 Claude Berge. Hypergraphes. Combinatoires des ensembles finis. 1987,  Paris, Gauthier-Villars, translated to English.
 Claude Berge. Hypergraphs. Combinatorics of Finite Sets.  1989, Amsterdam, North-Holland Mathematical Library, Elsevier, translated from French.
 Charles Leiserson, Liyun Li, Marc Moreno Maza and Yuzhen Xie " Parallel computation of the minimal elements of a poset." Proceedings of the 4th International Workshop on Parallel Symbolic Computation (PASCO) 2010: 53-62, ACM.

Compatibility

 • The Hypergraphs[DualHypergraph] command was introduced in Maple 2024.