In mathematics, the Tutte homotopy theorem, introduced by , generalises the concept of "path" from
graphs
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
* Graph (topology), a topological space resembling a graph in the sense of discr ...
to
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
s, 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
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
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
*
*
*
*{{Citation , last1=White , first1=Neil , editor1-last=White , editor1-first=Neil , title=Combinatorial geometries , url=https://books.google.com/books?id=xKPZlhqMqnQC , publisher=
Cambridge University Press
Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer.
Cambr ...
, series=Encyclopedia of Mathematics and its Applications , isbn=978-0-521-33339-9 , mr=921064 , year=1987 , volume=29 , chapter=Unimodular matroids , chapter-url=https://books.google.com/books?id=xKPZlhqMqnQC&pg=PA40 , pages=40–52 , doi=10.1017/CBO9781107325715
Matroid theory