Matroid girth

In matroid theory, a mathematical discipline, the girth of a matroid is the size of its smallest circuit or dependent set. The cogirth of a matroid is the girth of its dual matroid. Matroid girth generalizes the notion of the shortest cycle in a graph, the edge connectivity of a graph, Hall sets in bipartite graphs, even sets in families of sets, and general position of point sets. It is hard to compute, but fixed-parameter tractable for linear matroids when parameterized both by the matroid rank and the field size of a linear representation. The "girth" terminology generalizes the use of girth in graph theory, meaning the length of the shortest cycle in a graph: the girth of a graphic matroid is the same as the girth of its underlying graph. The girth of other classes of matroids also corresponds to important combinatorial problems. For instance, the girth of a co-graphic matroid (or the cogirth of a graphic matroid) equals the edge connectivity of the underlying graph, the number of edges in a minimum cut of the graph. The girth of a transversal matroid gives the cardinality of a minimum Hall set in a bipartite graph: this is a set of vertices on one side of the bipartition that does not form the set of endpoints of a matching in the graph. Any set of points in Euclidean space gives rise to a real linear matroid by interpreting the Cartesian coordinates of the points as the vectors of a matroid representation. The girth of the resulting matroid equals one plus the dimension of the space when the underlying set of point is in general position, and is smaller otherwise. Girths of real linear matroids also arise in compressed sensing, where the same concept is referred to as the spark of a matrix. The girth of a binary matroid gives the cardinality of a minimum even set, a subcollection of a family of sets that includes an even number of copies of each set element. Determining the girth of a binary matroid is NP-hard.