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 (this is the language used in Tutte's original paper, however in modern usage the flats of a matroid mean something different). 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 (ed.), Combinatorial geometries, Encyclopedia of Mathematics and its Applications, 29, Cambridge University Press, pp. 40–52, doi:10.1017/CBO9781107325715, ISBN 978-0-521-33339-9, MR 0921064
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.