Matroider

De senaste veckorna har jag haft nöjet att stifta bekantskap med teorin om matroider, som har starka kopplingar till linjär algebra och grafteori, och även till ändliga geometrier (ett ämne som jag är mycket förtjust i). Teorin hämtar sin motivation i och generaliserar studiet av linjärt beroende hos vektorer. Givet en matris M med kolonnvektorer v_1, v_2, \hdots, v_n och en mängd I \subseteq \{1, 2, \hdots, n\}, så kan vi ställa oss frågan huruvida vektorerna i multimängden \{v_i \;|\; i \in I\} är linjärt beroende eller inte. Matroidteorin har uppkommit genom försök att generalisera vissa grundläggande egenskaper hos sådana multimängder.

Bland de första att studera matroider var Hassler Whitney, som 1935 lade grunden till teorin (samt myntade begreppet matroid) i den mycket läsvärda artikeln On the Abstract Properties of Linear Dependence, där han introducerar matroider genom att ge flera olika, till synes väsensskilda men likväl ekvivalenta, definitioner (detta lyfts ofta fram som ett särdrag hos matroidteorin, och dylika definitioner kallas ibland kryptomorfa för att understryka denna, till sin natur svårdefinierade, egenskap).

Whitney var dock inte ensam om att tidigt intressera sig för linjärt beroende. Bland pionjärerna kan nämnas Garrett Birkhoff, Takeo Nakasawa, Saunders Mac Lane och Bartel van der Waerden. Själv introducerades jag till teorin om matroider av Michel Pocchiola, emedan den ingår som ett moment i hans kurs Combinatoire et optimisation som jag läser nu under vårterminen. För den som är intresserad kan jag varmt rekommendera James Oxleys introduktion What is a matroid?, som finns fritt tillgänglig på hans hemsida.

Annonser

Kommentera

Fyll i dina uppgifter nedan eller klicka på en ikon för att logga in:

WordPress.com Logo

Du kommenterar med ditt WordPress.com-konto. Logga ut / Ändra )

Twitter-bild

Du kommenterar med ditt Twitter-konto. Logga ut / Ändra )

Facebook-foto

Du kommenterar med ditt Facebook-konto. Logga ut / Ändra )

Google+ photo

Du kommenterar med ditt Google+-konto. Logga ut / Ändra )

Ansluter till %s