IsRegular - Maple Help

Hypergraphs

 IsRegular
 Check whether an hypergraph is linear or not

 Calling Sequence IsRegular(H)

Parameters

 H -

Description

 • The command IsRegular(H) checks whether the hypergraph H is regular or not.

Terminology

 • Degree : the degree of a vertex v of a hypergraph  H :=(X, Y)  is the number elements of Y to which v belongs, that is, the number of hyperedges of H to which v belongs.
 • Regular : A hypergraph H is said regular whenever all its vertices have the same degree.

Examples

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

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

Print its vertices and edges.

 > $\mathrm{Hypergraphs}:-\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]$ (2)

Compute the degree profile of H.

 > $\mathrm{DegreeProfile}\left(H\right)$
 $\left[{1}{,}{2}{,}{3}{,}{1}{,}{1}{,}{1}{,}{0}\right]$ (3)

Compute the rank and the anti-rank of H.

 > $\mathrm{Rank}\left(H\right);$$\mathrm{AntiRank}\left(H\right)$
 ${3}$
 ${1}$ (4)

Check whether H is regular.

 > $\mathrm{IsRegular}\left(H\right)$
 ${\mathrm{false}}$ (5)

Check whether H is uniform.

 > $\mathrm{IsUniform}\left(H\right)$
 ${\mathrm{false}}$ (6)

Create another hypergraph.

 > $H≔\mathrm{Lovasz}\left(3\right)$
 ${H}{≔}{\mathrm{< a hypergraph on 6 vertices with 10 hyperedges >}}$ (7)

Print its vertices and edges.

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

Compute the degree profile of H.

 > $\mathrm{DegreeProfile}\left(H\right)$
 $\left[{6}{,}{6}{,}{6}{,}{4}{,}{4}{,}{4}\right]$ (9)

Compute the rank and the anti-rank of H.

 > $\mathrm{Rank}\left(H\right);$$\mathrm{AntiRank}\left(H\right)$
 ${3}$
 ${3}$ (10)

Check whether H is regular.

 > $\mathrm{IsRegular}\left(H\right)$
 ${\mathrm{false}}$ (11)

Check whether H is uniform.

 > $\mathrm{IsUniform}\left(H\right)$
 ${\mathrm{true}}$ (12)

Create another hypergraph.

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

Print its vertices and edges.

 > $\mathrm{Hypergraphs}:-\mathrm{Vertices}\left(H\right);$$\mathrm{Hyperedges}\left(H\right)$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}\right]$
 $\left[\left\{{1}{,}{2}{,}{3}\right\}{,}\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}{,}{4}{,}{5}\right\}{,}\left\{{2}{,}{4}{,}{5}\right\}{,}\left\{{3}{,}{4}{,}{5}\right\}\right]$ (14)

Compute the degree profile of H.

 > $\mathrm{DegreeProfile}\left(H\right)$
 $\left[{6}{,}{6}{,}{6}{,}{6}{,}{6}\right]$ (15)

Compute the rank and the anti-rank of H.

 > $\mathrm{Rank}\left(H\right);$$\mathrm{AntiRank}\left(H\right)$
 ${3}$
 ${3}$ (16)

Check whether H is regular.

 > $\mathrm{IsRegular}\left(H\right)$
 ${\mathrm{true}}$ (17)

Check whether H is uniform.

 > $\mathrm{IsUniform}\left(H\right)$
 ${\mathrm{true}}$ (18)

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