Väittelijä selvitti, millaisilla kuvioilla ruutupaperia voi värittää kompleksisesti (Väitös: MSc Etienne Moutot, 15.7.2020, matematiikka)

Kun ruutupaperia väritetään useampaa väriä käyttäen, väritysmahdollisuuksia on loputtomasti. On siis helppo tehdä kompleksinen väritys, kun jokainen ruutu voidaan värittää vapaasti halutulla värillä. Jos taas vaaditaan, että värityksessä saa esiintyä vain tiettyjä kuvioita, kompleksisuuden aikaansaaminen muuttuu vaikeammaksi.

– Mitä useampia kuvioita sallitaan, sen vapaampia olemme luomaan kompleksisia värityksiä. Onko mahdollista löytää tarkka raja, joka erottaa kompleksiset väritykset yksinkertaisista? Ja kuinka nämä käsitteet edes tulisi täsmällisesti määritellä? pohtii Moutot väitöskirjassaan.

Nivat'n otaksuma liittää sallittujen kuvioiden lukumäärän värityksen kompleksisuuteen

Jaksollisesti samana toistuvat ruudukon väritykset ovat yksinkertaisia, sillä niitä on helppoa jatkaa toistamalla samaa kuviota loputtomasti. Jaksottomat väritykset puolestaan ovat kompleksisia.

Moutot tarkasteli tutkimuksessaan Nivat'n otaksumaa. Se on toistaiseksi todistamaton matemaattinen väite, joka liittää sallittujen kuvioiden lukumäärän värityksen jaksollisuuteen. Jos sallittuja kuvioita on riittävän vähän, on värityksen oltava jaksollinen ja siis yksinkertainen. Otaksuma antaa tarkan lukumäärän, joka pakottaa jaksollisuuden.

– Nivat'n otaksuma on tunnettu vuodesta 1997, ja sen uskotaan yleisesti pitävän paikkansa, mutta vedenpitävää todistusta otaksumalle ei ole vielä onnistuttu löytämään. Väitöskirjassa todistetaan otaksuma tietylle tärkeälle luokalle värityksiä. Todistus käyttää Turun yliopiston tutkijoiden Jarkko Karin ja Michal Szabadosin kehittämiä algebrallisia menetelmiä, Moutot kertoo.

Jos liian suuri määrä paikallisia kuvioita kielletään, ruudukon värittäminen saattaa muuttua mahdottomaksi. Ruudukkoa ei esimerkiksi voi värittää kahdella värillä, jos värityksessä sallitaan vain sellaiset 2x2-kuviot, joissa oikean alakulman väri eroaa kuvion kolmen muun ruudun väristä. Moutot halusi selvittää, milloin on mahdollista päätellä annetuista sallituista kuvioista, voidaanko ääretön ruudukko värittää.

– Tämä on niin sanottu domino-ongelma. Vastaus tietenkin riippuu annetuista kuvioista, eikä kysymykseen ole aina helppo vastata. Itse asiassa tiedetään, että ei ole mahdollista kirjoittaa tietokoneelle algoritmia, joka antaisi kaikissa tapauksissa oikean vastauksen. Jokainen algoritmikandidaatti on mahdollista saada antamaan väärä vastaus tai ajautumaan äärettömään silmukkaan syöttämällä sille sopivasti valitut hankalat sallitut kuviot, Moutot kertoo.

Väitöskirjan tulosten perusteella on kuitenkin mahdollista kirjoittaa algoritmi, joka toimii oikein aina, kun sallittuja kuvioita on riittävän vähän. Väitöskirjassa tarkastellaan domino-ongelmaa myös yleistetyissä ruudukoissa, kuten kahdeksankulmioiden muodostamassa ruudukossa, ja todistetaan, että yleispätevää algoritmia ei näissä tilanteissa ole olemassa.

***
MSc Etienne Moutot esittää väitöskirjansa ”Around the Domino Problem - Combinatorial Structures and Algebraic Tools” julkisesti tarkastettavaksi Turun yliopistossa keskiviikkona 15.7.2020 klo 16.30.

Turun yliopiston väitöstilaisuuksia ei koronavirustilanteen vuoksi järjestetä yleisötilaisuuksina. Väittelijä, vastaväittäjä ja kustos ovat vähintään ääniyhteydessä. Yleisön on mahdollista seurata väitöstä etäyhteyden kautta: https://www.twitch.tv/emoutot

Vastaväittäjänä toimii professori Fabien Durand (Université de Picardie Jules Verne, Ranska) ja kustoksena professori Jarkko Kari (Turun yliopisto). Tilaisuus on englanninkielinen. Väitöksen alana on matematiikka.

Turun yliopisto seuraa aktiivisesti koronavirustilannetta ja viranomaisten ohjeita. Yliopisto päivittää ohjeitaan tilanteen mukaan. Ohjeet ja linkit löytyvät osoitteesta: utu.fi/koronavirus

Väittelijän yhteystiedot: p. +336783850500, etienne.moutot@ens-lyon.org

> Väittelijän kuva

> Väitöskirja on julkaistu sähköisenä (pdf)