Aastal 1850, Thomas Penynton Kirkmanmatemaatik, kui ta ei täitnud oma põhiülesannet kirikuõpetajana, kirjeldas oma "koolitüdruku probleemi": "Viisteist noort daami koolis jalutavad seitse päeva järjest välja kolm korda: tuleb korraldada neid iga päev, nii et kaks ei käi kaks korda rippumas."
Kaasaegse matemaatiku jaoks on seda tüüpi probleem kõige parem ette kujutada hüpergraafina - sõlmede kogumina, mis on kogutud kolme või enama rühmana. 15 koolitüdrukut on sõlmed ja iga "kolme kõrvuti" rühma võib pidada kolmnurgaks, millel on kolm joont või serva, mis ühendavad kolme sõlme.
Kirkmani probleem küsib sisuliselt, kas on olemas nende kolmnurkade paigutus, mis ühendab kõik koolitüdrukud üksteisega, kuid lisandub piirang, et kahel kolmnurgal pole ühte serva. Serva jagamine tähendaks, et kaks koolitüdrukut peavad rohkem kui korra koos kõndima. See piirang tähendab, et iga tüdruk kõnnib nädala jooksul iga päev kahe uue sõbraga, nii et kõik võimalikud paarid saavad kokku täpselt korra.
See probleem ja teised sarnased on matemaatikuid petnud peaaegu kaks sajandit pärast seda, kui Kirkman oma küsimuse esitas. 1973. aastal poseeris legendaarne matemaatik Paul Erdős samasuguse. Ta küsis, kas on võimalik luua kahe näiliselt kokkusobimatu omadusega hüpergraafi. Esiteks peab iga sõlmepaar olema ühendatud täpselt ühe kolmnurgaga, nagu koolitüdrukute puhul. See omadus muudab graafiku kolmnurkadega tihedaks. Teine nõue sunnib kolmnurgad väga täpselt laiali laotama. (Täpsemalt nõuab see, et iga väikese kolmnurkade rühma puhul oleks vähemalt kolm sõlme rohkem kui kolmnurki.) "Teil on selline pisut vastuoluline käitumine, kui teil on tihe objekt, millel pole tihedaid osi," ütles ta. David Conlon, California Tehnoloogiainstituudi matemaatik.
Tänavu jaanuaris, keerukas 50-leheküljeline tõend, tõestasid neli matemaatikut, et sellist hüpergraafi on alati võimalik koostada, kui teil on piisavalt sõlmi. "See tehnilisuse hulk, mille [nad] läbisid, oli see hämmastav, " ütles ta Allan Lo, Birminghami ülikooli matemaatik. Conlon nõustus: "See on tõesti muljetavaldav töö."
Uurimisrühm ehitas süsteemi, mis rahuldas Erdősi kuratlikud nõudmised, alustades juhusliku kolmnurkade valimise protsessiga ja kujundades selle äärmiselt hoolikalt nende vajadustele vastavaks. "Tõestusse tehtavate keeruliste modifikatsioonide arv on tegelikult jahmatav," ütles Conlon.
Nende strateegia oli hoolikalt koostada hüpergraaf üksikutest kolmnurkadest. Kujutage näiteks ette meie 15 koolitüdrukut. Tõmmake iga paari vahele joon.
Siin on eesmärk nende joonte peal olevad kolmnurgad välja tõmmata nii, et kolmnurgad vastaksid kahele nõudele: Esiteks, kahel kolmnurgal pole ühte serva. (Süsteemid, mis vastavad sellele nõudele, nimetatakse Steineri kolmiksüsteemideks.) Ja teiseks, veenduge, et iga väike kolmnurkade alamhulk kasutab piisavalt palju sõlme.
Seda, kuidas teadlased seda tegid, saab ehk kõige paremini mõista analoogia abil.
Ütle, et selle asemel, et teha servadest kolmnurki, ehitad sa legoklotsidest maju. Esimesed paar hoonet, mille teete, on ekstravagantsed, struktuursete tugevduste ja keeruka ornamentikaga. Kui olete nendega lõpetanud, pange need kõrvale. Need toimivad "absorberina" - omamoodi struktureeritud varuna.
Nüüd hakake oma allesjäänud tellistest hooneid tegema, ilma suurema planeerimiseta. Kui teie Legode varu kahaneb, võite leida endale hulkuvaid klotse või kodusid, mis on ehituslikult ebakorrapärased. Kuid kuna neelavad hooned on nii üle pingutatud ja tugevdatud, saate siit-sealt telliseid välja kiskuda ja neid ilma katastroofi kogemata kasutada.
Steineri kolmiksüsteemi puhul proovite luua kolmnurki. Teie absorber on antud juhul hoolikalt valitud servade kollektsioon. Kui te ei suuda ülejäänud süsteemi kolmnurkadeks sorteerida, võite kasutada mõnda servi, mis viivad neeldurisse. Seejärel, kui olete selle tegemise lõpetanud, jagate absorbendi kolmnurkadeks.
Imendumine ei toimi alati. Kuid matemaatikud on selle protsessiga tegelenud, leides uusi viise, kuidas takistustest mööda hiilida. Näiteks võimas variant, mida nimetatakse iteratiivseks absorptsiooniks, jagab servad pesastatud komplektideks, nii et igaüks neist toimib järgmise suurima neeldujana.
"Viimase kümnendi jooksul on toimunud tohutuid edusamme," ütles Conlon. "See on midagi kunstiliiki, kuid nad on selle praegusel hetkel tõesti viinud kõrge kunsti tasemele."
Erdősi probleem oli keeruline isegi iteratiivse neeldumise korral. "Päris kiiresti sai selgeks, miks seda probleemi ei lahendatud," ütles Mehtaab Sawhney, üks neljast teadlasest, kes selle lahendasid, koos Ashwin Sah, kes on koos Sawhneyga Massachusettsi Tehnoloogiainstituudi magistrant; Michael Simkin, Harvardi ülikooli matemaatikateaduste ja rakenduste keskuse järeldoktor; ja Matthew Kwan, matemaatik Austria teaduse ja tehnoloogia instituudis. "Seal oli päris huvitavaid, päris raskeid tehnilisi ülesandeid."
Näiteks muudes iteratiivse neeldumise rakendustes, kui olete komplekti katmise lõpetanud – kas kolmnurkade, Steineri kolmiksüsteemide või muude struktuuridega muude probleemide korral – võite seda käsitleda ja unustada selle. Erdősi tingimused aga takistasid neljal matemaatikul seda teha. Probleemne kolmnurkade klaster võib kergesti hõlmata mitme neeldumiskomplekti sõlmi.
"Kolmnurk, mille valisite 500 sammu tagasi, peate kuidagi meeles pidama, kuidas sellele mõelda," ütles Sawhney.
Lõpuks said neli aru, et kui nad kolmnurgad hoolikalt valisid, võivad nad mööda hiilida vajadusest jälgida iga pisiasja. "Parem on mõelda mis tahes väikesele 100 kolmnurga komplektile ja tagada, et kolmnurkade komplekt valitakse õige tõenäosusega," ütles Sawhney.
Uue artikli autorid on optimistlikud, et nende tehnikat saab laiendada kaugemale sellest ühest probleemist. Neil on oma strateegiat juba rakendanud probleemile umbes Ladina ruudud, mis on nagu sudoku pusle lihtsustamine.
Lisaks sellele on mitmeid küsimusi, mis võivad lõpuks absorptsioonimeetoditele järele anda, ütles Kwan. "Kombinatoorikas on nii palju probleeme, eriti disainiteoorias, kus juhuslikud protsessid on tõesti võimas tööriist." Üks selline probleem, Ryser-Brualdi-Steini oletus, on samuti seotud ladina ruutudega ja on oodanud lahendust alates 1960. aastatest.
Kuigi imendumine võib vajada edasist arendamist enne, kui see probleem saab lahendada, on see alates selle loomisest 30 tagasi jõudnud kaugele. Maya Stein, Tšiili ülikooli matemaatilise modelleerimise keskuse asedirektor. "See on midagi, mida on tõesti hea näha, kuidas need meetodid arenevad."
