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., pp. 557–563; .
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 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.
szerint a problémát először E. Nelson vetette fel 1950-ben, először publikálta. 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 . 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., p. 19.
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 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.See, e.g., . 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.; lásd egy hasonló eredmény másik bizonyításához.
Kapcsolódó szócikkek Négyszín-tétel
Fordítás
Jegyzetek
Források . . . . . , Problem G10. . . . . . . ,
További információk
Kategória:Geometriai gráfelmélet Kategória:Gráfok színezése Kategória:Végtelen gráfok Kategória:Matematikai problémák