Matroid regulat - Regular matroid

În matematică, un matroid obișnuit este un matroid care poate fi reprezentat pe toate câmpurile .

Definiție

Un matroid este definit ca fiind o familie de subseturi ale unui set finit, satisfăcând anumite axiome. Seturile din familie se numesc „seturi independente”. Una dintre modalitățile de construire a unui matroid este de a selecta un set finit de vectori într-un spațiu vectorial și de a defini un subset de vectori care să fie independent în matroid atunci când acesta este liniar independent în spațiul vectorial. Fiecare familie de seturi construite în acest mod este un matroid, dar nu fiecare matroid poate fi construit în acest fel, iar spațiile vectoriale pe diferite câmpuri conduc la diferite seturi de matroide care pot fi construite din ele.

Un matroid este regulat atunci când, pentru fiecare câmp , poate fi reprezentat de un sistem de vectori peste . ${\ displaystyle M}$${\ displaystyle F}$${\ displaystyle M}$${\ displaystyle F}$

Proprietăți

Dacă un matroid este obișnuit, la fel este și matroidul său dual , la fel și fiecare dintre minorii săi . Fiecare sumă directă de matroide obișnuite rămâne regulată.

Fiecare matroid grafic (și fiecare matroid co-grafic) este obișnuit. În schimb, fiecare matroid obișnuit poate fi construit combinând matroide grafice, matroide co-grafice și un anumit matroid cu zece elemente care nu este nici grafic, nici co-grafic, utilizând o operație pentru combinarea matroidelor care generalizează operația sumă-clic pe grafice.

Numărul de baze dintr-un matroid regulat poate fi calculat ca determinant al unei matrice asociate, generalizând teorema arborelui matricial al lui Kirchhoff pentru matroizele grafice .

Caracterizări

Matroide uniform (linia patru puncte) nu este regulat: nu poate fi realizată prin două elemente câmp finit GF (2) , deci nu este un matroid binar , deși poate fi realizat peste toate celelalte domenii. Matroidul planului Fano (un matroid de gradul trei în care sunt dependente șapte din triplele de puncte) și dualul său nu sunt, de asemenea, regulate: pot fi realizate peste GF (2) și peste toate câmpurile caracteristice două, dar nu peste alte domenii decât cele. După cum a arătat Tutte (1958) , aceste trei exemple sunt fundamentale pentru teoria matroidelor regulate: fiecare matroid neregulat are cel puțin unul dintre aceste trei ca minor . Astfel, matroizele obișnuite sunt exact matroizele care nu au unul dintre cei trei minori interziși , planul Fano sau dualul său. ${\ displaystyle U {} _ {4} ^ {2}}$ ${\ displaystyle U {} _ {4} ^ {2}}$

Dacă un matroid este regulat, acesta trebuie să poată fi realizat în mod clar în cele două câmpuri GF (2) și GF (3). Inversul este adevărat: fiecare matroid care poate fi realizat în aceste două câmpuri este regulat. Rezultatul rezultă dintr-o caracterizare interzisă minoră a matroizelor realizabile pe aceste câmpuri, parte a unei familii de rezultate codificate de conjectura lui Rota .

Matroizele obișnuite sunt matroizele care pot fi definite dintr-o matrice total unimodulară , o matrice în care fiecare submatrică pătrată are determinantul 0, 1 sau -1. Vectorii care realizează matroidul pot fi luați ca rândurile matricei. Din acest motiv, matroidele obișnuite sunt uneori numite și matroide unimodulare . Echivalența matroidelor regulate și a matricilor unimodulare și caracterizarea lor de către minori interzise sunt rezultate profunde ale WT Tutte , inițial dovedite de el folosind teorema homotopie Tutte . Gerards (1989) a publicat ulterior o dovadă alternativă și mai simplă a caracterizării matricilor unimodulare de către minori interzise.

Algoritmi

Există un algoritm polinomial de timp pentru a testa dacă un matroid este regulat, având acces la matroid printr-un oracol de independență .

Referințe