Tutte homotopy theorem


In mathematics, the Tutte homotopy theorem, introduced by, 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, or 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.