Sammenhenger mellom koder, matroider, grafer og simplisielle komplekser

Abstract

Denne masteroppgaven handler hovedsakelig om å studere sammenhenger mellom ulike em- ner innen algebra og kombinatorikk. De matematiske konseptene som studeres, er lineære koder, matroider, grafer og simplisielle komplekser, og vi forsøker blant annet å vise hvordan konstruksjoner definert innenfor en av disse grenene også kan gi mening innenfor en annen. Kodeteori handler om å finne gode metoder for å sende informasjon gjennom en kanal der det kan forekomme forstyrrelser. Hovedproblemet i kodeteori er tredelt: For det første er det ønskelig med koder som er raske å sende, for det andre er det viktig at koden er stor nok til å sende alle de ulike informasjonsbitene og for det tredje må koden være robust mot forstyrrelser i kanalen. En kode består generelt av tupler av elementer fra en definert mengde kalt alfabetet. I denne oppgaven konsentrerer vi oss om lineære blokk-koder, og i dette tilfellet er tuplene elementer i et vektorrom over en kropp. Lineære blokk-koder er spesifisert ved en generatormatrise eller paritetssjekkmatrise, matriser der radene danner en basis for henholdsvis koden og dualkoden, som er det ortogonale komplementet til koden. Særlig vil vi studere såkalte MDS-koder, en klasse av lineære koder med spesielt gode egenskaper i forhold til det tredelte problemet skissert ovenfor, samt klasser av koder som i en viss forstand nesten er MDS.