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å enumerativ kombinatorik.

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.

En vanlig situation är att man vill visa att två mängder av objekt A_n och B_n har samma storlek. Exempelvis kan vi tänka oss att A_n är mängden av alla binära ord av längd n och att B_n är mängden av alla delmängder till mängden {1, 2, ..., n}. Man kan gå tillväga på olika sätt för att visa att storlekarna |A_n| och |B_n| sammanfaller:

• Räkna antalet element i vardera mängden. Vårt exempel: I ett binärt ord finns det två val för varje position i ordet och därmed totalt 2ⁿ val för hela ordet. En delmängd till en mängd av storlek n kan också se ut på 2ⁿ olika sätt, för det finns exakt två möjligheter för varje element: med i mängden eller inte med i mängden.
• Hitta en bijektion mellan mängderna. Till varje element i A_n ordnar vi alltså ett element i B_n på ett sådant sätt att varje element i A_n svarar mot exakt element i B_n, och vice versa. Vårt exempel: För ett givet binärt ord, bilda mängden bestående av alla k sådana att elementet på position k i ordet är en etta.
• Studera den genererande funktionen för vardera problemet:
  f(x) = |A₀| + |A₁| x + |A₂| x² + |A₃| x³ + ...
  g(x) = |B₀| + |B₁| x + |B₂| x² + |B₃| x³ + ...
  Använd sedan lämpliga metoder för att visa att de två funktionerna sammanfaller. I komplicerade situationer kan metoder från analysen komma väl till pass.

Målet för projektet är att studera kombinatoriska problem av ovan beskrivna slag och att använda sig av bijektioner och genererande funktioner för att lösa dessa.

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. Studenter som önskar vidare fördjupning rekommenderas varmt att följa kursen SF2715 Tillämpad kombinatorik, som ges under period 4.

Projektdel

Vi återkommer med information om projektdelens utformning.

Förkunskaper

Studenten bör ha klarat betyg C eller högre på de allra flesta av ettans och tvåans kurser i matematik. Det är en fördel, men definitivt inget krav, att ha läst en kurs i diskret matematik.

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

• Januari: Arbetetet påbörjas med inläsning.
• Början av mars: Projektformuleringar och arbetsplan ska finnas färdiga.
• Mitten/slutet av mars: Studenten lämnar disposition och skelett till handledaren.
• Början av maj: Rapport lämnas till handledaren för granskning.
• Mitten/slutet av maj: Redovisning, plagiatgranskning och betygssättning.