Теорема Тутте о гомотопии

В математике теорема о гомотопии Тутте , введенная Тутте ( 1958 ), обобщает понятие «пути» от графов к матроидам и грубо утверждает, что замкнутые пути могут быть записаны как композиции элементарных замкнутых путей, так что в некотором смысле они гомотопен тривиальному замкнутому пути.

Заявление

Матроид M на множестве Q задается классом непустых подмножеств M множества Q , называемых схемами , таких, что ни один элемент не содержит другого, и если X и Y находятся в M , a находится в X и Y , b является в X , но не в Y существует некоторый Z, , то в M b , но не a и содержащийся в X ∪ Y. содержащий

Подмножества Q , являющиеся объединениями схем, называются плоскими (это язык, используемый в оригинальной статье Тутте, однако в современном использовании плоские элементы матроида означают нечто иное). Элементы M называются 0-квартирами, минимальные непустые квартиры, не являющиеся 0-квартирами, называются 1-квартирами, минимальные непустые квартиры, не являющиеся 0-квартирами или 1-квартирами, называются 2-квартирами, и поэтому на.

Путь — это конечная последовательность 0-квартир такая, что любые два последовательных элемента пути лежат в некоторой 1-плоскости.

Элементарный путь — это путь вида ( X , Y , X ) или ( X , Y , Z , X ), где X , Y , Z все лежат в некоторой 2-плоскости.

Два пути P и Q, у которых последняя 0-квартира P совпадает с первой 0-квартирой Q, можно очевидным образом скомпоновать, чтобы получить путь PQ .

Два пути называются гомотопными, если один можно получить из другого операциями добавления или удаления элементарных путей внутри пути, другими словами, замены пути PR на PQR или наоборот, где Q элементарно.

Слабая форма теоремы Тутте о гомотопии утверждает, что любой замкнутый путь гомотопен тривиальному пути. Более сильная форма дает аналогичный результат для путей, не встречающих определенные «выпуклые» подмножества.

Ссылки

Тутт, Уильям Томас (1958), «Гомотопическая теорема для матроидов. I», Труды Американского математического общества , 88 (1): 144–160, doi : 10.2307/1993243 , ISSN 0002-9947 , JSTOR 1993243 , MR 0101526
Тутт, Уильям Томас (1958), «Гомотопическая теорема для матроидов. II», Труды Американского математического общества , 88 (1): 161–174, doi : 10.2307/1993244 , ISSN 0002-9947 , JSTOR 1993244 , MR 0101526
Тутте, В.Т. (1971), Введение в теорию матроидов , Современные аналитические и вычислительные методы в науке и математике, том. 37, Нью-Йорк: Американская издательская компания Elsevier, стр. 72–77, Zbl 0231.05027.
Уайт, Нил (1987), «Унимодулярные матроиды» , в книге Уайта Нила (ред.), Комбинаторные геометрии , Энциклопедия математики и ее приложений, том. 29, Cambridge University Press , стр. 40–52, doi : 10.1017/CBO9781107325715 , ISBN. 978-0-521-33339-9 , МР 0921064