gráfelméleti probléma From Wikipedia, the free encyclopedia
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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
