Fan - Maple Help

Hypergraphs[ExampleHypergraphs]

 Fan
 Return the Fan hypergraph of a given rank

 Calling Sequence Fan(r)

Parameters

 r -

Description

 • The command Fan(r) returns the Fan hypergraph of rank r.
 • That is, the hypergraph F whose vertex set V consists of the positive integers less or equal to r+1 and whose hyperedges are the set {1,...,r} together with the pairs {i, r+1} for  every positive integer i  less or equal to r.

Remarks

 • The hypergraph Fan(r)  is auto-transversal, that is, Fan(r) and its transversal hypergraph are equal.

Terminology

 • Transversal : If H :=(X, Y) is a hypergraph, then a subset S of X is transversal to H whenever S has a non-empty intersection with every hyperedge of H. If H :=(X, Y) is a hypergraph, then the transversal hypergraph of H is the hypergraph (X, Z) where Z consists of all transversals to H that are minimal w.r.t. inclusion.

Examples

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

Create the Fan hypergraph  of rank 4

 > $H≔\mathrm{Fan}\left(4\right)$
 ${H}{≔}{\mathrm{< a hypergraph on 5 vertices with 5 hyperedges >}}$ (1)

Print its vertices and edges.

 > $\mathrm{Vertices}\left(H\right);$$\mathrm{Hyperedges}\left(H\right)$
 $\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]$ (2)

Draw a graphical representation of this hypergraph.

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

Compute the transversal hypergraph T of H.

 > $T≔\mathrm{Transversal}\left(H\right)$
 ${T}{≔}{\mathrm{< a hypergraph on 5 vertices with 5 hyperedges >}}$ (3)

Check that H is auto-transversal, that is, H and T are equal.

 > $\mathrm{AreEqual}\left(H,T\right)$
 ${\mathrm{true}}$ (4)

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