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

Matroids

 IsMinorOf
 determine if a given matroid is a minor of another

 Calling Sequence IsMinorOf(M1,M2) IsMinorOf(M1,M2,mo,oo)

Parameters

 M1 - M2 - mo - (optional) equation of the form $\mathrm{maxiterations}=m$, where $m$ is a positive integer or the symbol $\mathrm{\infty }$ oo - (optional) equation of the form $\mathrm{output}=o$

Description

 • A matroid $\mathrm{M1}$ is a minor of another matroid $\mathrm{M2}$ if $\mathrm{M1}$ can be obtained from $\mathrm{M2}$ via a sequence of deletion and contraction operations. This procedure determines if $\mathrm{M1}$ is a minor of $\mathrm{M2}$.
 • In some cases, this question can be decided quickly, e.g., if $\mathrm{M1}$ has more entries in its ground set than $\mathrm{M2}$, the answer is no. Otherwise, this command enters into a loop that can take quite a long time to run. By default, Maple will issue an error message if it computes that the loop may take more than ${2}^{20}$ iterations. To use a different limit for the current call, you can supply the option $\mathrm{maxiterations}=m$, where $m$ is either a positive integer or the symbol $\mathrm{\infty }$.
 • By default, if $\mathrm{M1}$ is not a minor of $\mathrm{M2}$, this command returns the value $\mathrm{false}$. If $\mathrm{M1}$ is indeed a minor of $\mathrm{M2}$, it returns a sequence of three values: the constant $\mathrm{true}$ and two subsets $C$ and $\mathrm{D}$ of the ground set of $\mathrm{M2}$ such that $\mathrm{M1}$ is isomorphic to $\left(\mathrm{M2}\setminus \mathrm{D}\right)/C$. The output can be modified using an option of the form $\mathrm{output}=o$.
 – If you pass the option $\mathrm{output}=\mathrm{boolean}$, the command returns just $\mathrm{true}$ or $\mathrm{false}$.
 – If you pass the option $\mathrm{output}=\mathrm{contractions}$, the command returns just $C$ if $\mathrm{M1}$ is a minor of $\mathrm{M2}$, and the symbol $\mathrm{FAIL}$ otherwise.
 – If you pass the option $\mathrm{output}=\mathrm{deletions}$, the command returns just $\mathrm{D}$ if $\mathrm{M1}$ is a minor of $\mathrm{M2}$, and the symbol $\mathrm{FAIL}$ otherwise.
 – If you pass the option $\mathrm{output}=l$, where $l$ is a list consisting of any of the values $\mathrm{boolean}$, $\mathrm{contractions}$, and $\mathrm{deletions}$, the command returns an expression sequence of the corresponding outputs in the given order.
 – If you pass the option $\mathrm{output}=\mathrm{default}$, the command behaves as if the option had not been passed.

Examples

 > $\mathrm{with}\left(\mathrm{Matroids}\right):$
 > $\mathrm{with}\left(\mathrm{ExampleMatroids}\right):$

Let us verify that the uniform matroid of rank 1 on 2 elements is a minor of the Fano matroid.

 > $\mathrm{M1}≔\mathrm{UniformMatroid}\left(1,2\right)$
 ${\mathrm{M1}}{≔}⟨{thⅇ uniform matroiⅆ of rank 1 on 2 ⅇlⅇmⅇnts}⟩$ (1)
 > $\mathrm{M2}≔\mathrm{Fano}\left(\right)$
 ${\mathrm{M2}}{≔}⟨{a matroiⅆ on 7 ⅇlⅇmⅇnts with 14 circuits}⟩$ (2)
 > $\mathrm{IsMinorOf}\left(\mathrm{M1},\mathrm{M2}\right)$
 ${\mathrm{true}}{,}\left\{{4}\right\}{,}\left\{{3}{,}{5}{,}{6}{,}{7}\right\}$ (3)

We can verify the answer as follows.

 > $\mathrm{M3}≔\mathrm{Contraction}\left(\mathrm{Deletion}\left(\mathrm{M2},\left\{3,5,6,7\right\}\right),\left\{4\right\}\right)$
 ${\mathrm{M3}}{≔}⟨{thⅇ uniform matroiⅆ of rank 1 on 2 ⅇlⅇmⅇnts}⟩$ (4)
 > $\mathrm{AreIsomorphic}\left(\mathrm{M1},\mathrm{M3}\right)$
 ${\mathrm{true}}$ (5)

References

 James G. Oxley. Matroid Theory (Oxford Graduate Texts in Mathematics). New York: Oxford University Press. 2006.