1850, Thomas Penyngton Kirkman, en matematiker när han inte uppfyllde sitt huvudansvar som kyrkoherde i Church of England, beskrev sitt "skoltjejproblem": "Femton unga damer i en skola går ut tre jämsides i sju dagar i följd: det krävs att man ordnar dem dagligen, så att ingen två ska gå bredvid varandra två gånger."
För en modern matematiker föreställs denna typ av problem bäst som en hypergraf - en uppsättning noder samlade i grupper om tre eller fler. De 15 skolflickorna är noder, och varje grupp av "tre i linje" kan ses som en triangel, med tre linjer, eller kanter, som förbinder tre noder.
Kirkmans problem frågar i huvudsak om det finns ett arrangemang av dessa trianglar som förbinder alla skolflickor med varandra, men med den extra begränsningen att inga två trianglar delar en kant. Kantdelning skulle innebära att två skolflickor måste gå tillsammans mer än en gång. Denna begränsning innebär att varje tjej går med två nya vänner varje dag i en vecka, så att alla möjliga par träffas exakt en gång.
Detta problem och andra liknande det har lurat matematiker under nästan två århundraden sedan Kirkman ställde sin fråga. 1973 poserade den legendariske matematikern Paul Erdős en liknande. Han frågade om det är möjligt att bygga en hypergraf med två till synes inkompatibla egenskaper. För det första måste varje par av noder kopplas samman med exakt en triangel, som med skolflickorna. Denna egenskap gör grafen tät med trianglar. Det andra kravet tvingar trianglarna att spridas ut på ett mycket exakt sätt. (Specifikt kräver det att för en liten grupp av trianglar finns det minst tre fler noder än det finns trianglar.) "Du har det här något motsägelsefulla beteendet där du har ett tätt övergripande föremål som inte har några täta delar," sa David Conlon, en matematiker vid California Institute of Technology.
I januari, i ett intrikat 50-sidigt bevis, fyra matematiker bevisade att det alltid är möjligt att bygga en sådan hypergraf så länge du har tillräckligt med noder. "Mängden teknik som [de] gick igenom, bara för att få det här, det var fantastiskt," sa Allan Lo, en matematiker vid University of Birmingham. Conlon instämde: "Det är ett riktigt imponerande arbete."
Forskargruppen byggde ett system som tillfredsställde Erdős djävulska krav genom att börja med en slumpmässig process för att välja trianglar och konstruera det med extrem omsorg för att passa deras behov. "Antalet svåra ändringar som går in i beviset är faktiskt ganska häpnadsväckande," sa Conlon.
Deras strategi var att noggrant bygga hypergrafen av individuella trianglar. Tänk dig till exempel våra 15 skolflickor. Dra en linje mellan varje par.
Målet här är att spåra ut trianglar ovanpå dessa linjer så att trianglarna uppfyller två krav: För det första delar inga två trianglar en kant. (System som uppfyller detta krav kallas Steiner-trippelsystem.) Och för det andra, se till att varje liten delmängd av trianglar använder ett tillräckligt stort antal noder.
Sättet som forskarna gjorde detta på är kanske bäst att förstå med en analogi.
Säg att istället för att göra trianglar av kanter, bygger du hus av legoklossar. De första byggnaderna du gör är extravaganta, med strukturella förstärkningar och genomarbetade ornament. När du är klar med dessa, ställ dem åt sidan. De kommer att fungera som en "absorberare" - ett slags strukturerat lager.
Börja nu göra byggnader av dina kvarvarande tegelstenar, fortsätt utan mycket planering. När ditt utbud av lego minskar, kan du hitta dig själv med några herrelösa klossar, eller hem som är strukturellt osunda. Men eftersom absorbatorbyggnaderna är så överdrivna och förstärkta, kan du plocka ut några tegelstenar här och där och använda dem utan att uppvakta katastrof.
När det gäller Steiner-trippelsystemet, försöker du skapa trianglar. Din absorber, i det här fallet, är en noga utvald samling av kanter. Om du inte kan sortera resten av systemet i trianglar kan du använda några av kanterna som leder in i absorbatorn. Sedan, när du är klar med det, bryter du ner själva absorbatorn i trianglar.
Absorption fungerar inte alltid. Men matematiker har mixtrat med processen och hittat nya sätt att vessa runt hinder. Till exempel delar en kraftfull variant som kallas iterativ absorption in kanterna i en kapslad sekvens av uppsättningar, så att var och en fungerar som en absorbator för den näst största.
"Under det senaste decenniet eller så har det skett enorma förbättringar," sa Conlon. "Det är något av en konstform, men de har verkligen tagit det upp till nivån av hög konst vid det här laget."
Erdős problem var knepigt även med iterativ absorption. "Det blev ganska tydligt ganska snabbt varför det här problemet inte hade lösts," sa Mehtaab Sawhney, en av de fyra forskare som löste det, tillsammans med Ashwin Sah, som tillsammans med Sawhney är en doktorand vid Massachusetts Institute of Technology; Michael Simkin, en postdoktor vid Center of Mathematical Sciences and Applications vid Harvard University; och Matthew Kwan, en matematiker vid Institute of Science and Technology Österrike. "Det var ganska intressanta, ganska svåra tekniska uppgifter."
Till exempel, i andra tillämpningar av iterativ absorption, när du är klar med att täcka en uppsättning - antingen med trianglar, för Steiner-trippelsystem eller med andra strukturer för andra problem - kan du överväga att det är löst och glömma det. Erdős villkor hindrade dock de fyra matematikerna från att göra det. Ett problematiskt kluster av trianglar kan lätt involvera noder från flera absorbatoruppsättningar.
"En triangel du valde för 500 steg sedan, du måste på något sätt komma ihåg hur du ska tänka på det," sa Sawhney.
Vad de fyra så småningom kom på var att om de valde sina trianglar noggrant så kunde de kringgå behovet av att hålla reda på varje liten sak. "Vad det är bättre att göra är att tänka på en liten uppsättning av 100 trianglar och garantera att uppsättningen trianglar väljs med rätt sannolikhet," sa Sawhney.
Författarna till det nya dokumentet är optimistiska att deras teknik kan utvidgas bortom detta ena problem. De har redan tillämpat sin strategi till ett problem om latinska rutor, som är som en förenkling av ett sudoku-pussel.
Utöver det finns det flera frågor som så småningom kan ge efter för absorptionsmetoder, sa Kwan. "Det finns så många problem inom kombinatorik, särskilt inom designteori, där slumpmässiga processer är ett riktigt kraftfullt verktyg." Ett sådant problem, Ryser-Brualdi-Stein-förmodan, handlar också om latinska rutor och har väntat på en lösning sedan 1960-talet.
Även om absorption kan behöva utvecklas ytterligare innan det kan lösa problemet, har det kommit långt sedan starten för 30 sedan, sa Maya Stein, biträdande chef för Center for Mathematical Modeling vid University of Chile. "Det är något som är riktigt bra att se, hur dessa metoder utvecklas."
