Lovasz - Maple Help

Hypergraphs[ExampleHypergraphs]

 Lovasz
 Return the Lovasz hypergraph of a given rank

 Calling Sequence Lovasz(r)

Parameters

 r -

Description

 • The command Lovasz(r) returns the Lovasz hypergraph of rank r.
 • A formal definition  can be found on P. 58 in the English version (available online) of the book of Claude Berge  referenced below.

Remarks

 • The hypergraph Lovasz(r)  is auto-transversal, that is, Lovasz(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 Lovasz hypergraph  of rank 4

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

Print its vertices and edges.

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

Draw a graphical representation of this hypergraph.

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

Draw the line graph of H.

 > $G≔\mathrm{LineGraph}\left(H\right);$$\mathrm{GraphTheory}:-\mathrm{DrawGraph}\left(G\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected graph with 41 vertices, 820 edge\left(s\right), and 41 self-loop\left(s\right)}}$

Compute the transversal hypergraph T of H.

 > $T≔\mathrm{Transversal}\left(H\right)$
 ${T}{≔}{\mathrm{< a hypergraph on 10 vertices with 41 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][Lovasz] command was introduced in Maple 2024.