matroid theory In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...

, 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 Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual number, a ...

. Matroid girth generalizes the notion of the shortest cycle in a graph, the edge connectivity of a graph, Hall sets in

bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...

s, even sets in families of sets, and general position of point sets. It is hard to compute, but

fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...

for linear matroids when parameterized both by the

matroid rank In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset ''S'' of elements of the matroid is, similarly, the maximum size of an independent subset of ''S'', and ...

and the field size of a linear representation.

Examples

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 In the mathematical theory of Matroid theory, matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the tree (graph theory), forests in a given finite undirected graph. The dual matr ...

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 In graph theory, a minimum cut or min-cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets) that is minimal in some metric. Variations of the minimum cut problem consider weighted graphs, directed graphs, ter ...

of the graph. The girth of a

transversal matroid In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent ...

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 Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...

gives rise to a real

linear matroid In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of repre ...

by interpreting the

Cartesian coordinate In geometry, a Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of real numbers called ''coordinates'', which are the signed distances to the point from two fixed perpendicular o ...

s of the points as the vectors of a

matroid representation In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of repre ...

. The girth of the resulting matroid equals one plus the dimension of the space when the underlying set of point is in

general position In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that a ...

, and is smaller otherwise. Girths of real linear matroids also arise in

compressed sensing Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring and reconstructing a Signal (electronics), signal by finding solutions to Underdetermined s ...

, where the same concept is referred to as the spark of a matrix. The girth of a

binary matroid In matroid theory, a binary matroid is a matroid that can be represented over the finite field GF(2).. That is, up to isomorphism, they are the matroids whose elements are the columns of a (0,1)-matrix and whose sets of elements are independent if ...

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.

Computational complexity

Determining the girth of a

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

. Additionally, determining the girth of a linear matroid given by a matrix representing the matroid is W hard when parameterized by the girth or by the rank of the matroid, but fixed-parameter tractable when parameterized by a combination of the rank and the size of the underlying

field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...

. For an arbitrary matroid, given by an independence oracle, it is impossible to find the girth using a subexponential number of matroid queries. Similarly, for a real linear matroid of rank , with elements, described by an oracle that gives the

orientation Orientation may refer to: Positioning in physical space * Map orientation, the relationship between directions on a map and compass directions * Orientation (housing), the position of a building with respect to the sun, a concept in building des ...

of any -tuple of elements, it requires

\Omega(n^)

oracle queries to determine the girth. Computations using a girth oracle (an oracle that reports the smallest dependent subset of a given set of elements) have also been considered..

References

{{reflist

Girth Girth may refer to: Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...