Twierdzenie o homotopii Tutte'a

W matematyce twierdzenie o homotopii Tutte , wprowadzone przez Tutte ( 1958 ), uogólnia pojęcie „ścieżki” od grafów do matroidów i stwierdza z grubsza, że ścieżki zamknięte można zapisać jako kompozycje elementarnych ścieżek zamkniętych, tak że w pewnym sensie są one homotopijny względem trywialnej ścieżki zamkniętej.

Oświadczenie

Matroid na zbiorze Q jest określony przez klasę niepustych podzbiorów M z Q , zwanych obwodami , tak że żaden element M nie zawiera innego, a jeśli X i Y są w M , a jest w X i Y , b jest w X , ale nie w Y , to jest trochę Z w M zawierające b , ale nie a i zawarte w X ∪ Y .

Podzbiory Q , które są sumami obwodów, nazywane są mieszkaniami (jest to język używany w oryginalnej pracy Tutte'a, jednak we współczesnym użyciu mieszkania matroidu oznaczają coś innego). Elementy M nazywane są mieszkaniami 0, minimalne niepuste mieszkania, które nie są mieszkaniami 0, nazywane są mieszkaniami 1, minimalne niepuste mieszkania, które nie są mieszkaniami 0 lub 1, nazywane są mieszkaniami 2, i tak NA.

Ścieżka jest skończoną sekwencją 0-mieszkań, tak że dowolne dwa kolejne elementy ścieżki leżą w jakiejś 1-płaskiej .

Ścieżka elementarna to jedna z postaci ( X , Y , X ) lub ( X , Y , Z , X ) z X , Y , Z wszystkie leżą w jakiejś 2-płaskiej.

Dwie ścieżki P i Q takie, że ostatnia 0-płaska z P jest taka sama jak pierwsza 0-płaska z Q , można złożyć w oczywisty sposób, dając ścieżkę PQ .

Dwie ścieżki nazywane są homotopijnymi, jeśli jedną można uzyskać z drugiej przez operacje dodawania lub usuwania elementarnych ścieżek wewnątrz ścieżki, innymi słowy zmieniając ścieżkę PR na PQR lub odwrotnie, gdzie Q jest elementarne.

Słaba postać twierdzenia Tutte'a o homotopii mówi, że każda zamknięta ścieżka jest homotopijna względem ścieżki trywialnej. Silniejsza forma podaje podobny wynik dla ścieżek, które nie spełniają pewnych „wypukłych” podzbiorów.

Tutte , William Thomas ( 1958 ) _ _ _ _ _ _ _ _ _ _ _
Tutte, William Thomas (1958), „Twierdzenie o homotopii dla matroidów. II”, Transactions of the American Mathematical Society , 88 (1): 161–174, doi : 10.2307/1993244 , ISSN 0002-9947 , JSTOR 1993244 , MR 0101526
Tutte, WT (1971), Wprowadzenie do teorii matroidów , Nowoczesne metody analityczne i obliczeniowe w nauce i matematyce, tom. 37, Nowy Jork: American Elsevier Publishing Company, s. 72–77, Zbl 0231.05027
White, Neil (1987), „Unimodular matroids” , w White, Neil (red.), Kombinatoryczne geometrie , Encyklopedia matematyki i jej zastosowań, tom. 29, Cambridge University Press , s. 40–52, doi : 10.1017/CBO9781107325715 , ISBN 978-0-521-33339-9 , MR 0921064