• Source: 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.




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




Computational complexity


Determining the girth of a binary matroid is NP-hard.
Additionally, determining the girth of a linear matroid given by a matrix representing the matroid is W[1]-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.
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 r, with n elements, described by an oracle that gives the orientation of any r-tuple of elements, it requires



Ω
(

n

r
−
1


)


{\displaystyle \Omega (n^{r-1})}

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

Kata Kunci Pencarian:

• Matroid girth
• Girth (graph theory)
• Girth
• Matroid
• Dual graph
• K-edge-connected graph
• Matroid oracle
• Diamond graph
• Fano plane
• Wheel graph