Kuratowski - Maple Help

Hypergraphs[ExampleHypergraphs]

 Kuratowski
 Return a random hypergraph of given order and size

 Calling Sequence Kuratowski(S,r)

Parameters

 S - r -

Description

 • The command Kuratowski(S,r) returns the Kuratowski hypergraph on S, that is, the hypergraph K whose vertex set is S whose hyperedges are the subsets of S with exactly r elements.

Assumptions

 • The integer r must be  less or equal to n, where n is the cardinality of S. Otherwise, an error is raised.

Examples

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

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 >}}$ (1)

Draw a graphical representation of this hypergraph.

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

Observe that K3 is its own transversal.

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

Consider these two Kuratowski hypergraphs.

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

Draw a graphical representation of K2.

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

Draw a graphical representation of K4.

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

Observe that K2 is the transversal hypergraph of K4.

 > $T≔\mathrm{Transversal}\left(\mathrm{K2}\right);$$\mathrm{AreEqual}\left(T,\mathrm{K4}\right)$
 ${T}{≔}{\mathrm{< a hypergraph on 5 vertices with 5 hyperedges >}}$
 ${\mathrm{true}}$ (4)

Observe that K4 is the transversal hypergraph of K2.

 > $T≔\mathrm{Transversal}\left(\mathrm{K2}\right);$$\mathrm{AreEqual}\left(T,\mathrm{K4}\right)$
 ${T}{≔}{\mathrm{< a hypergraph on 5 vertices with 5 hyperedges >}}$
 ${\mathrm{true}}$ (5)

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[ExampleHypergraphs][Kuratowski] command was introduced in Maple 2024.