Tutte homotopy theorem

In mathematics, the Tutte homotopy theorem, introduced by Tutte (1958), generalises the concept of "path" from graphs to matroids, and states roughly that closed paths can be written as compositions of elementary closed paths, so that in some sense they are homotopic to the trivial closed path.

Statement

A matroid on a set Q is specified by a class of non-empty subsets M of Q, called circuits, such that no element of M contains another, and if X and Y are in M, a is in X and Y, b is in X but not in Y, then there is some Z in M containing b but not a and contained in X∪Y.

The subsets of Q that are unions of circuits are called flats. The elements of M are called 0-flats, the minimal non-empty flats that are not 0-flats are called 1-flats, the minimal nonempty flats that are not 0-flats or 1-flats are called 2-flats, and so on.

A path is a finite sequence of 0-flats such that any two consecutive elements of the path lie in some 1-flat.

An elementary path is one of the form (X,Y,X), or (X,Y,Z,X) with X,Y,Z all lying in some 2-flat.

Two paths P and Q such that the last 0-flat of P is the same as the first 0-flat of Q can be composed in the obvious way to give a path PQ.

Two paths are called homotopic if one can be obtained from the other by the operations of adding or removing elementary paths inside a path, in other words changing a path PR to PQR or vice versa, where Q is elementary.

A weak form of Tutte's homotopy theorem states that any closed path is homotopic to the trivial path. A stronger form states a similar result for paths not meeting certain "convex" subsets.

References

Tutte, William Thomas (1958), "A homotopy theorem for matroids. I", Transactions of the American Mathematical Society, 88: 144–160, doi:10.2307/1993243, ISSN 0002-9947, JSTOR 1993243, MR 0101526
Tutte, William Thomas (1958), "A homotopy theorem for matroids. II", Transactions of the American Mathematical Society, 88: 161–174, doi:10.2307/1993244, ISSN 0002-9947, JSTOR 1993244, MR 0101526
Tutte, W.T. (1971), Introduction to the theory of matroids, Modern Analytic and Computational Methods in Science and Mathematics, 37, New York: American Elsevier Publishing Company, pp. 72–77, Zbl 0231.05027
White, Neil (1987), "Unimodular matroids", in White, Neil, Combinatorial geometries, Encyclopedia of Mathematics and its Applications, 29, Cambridge University Press, pp. 40–52, ISBN 978-0-521-33339-9, MR 921064

This article is issued from Wikipedia - version of the 11/14/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.