Hadwiger–Nelson-probléma

A matematika, azon belül a geometriai gráfelmélet területén a Hugo Hadwigerről és Edward Nelsonról elnevezett Hadwiger–Nelson-probléma a sík (vagy az n dimenziós euklideszi tér, vagy más metrikus terek) színezéséhez szükséges minimális színek számának meghatározása, ha az egymástól 1 távolságra lévő semelyik két pont nem lehet egyforma színű. A válasz ismeretlen, de a leszűkítették az 5, 6 és 7 számok valamelyikére. Előfordulhat, hogy a pontos érték függ a választott halmazelméleti axiómarendszertől.^[1]

A kérdés gráfelméleti megfogalmazása a következő lehet. Legyen G a sík egységtávolsággráfa: egy olyan végtelen gráf, melynek csúcsai a sík összes pontjainak felelnek meg, a csúcsok között pedig akkor van él, ha a nekik megfelelő két pont közötti távolság éppen 1. A Hadwiger–Nelson-probléma a G kromatikus számának megadása. Emiatt a problémát hívják úgy is, hogy „a sík kromatikus számának megtalálása”. A (de Bruijn & Erdős 1951) eredményeként kimondott de Bruijn–Erdős-tétel értelmében a kiválasztási axióma igazságát feltételezve a probléma megegyezik a véges egységtávolsággráfokban lehetséges legnagyobb kromatikus szám megtalálásával.

(Jensen & Toft 1995) szerint a problémát először E. Nelson vetette fel 1950-ben, először (Gardner 1960) publikálta. (Hadwiger 1945) korábban publikált egy kapcsolódó eredményt, megmutatva, hogy a síkot fedő öt kongruens zárt halmaz valamelyike tartalmaz egységtávolságot; a problémát szintén említette egy későbbi cikkében (Hadwiger 1961). (Soifer 2008) részletesen kielemzi a problémát és történeti áttekintést ad róla.

A sík kromatikus számára vonatkozó alsó korlát, a négy következik a négy kromatikus számú, hét csúcsú egységtávolsággráf, az 1961-ben William és Leo Moser által felfedezett Moser-gráf létezéséből. A gráf a következőképp konstruálható: vegyünk két, az x közös csúcsban csatlakozó, egység oldalhosszú szabályos háromszöget. Mindkét háromszög egy másik él mentén egy másik szabályos háromszöghöz csatlakozik, ezeknek a hozzáadott háromszögeknek az y és z csúcsai egység távolságra vannak egymástól. Ha a sík három színnel színezhető lenne, a háromszögek színezése miatt y és z-nek is x-szel megegyező színűnek kellene lennie, de y és z egység távolságra vannak egymástól, ezért ellentmondásra jutottunk. Emiatt legalább négy színre szükség van a gráf, és így a gráfot tartalmazó sík színezéséhez. Körülbelül Moserrel egy időben Solomon W. Golomb is talált egy tíz csúcsú, négyes kromatikus számú egységtávolsággráfot, ami beállítja az alsó korlátot.^[2]

2018-ban Aubrey de Grey amatőr matematikus talált egy 1581 csúcsból álló, nem 4-színezhető egységtávolsággráfot, így a sík kromatikus száma is legalább 5. A bizonyítás számítógéppel segített.^[3] Gil Kalai matematikus^[4] és Scott Aaronson számítógéptudós^[5] kitárgyalták de Grey eredményét, Aaronson jelentette, hogy SAT solverek segítségével mások is megerősítették az eredményt. Kalai belinkelte Jordan Ellenberg és Noam Elkies további posztjait a témában, ahol Elkies egy Polymath projectet javasolt a de Grey-féle konstrukciónál kisebb méretű, nem 4-színezhető egységtávolsággráfok keresésére.

A hetes felső korlát, amit (Soifer 2008) szerint John R. Isbell ismert fel először, a sík az egységnél némileg kisebb átmérőjű, szabályos hatszögekkel való csempézéséből adódik, ami ismétlődő mintázattal a sík 7-színezését adja.

A probléma könnyen kiterjeszthető az euklideszi tér magasabb dimenzióira, illetve más metrikus terekre is. A „tér kromatikus száma” alatt általában a 3 dimenziós változatot értik. Ahogy a sík esetében, itt sem ismert a megoldás, de megmutatták, hogy a válasz legalább 6 és legfeljebb 15.^[6]

Felvethető az a kérdés is, hogy hány színre van szükség akkor, ha korlátozzuk a ponthalmazok lehetséges színeit.^[7] Az ilyen korlátozások növelhetik a szükséges színek számát, mivel egyes színezések már nem fogadhatóak el. Például ha minden színosztálynak Lebesgue-mérhetőnek kell lennie, legalább öt színre van szükség. A halmazelmélet Solovay-modelljében minden ponthalmaz mérhető, tehát ebben a modellben a sík kromatikus száma legalább 5. Ha egy színezésben Jordan-görbék által határolt régiók szerepelnek, akkor legalább 6 szín szükséges.^[8]

• Négyszín-tétel

• Ez a szócikk részben vagy egészben a Hadwiger–Nelson problem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

• de Bruijn, N. G. & Erdős, P. (1951), "A colour problem for infinite graphs and a problem in the theory of relations", Nederl. Akad. Wetensch. Proc. Ser. A 54: 371–373.
• Chilakamarri, K. B. (1993), "The unit-distance graph problem: a brief survey and some new results", Bull Inst. Combin. Appl. 8: 39–60.
• Chilakamarri, Kiran B. & Mahoney, Carolyn R. (1996), "Unit-distance graphs, graphs on the integer lattice and a Ramsey type result", Aequationes Mathematicae 51 (1-2): 48–67, DOI 10.1007/BF01831139.
• Coulson, D. (2004), "On the chromatic number of plane tilings", J. Austral. Math. Soc. 77 (2): 191–196, doi:10.1017/S1446788700013574, <http://www.austms.org.au/Publ/JAustMS/V77P2/a83.html>.
• Coulson, D. (2002), "A 15-colouring of 3-space omitting distance one", Discrete Math. 256: 83–90, DOI 10.1016/S0012-365X(01)00183-2.
• Croft, Hallard T.; Falconer, Kenneth J. & Guy, Richard K. (1991), Unsolved Problems in Geometry, Springer-Verlag, Problem G10.
• Gardner, Martin (1960), "Mathematical Games", Scientific American 203/4: 180.
• Hadwiger, Hugo (1945), "Überdeckung des euklidischen Raumes durch kongruente Mengen", Portugal. Math. 4: 238–242.
• Hadwiger, Hugo (1961), "Ungelöste Probleme No. 40", Elem. Math. 16: 103–104.
• Jensen, Tommy R. & Toft, Bjarne (1995), Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, pp. 150–152.
• Radoičić, Radoš & Tóth, Géza (2003), "Note on the chromatic number of the space", Discrete and Computational Geometry: The Goodman–Pollack Festschrift, vol. 25, Algorithms and Combinatorics, Berlin: Springer, pp. 695–698, doi:10.1007/978-3-642-55566-4_32, <http://sziami.cs.bme.hu/~geza/chromatic.pdf>.
• Shelah, Saharon & Soifer, Alexander (2003), "Axiom of choice and chromatic number of the plane", Journal of Combinatorial Theory, Series A 103 (2): 387–391, doi:10.1016/S0097-3165(03)00102-X, <http://www.uccs.edu/~faculty/asoifer/docs/AXIOMOFCHOICEinJCT.pdf>. Hozzáférés ideje: 2009-09-11 Archiválva 2011. június 14-i dátummal a Wayback Machine-ben.
• Soifer, Alexander (2008), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, New York: Springer, ISBN 978-0-387-74640-1,
• Woodall, D. R. (1973), "Distances realized by sets covering the plane", Journal of Combinatorial Theory, Series A 14: 187–200, DOI 10.1016/0097-3165(73)90020-4
• de Grey, Aubrey D.N.J (2018-04-08), The chromatic number of the plane is at least 5
• Kalai, Gil (April 10, 2018), Aubrey de Grey: The chromatic number of the plane is at least 5, <https://gilkalai.wordpress.com/2018/04/10/aubrey-de-grey-the-chromatic-number-of-the-plane-is-at-least-5/>
• Aaronson, Scott (April 11, 2018), Amazing progress on longstanding open problems, <https://www.scottaaronson.com/blog/?p=3697>

• O'Rourke, Joseph: Problem 57: Chromatic Number of the Plane. The Open Problems Project. [2006. augusztus 30-i dátummal az eredetiből archiválva]. (Hozzáférés: 2006. szeptember 26.)
• Mohar, Bojan: The chromatic number of the Unit Distance Graph, 2001
• Frankl Nóra, Hubai Tamás, Pálvölgyi Dömötör: A sík kromatikus száma (magyar nyelven). Érintő (Bolyai János Matematikai Társulat), 2018. szeptember 1.