Vanlig matroid
Inom matematiken är en vanlig matroid en matroid som kan representeras över alla fält .
Definition
En matroid definieras som en familj av delmängder av en ändlig mängd, som uppfyller vissa axiom. Uppsättningarna i familjen kallas "oberoende uppsättningar". Ett av sätten att konstruera en matroid är att välja en ändlig uppsättning vektorer i ett vektorrum , och att definiera en delmängd av vektorerna att vara oberoende i matroiden när den är linjärt oberoende i vektorrummet. Varje familj av uppsättningar konstruerade på detta sätt är en matroid, men inte varje matroid kan konstrueras på detta sätt, och vektorutrymmena över olika fält leder till olika uppsättningar av matroider som kan konstrueras från dem.
En matroid är regelbunden när, för varje fält , kan representeras av ett system av vektorer över .
Egenskaper
Om en matroid är regelbunden, så är dess dubbla matroid , och så är alla dess minderåriga . Varje direkt summa av vanliga matroider förblir regelbunden.
Varje grafisk matroid (och varje co-grafisk matroid) är regelbunden. Omvänt kan varje vanlig matroid konstrueras genom att kombinera grafiska matroider, kografiska matroider och en viss matroid med tio element som varken är grafisk eller kografisk, med hjälp av en operation för att kombinera matroider som generaliserar klicksummaoperationen på grafer .
Antalet baser i en vanlig matroid kan beräknas som determinanten för en associerad matris, vilket generaliserar Kirchhoffs matristrädsats för grafiska matriser .
Karakteriseringar
Den enhetliga matroiden fyrpunktslinjen) är inte regelbunden: den kan inte realiseras över det tvåelementiga finita fältet GF(2) , så det är inte en binär matroid , även om den kan realiseras över alla andra fält. Fano-planets matroid (en rank-tre matroid där sju av trippelna av punkter är beroende) och dess dubbla är inte heller regelbundna: de kan realiseras över GF(2) och över alla fält av karakteristiska två, men inte över några andra områden än de. Som Tutte (1958) visade är dessa tre exempel grundläggande för teorin om vanliga matroider: varje icke-reguljär matroid har minst en av dessa tre som biroll . Således är de vanliga matroiderna exakt de matroider som inte har en av de tre förbjudna minderåriga Fano-planet eller dess dubbla.
Om en matroid är regelbunden måste den tydligt kunna realiseras över de två fälten GF(2) och GF(3). Det omvända är sant: varje matroid som är realiserbar över båda dessa två fält är regelbunden. Resultatet följer av en förbjuden mindre karaktärisering av matroiderna som kan realiseras över dessa fält, en del av en familj av resultat kodifierade av Rotas gissningar .
De vanliga matroiderna är de matroider som kan definieras från en helt unimodulär matris , en matris där varje kvadratisk submatris har determinant 0, 1 eller −1. Vektorerna som realiserar matroiden kan tas som raderna i matrisen. Av denna anledning kallas vanliga matroider ibland också för unimodulära matroider . Ekvivalensen av vanliga matroider och unimodulära matriser, och deras karakterisering av förbjudna minderåriga, är djupa resultat av WT Tutte, som ursprungligen bevisades av honom med Tuttes homotopisats . Gerards (1989) publicerade senare ett alternativt och enklare bevis på karaktäriseringen av unimodulära matriser av förbjudna minderåriga.
Algoritmer
Det finns en polynomisk tidsalgoritm för att testa om en matroid är regelbunden, givet tillgång till matroiden genom ett oberoende orakel .