Wikipédia

Hadwiger–Nelson-probléma

gráfelméleti 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 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 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 szerkesztés

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 változatai szerkesztés

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]

Kapcsolódó szócikkek szerkesztés

Fordítás szerkeszté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.

Jegyzetek szerkesztés

  1. ↑ (Soifer 2008), pp. 557–563; (Shelah & Soifer 2003).
  2. ↑ (Soifer 2008), p. 19.
  3. ↑ (Grey 2018)
  4. ↑ (Kalai 2018)
  5. ↑ (Aaronson 2018)
  6. ↑ (Coulson 2002); (Radoičić & Tóth 2003).
  7. ↑ See, e.g., (Croft, Falconer & Guy 1991).
  8. ↑ (Woodall 1973); lásd (Coulson 2004) egy hasonló eredmény másik bizonyításához.

Források szerkesztés

További információk szerkesztés

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Hadwiger–Nelson-probléma&oldid=25564178”