I 1850, Thomas Penyngton Kirkman, en matematiker da han ikke oppfylte hovedansvaret som sokneprest i Church of England, beskrev sitt "skolepikeproblem": "Femten unge damer på en skole går ut tre på linje i syv dager etter hverandre: det er påkrevd å arrangere dem hver dag, for at ingen skal gå to ganger i forhold til hverandre.»
For en moderne matematiker er denne typen problemer best tenkt som en hypergraf - et sett med noder samlet i grupper på tre eller flere. De 15 skolejentene er noder, og hver gruppe på "tre på linje" kan betraktes som en trekant, med tre linjer, eller kanter, som forbinder tre noder.
Kirkmans problem spør i hovedsak om det er et arrangement av disse trekantene som forbinder alle skolejentene til hverandre, men med den ekstra begrensningen at ingen to trekanter deler en kant. Kantdeling vil innebære at to skolejenter må gå sammen mer enn én gang. Denne begrensningen betyr at hver jente går med to nye venner hver dag i en uke, slik at alle mulige par kommer sammen nøyaktig én gang.
Dette problemet og andre lignende har forvirret matematikere i nesten to århundrer siden Kirkman stilte spørsmålet sitt. I 1973 stilte den legendariske matematikeren Paul Erdős en lignende. Han spurte om det er mulig å bygge en hypergraf med to tilsynelatende inkompatible egenskaper. For det første må hvert par av noder være forbundet med nøyaktig en trekant, som med skolejentene. Denne egenskapen gjør grafen tett med trekanter. Det andre kravet tvinger trekantene til å bli spredt ut på en veldig presis måte. (Spesifikt krever det at for enhver liten gruppe trekanter er det minst tre flere noder enn det er trekanter.) "Du har denne litt motstridende oppførselen der du har et tett samlet objekt som ikke har noen tette deler," sa David Conlon, en matematiker ved California Institute of Technology.
Denne januar, i et intrikat bevis på 50 sider, viste fire matematikere at det alltid er mulig å bygge en slik hypergraf så lenge du har nok noder. "Mengden av teknikalitet som [de] gikk gjennom, bare for å få dette, det var fantastisk," sa Allan Lo, en matematiker ved University of Birmingham. Conlon var enig: "Det er et virkelig imponerende stykke arbeid."
Forskerteamet bygde et system som tilfredsstilte Erdős' djevelske krav ved å starte med en tilfeldig prosess for å velge trekanter og konstruere det med ekstrem forsiktighet for å passe deres behov. "Antallet vanskelige modifikasjoner som går inn i beviset er faktisk litt svimlende," sa Conlon.
Strategien deres var å nøye bygge hypergrafen av individuelle trekanter. Tenk deg for eksempel våre 15 skolejenter. Tegn en linje mellom hvert par.
Målet her er å spore ut trekanter på toppen av disse linjene slik at trekantene tilfredsstiller to krav: For det første deler ingen to trekanter en kant. (Systemer som oppfyller dette kravet kalles Steiner-trippelsystemer.) Og for det andre, sørg for at hver liten delmengde av trekanter bruker et tilstrekkelig stort antall noder.
Måten forskerne gjorde dette på er kanskje best forstått med en analogi.
Si at i stedet for å lage trekanter av kanter, bygger du hus av legoklosser. De første bygningene du lager er ekstravagante, med strukturelle forsterkninger og forseggjort ornamentikk. Når du er ferdig med disse, sett dem til side. De vil tjene som en "absorber" - en slags strukturert lager.
Begynn nå å lage bygninger av de gjenværende klossene dine, fortsett uten mye planlegging. Når forsyningen av lego minker, kan du finne deg selv med noen herreløse klosser, eller hjem som er strukturelt uheldige. Men siden absorpsjonsbygningene er så overdrevne og forsterkede, kan du plukke ut noen murstein her og der og bruke dem uten å komme til katastrofe.
Når det gjelder Steiner-trippelsystemet, prøver du å lage trekanter. Absorberen din, i dette tilfellet, er en nøye utvalgt samling av kanter. Hvis du ikke klarer å sortere resten av systemet i trekanter, kan du bruke noen av kantene som fører inn i absorberen. Så, når du er ferdig med det, bryter du ned selve absorberen i trekanter.
Absorpsjon fungerer ikke alltid. Men matematikere har puslet med prosessen, og funnet nye måter å vesle rundt hindringer på. For eksempel deler en kraftig variant kalt iterativ absorpsjon kantene inn i en nestet sekvens av sett, slik at hver av dem fungerer som en absorber for den nest største.
"I løpet av det siste tiåret eller så har det vært massive forbedringer," sa Conlon. "Det er noe av en kunstform, men de har virkelig båret det opp til nivået av høy kunst på dette tidspunktet."
Erdős' problem var vanskelig selv med iterativ absorpsjon. "Det ble ganske klart ganske raskt hvorfor dette problemet ikke var løst," sa Mehtaab Sawhney, en av de fire forskerne som løste det, sammen med Ashwin Sah, som sammen med Sawhney er hovedfagsstudent ved Massachusetts Institute of Technology; Michael Simkin, en postdoktor ved Center of Mathematical Sciences and Applications ved Harvard University; og Matthew Kwan, en matematiker ved Institutt for vitenskap og teknologi Østerrike. "Det var ganske interessante, ganske vanskelige tekniske oppgaver."
For eksempel, i andre applikasjoner av iterativ absorpsjon, når du er ferdig med å dekke et sett - enten med trekanter, for Steiner-trippelsystemer, eller med andre strukturer for andre problemer - kan du vurdere det behandlet og glemme det. Erdős forhold forhindret imidlertid de fire matematikerne fra å gjøre det. En problematisk klynge av trekanter kan lett involvere noder fra flere absorbersett.
"En trekant du valgte for 500 trinn siden, du må på en eller annen måte huske hvordan du tenker på det," sa Sawhney.
Det de fire til slutt fant ut var at hvis de valgte trekantene sine nøye, kunne de omgå behovet for å holde styr på hver minste ting. "Det som er bedre å gjøre er å tenke på ethvert lite sett med 100 trekanter og garantere at settet med trekanter er valgt med riktig sannsynlighet," sa Sawhney.
Forfatterne av den nye artikkelen er optimistiske på at teknikken deres kan utvides utover dette ene problemet. De har allerede har brukt strategien deres til et problem om latinske firkanter, som er som en forenkling av et sudoku-puslespill.
Utover det er det flere spørsmål som til slutt kan gi etter for absorpsjonsmetoder, sa Kwan. "Det er så mange problemer i kombinatorikk, spesielt innen designteori, der tilfeldige prosesser er et veldig kraftig verktøy." Et slikt problem, Ryser-Brualdi-Stein-formodningen, handler også om latinske firkanter og har ventet på en løsning siden 1960-tallet.
Selv om absorpsjon kan trenge videre utvikling før det kan løse problemet, har det kommet langt siden oppstarten for 30 siden, sa Maya Stein, nestleder for Senter for matematisk modellering ved Universitetet i Chile. "Det er noe som er veldig flott å se hvordan disse metodene utvikler seg."
