Nelson-Erdős-Hadwiger-ongelma

Nelson-Erdős-Hadwiger-ongelma on kombinatorisen geometrian ongelma , joka esitettiin alun perin euklidisen avaruuden värityksen tai kromaattisen lukumäärän ongelmana .

Vuodesta 2022 lähtien tehtävä on avoinna .

Ongelman selvitys

Nelson-Erdős-Hadwiger-ongelma herättää kysymyksen värien vähimmäismäärästä, jolla n - ulotteinen euklidinen avaruus voidaan värjätä siten, että ei ole samanvärisiä pisteitä, jotka ovat 1:n etäisyydellä toisistaan. Tätä lukua kutsutaan n - ulotteisen euklidisen avaruuden kromaattiseksi numeroksi .

Sama ongelma on järkevä mielivaltaiselle metriavaruudelle . Yleisessä tapauksessa anna olla metrinen tila ja . Kuinka monta väriä voidaan vähintään maalata siten, että samanväristen pisteiden välillä ei voi olla kiinteää etäisyyttä ? Tai mikä on metriavaruuden kromaattinen luku suhteessa kiellettyyn etäisyyteen ? $(X,\rho)$ $a>0$ ${\näyttötyyli \chi ((X,\rho ),a)}$ $(X,\rho )$ $a$ $(X,\rho)$ $a$

De Bruijn-Erdősin lauseen mukaan riittää, että ratkaistaan ongelma kaikille äärellisille pisteen osajoukoille.

Jotkut tulokset

Pienet mitat

On selvää, että yksiulotteisen avaruuden kromaattinen luku on kaksi, mutta vastausta ei tiedetä edes tasolle. On helppo todistaa, että koneen värjäämiseen tarvitaan vähintään 4 ja enintään 7 väriä, mutta pidemmälle pystyttiin siirtymään vasta 2018. Samalla esitettiin, että vastaus saattaa riippua joukkoteorian aksioomien valinnasta [1] [2] . Vuonna 2018 Aubrey de Gray osoitti, että 4 väriä ei riitä [3] .

Asymptotiikka

Olkoon Hölder - metriikka . Yläraja [4] on todistettu : $l_p$

{\displaystyle \chi ((\mathbb {R} ^{n},l_{p}),a)\leqslant (3+o(1))^{n))

ja alaraja [5] todistetaan :

{\displaystyle \chi ((\mathbb {R} ^{n},l_{p}),a)\geqslant (1 207...+o(1))^{n))

Joidenkin tiettyjen arvojen osalta alla olevat arviot ovat jonkin verran vahvistuneet. [6] Näin ollen on todettu, että n-ulotteisen avaruuden kromaattinen luku kasvaa asymptoottisesti eksponentiaalisesti, kun taas Borsukin ongelman ylä- ja alarajalla on eri kasvunopeus. ${\näyttötyyli p,a}$

Historia

1940 -luvun alussa sen ohjasivat Hugo Hadwiger ja Pal Erdős heistä riippumatta, suunnilleen samaan aikaan sen tekivät myös Eduard Nelson ja John Isbell .

Vuonna 1961 Hadwigerin kuuluisa teos julkaistiin ratkaisemattomista matemaattisista ongelmista , minkä jälkeen kromaattisia lukuja alettiin tutkia aktiivisesti.

Vuonna 1976 M. Benda ja M. Perles ehdottivat sen tarkastelua metristen avaruuksien yleisimmässä kontekstissa.

Vuonna 2018 Aubrey de Gray sai yksikköetäisyysgraafin, jossa on 1581 kärkeä, jota ei voi värittää 4 värillä. Matemaattinen yhteisö on parantanut di Grayn tulosta, sillä vuonna 2021 pienimmällä tunnetulla graafilla, jota ei voida maalata 4 värillä, on 509 kärkeä [7] .

Aubrey de Grayn todistuksen jälkeen vastaus Nelson-Erdős-Hadwiger-ongelmaan voi olla vain 5, 6 tai 7.

Muunnelmia ja yleistyksiä

Nelson-Erdős-Hadwiger-ongelma liittyy myös toiseen klassiseen kombinatorisen geometrian ongelmaan, Borsukin oletukseen , joka kumottiin yleisesti vuonna 1993.

Muistiinpanot

↑ Shelah, Saharon & Soifer , Alexander (2003), Valinnan aksiooma ja tason kromaattinen numero , Journal of Combinatorial Theory, Series A osa 103 (2): 387–391, doi : 10.1016/S0097-3165(03) 00102-X , < http://www.uccs.edu/~faculty/asoifer/docs/AXIOMOFCHOICEinJCT.pdf > . Haettu 29. huhtikuuta 2013. Arkistoitu 14. kesäkuuta 2011 Wayback Machinessa .
↑ Soifer, Alexander (2008), Matemaattinen värityskirja: Värityksen matematiikka ja sen tekijöiden värikäs elämä , New York: Springer, ISBN 978-0-387-74640-1
↑ Vladimir Korolev. Matemaatikoilta puuttui neljä väriä koneen värittämiseksi . N+1 (10. huhtikuuta 2018). Haettu 10. huhtikuuta 2018. Arkistoitu alkuperäisestä 10. huhtikuuta 2018. (määrätön)
↑ Larman DG, Rogers CA Etäisyyden toteutuminen joukkojen sisällä euklidisessa avaruudessa// Mathematika. - 1972. -19. - C. 1-24.
↑ Frankl P., Wilson RM Leikkauslauseet geometrisillä seurauksilla// Combinatorica. - 1981. - 1. - C. 357-368.
↑ A. M. Raigorodsky, "Borsukin hypoteesin ympärillä" . Haettu 24. toukokuuta 2013. Arkistoitu alkuperäisestä 14. joulukuuta 2014. (määrätön)
↑ Hadwiger-Nelsonin ongelma - Polymath Wiki . Haettu 24. maaliskuuta 2021. Arkistoitu alkuperäisestä 12. huhtikuuta 2021. (määrätön)

Kirjallisuus

A. Raigorodsky, V. Voronov, A. Savvatejev. Läpimurto tasovärjäyksen ongelmassa // Kvant. - 2018. - Nro 11 . - S. 2-9 . - doi : 10.4213/kvant20181101 . (Venäjän kieli)