Matroid

Inom kombinatorik , en gren av matematiken , / är ˈm eɪ t r ɔɪ d / en matroid en struktur som abstraherar och generaliserar begreppet linjärt oberoende i vektorrum . Det finns många likvärdiga sätt att definiera en matroid axiomatiskt , det viktigaste är i termer av: oberoende uppsättningar; baser eller kretsar; rangordna funktioner; stängningsoperatörer; och slutna uppsättningar eller lägenheter. På språket för delvis ordnade uppsättningar är en finit enkel matroid ekvivalent med ett geometriskt gitter .

Matroidteorin lånar i stor utsträckning från terminologin för både linjär algebra och grafteorin , till stor del för att det är abstraktionen av olika föreställningar av central betydelse inom dessa områden. Matroider har funnit tillämpningar inom geometri , topologi , kombinatorisk optimering , nätverksteori och kodningsteori .

Definition

Det finns många likvärdiga ( kryptomorfa ) sätt att definiera en (ändlig) matroid.

Oberoende set

När det gäller oberoende är en finit matroid $M$ ett par ${\displaystyle (E,{\mathcal {I}})} ,$ där $E$ är en finit mängd ( kallas jordmängden ) och ${\mathcal {I}}$ är en familj av delmängder av $E$ (kallas de oberoende uppsättningarna ) med följande egenskaper:

(I1) Den tomma mängden är oberoende, dvs $\emptyset \in {\mathcal {I}}$ .
(I2) Varje delmängd av en oberoende mängd är oberoende, dvs. för varje $A'\subseteq A\subseteq E$ , om $A\in {\mathcal {I }}$ sedan $A'\in {\mathcal {I}}$ . Detta kallas ibland den ärftliga egenskapen eller den nedåtstängda egenskapen.
(I3) Om $A$ och $B$ är två oberoende uppsättningar (dvs varje uppsättning är oberoende) och $A$ har fler element än $B$ , så finns det $x\in A\backslash B$ så att $B\cup \{x\}$ är i ${\mathcal {I}}$ . Detta kallas ibland förökningsegenskapen eller den oberoende uppsättningsutbytesegenskapen .

De två första egenskaperna definierar en kombinatorisk struktur som kallas ett oberoende system (eller abstrakt förenklat komplex ). Egentligen, om man antar (I2), är egenskapen (I1) ekvivalent med det faktum att minst en delmängd av $E$ är oberoende, dvs. ${\mathcal {I}}\neq \emptyset$ .

Baser och kretsar

En delmängd av jordmängden $E$ som inte är oberoende kallas beroende . En maximal oberoende mängd – det vill säga en oberoende mängd som blir beroende av att lägga till något element av $E$ – kallas en bas för matroiden. En krets i en matroid $M$ är en minimalt beroende delmängd av $E$ — det vill säga en beroende uppsättning vars korrekta delmängder alla är oberoende. Terminologin uppstår eftersom kretsarna i grafiska matroider är cykler i motsvarande grafer.

De beroende mängderna, baserna eller kretsarna i en matroid karaktäriserar matroiden helt: en mängd är oberoende om och endast om den inte är beroende, om och bara om den är en delmängd av en bas, och om och bara om den gör det inte innehålla en krets. Samlingarna av beroende uppsättningar, baser och kretsar har var och en enkla egenskaper som kan tas som axiom för en matroid. Till exempel kan man definiera en matroid $M$ som ett par $(E,{\mathcal {B}})$ , där $E$ är en ändlig mängd som tidigare och ${\mathcal {B}}$ är en samling av delmängder av $E$ , kallade "baser", med följande egenskaper:

(B1) ${\mathcal {B}}$ är inte tom.
(B2) Om $A$ och $B$ är distinkta medlemmar av ${\mathcal {B}}$ och $a\in A\smallsetminus B$ , då finns det ett element $b\in B\smallsetminus A$ så att $(A\smallsetminus \{a\}) \cup \{b\}\in {\mathcal {B}}$ . Denna egenskap kallas grundbytesegenskapen .

Det följer av grundutbytesegenskapen att ingen medlem av ${\mathcal {B}}$ kan vara en riktig delmängd av en annan.

Rangordna funktioner

Det är ett grundläggande resultat av matroidteorin, direkt analogt med en liknande sats om baser i linjär algebra , att alla två baser av en matroide $M$ har samma antal element. Detta nummer kallas rangen för $M$ . Om $M$ är en matroid på $E$ , och $A$ är en delmängd av $E$ , då kan en matroid på $A$ definieras av anser att en delmängd av $A$ är oberoende om och endast om den är oberoende i $M$ . Detta gör att vi kan prata om submatroider och om rangen för vilken delmängd som helst av $E$ . Rangen för en delmängd $A$ ges av rankfunktionen $r(A)$ för matroiden, som har följande egenskaper:

(R1) Värdet på rangfunktionen är alltid ett icke-negativt heltal .
(R2) För varje delmängd $A\subset E$ , har vi $r(A)\leq |A|$ .
(R3) För två valfria delmängder $A,B\subset E$ , har vi: $r(A\cup B)+r(A\cap B)\leq r(A)+r(B)$ . Det vill säga rangen är en submodulär funktion .
(R4) För varje uppsättning $A$ och element $x$ har vi: $r(A) )\leq r(A\kopp \{x\})\leq r(A)+1$ . Av den första olikheten följer mer generellt att, om $A\subseteq B\subseteq E$ , då $r(A) \leq r(B)\leq r(E)$ . Det vill säga rang är en monoton funktion .

Dessa egenskaper kan användas som en av de alternativa definitionerna av en finit matroid: om $(E,r)$ uppfyller dessa egenskaper, då kan de oberoende uppsättningarna av en matroid över $E$ definieras som de delmängder $A$ av $E$ med $r(A)=|A|$ . På språket för partiellt ordnade uppsättningar är en sådan matroidstruktur ekvivalent med det geometriska gittret vars element är delmängderna ${\displaystyle A\subset M} ,$ delvis ordnade genom inkludering.

Skillnaden $|A|-r(A)$ kallas nulliteten för delmängden $A$ . Det är det minsta antalet element som måste tas bort från $A$ för att få en oberoende uppsättning. Nulliteten för $E$ i $M$ kallas nulliteten för $M$ . Skillnaden $r(E)-r(A)$ kallas ibland koran för delmängden $A$ .

Stängningsoperatörer

Låt $M$ vara en matroid på en finit mängd $E$ , med rangfunktion $r$ enligt ovan. Stängningen (eller spann ) $\operatorname {cl} (A)}$ displaystyle för en delmängd $A$ av $E$ är uppsättningen

\operatorname {cl} (A)={\Bigl \{}x\in E\mid r(A)=r{\bigl (}A\cup \{x\}{\bigr )}{\ Större \}}.

Detta definierar en stängningsoperator $\operatorname {cl} :{\mathcal {P}}(E)\to {\mathcal {P}}(E)$ där ${\mathcal {P}}$ betecknar power set , med följande egenskaper:

(C1) För alla delmängder $X$ av $E$ , $X\subseteq \operatorname {cl} (X)$ .
(C2) För alla delmängder $X$ av $E$ , $\operatorname {cl} (X)=\operatörsnamn { cl} (\operatörsnamn {cl} (X))$ .
(C3) För alla delmängder $X$ och $Y$ av $E$ med $X\subseteq Y$ , $\operatörsnamn {cl} (X)\subseteq \operatörsnamn {cl} (Y)$ .
(C4) För alla element $a$ och $b$ av $E$ och alla delmängder $Y$ av $E$ , om $a\in \operatörsnamn {cl} (Y\cup \{b\})\smallsetminus \operatörsnamn {cl} (Y)$ sedan $b\in \operatörsnamn {cl} (Y\cup \{a\})\smallsetminus \operatörsnamn {cl} (Y)$ .

De tre första av dessa egenskaper är de definierande egenskaperna för en stängningsoperatör. Den fjärde kallas ibland Mac Lane – Steinitz utbytesfastighet . Dessa egenskaper kan tas som en annan definition av matroid: varje funktion $\operatorname {cl} :{\mathcal {P}}(E)\to {\mathcal {P }}(E)$ som följer dessa egenskaper bestämmer en matroid.

Lägenheter

En uppsättning vars stängning är lika med sig själv sägs vara stängd , eller en platt eller subspace av matroiden. En uppsättning är stängd om den är maximal för sin rang, vilket innebär att tillägg av något annat element till uppsättningen skulle öka rangordningen. De slutna uppsättningarna av en matroid kännetecknas av en täckande partitionsegenskap:

(F1) Hela punktuppsättningen $E$ är stängd.
(F2) Om $S$ och $T$ är platt, då är $S\cap T$ en platt.
(F3) Om $S$ är en platt, så är varje element i $E\smallsetminus S$ i exakt en av plattorna $T$ som täcker $S$ (vilket betyder att $T$ korrekt innehåller $S$ men det finns ingen platt $U$ mellan $S$ och $T$ ).

Klassen ${\mathcal {L}}(M)$ för alla lägenheter, delvis ordnade efter inkludering av mängder, bildar ett matroidgitter . Omvänt bildar varje matroidgitter $L$ en matroid över dess uppsättning $E$ av atomer under följande stängningsoperator: för en uppsättning $S$ av atomer med join $\ bigvee S$ ,

\operatörsnamn {cl} (S)=\{x\in E\mid x\leq \bigvee S\}

.

Plattorna i denna matroid överensstämmer en-för-en med elementen i gallret; den platta som motsvarar gitterelementet $y$ är mängden

\{x\in E\mid x\leq y\}

.

Sålunda är gittret av plattor i denna matroid naturligt isomorft till $L$ .

Hyperplan

I en matroid med rang $r$ kallas en lägenhet med rang ${\displaystyle r-1} ett$ hyperplan . (Hyperplan kallas också coatoms eller copoints .) Dessa är de maximala korrekta plattorna; det vill säga den enda supermängden av ett hyperplan som också är en platt är mängden $E$ av alla element i matroiden. En ekvivalent definition är att en koatom är en delmängd av E som inte sträcker sig över M , men sådan att tillsats av något annat element till den gör en spännmängd.

Familjen ${\mathcal {H}}$ av hyperplan i en matroid har följande egenskaper, som kan tas som ytterligare en axiomatisering av matroider:

(H1) Det finns inga distinkta uppsättningar $X$ och $Y$ i ${\mathcal {H}}$ med $X\subseteq Y$ . Det vill säga hyperplanen bildar en Sperner-familj .
(H2) För varje $x\in E$ och distinkta $Y,Z\in {\mathcal {H}}$ med $x\ inte i Y\cup Z$ , det finns $X\i {\mathcal {H}}$ med $(Y\cap Z)\cup \ {x\}\subseteq X$ .

Grafoider

Minty (1966) definierade en grafoid som en trippel $(L,C,D)$ där $C$ och $D$ är klasser av icke-tomma delmängder av $L$ så att

(G1) inget element i $C$ (kallad "krets") innehåller en annan,
(G2) inget element i $D$ (kallas en "samkrets") innehåller en annan,
(G3) no set i $C$ och set in $D$ skär i exakt ett element, och
(G4) närhelst $L$ representeras som den disjunkta föreningen av delmängder $R,G,B$ med $G=\{g\}$ ( en singleton-uppsättning), då finns antingen en $X\in C$ så att $g\in X\subseteq R\cup G$ eller en ${\ displaystil Y\in D}$ existerar så att $g\in Y\subseteq B\cup G.$

Han bevisade att det finns en matroid för vilken $C$ är klassen av kretsar och $D$ är klassen av samkretsar. Omvänt, om $C$ och $D$ är krets- och samkretsklasserna för en matroid $M$ med jorduppsättning ${\displaystyle E},$ då $(E,C,D)$ är en grafoid. Således ger grafoider en självdubbel kryptomorf axiomatisering av matroider.

Exempel

Gratis matroid

Låt $E$ vara en finit mängd. Mängden av alla delmängder av $E$ definierar de oberoende uppsättningarna av en matroid. Det kallas den fria matroiden över $E$ .

Enhetliga matroider

Låt $E$ vara en finit mängd och $k$ ett naturligt tal . Man kan definiera en matroid på $E$ genom att ta varje $k$ -elementdelmängd av $E$ som bas. Detta är känt som den enhetliga matroiden av rang $k$ . En enhetlig matroid med rang $k$ och med $n$ element betecknas $U_{k,n}$ . Alla enhetliga matroider av rang minst 2 är enkla (se § Ytterligare terminologi ) . Den enhetliga matroiden av rang 2 på $\displaystyle n}$ { punkter kallas $n$ -punktslinjen . En matroid är enhetlig om och endast om den inte har några kretsar av storlek mindre än ett plus matroidens rangordning. De direkta summorna av enhetliga matroider kallas partitionsmatroider .

I den enhetliga matroiden $U_{0,n}$ , är varje element en loop (ett element som inte tillhör någon oberoende uppsättning), och i den enhetliga matroiden $U_{ n,n}$ , varje element är en coloop (ett element som tillhör alla baser). Den direkta summan av matroider av dessa två typer är en partitionsmatroid där varje element är en loop eller en coloop; det kallas en diskret matroid . En ekvivalent definition av en diskret matroid är en matroid där varje korrekt, icke-tom delmängd av jorduppsättningen $E$ är en separator.

Matroider från linjär algebra

Fano-matroiden, härledd från Fano-planet . Den är GF(2) -linjär men inte reallinjär.

Vámos -matroiden , inte linjär över något fält

Matroidteorin utvecklades huvudsakligen utifrån en djupgående undersökning av egenskaperna hos oberoende och dimension i vektorrum. Det finns två sätt att presentera matroiderna definierade på detta sätt:

Om $E$ är någon ändlig delmängd av ett vektorrum $V$ , så kan vi definiera en matroid $M$ på $E$ genom att ta de oberoende uppsättningarna av ${\ displaystyle M}$ för att vara de linjärt oberoende delmängderna av $E$ . Giltigheten av de oberoende uppsättningarnas axiom för denna matroid följer av Steinitz utbyteslemma . Om $M$ är en matroid som kan definieras på detta sätt, säger vi att mängden $E$ representerar $M$ . Matroider av detta slag kallas vektormatroider . Ett viktigt exempel på en matroid definierad på detta sätt är Fano-matroiden, en rank-tre-matroid härledd från Fano-planet , en ändlig geometri med sju punkter (de sju elementen i matroiden) och sju linjer (de rätta icke-triviala plattorna i matroid). Det är en linjär matroid vars element kan beskrivas som de sju icke-nollpunkterna i ett tredimensionellt vektorrum över det finita fältet GF(2) . Det är dock inte möjligt att tillhandahålla en liknande representation för Fano-matroiden med de reella talen istället för GF(2).
En matris $A$ med poster i ett fält ger upphov till en matroid $M$ på dess uppsättning kolumner. De beroende uppsättningarna av kolumner i matroiden är de som är linjärt beroende som vektorer. Denna matroid kallas kolumnmatroiden för $A$ , och $A$ sägs representera $M$ . Till exempel kan Fano-matroiden representeras på detta sätt som en 3 × 7 ( 0,1)-matris . Kolumnmatroider är bara vektormatroider under ett annat namn, men det finns ofta skäl att gynna matrisrepresentationen. (Det finns en teknisk skillnad: en kolumnmatroid kan ha distinkta element som är samma vektor, men en vektormatroid enligt definitionen ovan kan inte. Vanligtvis är denna skillnad obetydlig och kan ignoreras, men genom att låta E {\displaystyle E $vara$ en multiset av vektorer en bringar de två definitionerna i fullständig överensstämmelse.)

En matroid som är likvärdig med en vektormatroid, även om den kan presenteras annorlunda, kallas representabel eller linjär . Om $M$ är ekvivalent med en vektormatroid över ett fält $F$ , då säger vi att $M$ är representabel över $F$ ; i synnerhet är $M$ realrepresenterbar om den är representerbar över de reella talen. Till exempel, även om en grafisk matroid (se nedan) presenteras i form av en graf, kan den också representeras av vektorer över vilket fält som helst. Ett grundläggande problem inom matroideorin är att karakterisera de matroider som kan representeras över ett givet fält $F$ ; Rotas gissning beskriver en möjlig karakterisering för varje ändligt fält . De viktigaste resultaten hittills är karakteriseringar av binära matroider (de som är representerade över GF(2)) på grund av Tutte (1950-talet), av ternära matroider (representerbara över 3-elementsfältet) på grund av Reid och Bixby, och separat för Seymour (1970-talet) ), och av kvartära matroider (representerbara över fältet med fyra element) på grund av Geelen, Gerards och Kapoor (2000). Detta är väldigt mycket ett öppet område. ^{[ behöver uppdateras? ]}

En vanlig matroid är en matroid som är representerad över alla möjliga fält. Vámos -matroiden är det enklaste exemplet på en matroid som inte kan representeras över något fält.

Matroider från grafteori

En andra originalkälla för teorin om matroider är grafteori .

Varje finit graf (eller multigraf ) $G$ ger upphov till en matroid $M(G)$ enligt följande: ta som $E$ mängden av alla kanter i ${\ displaystyle G}$ och betrakta en uppsättning kanter som är oberoende om och endast om det är en skog ; det vill säga om den inte innehåller en enkel cykel . Då kallas ${\displaystyle M(G)} en$ cykelmatroid . Matroider härledda på detta sätt är grafiska matroider . Inte varje matroid är grafisk, men alla matroider på tre element är grafiska. Varje grafisk matroid är regelbunden.

Andra matroider på grafer upptäcktes senare:

Den bicirkulära matroiden av en graf definieras genom att kalla en uppsättning kanter oberoende om varje ansluten delmängd innehåller högst en cykel.
I valfri riktad eller oriktad graf $G$ låt $E$ och $F$ vara två distinkta uppsättningar av hörn. I uppsättningen $E$ , definiera en delmängd $U$ att vara oberoende om det finns $|U|$ vertex-disjunkte banor från $F$ till $U$ . Detta definierar en matroid på $E$ som kallas en gammoid : en strikt gammoid är en där mängden $E$ är hela vertexuppsättningen av $G$ .
I en tvådelad graf $G=(U,V,E)$ kan man bilda en matroid där elementen är hörn på ena sidan $U$ av bipartitionen , och de oberoende delmängderna är uppsättningar av ändpunkter för matchningar av grafen. Detta kallas en transversal matroid , och det är ett specialfall av en gammoid. De transversala matroiderna är de dubbla matroiderna till de strikta gammoiderna.
Grafiska matroider har generaliserats till matroider från signerade grafer , förstärkningsgrafer och partiska grafer . En graf $G$ med en utmärkande linjär klass $B$ av cykler, känd som en "biased graph" $(G,B)$ , har två matroider, kända som rammatroiden och lyftmatroiden för den snedställda grafen . Om varje cykel tillhör den distingerade klassen, sammanfaller dessa matroider med cykelmatroiden för $G$ . Om ingen cykel urskiljs är rammatroiden den bicirkulära matroiden av $G$ . En förtecknad graf, vars kanter är märkta med tecken, och en förstärkningsgraf, som är en graf vars kanter är märkta orienterbart från en grupp, ger var och en upphov till en partisk graf och har därför ram- och lyftmatroider.
Lamangraferna bildar baserna för den tvådimensionella styvhetsmatroid , en matroid som definieras i teorin om strukturell styvhet .
Låt $G$ vara en sammankopplad graf och $E$ vara dess kantmängd. Låt $I$ vara samlingen av delmängder $F$ av $E$ så att $GF$ fortfarande är ansluten. Då är $M^{*}(G)$ , vars elementmängd är $E$ och med $I$ som sin klass av oberoende mängder, en matroid som kallas bindningen matroid av $G$ . Rangfunktionen $r(F)$ är det cyklomatiska numret för subgrafen som induceras på kantdelmängden ${\displaystyle F} ,$ vilket är lika med antalet kanter utanför en maximal skog för den subgrafen, och även antalet oberoende cykler i den.

Matroider från fältförlängningar

En tredje ursprunglig källa till matroidteori är fältteorin .

En förlängning av ett fält ger upphov till en matroid. Antag att $F$ och $K$ är fält där $K$ innehåller $F$ . Låt $E$ vara vilken ändlig delmängd som helst av $K$ . Definiera en delmängd $S$ av $E$ för att vara algebraiskt oberoende om tilläggsfältet $F(S)$ har transcendensgrad lika med $|S|$ .

En matroid som är likvärdig med en matroid av detta slag kallas en algebraisk matroid . Problemet med att karakterisera algebraiska matroider är extremt svårt; lite är känt om det. Vámos matroid ger ett exempel på en matroid som inte är algebraisk.

Grundläggande konstruktioner

Det finns några vanliga sätt att göra nya matroider av gamla.

Dualitet

Om M är en finit matroid kan vi definiera den ortogonala eller dubbla matroiden M * genom att ta samma underliggande mängd och kalla en mängd för en bas i M * om och endast om dess komplement är en bas i M . Det är inte svårt att verifiera att M * är en matroid och att dualen av M * är M .

Dualen kan lika väl beskrivas i termer av andra sätt att definiera en matroid. Till exempel:

En mängd är oberoende i M * om och endast om dess komplement spänner över M .
En mängd är en krets av M * om och endast om dess komplement är en koatom i M .
Rangfunktionen för dualen är $r^{*}(S)=|S|-r(M)+r\left(E\smallsetminus S\right)$ .

Enligt en matroidversion av Kuratowskis teorem är dualen av en grafisk matroid M en grafisk matroid om och endast om M är matroiden av en plan graf . I det här fallet är dualen av M matroiden av den dubbla grafen för G . Dualen av en vektormatroid som kan representeras över ett speciellt fält F är också representerad över F . Dual av en transversal matroid är en strikt gammoid och vice versa.

Exempel

Cykelmatroiden för en graf är den dubbla matroiden av dess bindningsmatroid.

Minderåriga

Om M är en matroid med elementmängd E , och S är en delmängd av E , skrivs begränsningen av M till S , M | S , är matroiden på mängden S vars oberoende mängder är de oberoende mängderna av M som finns i S . Dess kretsar är kretsarna av M som ingår i S och dess rangfunktion är den för M begränsad till delmängder av S . I linjär algebra motsvarar detta att begränsa till det delutrymme som genereras av vektorerna i S . På motsvarande sätt om T = M − S kan detta betecknas radering av T , skrivet M \ T eller M − T . Submatroiderna av M är just resultatet av en rad deletioner: ordningen är irrelevant.

Begränsningens dubbla funktion är sammandragning. Om T är en delmängd av E , är kontraktionen av M med T , skriven M / T , matroiden på den underliggande mängden E − T vars rangfunktion är $r'(A)=r(A\cup T)-r(T).$ I linjär algebra motsvarar detta att titta på kvotutrymmet av det linjära rymden som genereras av vektorerna i T , tillsammans med bilderna av vektorerna i E - T .

En matroid N som erhålls från M genom en sekvens av restriktions- och kontraktionsoperationer kallas en minor av M . Vi säger att M innehåller N som moll . Många viktiga familjer av matroider kan kännetecknas av de mindre-minimala matroider som inte tillhör familjen; dessa kallas förbjudna eller uteslutna minderåriga .

Summor och fackföreningar

Låt M vara en matroid med en underliggande uppsättning av element E och låt N vara en annan matroid på en underliggande uppsättning F . Den direkta summan av matroiderna M och N är matroiden vars underliggande mängd är den disjunkta föreningen av E och F , och vars oberoende mängder är de disjunkta föreningarna av en oberoende mängd M med en oberoende mängd N .

Unionen av M och N är matroiden vars underliggande mängd är unionen (inte den disjunkta unionen) av E och F , och vars oberoende mängder är de delmängder som är unionen av en oberoende mängd i M och en i N . Vanligtvis används termen "union" när E = F , men det antagandet är inte väsentligt. Om E och F är disjunkta är föreningen den direkta summan.

Ytterligare terminologi

Låt M vara en matroid med en underliggande uppsättning element E .

E kan kallas grundmängden av M . Dess element kan kallas punkterna för M .
En delmängd av E spänner över M om dess stängning är E . En mängd sägs spänna över en sluten mängd K om dess stängning är K .
Omkretsen av en matroid är storleken på dess minsta krets eller beroende uppsättning .
Ett element som bildar en enelementskrets av M kallas en loop . På motsvarande sätt är ett element en slinga om det inte tillhör någon bas.
Ett element som inte tillhör någon krets kallas en coloop eller isthmus . På motsvarande sätt är ett element en coloop om det tillhör varje bas. Loop och coloops är ömsesidigt dubbla.
Om en tvåelementsmängd { f, g } är en krets av M , då är f och g parallella i M .
En matroid kallas enkel om den inte har några kretsar som består av 1 eller 2 element. Det vill säga, den har inga slingor och inga parallella element. Termen kombinatorisk geometri används också. En enkel matroid som erhålls från en annan matroid M genom att ta bort alla slingor och ta bort ett element från varje 2-elementskrets tills inga 2-elementskretsar återstår kallas en förenkling av M . En matroid är co-enkel om dess dubbla matroid är enkel.
En förening av kretsar kallas ibland en cykel av M . En cykel är därför komplementet till en lägenhet av den dubbla matroiden. (Denna användning strider mot den vanliga betydelsen av "cykel" i grafteorin.)
En separator för M är en delmängd S av E så att $r(S)+r(ES)=r(M)$ . En korrekt eller icke-trivial separator är en separator som varken är E eller den tomma uppsättningen. En irreducerbar separator är en icke-tom separator som inte innehåller någon annan icke-tom separator. De icke reducerbara separatorerna delar upp jordsatsen E .
En matroid som inte kan skrivas som den direkta summan av två icke-tomma matroider, eller motsvarande som inte har några ordentliga separatorer, kallas kopplad eller irreducerbar . En matroid är ansluten om och bara om dess dubbla är ansluten.
En maximal irreducerbar submatroid av M kallas en komponent av M . En komponent är begränsningen av M till en irreducerbar separator, och tvärtom är begränsningen av M till en irreducerbar separator en komponent. En separator är en förening av komponenter.
En matroid M kallas en rammatroid om den, eller en matroid som innehåller den, har en bas så att alla punkter i M finns i linjerna som förenar par av baselement.
En matroid kallas en beläggningsmatroid om alla dess kretsar har en storlek som är minst lika med dess rang.
Den matroida polytopen $P_{M}$ är det konvexa skrovet för indikatorvektorerna för baserna i $\displaystyle M}$ .

Algoritmer

Girig algoritm

En viktad matroid är en matroid tillsammans med en funktion från dess element till de icke-negativa reella talen . Vikten av en delmängd av element definieras som summan av vikterna av elementen i delmängden. Den giriga algoritmen kan användas för att hitta en maxviktsbas för matroiden, genom att starta från den tomma uppsättningen och upprepade gånger lägga till ett element i taget, vid varje steg välja ett maximiviktselement bland de element vars tillägg skulle bevara oberoendet av den utökade uppsättningen. Denna algoritm behöver inte veta något om detaljerna i matroidens definition, så länge den har tillgång till matroiden genom ett oberoende orakel , en subrutin för att testa om en uppsättning är oberoende.

Denna optimeringsalgoritm kan användas för att karakterisera matroider: om en familj F av uppsättningar, slutna företag med delmängder, har egenskapen att, oavsett hur uppsättningarna viktas, den giriga algoritmen hittar en maximal viktuppsättning i familjen, då F måste vara familjen av oberoende uppsättningar av en matroid.

Begreppet matroid har generaliserats för att tillåta andra typer av uppsättningar där en girig algoritm ger optimala lösningar; se greedoid och matroid inbäddning för mer information.

Matroid-partitionering

Problemet med matroidpartitionering är att dela upp elementen i en matroid i så få oberoende uppsättningar som möjligt, och matroidpackningsproblemet är att hitta så många osammanhängande uppsättningar som möjligt. Båda kan lösas i polynomtid och kan generaliseras till problemet med att beräkna rangen eller hitta en oberoende mängd i en matroidsumma.

Matroid korsning

Skärningspunkten mellan två eller flera matroider är familjen av uppsättningar som samtidigt är oberoende i var och en av matroiderna. Problemet med att hitta den största mängden, eller den maximalt viktade mängden, i skärningspunkten mellan två matroider kan hittas i polynomtid och ger en lösning på många andra viktiga kombinatoriska optimeringsproblem. Till exempel maximal matchning i tvådelade grafer uttryckas som ett problem med att skära två partitionsmatroider . Men att hitta den största uppsättningen i en korsning av tre eller fler matroider är NP-komplett .

Matroid programvara

Två fristående system för beräkningar med matroider är Kingans Oid och Hlinenys Macek . Båda är paket med öppen källkod. "Oid" är ett interaktivt, utbyggbart mjukvarusystem för att experimentera med matroider. "Macek" är ett specialiserat mjukvarusystem med verktyg och rutiner för någorlunda effektiva kombinatoriska beräkningar med representativa matroider.

Båda matematiska mjukvarusystemen med öppen källkod SAGE och Macaulay2 innehåller matroidpaket.

Polynominvarianter

Det finns två särskilt signifikanta polynom associerade med en finit matroid M på jorduppsättningen E . Var och en är en matroidinvariant , vilket betyder att isomorfa matroider har samma polynom.

Karakteristiskt polynom

Det karakteristiska polynomet för M (som ibland kallas det kromatiska polynomet , även om det inte räknar färger), definieras som

p_{M}(\lambda ):=\summa _{S\subseteq E}(-1)^{|S|}\lambda ^{r(E )-r(S)},

eller motsvarande (så länge den tomma uppsättningen är stängd i M ) som

p_{M}(\lambda ):=\sum _{A}\mu (\emptyset ,A)\lambda ^{r(E)-r(A)}\ ,

där μ betecknar Möbius-funktionen för matroidens geometriska gitter och summan tas över alla flatorna A i matroiden.

När M är cykelmatroiden M ( G ) i en graf G , är det karakteristiska polynomet en lätt transformation av det kromatiska polynomet , som ges av χ _G (λ) = λ ^c p _{M ( G )} (λ), där c är antalet anslutna komponenter i G .

När M är bindningsmatroiden M *( G ) i en graf G , är det karakteristiska polynomet lika med flödespolynomet för G.

När M är matroiden M ( A ) för ett arrangemang A av linjära hyperplan i R ⁿ (eller F ⁿ där F är vilket fält som helst), ges det karakteristiska polynomet för arrangemanget av p _A (λ) = λ ^{n − r ( M )} pM (X) _.

Beta invariant

Beta -invarianten för en matroid, introducerad av Crapo (1967), kan uttryckas i termer av det karakteristiska polynomet p som en utvärdering av derivatan

\beta (M)=(-1)^{r(M)-1}p_{M}'(1 )\

eller direkt som

\beta (M)=(-1)^{r(M)}\sum _{X\subseteq E}(-1)^{|X|}r(X)\ .

Beta-invarianten är icke-negativ och är noll om och endast om M är frånkopplad, tom, eller en slinga. Annars beror det bara på gallret av lägenheter i M . Om M inte har några loopar och koloopar så är β( M ) = β( M ^∗ ).

Whitney nummer

Whitney -talen för den första typen av M är koefficienterna för potenserna av $\lambda$ i det karakteristiska polynomet. Specifikt är det i -te Whitney-talet $w_{i}(M)$ koefficienten för $\lambda ^{r(M)-i}$ och är summan av Möbius funktionsvärden:

w_{i}(M)=\summa \{\mu (\emptyset ,A):r(A )=i\},

summeras över lägenheter av rätt rang. Dessa siffror växlar i tecken, så att $(-1)^{i}w_{i}(M)>0$ för $0\leq i\leq r(M).$

Whitney -talen för den andra typen av M är antalet lägenheter i varje rang. Det vill säga, $W_{i}(M)$ är antalet rank- i -lägenheter.

Whitney-talen av båda slagen generaliserar Stirling-talen av det första och andra slaget, som är Whitney-talen för cykelmatroiden för hela grafen och motsvarande för partitionsgittret . De fick sitt namn efter Hassler Whitney , (med)grundaren av matroidteorin, av Gian-Carlo Rota . Namnet har utökats till liknande nummer för ändligt rangordnade partiellt ordnade uppsättningar .

Tutte polynom

Tuttepolynomet för en matroid, TM ( x , y ), generaliserar det karakteristiska polynomet till två variabler _. Detta ger den mer kombinatoriska tolkningar och ger den också dualitetsegenskapen

{\displaystyle T_{M^{*}}(x,y)=T_{M}(y,x)

vilket innebär ett antal dualiteter mellan egenskaper hos M och egenskaper hos M *. En definition av Tutte-polynomet är

T_{M}(x,y)=\summa _{S\subseteq E}(x-1)^{r(M)-r(S)}(y-1)^{|S|- r(S)}.

Detta uttrycker Tutte-polynomet som en utvärdering av corank-nullitet eller ranggenererande polynom ,

R_{M}(u,v)=\sum _{S\subseteq E}u^{r(M)-r(S)}v^{|S|-r(S)}.

_Från denna definition är det lätt att se att det karakteristiska polynomet upp till en enkel faktor är en utvärdering av TM , specifikt,

p_{M}(\lambda )=(-1)^{r(M)}T_{M}(1-\lambda ,0).

En annan definition är i termer av interna och externa aktiviteter och en summa över baser, vilket återspeglar det faktum att T (1,1) är antalet baser. Detta, som summerar över färre delmängder men har mer komplicerade termer, var Tuttes ursprungliga definition.

Det finns en ytterligare definition i termer av rekursion genom deletion och sammandragning. Raderings-sammandragningsidentiteten är

F(M)=F(Me)+F(M/e)

när

e

varken är en loop eller en coloop.

En invariant av matroider (dvs. en funktion som har samma värde på isomorfa matroider) som uppfyller denna rekursion och det multiplikativa villkoret

F(M\oplus M')=F(M)F(M')

sägs vara en Tutte-Grothendieck invariant . Tuttepolynomet är den mest allmänna sådana invarianten; det vill säga Tutte-polynomet är en Tutte-Grothendieck-invariant och varje sådan invariant är en utvärdering av Tutte-polynomet.

Tuttepolynomet TG för en graf är Tuttepolynomet TM ₍_{G ) dess cykelmatroide} för .

Oändliga matroider

Teorin om oändliga matroider är mycket mer komplicerad än den för finita matroider och utgör ett eget ämne. Under en lång tid har en av svårigheterna varit att det fanns många rimliga och användbara definitioner, av vilka ingen verkade fånga alla viktiga aspekter av finita matroideor. Till exempel verkade det vara svårt att ha baser, kretsar och dualitet tillsammans i en uppfattning om oändliga matroider.

Den enklaste definitionen av en oändlig matroid är att kräva finit rang ; det vill säga rangordningen för E är ändlig. Denna teori liknar den för finita matroider förutom att dualiteten misslyckats på grund av att dualen av en oändlig matroid av finit rang inte har finit rang. Finit-rank matroider inkluderar alla delmängder av finita dimensionella vektorrum och fältförlängningar av finita transcendensgrad .

Den nästa enklaste oändliga generaliseringen är finitära matroider, även känd som pregeometrier . En matroid med möjligen oändlig jorduppsättning är finitär om den har egenskapen att

x\in \operatörsnamn {cl} (Y)\ \Leftrightarrow \ {\text{ det finns en ändlig mängd }}Y'\subseteq Y{\text{ så att }}x\i \operatörsnamn {cl} (Y').

På motsvarande sätt innehåller varje beroende uppsättning en finit beroende uppsättning. Exempel är linjärt beroende av godtyckliga delmängder av oändliga dimensionella vektorrum (men inte oändliga beroenden som i Hilbert- och Banach-rum ), och algebraiskt beroende i godtyckliga delmängder av fältförlängningar av möjligen oändlig transcendensgrad. Återigen, klassen av finitär matroid är inte självdual, eftersom dualen av en finitär matroid inte är finitär. Finitära oändliga matroider studeras i modellteori , en gren av matematisk logik med starka band till algebra .

I slutet av 1960-talet bad matroideoretiker om en mer allmän uppfattning som delar de olika aspekterna av finita matroider och generaliserar deras dualitet. Många föreställningar om oändliga matroider definierades som svar på denna utmaning, men frågan förblev öppen. En av de metoder som DA Higgs undersökte blev känd som B-matroider och studerades av Higgs, Oxley och andra på 1960- och 1970-talen. Enligt ett färskt resultat av Bruhn, Diestel och Kriesell et al. ( 2013 ) löser det problemet: När de kom fram till samma föreställning oberoende, gav de fem ekvivalenta system av axiom – i termer av oberoende, baser, kretsar, stängning och rang. Dualiteten hos B-matroider generaliserar dualiteter som kan observeras i oändliga grafer.

Självständighetsaxiomen är följande:

Den tomma uppsättningen är oberoende.
Varje delmängd av en oberoende uppsättning är oberoende.
För varje icke-maximal (under mängd inkludering) oberoende mängd I och maximal oberoende mängd J , finns det $x\in J\smallsetminus I$ så att $I\cup \{ x\}$ är oberoende.
För varje delmängd X av basutrymmet kan varje oberoende delmängd I av X utökas till en maximal oberoende delmängd av X .

Med dessa axiom har varje matroid en dubbel.

Historia

Matroidteorin introducerades av Hassler Whitney ( 1935 ). Det upptäcktes också självständigt av Takeo Nakasawa , vars arbete var bortglömt i många år ( Nishimura & Kuroda 2009) .

I sin framträdande uppsats tillhandahöll Whitney två axiom för oberoende och definierade alla strukturer som ansluter sig till dessa axiom som "matroider". (Även om det kanske var underförstått, inkluderade han inte ett axiom som kräver att minst en delmängd är oberoende.) Hans viktigaste observation var att dessa axiom ger en abstraktion av "oberoende" som är gemensam för både grafer och matriser. På grund av detta liknar många av termerna som används i matroidteori termerna för deras analoga begrepp i linjär algebra eller grafteori .

Nästan omedelbart efter att Whitney först skrev om matroider, skrevs en viktig artikel av Saunders Mac Lane ( 1936 ) om förhållandet mellan matroider och projektiv geometri . Ett år senare BL van der Waerden ( 1937 ) likheter mellan algebraiskt och linjärt beroende i sin klassiska lärobok om modern algebra.

På 1940-talet utvecklade Richard Rado ytterligare teori under namnet "självständighetssystem" med ett öga mot transversal teori , där hans namn för ämnet fortfarande används ibland.

På 1950-talet blev WT Tutte den främsta figuren inom matroidteorin, en position han behöll i många år. Hans bidrag var rikliga, inklusive karaktäriseringen av binära , vanliga och grafiska matroider av uteslutna minderåriga ; satsen för representativitet med reguljär matroid; teorin om kedjegrupper och deras matroider; och verktygen han använde för att bevisa många av sina resultat, "Path theorem" och " Tutte homotopy theorem " (se t.ex. Tutte 1965 ), som är så komplexa att senare teoretiker har gjort stora besvär för att eliminera nödvändigheten av att använda dem i bevis. (Ett fint exempel är AMH Gerards korta bevis ( 1989 ) på Tuttes karaktärisering av vanliga matroider.)

Henry Crapo ( 1969 ) och Thomas Brylawski ( 1972 ) generaliserade till matroider Tuttes "dikromat", ett grafiskt polynom som nu är känt som Tutte-polynomet (namngivet av Crapo). Deras arbete har nyligen (särskilt på 2000-talet) följts av en flod av papper – men inte lika många som på Tutte-polynomet i en graf.

1976 publicerade Dominic Welsh den första omfattande boken om matroidteori.

Paul Seymours upplösningsteorem för reguljära matroider ( 1980 ) var det mest betydelsefulla och inflytelserika arbetet under det sena 1970-talet och 1980-talet. Ett annat grundläggande bidrag, av Kahn & Kung (1982) , visade varför projektiva geometrier och Dowling-geometrier spelar en så viktig roll i matroidteorin.

Vid den här tiden fanns det många andra viktiga bidragsgivare, men man bör inte utesluta att nämna Geoff Whittles utvidgning till ternära matroider av Tuttes karaktärisering av binära matroider som är representativa över rationalerna ( Whittle 1995 ), kanske det största enskilda bidraget från 1990- talet . Under den aktuella perioden (sedan omkring 2000) Matroid Minors Project av Jim Geelen , Gerards, Whittle och andra, som försöker kopiera framgången för Robertson–Seymour Graph Minors Project för matroider som kan representeras över ett ändligt fält (se Robertson –Seymour theorem ), har gjort betydande framsteg i strukturteorin för matroider. Många andra har också bidragit till den delen av matroideorin, som (under 2000-talets första och andra decennier) blomstrar.

Forskare

Matematiker som var pionjärer i studiet av matroider inkluderar Takeo Nakasawa , Saunders Mac Lane , Richard Rado , WT Tutte , BL van der Waerden och Hassler Whitney . Andra stora bidragsgivare inkluderar Jack Edmonds , Jim Geelen , Eugene Lawler , László Lovász , Gian-Carlo Rota , PD Seymour och Dominic Welsh .

Se även

Anteckningar

Bruhn, Henning; Diestel, Reinhard; Kriesell, Matthias; Pendavingh, Rudi; Wollan, Paul (2013), "Axioms for Infinite Matroids", Advances in Mathematics , 239 : 18–46, Arxiv : 1003.3919 , doi : 10.1016/j.aim.2013.01.011 , MR 3045140 , S2CID 10436077 .
Bryant, Victor; Perfect, Hazel (1980), Independence Theory in Combinatorics , London och New York: Chapman and Hall, ISBN 978-0-412-22430-0 .
Brylawski, Thomas H. (1972), "A decomposition for combinatorial geometries", Transactions of the American Mathematical Society , 171 : 235–282, doi : 10.2307/1996381 , JSTOR 1996381 .
Crapo, Henry H. (1969), "The Tutte polynomial", Aequationes Mathematicae , 3 (3): 211–229, doi : 10.1007/BF01817442 , S2CID 119602825 .
Crapo, Henry H. ; Rota, Gian-Carlo (1970), On the Foundations of Combinatorial Theory: Combinatorial Geometries , Cambridge, Mass.: MIT Press, ISBN 978-0-262-53016-3 , MR 0290980 .
Geelen, Jim; Gerards, AMH; Whittle, Geoff (2007), "Mot en matroid-moll struktur teori", i Grimmett, Geoffrey; et al. (red.), Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh , Oxford Lecture Series in Mathematics and its Applications, vol. 34, Oxford: Oxford University Press, s. 72–82 .
Gerards, AMH (1989), "Ett kort bevis på Tuttes karakterisering av totalt unimodulära matriser", Linear Algebra and Its Applications , 114/115: 207–212, doi : 10.1016/0024-3795(89) 90461-89 .
Kahn, Jeff; Kung, Joseph PS (1982), "Varieties of combinatorial geometries", Transactions of the American Mathematical Society , 271 (2): 485–499, doi : 10.2307/1998894 , JSTOR 1998894 .
Kingan, Robert; Kingan, Sandra (2005), "A software system for matroids", Graphs and Discovery , DIMACS Series in Discrete Mathematics and Theoretical Computer Science, s. 287–296 .
Kung, Joseph PS, red. (1986), A Source Book in Matroid Theory , Boston: Birkhäuser, doi : 10.1007/978-1-4684-9199-9 , ISBN 978-0-8176-3173-4 , MR 0890330 .
Mac Lane, Saunders (1936), "Några tolkningar av abstrakt linjärt beroende i termer av projektiv geometri", American Journal of Mathematics , 58 (1): 236–240, doi : 10.2307/2371070 , JSTOR 2371070 .
Minty, George J. (1966), "Om de axiomatiska grunderna för teorierna om riktade linjära grafer, elektriska nätverk och nätverksprogrammering", Journal of Mathematics and Mechanics , 15 : 485–520, MR 0188102 .
Nishimura, Hirokazu; Kuroda, Susumu, red. (2009), En förlorad matematiker, Takeo Nakasawa. The forgotten father of matroid theory , Basel: Birkhäuser Verlag, doi : 10.1007/978-3-7643-8573-6 , ISBN 978-3-7643-8572-9 , MR 2516551 , Zbl 0 10013 .
Oxley, James (1992), Matroid Theory , Oxford: Oxford University Press, ISBN 978-0-19-853563-8 , MR 1207587 , Zbl 0784.05002 .
Recski, András (1989), Matroid Theory and its Applications in Electric Network Theory and in Statics , Algorithms and Combinatorics, vol. 6, Berlin och Budapest: Springer-Verlag och Akademiai Kiado, doi : 10.1007/978-3-662-22143-3 , ISBN 978-3-540-15285-9 , MR 1027839 .
Sapozhenko, AA (2001) [1994], "Matroid" , Encyclopedia of Mathematics , EMS Press
Seymour, Paul D. (1980), "Decomposition of regular matroids", Journal of Combinatorial Theory , Series B, 28 (3): 305–359, doi : 10.1016/0095-8956(80)90075-1 , hdl : 10338 .dmlcz/101946 , Zbl 0443.05027 .
Truemper, Klaus (1992), Matroid Decomposition , Boston: Academic Press, ISBN 978-0-12-701225-4 , MR 1170126 .
Tutte, WT (1959), "Matroids and graphs", Transactions of the American Mathematical Society , 90 (3): 527–552, doi : 10.2307/1993185 , JSTOR 1993185 , MR 0101527 .
Tutte, WT (1965), "Lectures on matroids", Journal of Research of the National Bureau of Standards Section B , 69 : 1–47 .
Tutte, WT (1971), Introduktion till teorin om matroider , Moderna analytiska och beräkningsmetoder i naturvetenskap och matematik, vol. 37, New York: American Elsevier Publishing Company, Zbl 0231.05027 .
Vámos, Peter (1978), "The missing axiom of matroid theory is lost forever", Journal of the London Mathematical Society , 18 (3): 403–408, doi : 10.1112/jlms/s2-18.3.403 .
van der Waerden, BL (1937), Moderne Algebra .
Welsh, DJA (1976), Matroid Theory , LMS Monographs, vol. 8, Academic Press, ISBN 978-0-12-744050-7 , Zbl 0343.05002 .
White, Neil, red. (1986), Theory of Matroids , Encyclopedia of Mathematics and its Applications, vol. 26, Cambridge: Cambridge University Press, ISBN 978-0-521-30937-0 , Zbl 0579.00001 .
White, Neil, red. (1987), Combinatorial geometries , Encyclopedia of Mathematics and its Applications, vol. 29, Cambridge: Cambridge University Press , ISBN 978-0-521-33339-9 , Zbl 0626.00007
White, Neil, red. (1992), Matroid Applications , Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge: Cambridge University Press, ISBN 978-0-521-38165-9 , Zbl 0742.00052 .
Whitney, Hassler (1935), "On the abstract properties of linear dependence", American Journal of Mathematics , 57 (3): 509–533, doi : 10.2307/2371182 , hdl : 10338.dmlcz/100694 , JSTOR 71820 , 1181207 , 1181203 . Omtryckt i Kung (1986) , s. 55–79.
Whittle, Geoff (1995), "A characterization of the matroids representable over GF (3) and the rationals", Journal of Combinatorial Theory , Series B, 65 (2): 222–261, doi : 10.1006/jctb.1995.1052 .

externa länkar

"Matroid" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
Kingan, Sandra: Matroidteori . En stor bibliografi över matroidpapper, matroidprogramvara och länkar.
Locke, SC: Greedy Algorithms .
Pagano, Steven R.: Matroider och signerade grafer .
Mark Hubenthal: A Brief Look At Matroids ( PDF ) (innehåller bevis för påståenden i denna artikel)
James Oxley: Vad är en matroid? (PDF)
Neil White: Matroidapplikationer