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 the rank function of the matroid maps sets of elements to their ranks.

The rank function is one of the fundamental concepts of matroid theory via which matroids may be axiomatized. The rank functions of matroids form an important subclass of the submodular set functions, and the rank functions of the matroids defined from certain other types of mathematical object such as undirected graphs, matrices, and field extensions are important within the study of those objects.

Properties and axiomatization

The rank function of a matroid obeys the following properties.

These properties may be used as axioms to characterize the rank function of matroids: every integer-valued submodular function on the subsets of a finite set that obeys the inequalities r(A)\le r(A\cup\{x\})\le r(A)+1 for all A and x is the rank function of a matroid.[1][2]

Other matroid properties from rank

The rank function may be used to determine the other important properties of a matroid:

Ranks of special matroids

In graph theory, the circuit rank (or cyclomatic number) of a graph is the corank of the associated graphic matroid; it measures the minimum number of edges that must be removed from the graph to make the remaining edges form a forest.[5] Several authors have studied the parameterized complexity of graph algorithms parameterized by this number.[6][7]

In linear algebra, the rank of a linear matroid defined by linear independence from the columns of a matrix is the rank of the matrix,[8] and it is also the dimension of the vector space spanned by the columns.

In abstract algebra, the rank of a matroid defined from sets of elements in a field extension L/K by algebraic independence is known as the transcendence degree.[9]

See also

References

  1. Shikare, M. M.; Waphare, B. N. (2004), Combinatorial Optimization, Alpha Science Int'l Ltd., p. 155, ISBN 9788173195600.
  2. Welsh, D. J. A. (2010), Matroid Theory, Courier Dover Publications, p. 8, ISBN 9780486474397.
  3. 1 2 3 Oxley (2006), p. 25.
  4. Oxley (2006), p. 34.
  5. Berge, Claude (2001), "Cyclomatic number", The Theory of Graphs, Courier Dover Publications, pp. 27–30, ISBN 9780486419756.
  6. Coppersmith, Don; Vishkin, Uzi (1985), "Solving NP-hard problems in 'almost trees': Vertex cover", Discrete Applied Mathematics 10 (1): 27–45, doi:10.1016/0166-218X(85)90057-5, Zbl 0573.68017.
  7. Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan (2001), "Fixed-parameter complexity of λ-labelings", Discrete Applied Mathematics 113 (1): 59–72, doi:10.1016/S0166-218X(00)00387-5, Zbl 0982.05085.
  8. Oxley, James G. (2006), Matroid Theory, Oxford Graduate Texts in Mathematics 3, Oxford University Press, p. 81, ISBN 9780199202508.
  9. Lindström, B. (1988), "Matroids, algebraic and non-algebraic", Algebraic, extremal and metric combinatorics, 1986 (Montreal, PQ, 1986), London Math. Soc. Lecture Note Ser. 131, Cambridge: Cambridge Univ. Press, pp. 166–174, MR 1052666.
This article is issued from Wikipedia - version of the Monday, August 10, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.