Hadwiger–Nelson-probléma

A sík színezése hét színnel, és a sík egy 4 kromatikus számú egységtávolsággráfja, a Moser-gráf, melyek a Hadwiger–Nelson-probléma alsó és felső korlátját jelentik.

Solomon W. Golomb tíz csúcsú 4 kromatikus számú egységtávolsággráfja

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.

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.

Alsó és felső korlátok

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.

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. Gil Kalai matematikus és Scott Aaronson számítógéptudós 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 változatai

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.

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. 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.

Kapcsolódó szócikkek

• Négyszín-tétel

Fordítás

• 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.

Források

• 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>

További információk

• 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.