
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]]);

${A}{\u2254}\left[\begin{array}{cccc}{1}& {\mathrm{1}}& {0}& {1}\\ {1}& {1}& {1}& {0}\\ {1}& {1}& {0}& {1}\end{array}\right]$
 (1) 
$\left[{\mathrm{AreIsomorphic}}{\,}{\mathrm{Bases}}{\,}{\mathrm{CharacteristicPolynomial}}{\,}{\mathrm{Circuits}}{\,}{\mathrm{Contraction}}{\,}{\mathrm{Deletion}}{\,}{\mathrm{DependentSets}}{\,}{\mathrm{Dual}}{\,}{\mathrm{ExampleMatroids}}{\,}{\mathrm{Flats}}{\,}{\mathrm{GroundSet}}{\,}{\mathrm{Hyperplanes}}{\,}{\mathrm{IndependentSets}}{\,}{\mathrm{IsMinorOf}}{\,}{\mathrm{Matroid}}{\,}{\mathrm{Rank}}{\,}{\mathrm{SetDisplayStyle}}{\,}{\mathrm{TuttePolynomial}}\right]$
 (2) 
${M}{\u2254}\u27e8\begin{array}{c}{\mathrm{th\ⅇ\; lin\ⅇar\; matroi\ⅆ\; whos\ⅇ\; groun\ⅆ\; s\ⅇt\; is\; th\ⅇ\; s\ⅇt\; of\; column\; v\ⅇctors\; of\; th\ⅇ\; matrix:}}\\ \left[\begin{array}{cccc}{1}& {\mathrm{1}}& {0}& {1}\\ {1}& {1}& {1}& {0}\\ {1}& {1}& {0}& {1}\end{array}\right]\end{array}\u27e9$
 (3) 
•

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

•

We can ask for which subsets of columns are:

–

linearly dependent, and

–

bases for the column space of A.

$\left[{\varnothing}{\,}\left\{{1}\right\}{\,}\left\{{2}\right\}{\,}\left\{{3}\right\}{\,}\left\{{4}\right\}{\,}\left\{{1}{\,}{2}\right\}{\,}\left\{{1}{\,}{3}\right\}{\,}\left\{{2}{\,}{3}\right\}{\,}\left\{{1}{\,}{4}\right\}{\,}\left\{{2}{\,}{4}\right\}{\,}\left\{{3}{\,}{4}\right\}{\,}\left\{{1}{\,}{2}{\,}{3}\right\}{\,}\left\{{1}{\,}{2}{\,}{4}\right\}{\,}\left\{{2}{\,}{3}{\,}{4}\right\}\right]$
 (4) 
$\left[\left\{{1}{\,}{3}{\,}{4}\right\}{\,}\left\{{1}{\,}{2}{\,}{3}{\,}{4}\right\}\right]$
 (5) 
$\left[\left\{{1}{\,}{2}{\,}{3}\right\}{\,}\left\{{1}{\,}{2}{\,}{4}\right\}{\,}\left\{{2}{\,}{3}{\,}{4}\right\}\right]$
 (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);

${\mathrm{Mmodular}}{\u2254}\u27e8\begin{array}{c}{\mathrm{th\ⅇ\; lin\ⅇar\; matroi\ⅆ\; whos\ⅇ\; groun\ⅆ\; s\ⅇt\; is\; th\ⅇ\; s\ⅇt\; of\; column\; v\ⅇctors\; of\; th\ⅇ\; matrix:}}\\ \left[\begin{array}{cccc}{1}& {1}& {0}& {1}\\ {1}& {1}& {1}& {0}\\ {1}& {1}& {0}& {1}\end{array}\right]\phantom{\rule[0.0ex]{0.3em}{0.0ex}}{\mathbf{mod}}\phantom{\rule[0.0ex]{0.3em}{0.0ex}}{2}\end{array}\u27e9$
 (7) 
$\left[\left\{{1}{\,}{3}\right\}{\,}\left\{{2}{\,}{3}\right\}{\,}\left\{{1}{\,}{4}\right\}{\,}\left\{{2}{\,}{4}\right\}{\,}\left\{{3}{\,}{4}\right\}\right]$
 (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}});

${G}{\u2254}{\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 4\; vertices\; and\; 4\; edge(s)}}$
 (11) 
>

GraphicMatroid := Matroid(G);

${\mathrm{GraphicMatroid}}{\u2254}\u27e8\begin{array}{c}{\mathrm{th\ⅇ\; graphic\; matroi\ⅆ\; on\; th\ⅇ\; graph:}}\\ {\mathrm{PLOT}}{}\left({\mathrm{...}}\right)\end{array}\u27e9$
 (12) 
>

Circuits(GraphicMatroid);

$\left[\left\{{''a\_b''}{\,}{''a\_d''}{\,}{''b\_d''}\right\}\right]$
 (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.

$\left[\left\{{''a\_b''}{\,}{''a\_c''}{\,}{''a\_d''}\right\}{\,}\left\{{''a\_b''}{\,}{''a\_c''}{\,}{''b\_d''}\right\}{\,}\left\{{''a\_c''}{\,}{''a\_d''}{\,}{''b\_d''}\right\}\right]$
 (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.

$\left[\left\{{1}{\,}{3}{\,}{4}\right\}\right]$
 (16) 
$\left[\left\{{1}{\,}{2}\right\}{\,}\left\{{1}{\,}{3}{\,}{4}\right\}{\,}\left\{{2}{\,}{3}{\,}{4}\right\}\right]$
 (17) 
•

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

•

A matroid is a pair $M\=\left(E\,I\right)$, where

–

$E$ is a finite set called the ground set and

–

$\mathrm{I}$ is a collection of subsets of $E$ 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 $\mathrm{I1}$ and $\mathrm{I2}$ are independent sets and $\mathrm{I1}$ has more elements than $\mathrm{I2}$, then there exists an element of $\mathrm{I2}$ which when included in $\mathrm{I1}$ 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}]);

${\mathrm{AxiomaticMatroid}}{\u2254}\u27e8{\mathrm{a\; matroi\ⅆ\; on\; 3\; \ⅇl\ⅇm\ⅇnts\; with\; 5\; in\ⅆ\ⅇp\ⅇn\ⅆ\ⅇnt\; s\ⅇts}}\u27e9$
 (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);

$\left[\left\{{1}{\,}{2}\right\}\right]$
 (19) 
>

Bases(AxiomaticMatroid);

$\left[\left\{{1}{\,}{3}\right\}{\,}\left\{{2}{\,}{3}\right\}\right]$
 (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>);

${\mathrm{AlgebraicMatroid}}{\u2254}\u27e8\begin{array}{c}{\mathrm{th\ⅇ\; alg\ⅇbraic\; matroi\ⅆ\; on\; th\ⅇ\; polynomial\; i\ⅆ\ⅇal:}}\\ \u27e8{{z}}^{{2}}{+}{y}{\,}{{z}}^{{2}}{+}{x}{+}{y}\u27e9\end{array}\u27e9$
 (21) 
>

DependentSets(AlgebraicMatroid);

$\left[\left\{{1}\right\}{\,}\left\{{1}{\,}{2}\right\}{\,}\left\{{1}{\,}{3}\right\}{\,}\left\{{2}{\,}{3}\right\}{\,}\left\{{1}{\,}{2}{\,}{3}\right\}\right]$
 (22) 
•

That $\left\{1\right\}$ is a dependent set indicates that there exists a polynomial in the ideal which involves only the first variable, $x$.

•

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

$\left[{\mathrm{Fano}}{\,}{\mathrm{Hesse}}{\,}{\mathrm{MacLane}}{\,}{\mathrm{NCubeMatroid}}{\,}{\mathrm{NonFano}}{\,}{\mathrm{NonPappus}}{\,}{\mathrm{Pappus}}{\,}{\mathrm{TicTacToe}}{\,}{\mathrm{UniformMatroid}}{\,}{\mathrm{Vamos}}\right]$
 (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});

${\mathrm{ContractionMatroid}}{\u2254}\u27e8{\mathrm{a\; matroi\ⅆ\; on\; 4\; \ⅇl\ⅇm\ⅇnts\; with\; 1\; circuit}}\u27e9$
 (24) 
>

AreIsomorphic(ContractionMatroid,AxiomaticMatroid);

>

IsMinorOf(ContractionMatroid,GraphicMatroid);

${\mathrm{true}}{,}{\varnothing}{,}{\varnothing}$
 (26) 
$\u27e8{\mathrm{a\; matroi\ⅆ\; on\; 4\; \ⅇl\ⅇm\ⅇnts\; with\; 3\; bas\ⅇs\; of\; siz\ⅇ\; 1}}\u27e9$
 (27) 
>

Matroids:TuttePolynomial(GraphicMatroid,x,y);

${{x}}^{{3}}{+}{{x}}^{{2}}{+}{x}{}{y}$
 (28) 
>

Matroids:CharacteristicPolynomial(GraphicMatroid,k);

${{k}}^{{3}}{}{4}{}{{k}}^{{2}}{+}{5}{}{k}{}{2}$
 (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 $\left(V\,E\right)$ consisting of a finite set $V$ called vertices and a collection $E$ of subsets of $V$ 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 selfloops are allowed).

•

We create a hypergraph with the Hypergraph command.

$\left[{\mathrm{AddHyperedges}}{\,}{\mathrm{AddVertices}}{\,}{\mathrm{AntiRank}}{\,}{\mathrm{AreEqual}}{\,}{\mathrm{AreIsomorphic}}{\,}{\mathrm{ComplementHypergraph}}{\,}{\mathrm{DegreeProfile}}{\,}{\mathrm{Draw}}{\,}{\mathrm{DualHypergraph}}{\,}{\mathrm{ExampleHypergraphs}}{\,}{\mathrm{Hyperedges}}{\,}{\mathrm{Hypergraph}}{\,}{\mathrm{IsConnected}}{\,}{\mathrm{IsEdge}}{\,}{\mathrm{IsLinear}}{\,}{\mathrm{IsRegular}}{\,}{\mathrm{IsUniform}}{\,}{\mathrm{LineGraph}}{\,}{\mathrm{Max}}{\,}{\mathrm{Min}}{\,}{\mathrm{NumberOfHyperedges}}{\,}{\mathrm{NumberOfVertices}}{\,}{\mathrm{PartialHypergraph}}{\,}{\mathrm{Rank}}{\,}{\mathrm{SubHypergraph}}{\,}{\mathrm{Transversal}}{\,}{\mathrm{VertexEdgeIncidenceGraph}}{\,}{\mathrm{Vertices}}\right]$
 (30) 
>

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

${H}{\u2254}{\mathrm{<\; a\; hypergraph\; on\; 4\; vertices\; with\; 3\; hyperedges\; >}}$
 (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}]);

${\mathrm{H2}}{\u2254}{\mathrm{<\; a\; hypergraph\; on\; 5\; vertices\; with\; 6\; hyperedges\; >}}$
 (32) 
>

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

$\left[{\mathrm{false}}{\,}{\mathrm{true}}{\,}{6}{\,}{5}{\,}{\mathrm{true}}{\,}\left[{2}{\,}{2}{\,}{2}{\,}{1}\right]\right]$
 (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 bitvectors to make hefty calculations fast and feasible.

>

with(ExampleHypergraphs);

$\left[{\mathrm{Fan}}{\,}{\mathrm{Kuratowski}}{\,}{\mathrm{Lovasz}}{\,}{\mathrm{NonEmptyPowerSet}}{\,}{\mathrm{RandomHypergraph}}\right]$
 (34) 
•

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

>

R := RandomHypergraph(10,100);

${R}{\u2254}{\mathrm{<\; a\; hypergraph\; on\; 10\; vertices\; with\; 100\; hyperedges\; >}}$
 (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.

$\left[\left\{{6}{\,}{7}{\,}{9}\right\}{\,}\left\{{2}{\,}{3}{\,}{10}\right\}{\,}\left\{{7}{\,}{9}{\,}{10}\right\}{\,}\left\{{1}{\,}{2}{\,}{4}{\,}{5}\right\}{\,}\left\{{1}{\,}{4}{\,}{5}{\,}{7}\right\}{\,}\left\{{1}{\,}{4}{\,}{6}{\,}{7}\right\}{\,}\left\{{1}{\,}{3}{\,}{4}{\,}{8}\right\}{\,}\left\{{1}{\,}{3}{\,}{7}{\,}{8}\right\}{\,}\left\{{2}{\,}{3}{\,}{7}{\,}{8}\right\}{\,}\left\{{1}{\,}{3}{\,}{4}{\,}{9}\right\}{\,}\left\{{2}{\,}{4}{\,}{5}{\,}{9}\right\}{\,}\left\{{2}{\,}{3}{\,}{6}{\,}{9}\right\}{\,}\left\{{1}{\,}{3}{\,}{8}{\,}{9}\right\}{\,}\left\{{3}{\,}{5}{\,}{8}{\,}{9}\right\}{\,}\left\{{1}{\,}{2}{\,}{4}{\,}{10}\right\}{\,}\left\{{1}{\,}{4}{\,}{5}{\,}{10}\right\}{\,}\left\{{2}{\,}{4}{\,}{5}{\,}{10}\right\}{\,}\left\{{1}{\,}{3}{\,}{6}{\,}{10}\right\}{\,}\left\{{2}{\,}{5}{\,}{6}{\,}{10}\right\}{\,}\left\{{1}{\,}{3}{\,}{7}{\,}{10}\right\}{\,}\left\{{2}{\,}{4}{\,}{7}{\,}{10}\right\}{\,}\left\{{1}{\,}{2}{\,}{8}{\,}{10}\right\}{\,}\left\{{1}{\,}{3}{\,}{8}{\,}{10}\right\}{\,}\left\{{3}{\,}{4}{\,}{8}{\,}{10}\right\}{\,}\left\{{4}{\,}{6}{\,}{8}{\,}{10}\right\}{\,}\left\{{6}{\,}{7}{\,}{8}{\,}{10}\right\}{\,}\left\{{1}{\,}{4}{\,}{9}{\,}{10}\right\}{\,}\left\{{1}{\,}{2}{\,}{3}{\,}{5}{\,}{7}\right\}{\,}\left\{{1}{\,}{3}{\,}{5}{\,}{6}{\,}{7}\right\}{\,}\left\{{2}{\,}{3}{\,}{5}{\,}{6}{\,}{7}\right\}{\,}\left\{{3}{\,}{4}{\,}{5}{\,}{6}{\,}{7}\right\}{\,}\left\{{1}{\,}{2}{\,}{3}{\,}{5}{\,}{8}\right\}{\,}\left\{{2}{\,}{4}{\,}{6}{\,}{7}{\,}{8}\right\}{\,}\left\{{1}{\,}{5}{\,}{6}{\,}{7}{\,}{8}\right\}{\,}\left\{{3}{\,}{4}{\,}{5}{\,}{6}{\,}{9}\right\}{\,}\left\{{2}{\,}{3}{\,}{5}{\,}{7}{\,}{9}\right\}{\,}\left\{{3}{\,}{4}{\,}{7}{\,}{8}{\,}{9}\right\}{\,}\left\{{1}{\,}{5}{\,}{6}{\,}{8}{\,}{10}\right\}{\,}\left\{{1}{\,}{5}{\,}{6}{\,}{9}{\,}{10}\right\}\right]$
 (36) 
 (37) 
>

Hyperedges(Transversal(R));

 (38) 
•

Put another way, consider the hypergraph $\mathrm{Food}$ whose vertices are ingredients in your kitchen, and whose hyperedges are recipes.

•

Then $\mathrm{Min}\left(\mathrm{Food}\right)$ are those recipes which require a minimal set of ingredients (i.e. removing any ingredient prevents any recipe from being made).

•

$\mathrm{Max}\left(\mathrm{Food}\right)$ are those recipes which maximally use ingredients (i.e. you cannot include an additional ingredient to make a bigger recipe).

•

$\mathrm{Transversal}\left(\mathrm{Food}\right)$ 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 $M$ are just $\mathrm{Min}\left(\mathrm{DependentSets}\left(M\right)\right)$.

•

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

>

DrawGraph(Hypergraphs:LineGraph(H));

$\left[{3}{\,}{2}\right]$
 (39) 
>

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

$\left[{\mathrm{true}}{\,}{\mathrm{false}}{\,}{\mathrm{false}}\right]$
 (40) 
>

with(ExampleHypergraphs);

$\left[{\mathrm{Fan}}{\,}{\mathrm{Kuratowski}}{\,}{\mathrm{Lovasz}}{\,}{\mathrm{NonEmptyPowerSet}}{\,}{\mathrm{RandomHypergraph}}\right]$
 (41) 
>

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

$\left[{\mathrm{PLOT}}{}\left({\mathrm{...}}\right){\,}{\mathrm{PLOT}}{}\left({\mathrm{...}}\right)\right]$
 (42) 
>

NumberOfHyperedges(Lovasz(5));



