getSeparation -- finds a k-separation of a matroid

For a matroid M on a ground set E, and k >= 1, a (2-)partition (X, E - X) of E(M) is called a k-separation of M if |X| >= k, |E - X| >= k, and rank(X) + rank(E - X) - rank(M) <= k-1. The separation is called minimal if either |X| = k or |E - X| = k.

This method computes a k-separation of M, if one exists. If no k-separation of M exists, then null is returned.

Efficiency is achieved by using special structure of k-separations: if (X, E - X) is a minimal k-separation (and no m-separation with m < k exists) with |X| = k, then X is either an independent cocircuit or a coindependent circuit. On the other hand, if (X, E - X) is a nonminimal separation with |E - X| minimal, then X is both a flat and a coflat. In particular, if the ranks of all flats have been previously computed (e.g. via fVector), then this method should finish quickly.

For k = 1, it is generally more efficient to use components and isConnected than this method.

i1 : G = graph({{0,1},{1,2},{2,3},{3,4},{4,5},{5,6},{6,0},{0,2},{0,3},{0,4},{1,3},{3,5},{3,6}})

o1 = Graph{0 => {1, 2, 3, 4, 6}   }
           1 => {0, 2, 3}
           2 => {0, 1, 3}
           3 => {0, 1, 2, 4, 5, 6}
           4 => {0, 3, 5}
           5 => {3, 4, 6}
           6 => {0, 3, 5}

o1 : Graph

i2 : M = matroid G

o2 = a "matroid" of rank 6 on 13 elements

o2 : Matroid

i3 : getSeparation(M, 2)

o3 = set {2, 3, 4, 8, 9, 10, 11, 12}

o3 : Set