matroid theory In combinatorics, a branch of mathematics, 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 ...

, 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 In matroid theory, the dual of a matroid M is another matroid M^\ast that has the same elements as M, and in which a set is independent if and only if M has a basis set disjoint from it... Matroid duals go back to the original paper by Hassler ...

. 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 mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

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

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

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

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 branch of mathematics, 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 ...

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, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...

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 A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured in ...

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

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

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

, where the same concept is referred to as the

spark Spark commonly refers to: * Spark (fire), a small glowing particle or ember * Electric spark, a form of electrical discharge Spark may also refer to: Places * Spark Point, a rocky point in the South Shetland Islands People * Spark (surname) * ...

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

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, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

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

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