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.

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.

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

Jegyzetek

Források
.
.
.
.
.
, Problem G10.
.
.
.
.
.
 .
,

További információk 
 
 
 

Geometriai gráfelmélet
Gráfok színezése
Végtelen gráfok
Matematikai problémák
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óltávolságra lévő semelyik két pont nem lehet egyforma színű . A válasz ismeretlen , de a leszűkítették azésszá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 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 felben , 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 , azben 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 egycsúcsból álló , nemszínezhető egységtávolsággráfot , így a sík kromatikus száma is legalább 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ű , nemszí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íkszí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 adimenzió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és legfeljebb 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 Ha egy színezésben Jordan-görbék által határolt régiók szerepelnek , akkor legalábbszín szükséges . Kapcsolódó szócikkek Négyszín-tétel Fordítás Jegyzetek Források . . . . . Problem G10 . . . . . . \ . További információk Geometriai gráfelmélet Gráfok színezése Végtelen gráfok Matematikai problémák