Matroids and Hypergraphs - Maple 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

 • 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}{≔}\left[\begin{array}{cccc}{1}& {-1}& {0}& {1}\\ {1}& {1}& {1}& {0}\\ {1}& {1}& {0}& {1}\end{array}\right]$ (1)
 > with(Matroids);
 $\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 := Matroid(A);
 ${M}{≔}⟨\begin{array}{c}{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]\end{array}⟩$ (3)
 • This matroid encodes the linear dependencies among the columns of $A$. The so-called 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 independent,
 – linearly dependent, and
 – bases for the column space of A.
 > IndependentSets(M);
 $\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)
 > DependentSets(M);
 $\left[\left\{{1}{,}{3}{,}{4}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{4}\right\}\right]$ (5)
 > Bases(M);
 $\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}}{≔}⟨\begin{array}{c}{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}⟩$ (7)
 > Bases(Mmodular);
 $\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).
 > Rank(M);
 ${3}$ (9)
 > Rank(Mmodular);
 ${2}$ (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}});
 ${G}{≔}{\mathrm{Graph 1: an undirected graph with 4 vertices and 4 edge\left(s\right)}}$ (11)
 > GraphicMatroid := Matroid(G);
 ${\mathrm{GraphicMatroid}}{≔}⟨\begin{array}{c}{thⅇ graphic matroiⅆ on thⅇ graph:}\\ {\mathrm{PLOT}}{}\left({\mathrm{...}}\right)\end{array}⟩$ (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.
 > Bases(GraphicMatroid);
 $\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.
 > Rank(GraphicMatroid);
 ${3}$ (15)
 > Circuits(M);
 $\left[\left\{{1}{,}{3}{,}{4}\right\}\right]$ (16)
 > Circuits(Mmodular);
 $\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
 – $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}}{≔}⟨{a matroiⅆ on 3 ⅇlⅇmⅇnts with 5 inⅆⅇpⅇnⅆⅇnt sⅇts}⟩$ (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();
 ${\mathrm{AlgebraicMatroid}}{≔}⟨\begin{array}{c}{thⅇ algⅇbraic matroiⅆ on thⅇ polynomial iⅆⅇal:}\\ ⟨{{z}}^{{2}}{+}{y}{,}{{z}}^{{2}}{+}{x}{+}{y}⟩\end{array}⟩$ (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 well-known matroids, which can be made available by loading the ExampleMatroids subpackage.
 > with(ExampleMatroids);
 $\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;
 • 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});
 ${\mathrm{ContractionMatroid}}{≔}⟨{a matroiⅆ on 4 ⅇlⅇmⅇnts with 1 circuit}⟩$ (24)
 > AreIsomorphic(ContractionMatroid,AxiomaticMatroid);
 ${\mathrm{false}}$ (25)
 > IsMinorOf(ContractionMatroid,GraphicMatroid);
 ${\mathrm{true}}{,}{\varnothing }{,}{\varnothing }$ (26)
 > Dual(M);
 $⟨{a matroiⅆ on 4 ⅇlⅇmⅇnts with 3 basⅇs of sizⅇ 1}⟩$ (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 self-loops are allowed).
 • We create a hypergraph with the Hypergraph command.
 > with(Hypergraphs);
 $\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}{≔}{\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.
 > Draw(H);
 • 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.
 ${\mathrm{H2}}{≔}{\mathrm{< a hypergraph on 5 vertices with 6 hyperedges >}}$ (32)
 > Draw(H2);
 > [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 bit-vectors 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}{≔}{\mathrm{< a hypergraph on 10 vertices with 100 hyperedges >}}$ (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));
 $\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)
 > Hyperedges(Max(R));
 $\left[\left\{{2}{,}{4}{,}{5}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{4}{,}{5}{,}{6}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{5}{,}{7}\right\}{,}\left\{{2}{,}{4}{,}{5}{,}{7}{,}{9}\right\}{,}\left\{{1}{,}{2}{,}{6}{,}{7}{,}{9}\right\}{,}\left\{{1}{,}{2}{,}{4}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{5}{,}{6}{,}{7}{,}{8}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{9}\right\}{,}\left\{{2}{,}{3}{,}{5}{,}{6}{,}{7}{,}{9}\right\}{,}\left\{{2}{,}{3}{,}{4}{,}{5}{,}{8}{,}{9}\right\}{,}\left\{{1}{,}{3}{,}{4}{,}{5}{,}{6}{,}{10}\right\}{,}\left\{{2}{,}{3}{,}{4}{,}{6}{,}{7}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{5}{,}{6}{,}{7}{,}{10}\right\}{,}\left\{{1}{,}{4}{,}{5}{,}{6}{,}{7}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{4}{,}{6}{,}{8}{,}{10}\right\}{,}\left\{{2}{,}{3}{,}{4}{,}{7}{,}{8}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{5}{,}{7}{,}{8}{,}{10}\right\}{,}\left\{{3}{,}{4}{,}{5}{,}{7}{,}{8}{,}{10}\right\}{,}\left\{{2}{,}{4}{,}{6}{,}{7}{,}{8}{,}{10}\right\}{,}\left\{{1}{,}{3}{,}{5}{,}{6}{,}{9}{,}{10}\right\}{,}\left\{{2}{,}{3}{,}{6}{,}{7}{,}{9}{,}{10}\right\}{,}\left\{{2}{,}{3}{,}{6}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{5}{,}{6}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{4}{,}{6}{,}{8}{,}{9}\right\}{,}\left\{{1}{,}{3}{,}{5}{,}{6}{,}{7}{,}{8}{,}{9}\right\}{,}\left\{{3}{,}{4}{,}{5}{,}{6}{,}{7}{,}{8}{,}{9}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{5}{,}{6}{,}{8}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{6}{,}{7}{,}{8}{,}{10}\right\}{,}\left\{{1}{,}{3}{,}{4}{,}{5}{,}{7}{,}{9}{,}{10}\right\}{,}\left\{{3}{,}{4}{,}{5}{,}{6}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{4}{,}{5}{,}{7}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{2}{,}{5}{,}{6}{,}{7}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{3}{,}{4}{,}{6}{,}{7}{,}{8}{,}{9}{,}{10}\right\}\right]$ (37)
 > Hyperedges(Transversal(R));
 $\left[\left\{{3}{,}{4}{,}{6}{,}{10}\right\}{,}\left\{{3}{,}{5}{,}{6}{,}{10}\right\}{,}\left\{{2}{,}{3}{,}{7}{,}{10}\right\}{,}\left\{{3}{,}{4}{,}{7}{,}{10}\right\}{,}\left\{{3}{,}{5}{,}{7}{,}{10}\right\}{,}\left\{{1}{,}{7}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{4}{,}{7}\right\}{,}\left\{{1}{,}{2}{,}{4}{,}{5}{,}{7}\right\}{,}\left\{{1}{,}{3}{,}{4}{,}{5}{,}{7}\right\}{,}\left\{{2}{,}{3}{,}{4}{,}{5}{,}{7}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{6}{,}{7}\right\}{,}\left\{{1}{,}{3}{,}{4}{,}{6}{,}{7}\right\}{,}\left\{{2}{,}{3}{,}{4}{,}{6}{,}{7}\right\}{,}\left\{{1}{,}{3}{,}{5}{,}{6}{,}{7}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{7}{,}{8}\right\}{,}\left\{{1}{,}{2}{,}{4}{,}{7}{,}{8}\right\}{,}\left\{{1}{,}{2}{,}{5}{,}{7}{,}{8}\right\}{,}\left\{{1}{,}{3}{,}{5}{,}{7}{,}{8}\right\}{,}\left\{{3}{,}{4}{,}{5}{,}{7}{,}{8}\right\}{,}\left\{{1}{,}{2}{,}{6}{,}{7}{,}{8}\right\}{,}\left\{{2}{,}{4}{,}{6}{,}{7}{,}{8}\right\}{,}\left\{{3}{,}{4}{,}{6}{,}{7}{,}{8}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{6}{,}{9}\right\}{,}\left\{{1}{,}{2}{,}{4}{,}{6}{,}{9}\right\}{,}\left\{{1}{,}{3}{,}{4}{,}{6}{,}{9}\right\}{,}\left\{{2}{,}{3}{,}{4}{,}{6}{,}{9}\right\}{,}\left\{{2}{,}{3}{,}{5}{,}{6}{,}{9}\right\}{,}\left\{{1}{,}{2}{,}{4}{,}{7}{,}{9}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{8}{,}{9}\right\}{,}\left\{{1}{,}{2}{,}{4}{,}{8}{,}{9}\right\}{,}\left\{{2}{,}{3}{,}{4}{,}{8}{,}{9}\right\}{,}\left\{{1}{,}{2}{,}{5}{,}{8}{,}{9}\right\}{,}\left\{{3}{,}{4}{,}{5}{,}{8}{,}{9}\right\}{,}\left\{{1}{,}{2}{,}{6}{,}{8}{,}{9}\right\}{,}\left\{{3}{,}{4}{,}{6}{,}{8}{,}{9}\right\}{,}\left\{{1}{,}{2}{,}{7}{,}{8}{,}{9}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{6}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{5}{,}{7}{,}{10}\right\}{,}\left\{{1}{,}{5}{,}{6}{,}{7}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{6}{,}{8}{,}{10}\right\}{,}\left\{{2}{,}{4}{,}{6}{,}{8}{,}{10}\right\}{,}\left\{{1}{,}{5}{,}{6}{,}{8}{,}{10}\right\}{,}\left\{{4}{,}{5}{,}{6}{,}{8}{,}{10}\right\}{,}\left\{{2}{,}{4}{,}{7}{,}{8}{,}{10}\right\}{,}\left\{{4}{,}{6}{,}{7}{,}{8}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{4}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{3}{,}{4}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{5}{,}{9}{,}{10}\right\}{,}\left\{{3}{,}{4}{,}{5}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{2}{,}{6}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{3}{,}{6}{,}{9}{,}{10}\right\}{,}\left\{{2}{,}{4}{,}{7}{,}{9}{,}{10}\right\}{,}\left\{{4}{,}{5}{,}{7}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{3}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{3}{,}{4}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{5}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{4}{,}{5}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{1}{,}{6}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{5}{,}{6}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{2}{,}{7}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{4}{,}{7}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{5}{,}{7}{,}{8}{,}{9}{,}{10}\right\}{,}\left\{{2}{,}{3}{,}{5}{,}{7}{,}{8}{,}{9}\right\}{,}\left\{{2}{,}{5}{,}{6}{,}{7}{,}{8}{,}{9}\right\}{,}\left\{{1}{,}{2}{,}{4}{,}{5}{,}{6}{,}{10}\right\}\right]$ (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));
 > [Rank(H),AntiRank(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)
 > Draw(Lovasz(5));
 > NumberOfHyperedges(Lovasz(5));
 ${206}$ (43)