Max - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Hypergraphs

 Max
 Return the hyperedges that are maximal w.r.t. inclusion

 Calling Sequence Max(H)

Parameters

 H -

Description

 • The command Max(H) returns the hypergraph L whose vertex set is the vertex set of H and whose hyperedges are the hyperedges of H which are maximal w.r.t. inclusion.
 • Therefore, the hypergraph L  is the partial hypergraph of H whose hyperedges are not comparable w.r.t. inclusion and such that every hyperedge of H is contained in one hyperedge of L.
 • Hence, the hyperedges of L are the maximla elements of the partially ordered set (poset) whose vertices are the hyperedges of H and whose ordering is the set-theoretic inclusion.

Terminology

 • Max : If H :=(X, Y) is a hypergraph, then Max(H) is the hypergraph (X, Z) where Z consists of all hyperedges of H which are maximal w.r.t. inclusion.

Examples

 > $\mathrm{with}\left(\mathrm{Hypergraphs}\right):$$\mathrm{with}\left(\mathrm{ExampleHypergraphs}\right)$
 $\left[{\mathrm{Fan}}{,}{\mathrm{Kuratowski}}{,}{\mathrm{Lovasz}}{,}{\mathrm{NonEmptyPowerSet}}{,}{\mathrm{RandomHypergraph}}\right]$ (1)

Create a hypergraph from its vertices and edges.

 > $H≔\mathrm{Hypergraph}\left(\left[1,2,3,4,5,6,7\right],\left[\left\{1,2,3\right\},\left\{2,3\right\},\left\{4\right\},\left\{3,5,6\right\}\right]\right)$
 ${H}{≔}{\mathrm{< a hypergraph on 7 vertices with 4 hyperedges >}}$ (2)

Print the vertices and edges of H.

 > $\mathrm{Vertices}\left(H\right);$$\mathrm{Hyperedges}\left(H\right)$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}{,}{7}\right]$
 $\left[\left\{{4}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{1}{,}{2}{,}{3}\right\}{,}\left\{{3}{,}{5}{,}{6}\right\}\right]$ (3)

Draw a graphical representation of this hypergraph.

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

Compute Max(H), print its vertices and edges, draw a graphical representation of it.

 > $M≔\mathrm{Max}\left(H\right);$$\mathrm{Vertices}\left(M\right);$$\mathrm{Hyperedges}\left(M\right);$$\mathrm{Draw}\left(M\right)$
 ${M}{≔}{\mathrm{< a hypergraph on 7 vertices with 3 hyperedges >}}$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}{,}{7}\right]$
 $\left[\left\{{4}\right\}{,}\left\{{1}{,}{2}{,}{3}\right\}{,}\left\{{3}{,}{5}{,}{6}\right\}\right]$

Compute Min(H), print its vertices and edges, draw a graphical representation of  it.

 > $M≔\mathrm{Min}\left(H\right);$$\mathrm{Vertices}\left(M\right);$$\mathrm{Hyperedges}\left(M\right);$$\mathrm{Draw}\left(M\right)$
 ${M}{≔}{\mathrm{< a hypergraph on 7 vertices with 3 hyperedges >}}$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}{,}{7}\right]$
 $\left[\left\{{4}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{3}{,}{5}{,}{6}\right\}\right]$

Compute the transversal hypergraph of H.

 > $T≔\mathrm{Transversal}\left(H\right);$$\mathrm{Vertices}\left(T\right);$$\mathrm{Hyperedges}\left(T\right);$$\mathrm{Draw}\left(T\right)$
 ${T}{≔}{\mathrm{< a hypergraph on 7 vertices with 3 hyperedges >}}$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}{,}{7}\right]$
 $\left[\left\{{3}{,}{4}\right\}{,}\left\{{2}{,}{4}{,}{5}\right\}{,}\left\{{2}{,}{4}{,}{6}\right\}\right]$

Observe that Transversal(T) and Min(H) are equal.

 > $\mathrm{TT}≔\mathrm{Transversal}\left(T\right);$$\mathrm{Hyperedges}\left(\mathrm{TT}\right);$$\mathrm{AreEqual}\left(\mathrm{TT},\mathrm{Min}\left(H\right)\right)$
 ${\mathrm{TT}}{≔}{\mathrm{< a hypergraph on 7 vertices with 3 hyperedges >}}$
 $\left[\left\{{4}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{3}{,}{5}{,}{6}\right\}\right]$
 ${\mathrm{true}}$ (4)

Consider the following Kuratowski hypergraph.

 > $\mathrm{K3}≔\mathrm{Kuratowski}\left(\left\{1,2,3,4,5\right\},3\right)$
 ${\mathrm{K3}}{≔}{\mathrm{< a hypergraph on 5 vertices with 10 hyperedges >}}$ (5)

Observe that K3 is its own transversal.

 > $\mathrm{AreEqual}\left(\mathrm{Transversal}\left(\mathrm{K3}\right),\mathrm{K3}\right)$
 ${\mathrm{true}}$ (6)

Consider a random hypergraph on 5 points and 15 hyperedges.

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

Compute its minimal hyperedges.

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

Compute the transversal hypergraph  T of  R and the transversal hypergraph TT of  .T

 > $T≔\mathrm{Transversal}\left(R\right);$$\mathrm{Hyperedges}\left(T\right)$
 ${T}{≔}{\mathrm{< a hypergraph on 5 vertices with 3 hyperedges >}}$
 $\left[\left\{{1}{,}{2}{,}{5}\right\}{,}\left\{{2}{,}{4}{,}{5}\right\}{,}\left\{{1}{,}{3}{,}{4}{,}{5}\right\}\right]$ (9)
 > $\mathrm{TT}≔\mathrm{Transversal}\left(T\right);$$\mathrm{Hyperedges}\left(\mathrm{TT}\right)$
 ${\mathrm{TT}}{≔}{\mathrm{< a hypergraph on 5 vertices with 5 hyperedges >}}$
 $\left[\left\{{5}\right\}{,}\left\{{1}{,}{2}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{1}{,}{4}\right\}{,}\left\{{2}{,}{4}\right\}\right]$ (10)

Observe that TT and M are equal.

 > $\mathrm{AreEqual}\left(\mathrm{TT},M\right)$
 ${\mathrm{true}}$ (11)

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[Max] command was introduced in Maple 2024.
 • For more information on Maple 2024 changes, see Updates in Maple 2024.