Examensarbete på grundnivå i kombinatorik

Kontaktperson: Liam Solus

Förkunskaper

För att ha utbyte av ett examensarbete i kombinatorik, bör du ha klarat betyg C eller högre på de allra flesta av ettans och tvåans kurser i matematik och ha kunskaper i nivå med en student som läser tredje året på teknisk fysik. Det är en fördel, men definitivt inget krav, att ha läst en kurs i diskret 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.

Vi kan börja med ett exempel.

Exempel på projekt: metoder från linjär algebra inom kombinatorik

Facebook upptäckte att det fanns helt för många grupper på sajten. Därför bestämde de sig för en ny regel: grupper får endast ha ett udda antal medlemmar. Hur många distinkta grupper kan det då finnas, om det finns n användare på Facebook? (Två grupper tycks vara lika om de har samma medlemmar.)

Facebook märkte att det ändå fanns helt för många grupper, så de lade till en till regel: varje par av olika grupper får endast att ha ett jämnt antal gemensamma medlemmar. Hur många olika grupper kan det då finnas?

Detta är ett exempel på en kombinatorisk fråga som på ett väldigt elegant och förvånande sätt kan lösas med hjälp av en annan del av matematiken, nämligen linjär algebra. Det är en av charmerna med kombinatorik: ibland får man använda helt oväntade redskap för att räkna något eller förstå sig på en kombinatorisk struktur. Ett möjligt projekt vore att förstå sig på ovan exempel, och försöka sig på frågor i samma stil. För detta ändamål vore det bra att ha (eller snarast införskaffa) bra förståelse av koncepten vektorrum, linjärt oberoende, dimension, och inre produkter.

Mer om kombinatorik?

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 , ett till synes harmlöst grafteoretiskt problem som den ungerske matematikern  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.

Number theory project example

Bounded gaps between primes

It was a recent major breakthrough in analytic number theory when Yitang Zhang proved that there exists a natural number \(H\), in fact \(H = 70 000 000\), such that there are infinitely many pairs of distinct primes \(p\) and \(q\) with a gap \(|p-q|\) of at most \(H\). Thus, if we enumerate the primes as \(p_1, p_2\), ... in increasing order, then \(\liminf_{n \to \infty} (p_{n+1} - p_n)\) is at most H. Shortly after this result was announced, James Maynard gave a much shorter and more elementary proof, which also improved the value of \(H\) to 600. The aim of this project is to understand Maynard's proof and the mathematics involved.


[1] J. Maynard, Small gaps between primes, Annals of Math. 181 (2015), 383-413.
[2] Y. Zhang, Bounded gaps between primes, Annals of Math. 179 (2014), 1121-1174.

Tidigare exempel på projekt: 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:

1. 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.

2. 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.

3. Studera den genererande funktionen för vardera problemet:

f(x) = |A₀| + |A1| x + |A2| x² + |A3| x³ + ... 

g(x) = |B0| + |B1| x + |B2| x² + |B3| 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.