Matroid menší - Matroid minor

V matematické teorii matroidy, a Méně důležitý matroidu M je další matroid N který je získán z M sledem restrikčních a kontrakčních operací. Matroidní nezletilí jsou úzce spjati s nezletilí v grafu a operace omezení a kontrakce, kterými jsou vytvořeny, odpovídají operacím odstranění hran a kontrakce okraje v grafech. Teorie nezletilých matroidů vede ke strukturním rozkladům matroidů a charakterizaci rodin matroidů zakázanými nezletilými, analogicky k odpovídající teorii v grafech.

Definice

Li M je matroid na scéně E a S je podmnožinou E, pak omezení M na S, psaný M |S, je matroid na scéně S jejichž nezávislé množiny jsou nezávislé množiny M které jsou obsaženy v S. Jeho obvody jsou obvody M které jsou obsaženy v S a jeho hodnostní funkce je to z M omezeno na podmnožiny S.

Li T je nezávislá podmnožina E, kontrakce M podle T, psaný M/T, je matroid na podkladové sadě E - T jejichž nezávislé množiny jsou množiny, jejichž unie s T je nezávislý v M. Tuto definici lze rozšířit na libovolné T výběrem základny pro T a definování souboru, který bude v kontrakci nezávislý, pokud jeho spojení s tímto základem zůstane nezávislé v M. Hodnostní funkce kontrakce je ${ displaystyle r '(A) = r (A cup T) -r (T).}$

Matroid N je nezletilý matroid M pokud to lze postavit z M restrikčními a kontrakčními operacemi.

Z hlediska geometrická mříž tvořený plochami matroidu, přičemž menší z matroidů odpovídá přijetí intervalu mřížky, části mřížky ležící mezi daným dolním a horním vázaným prvkem.^[1]

Zakázané charakterizace matroidů

Mnoho důležitých rodin matroidů je uzavřeno kvůli operaci přijímání nezletilých: pokud je matroid M patří do rodiny, pak každý nezletilý z M také patří do rodiny. V tomto případě může být rodina charakterizována sadou „zakázaných matroidů“, menších a minimálních matroidů, které do rodiny nepatří. Matroid patří do rodiny právě tehdy, když nemá zakázaného matroida jako nezletilý. Sada zakázaných matroidů je často, ale ne vždy, konečná, paralelně s Věta Robertson – Seymour který uvádí, že množina zakázaných nezletilých z rodiny grafů s menšími uzavřenými je vždy konečná.

Příklad tohoto jevu je uveden v pravidelné matroidy, matroidy, které jsou reprezentovatelné ve všech polích. Ekvivalentně je matroid pravidelný, pokud může být reprezentován a zcela unimodulární matice (matice, jejíž čtvercové dílčí matice mají všechny determinanty rovné 0, 1 nebo −1). Tutte (1958) prokázal, že matroid je pravidelný právě tehdy, pokud nemá jednoho ze tří zakázaných nezletilých: jednotný matroid ${ displaystyle U {} _ {4} ^ {2}}$ (čtyřbodová čára), Fano letadlo, nebo duální matroid letadla Fano. K tomu využil své obtížné homotopická věta. Od té doby byly nalezeny jednodušší důkazy.

The grafické matroidy, matroidy, jejichž nezávislé množiny jsou lesními podgrafy grafu, mají pět zakázaných nezletilých: tři pro běžné matroidy a dva duály grafických matroidů pro grafy K.₅ a K._3,3 že tím Wagnerova věta jsou zakázány nezletilé osoby pro rovinné grafy.

The binární matroidy, matroidy reprezentovatelné nad dvěma prvky konečné pole, zahrnují grafické i běžné matroidy. Tutte opět ukázal, že tyto matroidy mají zakázanou minoritní charakterizaci: jsou to matroidy, které nemají čtyřbodovou linii jako minor. Rota se domnívala že pro každé konečné pole mají matroidy reprezentovatelné nad tímto polem konečně mnoho zakázaných nezletilých.^[2] Úplný důkaz této domněnky oznámili Geelen, Gerards a Whittle;^[3] od roku 2015^{[Aktualizace]} neobjevilo se to. Matroidy, které lze reprezentovat nad reálná čísla mít nekonečně mnoho zakázaných nezletilých.^[4]

Šířka větve

Odvětvové rozklady matroidů lze definovat analogicky k jejich definici pro grafy. Rozklad větví matroidu je a hierarchické shlukování prvků matroidu, představovaných jako nezakořeněný binární strom s prvky matroidu na jeho listech. Odstraněním kteréhokoli okraje tohoto stromu dělí matroidy na dvě nesouvislé podmnožiny; takový oddíl se nazývá e-separace. Li r označuje hodnostní funkci matroidu, pak je šířka e-separace definována jako r(A) + r(B) − r(M) + 1. Šířka rozkladu je maximální šířka kterékoli z jeho e-separací a šířka větve matroidu je minimální šířka kteréhokoli z jeho větvených rozkladů.

Šířka větve grafu a šířka větve odpovídající grafický matroid se mohou lišit: například tři hrany graf cesty a tři hrany hvězda mají různé šířky větví, 2 a 1, ale oba indukují stejný grafický matroid s šířkou větve 1.^[5] U grafů, které nejsou stromy, se však šířka větve grafu rovná šířce větve přidruženého grafického matroidu.^[6] Šířka větve matroidu se vždy rovná šířce větve jeho duální.^[5]

Šířka větve je důležitou součástí pokusů rozšířit teorii nezletilých grafů na matroidy: ačkoli šířka stromu lze také zobecnit na matroidy,^[7] a hraje větší roli než šířka větve v teorii nezletilých grafů, šířka větve má výhodnější vlastnosti v prostředí matroidů.^[8]Pokud menší uzavřená rodina matroidů reprezentovatelná přes konečné pole nezahrnuje grafické matroidy všech rovinných grafů, pak existuje konstanta vázaná na šířku větve matroidů v rodině, která zobecňuje podobné výsledky pro menší uzavřené rodiny grafů.^[9]

Dobře kvazi-objednávání

The Věta Robertson – Seymour znamená, že každá vlastnost matroidu z grafický matroidy charakterizované seznamem zakázaných nezletilých lze charakterizovat konečným seznamem. Další způsob, jak říci totéž, je, že částečná objednávka na grafických matroidech vytvořených vedlejší operací je a dobře kvazi-objednávání. Příklad skutečných reprezentativních matroidů, které mají nekonečně mnoho zakázaných nezletilých, však ukazuje, že menší uspořádání není dobře kvazi-uspořádání na všech matroidech.

Robertson a Seymour se domnívali, že matroidy jsou reprezentovatelné v každém konkrétním případě konečné pole jsou dobře kvazi objednané. Zatím to bylo prokázáno pouze pro matroidy ohraničené šířky větví.^[10]

Matroidní rozklady

The věta o struktuře grafu je důležitým nástrojem v teorii nezletilých grafů, podle kterého lze grafy v jakékoli méně uzavřené rodině sestavit z jednodušších grafů klika-součet operace. Některé analogické výsledky jsou také známy v teorii matroidů. Zejména, Seymourova věta o rozkladu uvádí, že všechny běžné matroidy lze sestavit jednoduchým způsobem jako klikový součet grafických matroidů, jejich dualů a jednoho speciálního matroidu s 10 prvky.^[11] Jako následek, lineární programy definované zcela unimodulárními maticemi lze vyřešit kombinačně kombinací řešení do sady minimální kostra problémy odpovídající grafické a ko-grafické části tohoto rozkladu.

Algoritmy a složitost

Jednou z důležitých složek teorie grafů je existence algoritmu pro testování, zda je graf H je menší než jiný graf G, přičemž trvá čas, který je polynomiální G pro jakoukoli pevnou volbu H (a ještě silněji fixovatelný parametr pokud je velikost H se může měnit). Kombinací tohoto výsledku s Robertsonovou-Seymourovou větou je možné rozpoznat členy jakékoli rodiny méně uzavřených grafů v polynomiální čas. Odpovídajícím způsobem by v teorii matroidů bylo žádoucí vyvinout efektivní algoritmy pro rozpoznávání toho, zda daný fixní matroid je menší než vstupní matroid. Bohužel takový silný výsledek není možný: v matroid věštec model, jediní nezletilí, které lze rozpoznat v polynomiálním čase, jsou jednotné matroidy s hodností nebo corank jeden.^[12] Pokud je však problém omezen na matroidy, které jsou reprezentovatelné nad nějakým pevným konečným polem (a jsou reprezentovány jako matice nad tímto polem), pak, jako v případě grafu, se předpokládá, že je možné rozpoznat matroidy, které obsahují jakékoli pevné menší v polynomiálním čase.^[8]

Poznámky

Reference