# getSeparation -- finds a k-separation of a matroid

## Synopsis

• Usage:
getSeparation(M, k)
• Inputs:
• Outputs:
• a set, a k-separation of M, if one exists, or null if none exists

## Description

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