Macaulay2 » Documentation
Packages » Matroids :: hasMinor
next | previous | forward | backward | up | index | toc

hasMinor -- whether a matroid has a given minor



Determines if N is a minor of M, i.e. can be obtained from M by a contraction followed by a deletion. Since deletion and contraction by disjoint subsets commute, every sequence of deletion and contraction operations can be written as a single contraction and a single deletion.

Many families of matroids can be defined by a list of forbidden minors: i.e. a matroid M is in the family iff M does not have any of the forbidden minors as a minor. For instance, a matroid is representable over F_2 iff it does not have U_{2,4} as a minor, i.e. U_{2,4} is the (sole) forbidden minor for binary matroids.

There are 2 strategies for this method: the default (and generally fastest) method is ``Strategy => "flats"'', which can be sped up by precomputing the fVector of M. Otherwise, all independent/coindependent sets of a certain size/rank are iterated over.

i1 : (M4, M5, M6) = (4,5,6)/completeGraph/matroid

o1 = (a "matroid" of rank 3 on 6 elements, a "matroid" of rank 4 on 10
     elements, a "matroid" of rank 5 on 15 elements)

o1 : Sequence
i2 : hasMinor(M4, uniformMatroid(2,4))

o2 = false
i3 : time hasMinor(M6, M5)
 -- used 2.89979s (cpu); 2.0617s (thread); 0s (gc)

o3 = true

See also

Ways to use hasMinor :

For the programmer

The object hasMinor is a method function with options.