# hasMinor -- whether a matroid has a given minor

## Synopsis

• Usage:
hasMinor(M, N)
• Inputs:
• M, ,
• N, ,
• Outputs:
• , whether N is a minor of M

## Description

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 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.

If a minor is found that is isomorphic to N, then the sets to be contracted and deleted are printed.

 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 0.850277 seconds o3 = true