Ti numero

Thue-luku on kaavion ominaisuus, kromaattisen indeksin erityinen muunnelma . Määritetään värien vähimmäismääräksi, joka vaaditaan ei- toistuvaan värjäykseen , toisin sanoen värien määrittämiseen graafin reunoihin siten, että graafissa ei ole yksinkertaista tasapituista polkua, jossa reunojen värit ensimmäisellä puoliskolla reitin värit muodostavat saman järjestyksen kuin reunojen värit matkan toisella puoliskolla.

Sen esitteli vuonna 2002 Noga Alonin [1] johtama matemaatikkoryhmä , ja se nimettiin Axel Thuen mukaan, joka tutki luvun tiukkaan määrittämiseen tarvittavia neliön muotoisia vapaita sanoja .

Tämän ominaisuuden muunnelmia on tutkittu myös käyttämällä huippuvärjäystä ja yleisemmin reittejä [2] [3] [4] [5] .

Esimerkki

Tarkastellaan viisikulmiota , eli sykliä , jossa on viisi kärkeä. Jos värjäämme reunat kahdella värillä, osa kahdesta vierekkäisestä reunasta on samanvärinen . Näiden kahden reunan muodostamalla polulla on toistuva värisarja . Jos värjäät reunat kolmella värillä, yhtä kolmesta väristä käytetään vain kerran. Kahden muun värin muodostamalla neljän reunan polulla on joko peräkkäiset samanväriset reunat tai se muodostaa toistuvan sarjan . Neljällä värillä toistoa ei ole vaikea välttää, joten syklin to-numero on neljä. $x$ $xx$ $xyxy$ $C_{5}$

Tulokset

Alon ym. käyttivät Lovaksen paikallista lemmaa todistaakseen, että minkä tahansa graafin Thue-luku on enintään sen maksimiasteen neliö. He antoivat esimerkin, joka osoittaa, että joillekin kaavioille tämä neliöllinen riippuvuus on välttämätön. Lisäksi he osoittivat, että neljän tai useamman kärjen polun Thue-luku on täsmälleen kolme, minkä tahansa syklin Thue-luku on enintään neljä ja Petersen-graafin Thue-luku on tasan viisi.

Tunnetut syklit, joiden toista numero on neljä, ovat , , ', , , . Alon ym. olettivat, että minkä tahansa suuremman syklin Thue-luku on kolme. Laskennallisen todentamisen avulla varmistettiin, että edellä luetellut syklit ovat ainoat, joiden Thue numero neljä on pituisten syklien joukossa . Vuonna 2002 osoitettiin, että kaikkien jaksojen, joiden pituus on 18 tai enemmän, Thue-luku on 3 [6] . $C_{5}$ ${\displaystyle C_{7))$ $C_{9}$ $C_{1}0$ $C_{1}4$ $C_{1}7$ $\leqslant 2001$

Laskennallinen monimutkaisuus

Sen tarkistaminen, onko värjäyksellä toistuva polku, on NP-täydellinen , joten sen tarkistaminen, onko väritys ei-toistuva, sisältyy co-NP- luokkaan, ja Fedor Manin osoitti sen olevan co-NP-täydellinen . Ongelma tällaisen värityksen löytämisessä kuuluu polynomihierarkiaan , ja Manin osoitti myös, että se on täydellinen tälle tasolle. ${\displaystyle \Sigma _{2}^{P))$

Muistiinpanot

↑ Noga, Grischuk, Khalushchiak, Riordan, 2002 .
↑ Barat, Waryu, 2008 .
↑ Barat, Wood, 2005 .
↑ Brechard, Klavzhar, 2004 .
↑ Kündgen, Pelsmeier, 2008 .
↑ Curry, 2002 .

Kirjallisuus

Noga Alon , Jaroslaw Grytczuk, Mariusz Haluszczak, Oliver Riordan. Ei-toistuva kaavioiden värjäys // Satunnaiset rakenteet ja algoritmit. - 2002. - T. 21 , no. 3-4 . — S. 336–346 . doi :/ rsa.10057 .
János Barát, Varjú PP Graafeiden neliövapaista reunavärityksistä // Ars Combinatoria. - 2008. - T. 87 . — S. 377–383 .
Janos Barat, David Wood. Huomautuksia ei-toistuvasta kuvaajan värjäyksestä // Electronic Journal of Combinatorics. - 2005. - T. 15 , no. 1 . - arXiv : math.CO/0509608 .
Bostjan Bresar, Sandi Klavzar. Kaavioiden neliötön väritys // Ars Combin .. - 2004. - T. 70 . - s. 3-13 .
James D. Currie. On olemassa kolmiosaisia pyöreitä neliövapaita sanoja, joiden pituus on n , kun n ≥ 18 // Electronic Journal of Combinatorics. - 2002. - T. 9 , numero. 1 .
Jarosław Grytczuk. Ei-toistuva kaavioiden väritys – kysely // International Journal of Mathematics and Mathematical Sciences. – 2007.
André Kündgen, Michael J. Pelsmajer. Rajoitetun puunleveyden kuvaajien ei-toistuvat värjäykset // Diskreetti matematiikka. - 2008. - T. 308 , no. 19 . — S. 4473–4478 . - doi : 10.1016/j.disc.2007.08.043 .
Fedor Manin. Graafeiden ei-toistuvan reunavärjäyksen monimutkaisuus. - 2007. - . - arXiv : 0709.4497 .
Marcus Schaefer, Christopher Umans. Täydellisyys polynomi-aikahierarkiassa: kokoelma . - 2005. Arkistoitu 3. maaliskuuta 2016.