|
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]]);
|
| (2) |
| (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 dependent, and
|
–
|
bases for the column space of A.
|
| (4) |
| (5) |
| (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) |
| (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).
|
•
|
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.
|
>
|
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.
|
| (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.
|
| (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);
|
>
|
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.
|
| (23) |
•
|
Additionally, one may perform several operations on matroids:
|
•
|
AreIsomorphic: determine if two matroids are the same, under some relabeling of the ground set;
|
•
|
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.
|
•
|
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);
|
>
|
IsMinorOf(ContractionMatroid,GraphicMatroid);
|
| (27) |
>
|
Matroids:-TuttePolynomial(GraphicMatroid,x,y);
|
>
|
Matroids:-CharacteristicPolynomial(GraphicMatroid,k);
|
|
|
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.
|
| (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.
|
>
|
H2 := AddHyperedges(AddVertices(H,["apple"]),[{1,4},{2,"apple",3,4},{3}]);
|
| (32) |
>
|
[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) |
•
|
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.
|
| (36) |
| (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));
|
>
|
[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) |
>
|
NumberOfHyperedges(Lovasz(5));
|
|
|
|