Vuonna 1850, Thomas Penynton Kirkman, matemaatikko, kun hän ei täyttänyt päätehtäväänsä Englannin kirkon kirkkoherrana, kuvaili ”koulutyttö-ongelmaansa”: ”Viisitoista nuorta naista kävelee koulussa kolmessa peräkkäisessä järjestyksessä seitsemän päivän ajan peräkkäin: se on järjestettävä. niitä joka päivä, jottei kaksi kävele kahdesti rinnakkain."
Nykyajan matemaatikolle tällainen ongelma on parasta kuvitella hypergraafina - joukkona solmuja, jotka on koottu kolmen tai useamman henkilön ryhmiin. 15 koulutyttöä ovat solmuja, ja jokainen "kolmen rinnakkainen" ryhmä voidaan ajatella kolmiona, jossa on kolme viivaa tai reunaa, jotka yhdistävät kolme solmua.
Kirkmanin ongelma pohjimmiltaan kysyy, onko näiden kolmioiden järjestely, joka yhdistää kaikki koulutytöt toisiinsa, mutta lisärajoituksella, että kahdella kolmiolla ei ole yhteistä reunaa. Reunojen jakaminen merkitsisi sitä, että kahden koulutytön täytyy kävellä yhdessä useammin kuin kerran. Tämä rajoitus tarkoittaa, että jokainen tyttö kävelee kahden uuden ystävän kanssa joka päivä viikon ajan, joten jokainen mahdollinen pari kokoontuu tasan kerran.
Tämä ongelma ja muut vastaavat ovat houkutelleet matemaatikoita lähes kahden vuosisadan ajan sen jälkeen, kun Kirkman esitti kysymyksensä. Vuonna 1973 legendaarinen matemaatikko Paul Erdős esitti samanlaisen. Hän kysyi, onko mahdollista rakentaa hypergraafi, jossa on kaksi näennäisesti yhteensopimatonta ominaisuutta. Ensinnäkin jokainen solmupari on yhdistettävä täsmälleen yhdellä kolmiolla, kuten koulutyttöjen kohdalla. Tämä ominaisuus tekee kaaviosta tiheän kolmioiden kanssa. Toinen vaatimus pakottaa kolmiot levittämään hyvin tarkasti. (Erityisesti se edellyttää, että missä tahansa pienessä kolmioryhmässä on vähintään kolme solmua enemmän kuin kolmioita.) "Sinulla on tämä hieman ristiriitainen käyttäytyminen, kun sinulla on tiheä kokonaisuus, jolla ei ole tiheitä osia", sanoi sanoi. David Conlon, matemaatikko California Institute of Technologyssa.
Tänä tammikuussa, monimutkainen 50-sivuinen vedos, neljä matemaatikkoa osoitti, että tällainen hypergraafi on aina mahdollista rakentaa, kunhan sinulla on tarpeeksi solmuja. "Se teknisyyden määrä, jonka [he] kävivät läpi, vain saadakseen tämän, oli hämmästyttävää", sanoi Allan Lo, matemaatikko Birminghamin yliopistosta. Conlon oli samaa mieltä: "Se on todella vaikuttava teos."
Tutkimusryhmä rakensi järjestelmän, joka täytti Erdősin pirulliset vaatimukset aloittamalla satunnaisella kolmioiden valintaprosessilla ja suunnittelemalla sen erittäin huolellisesti heidän tarpeisiinsa. "Todistukseen liittyvien vaikeiden muutosten määrä on itse asiassa hämmästyttävä", Conlon sanoi.
Heidän strategiansa oli rakentaa hypergrafi huolellisesti yksittäisistä kolmioista. Kuvittele esimerkiksi 15 koulutyttöämme. Piirrä viiva jokaisen parin väliin.
Tavoitteena on jäljittää näiden viivojen päälle kolmiot siten, että kolmiot täyttävät kaksi vaatimusta: Ensinnäkin kahdella kolmiolla ei ole yhteistä reunaa. (Järjestelmiä, jotka täyttävät tämän vaatimuksen, kutsutaan Steiner-kolmiojärjestelmiksi.) Ja toiseksi, varmista, että jokainen pieni kolmioiden osajoukko käyttää riittävän suurta määrää solmuja.
Tapa, jolla tutkijat tekivät tämän, ymmärretään ehkä parhaiten analogisesti.
Sano, että sen sijaan, että tekisit kolmioita reunoista, rakennat taloja legopalikoista. Ensimmäiset rakentamasi rakennukset ovat ylellisiä, ja niissä on rakenteellisia vahvistuksia ja taidokkaita koristeita. Kun olet tehnyt nämä, laita ne sivuun. Ne toimivat "absorberina" - eräänlaisena strukturoituna varastona.
Aloita nyt rakennusten tekeminen jäljellä olevista tiilistä jatkaen ilman paljon suunnittelua. Kun Lego-tarjouksesi hupenee, saatat löytää itsesi harhaanjohtavista palikoista tai koteja, jotka ovat rakenteellisesti epäkuntoisia. Mutta koska absorboivat rakennukset ovat niin ylikunnostettuja ja vahvistettuja, voit repiä tiiliä sieltä täältä ja käyttää niitä ilman katastrofia.
Steinerin kolmoisjärjestelmän tapauksessa yrität luoda kolmioita. Absorberi on tässä tapauksessa huolella valittu kokoelma reunoja. Jos et pysty lajittelemaan muuta järjestelmää kolmioiksi, voit käyttää joitain reunoja, jotka johtavat vaimentimeen. Sitten, kun olet tehnyt sen, jaat itse vaimentimen kolmioksi.
Imeytyminen ei aina toimi. Mutta matemaatikot ovat työstäneet prosessia ja löytäneet uusia tapoja kiertää esteitä. Esimerkiksi tehokas muunnelma, jota kutsutaan iteratiiviseksi absorptioksi, jakaa reunat sisäkkäisiksi joukoiksi siten, että jokainen niistä toimii absorboijana seuraavaksi suurimmalle.
"Viime vuosikymmenen aikana on tapahtunut valtavia parannuksia", sanoi Conlon. "Se on eräänlainen taidemuoto, mutta he ovat todella vieneet sen korkealle taiteen tasolle tässä vaiheessa."
Erdősin ongelma oli hankala jopa iteratiivisen absorption kanssa. "Siksi kävi melko nopeasti selväksi, miksi tätä ongelmaa ei ollut ratkaistu", sanoi Mehtaab Sawhney, yksi neljästä tutkijasta, jotka ratkaisivat sen, sekä Ashwin Sah, joka on Sawhneyn kanssa jatko-opiskelija Massachusetts Institute of Technologyssa; Michael Simkin, tutkijatohtori Harvardin yliopiston matematiikan tieteiden ja sovellusten keskuksessa; ja Matthew Kwan, matemaatikko Itävallan tiede- ja teknologiainstituutissa. "Oli aika mielenkiintoisia, melko vaikeita teknisiä tehtäviä."
Esimerkiksi muissa iteratiivisen absorption sovelluksissa, kun olet päättänyt peittää joukon – joko kolmioilla, Steinerin kolmoisjärjestelmillä tai muilla rakenteilla muita ongelmia varten – voit katsoa sen käsitellyksi ja unohtaa sen. Erdősin ehdot kuitenkin estivät neljää matemaatikkoa tekemästä sitä. Ongelmallinen kolmioryhmä voi helposti sisältää solmuja useista absorboijajoukoista.
"Kolmio, jonka valitsit 500 askelta sitten, sinun täytyy jotenkin muistaa, miten sitä ajatellaan", Sawhney sanoi.
Lopulta nämä neljä päättivät, että jos he valitsivat kolmiot huolellisesti, he voisivat kiertää tarpeen seurata jokaista pientä asiaa. "On parempi ajatella mitä tahansa pientä 100 kolmion sarjaa ja taata, että kolmiot valitaan oikealla todennäköisyydellä", sanoi Sawhney.
Uuden paperin kirjoittajat ovat optimistisia, että heidän tekniikkaansa voidaan laajentaa tämän yhden ongelman ulkopuolelle. Heillä on ovat jo soveltaneet strategiaansa asiaan liittyvään ongelmaan Latinalaiset neliöt, jotka ovat kuin yksinkertaistus sudoku-pulmasta.
Tämän lisäksi on useita kysymyksiä, jotka voivat lopulta antaa periksi absorptiomenetelmille, sanoi Kwan. "Kombinatoriikassa on niin monia ongelmia, etenkin suunnitteluteoriassa, jossa satunnaiset prosessit ovat todella tehokas työkalu." Yksi tällainen ongelma, Ryser-Brualdi-Stein-oletus, koskee myös latinalaisia neliöitä ja on odottanut ratkaisua 1960-luvulta lähtien.
Vaikka imeytyminen saattaa vaatia lisäkehitystä ennen kuin se voi ratkaista ongelman, se on edennyt pitkän matkan perustamisestaan 30 sitten, sanoi. Maya Stein, Chilen yliopiston matemaattisen mallinnuksen keskuksen apulaisjohtaja. "Se on todella hienoa nähdä, kuinka nämä menetelmät kehittyvät."
