Lovasz - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.
Our website is currently undergoing maintenance, which may result in occasional errors while browsing. We apologize for any inconvenience this may cause and are working swiftly to restore full functionality. Thank you for your patience.

Online Help

All Products    Maple    MapleSim


Hypergraphs[ExampleHypergraphs]

  

Lovasz

  

Return the Lovasz hypergraph of a given rank

 

Calling Sequence

Parameters

Description

Examples

References

Compatibility

Calling Sequence

Lovasz(r)

Parameters

r

-

posint

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

withHypergraphs:withExampleHypergraphs:

Create the Lovasz hypergraph  of rank 4

HLovasz4

H< a hypergraph on 10 vertices with 41 hyperedges >

(1)

Print its vertices and edges.

VerticesH&semi;HyperedgesH

1&comma;2&comma;3&comma;4&comma;5&comma;6&comma;7&comma;8&comma;9&comma;10

1&comma;2&comma;4&comma;7&comma;1&comma;3&comma;4&comma;7&comma;2&comma;3&comma;4&comma;7&comma;1&comma;2&comma;5&comma;7&comma;1&comma;3&comma;5&comma;7&comma;2&comma;3&comma;5&comma;7&comma;1&comma;2&comma;6&comma;7&comma;1&comma;3&comma;6&comma;7&comma;2&comma;3&comma;6&comma;7&comma;4&comma;5&comma;6&comma;7&comma;1&comma;2&comma;4&comma;8&comma;1&comma;3&comma;4&comma;8&comma;2&comma;3&comma;4&comma;8&comma;1&comma;2&comma;5&comma;8&comma;1&comma;3&comma;5&comma;8&comma;2&comma;3&comma;5&comma;8&comma;1&comma;2&comma;6&comma;8&comma;1&comma;3&comma;6&comma;8&comma;2&comma;3&comma;6&comma;8&comma;4&comma;5&comma;6&comma;8&comma;1&comma;2&comma;4&comma;9&comma;1&comma;3&comma;4&comma;9&comma;2&comma;3&comma;4&comma;9&comma;1&comma;2&comma;5&comma;9&comma;1&comma;3&comma;5&comma;9&comma;2&comma;3&comma;5&comma;9&comma;1&comma;2&comma;6&comma;9&comma;1&comma;3&comma;6&comma;9&comma;2&comma;3&comma;6&comma;9&comma;4&comma;5&comma;6&comma;9&comma;1&comma;2&comma;4&comma;10&comma;1&comma;3&comma;4&comma;10&comma;2&comma;3&comma;4&comma;10&comma;1&comma;2&comma;5&comma;10&comma;1&comma;3&comma;5&comma;10&comma;2&comma;3&comma;5&comma;10&comma;1&comma;2&comma;6&comma;10&comma;1&comma;3&comma;6&comma;10&comma;2&comma;3&comma;6&comma;10&comma;4&comma;5&comma;6&comma;10&comma;7&comma;8&comma;9&comma;10

(2)

Draw a graphical representation of this hypergraph.

DrawH

Draw the line graph of H.

GLineGraphH&semi;GraphTheory:-DrawGraphG

GGraph 1: an undirected graph with 41 vertices, 820 edge(s), and 41 self-loop(s)

Compute the transversal hypergraph T of H.

TTransversalH

T< a hypergraph on 10 vertices with 41 hyperedges >

(3)

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

AreEqualH&comma;T

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.

• 

For more information on Maple 2024 changes, see Updates in Maple 2024.

See Also

Hypergraphs[Transversal]