Allmän information om examensarbetet på studentwebben

Specifik information för ämnesvalet matematik

Vad är kombinatorik?

Kombinatorik brukar, en aning diffust, definieras som studiet av "diskreta strukturer", vilket mer konkret innebär studiet av ändliga och uppräkneliga mängder. Kombinatorik sågs ursprungligen mest som en hjälpvetenskap till andra grenar av matematiken, i synnerhet sannolikhetsteori, algebra och talteori. Numera är ämnet etablerat som en självständig disciplin, och det finns ett stort antal vetenskapliga tidskrifter som är inriktade mot kombinatoriska problem.

Gränslinjen mellan kombinatorik och andra grenar inom matematiken är inte alltid lätt att dra. Diskret sannolikhetsteori, talteori och teorin för ändliga algebraiska strukturer är exempel på ämnesområden där fokus ligger på just diskreta strukturer. Det blir ofta upp till de enskilda forskarna att själva avgöra hur deras ämnesområde ska benämnas: probabilistisk kombinatorik eller diskret sannolikhetsteori; aritmetisk kombinatorik eller kombinatorisk talteori; algebraisk kombinatorik eller kombinatorisk algebra.

En attraktiv egenskap hos många problem inom kombinatoriken är att de går att beskriva på ett sätt som är begripligt även för en lekman. Ämnets karaktär inspirerar gärna till fantasifulla omformuleringar i termer av exempelvis bollar i urnor, fotbollsturneringar och apor som hoppar mellan träd (till viss förtret för mer traditionsbundna representanter för matematikersläktet).

Att problemen ofta är lätta att formulera innebär dock inte att de är lätta att lösa. Inte sällan krävs synnerligen sofistikerade metoder för att hitta en lösning. Ett berömt exempel är Knesers förmodan, ett till synes harmlöst grafteoretiskt problem som den ungerske matematikern László Lovász löste med hjälp av avancerade verktyg från algebraisk topologi. Att kombinatoriker i första hand intresserar sig för kombinatoriska problem innebär alltså inte att de nödvändigtvis begränsar sig till diskreta metoder för att lösa problemen. I synnerhet vore det direkt missvisande att prata om kombinatoriken som ett delområde till "diskret matematik". Det sistnämnda är för övrigt ingen gren av matematiken utan snarare en informell beteckning på en uppsjö av matematiska metoder.

Vårens projektarbete i kombinatorik

Översikt

I vårens projekt kommer vi att fokusera på de två kanske mest klassiska grenarna inom kombinatoriken, nämligen enumerativ kombinatorik och grafteori. Målet för projektet kommer att vara att studera enumerativa egenskaper hos olika grafer.

Enumerativ kombinatorik är den gren av matematiken där man studerar storleken på ändliga mängder. Den klassiska formuleringen på problem inom ämnet är att man vill räkna antalet "objekt" med en given "struktur". "Objekten" kan exempelvis vara delmängder till mängden {1, 2, ..., n}, och "strukturen" kan vara att vi bara tillåter delmängder med exakt k element eller delmängder av element vars totalsumma är precis k. De allra flesta intressanta enumerativa problem går att beskriva i termer av en eller flera parametrar, i ovanstående exempel n och k. Det naturliga målet blir då att hitta en sluten formel som gäller för så många val av parametrar som möjligt.

Inom grafteorin studerar man de geometriska objekt som brukar betecknas grafer; se bilden till höger för ett exempel. En graf består av en samling punkter tillsammans med ett antal linjestycken (eller mer allmänna kurvstycken) som sammanbinder varsitt par av punkter. Man brukar använda termerna hörn och kanter för att beteckna punkter respektive linjestycken. I en graf finns det många strukturer att studera, exempelvis stigar, cykler, träd och uppspännande träd. Man kan även studera mer avancerade strukturer, som hörnfärgningar med egenskapen att sammanbundna hörn har olika färg.

Illustrerande exempel

Här är ett exempel på ett enumerativt problem i grafteori: I nedanstående graf med 2x6 hörn, beräkna antalet stigar från övre vänstra hörnet till nedra högra hörnet. Inget hörn får passeras fler än en gång. Kan du lösa samma problem för en graf med 2xn hörn, där n ≥ 1?

Svårighetsgraden på problem av det här slaget beror väldigt mycket på valet av graf. Redan med nedanstående typ av graf blir ovanstående problem betydligt svårare (om än inte på något sätt olösbart) i det allmänna fallet med 2xn hörn.

Denna "kaotiska"egenskap hos kombinatoriska problem är vanligt förekommande. En liten förändring i problemformuleringen kan alltså ha enorma konsekvenser för problemets lösbarhet. En del av projektet går ut på att leta rätt på "guldkornen", alltså de problemvarianter som faktiskt går att lösa.

Ovanstående problem, formulerade i termer av parametern n, har egenskapen att de inbjuder till rekursiva angreppsmetoder, alltså metoder som går ut på att man försöker relatera lösningen för ett givet värde på n till lösningarna för mindre värden på n. Rekursiva resonemang utgör en central del av projektet.

Inläsningsdel

Projektet inleds med en inläsningsdel i form av en informell studiecirkel, där deltagarna hjälps åt att lära sig den nödvändiga teorin. Vi kommer att gå igenom den grundläggande kombinatoriska teorin med begrepp som talföljder, rekursioner och formella potensserier. Det blir även tillfälle att friska upp minnet från tidigare kurser. Bland annat linjär algebra och teorin för differentialekvationer visar sig komma till användning när man vill lösa vissa kombinatoriska problem.

Projektdel

Vi återkommer med information om projektdelens utformning.

Förkunskaper

Det är önskvärt att studenten antingen har kunskaper motsvarande kursen SF1630 Diskret matematik eller planerar att läsa denna kurs under våren 2010. Kursen är nyttig framför allt för att den förbättrar förmågan att föra den typ av matematiska resonemang som dyker upp i projektet. Studenter som redan inhämtat SF1630 uppmuntras att följa kursen SF2708 Kombinatorik, som ges på Stockholms universitet under våren.

Kontaktpersoner

För frågor angående inriktningen mot kombinatorik:
Jakob Jonsson, jakobj@math.kth.se

Samordnare för ämnesområdet matematik:
Mattias Dahl, dahl@math.kth.se

Ungefärlig tidsplan för projektarbetet

• Vecka 3, 18/1: Arbetetet påbörjas med inläsning.
• Vecka 9, 1/3: Projektformuleringar och arbetsplan ska finnas färdiga.
• Vecka 12, 22/3: Studenten lämnar disposition och skelett till handledaren.
• Vecka 18, 3/5: Rapport lämnas till handledaren för granskning måndag 3/5. Rapport återlämnas med kommentarer fredag 7/5.
• Vecka 20 (preliminärt): Redovisning.
• Vecka 21: Plagiatgranskning och betygssättning.