Matroids and Hypergraphs - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

Home : Support : Online Help : What's New and Release Notes : Matroids and Hypergraphs

The Matroids and Hypergraphs Packages in Maple 2024

• 

Maple 2024 adds a new package for dealing with Matroids and a new package for dealing with Hypergraphs.

 

Matroids

Hypergraphs

Matroids

• 

A matroid is an abstract mathematical object which encodes the notion of independence. It has relevant applications in graph theory, linear algebra, geometry, topology, network theory, and more. Matroid theory is a thriving area of research.

• 

The simplest way to construct a matroid is via a matrix. Matroids constructed this way are called linear or representable.

A := Matrix([[1,-1,0,1],[1,1,1,0],[1,1,0,1]]);

(1)

with(Matroids);

(2)

M := Matroid(A);

(3)
• 

This matroid encodes the linear dependencies among the columns of . The so-called ground set of the matroid consists of the numbers 1 through 4, interpreted as column indices into .

• 

We can ask for which subsets of columns are:

– 

linearly independent,

– 

linearly dependent, and

– 

bases for the column space of A.

IndependentSets(M);

(4)

DependentSets(M);

(5)

Bases(M);

(6)
• 

These answers change if the column vectors are considered over a finite field, e.g. the field with two elements:

Mmodular := Matroid(A,2);

(7)

Bases(Mmodular);

(8)
• 

Notice that the size of a basis changed from 3 to 2. This number is the rank of the matroid, which agrees with the familiar notion of rank (of the column space).

Rank(M);

(9)

Rank(Mmodular);

(10)
• 

Matroids are much more general than this! As an abstraction of independence, matroids also encode graph independence.

• 

Given a graph G, a subset of its edges are called dependent if they contain a path which forms a closed loop, known as a circuit.

with(GraphTheory):

G := Graph({{a,b},{a,c},{b,d},{a,d}});

(11)

GraphicMatroid := Matroid(G);

(12)

Circuits(GraphicMatroid);

(13)
• 

Inspired by linear algebra, one may take the definition of a basis as a maximal independent set. The bases of a graphic matroid are its spanning forests.

Bases(GraphicMatroid);

(14)
• 

In fact, every concept about linear independence coming from linear algebra (rank, bases, etc) can be axiomatized and interpreted for a graphic matroid.

• 

Conversely, the concept of a circuit from graph theory applies to linear matroids.

Rank(GraphicMatroid);

(15)

Circuits(M);

(16)

Circuits(Mmodular);

(17)
• 

This is the power of the abstraction of matroids. One rigorous definition of a matroid is as follows.

• 

A matroid is a pair , where

– 

 is a finite set called the ground set and

– 

 is a collection of subsets of  called independent sets which satisfy the axioms:

• 

(Axiom 1) The empty set is an independent set.

• 

(Axiom 2) Every subset of an independent set is independent.

• 

(Axiom 3) If  and  are independent sets and  has more elements than , then there exists an element of  which when included in  results in an independent set.

• 

The matroid package includes functionality for constructing a matroid directly from its independent sets:

AxiomaticMatroid := Matroid([1,2,3], independentsets = [{},{1},{2},{3},{1,3},{2,3}]);

(18)
• 

In fact, for each of the matroid properties of independent sets, bases, dependent sets, and circuits we have seen, one may construct a matroid (provided they satisfy certain axioms, listed on the Matroid help page).

• 

Each property uniquely determines the rest, and the matroids package supports several other axiomatic constructions (via flats, hyperplanes, or a rank function).

• 

Algorithms which convert between these representations are called cryptomorphisms. The matroids package showcases fast implementations of these algorithms.

Circuits(AxiomaticMatroid);

(19)

Bases(AxiomaticMatroid);

(20)
• 

Beyond linear matroids constructed from a matrix, graphic matroids constructed from a graph, and general matroids constructed via axioms, the matroid package also features the construction of algebraic matroids, created from polynomial ideals.

with(PolynomialIdeals):

AlgebraicMatroid := Matroid(<x+y+z^2,z^2+y>);

(21)

DependentSets(AlgebraicMatroid);

(22)
• 

That  is a dependent set indicates that there exists a polynomial in the ideal which involves only the first variable, .

• 

The matroids package features a gallery of well-known matroids, which can be made available by loading the ExampleMatroids subpackage.

with(ExampleMatroids);

(23)
• 

Additionally, one may perform several operations on matroids:

• 

AreIsomorphic: determine if two matroids are the same, under some relabeling of the ground set;

• 

Deletion and Contraction: generalizations of deletion and contraction of edges of a graph;

• 

Dual: a generalization of the dual of a planar graph. Unlike for graphs, duals of matroids always exist. For linear matroids, duality corresponds to orthogonal complements of the row space.

• 

TuttePolynomial and CharacteristicPolynomial: polynomial invariants of matroids which generalize those of a graph;

• 

IsMinorOf: a test to check if one matroid can be obtained by another via a sequence of deletions and contractions.

ContractionMatroid := Contraction(GraphicMatroid,{4});

(24)

AreIsomorphic(ContractionMatroid,AxiomaticMatroid);

(25)

IsMinorOf(ContractionMatroid,GraphicMatroid);

(26)

Dual(M);

(27)

Matroids:-TuttePolynomial(GraphicMatroid,x,y);

(28)

Matroids:-CharacteristicPolynomial(GraphicMatroid,k);

(29)

Hypergraphs

• 

The Hypergraphs package is the computational backbone of the matroids package, and it is much more than that!

• 

A hypergraph is a pair  consisting of a finite set  called vertices and a collection  of subsets of  called hyperedges.

• 

Hypergraphs, as indicated by the name, generalize graphs: a graph can be thought of as a hypergraph where every hyperedge has size two (or size one if self-loops are allowed).

• 

We create a hypergraph with the Hypergraph command.

with(Hypergraphs);

(30)

H := Hypergraph([1,2,3,4],[{1,2},{1,3},{2,3,4}]);

(31)
• 

For few vertices and hyperedges, one can visualize a hypergraph as an augmented graph.

• 

Distinguished nodes of the graph correspond to vertices of the hypergraph. Pairs of nodes are connected, as usual, if they form a (hyper)edge.

• 

Additional, auxiliary nodes are included for every hyperedge of size greater than two and auxiliary edges connect such nodes with the vertices they include.

Draw(H);

• 

Procedures for manipulating hypergraphs include AddHyperedges and AddVertices.

• 

Given a hypergraph, the functions ComplementHypergraph, DualHypergraph, and SubHypergraph create new hypergraphs in the ways the names suggest.

• 

Basic functionality such as Hyperedges, NumberOfHyperedges, Vertices, and NumberOfVertices are available, as are simple queries including AreEqual, IsConnected, and IsEdge.

• 

The functions DegreeProfile and VertexEdgeIncidenceGraph directly generalize those notions from graphs to hypergraphs.

H2 := AddHyperedges(AddVertices(H,["apple"]),[{1,4},{2,"apple",3,4},{3}]);

(32)

Draw(H2);

[AreEqual(H,H2), IsEdge(H2,{2,1}), NumberOfHyperedges(H2), Hypergraphs:-NumberOfVertices(H2), Hypergraphs:-IsConnected(H2), DegreeProfile(H)];

(33)
• 

The major advancement in Maple with the hypergraphs package has to do with what goes on behind the scenes.

• 

Subsets are carefully encoded using bit-vectors to make hefty calculations fast and feasible.

with(ExampleHypergraphs);

(34)
• 

Below, we illustrate the core hypergraph algorithms on a random hypergraph on 10 vertices with 100 hyperedges.

R := RandomHypergraph(10,100);

(35)

Draw(R);

• 

The Min function computes the hyperedges which do not properly contain another hyperedge.

• 

The Max function computes those which are not properly contained in another hyperedge.

• 

The Transversal function computes the sets of vertices for which every hyperedge contains some element in that set.

Hyperedges(Min(R));

(36)

Hyperedges(Max(R));

(37)

Hyperedges(Transversal(R));

(38)
• 

Put another way, consider the hypergraph  whose vertices are ingredients in your kitchen, and whose hyperedges are recipes.

• 

Then  are those recipes which require a minimal set of ingredients (i.e. removing any ingredient prevents any recipe from being made).

• 

 are those recipes which maximally use ingredients (i.e. you cannot include an additional ingredient to make a bigger recipe).

• 

 are all sets of ingredients an adversary could steal from your fridge which would prevent you from making any recipe.

• 

In the context of matroids, the sets of subsets that can be used to define a matroid axiomatically are all hypergraphs, and they are stored as such if they are known for a given matroid. Several cryptomorphisms come directly from these hypergraph operations. For example, the Circuits of a matroid  are just .

• 

Below, we illustrate the remaining functionality and invite you to check out the details on our help pages!

DrawGraph(Hypergraphs:-LineGraph(H));

[Rank(H),AntiRank(H)];

(39)

[IsLinear(H),IsRegular(H),IsUniform(H)];

(40)

with(ExampleHypergraphs);

(41)

[Draw(Kuratowski({1,2,3,4,5},2)),Draw(Kuratowski({1,2,3,4},3))];

(42)

Draw(Lovasz(5));

NumberOfHyperedges(Lovasz(5));

(43)

See Also

GraphTheory

Hypergraphs

Matroids

 


Download Help Document