Leírás
SZTE, TTIK, Bolyai Intézet, Kombinatorika szeminárium
Absztrakt.
Hadwiger és Nelson egymástól függetlenül vetette fel az alábbi több mint 70 éves problémát: Színezzük ki a sík pontjait úgy, hogy tetszőleges két egységtávolságra lévő pont színe különbözzön egymástól. Mi a szükséges színek minimális száma?
Nagyon korán kiderült, hogy a válasz a 4,5,6,7 számok egyike. Ez egy könnyen, akár középiskolában is elmondható észrevétel. Meglepő, hogy hosszú evtizedekig nem volt lényeges előrelépés ebben a problémában.
2018-ban, Aubrey de Grey műkedvelő(!) matematikus (foglalkozása biológus) áttörést ért el. A lehetőségeket leszűkítette az 5,6,7 értékekre. Világos, hogy ehhez egy ügyes, véges gráfot kell megkonstruálnia, majd ellenőrizni ennek egy tulajdonságát.
A konstrukciót talán egyszerűnek is lehet nevezni. Az ellenőrzés azonban nem egyszerű. Most sem ismert számítógép nélküli bizonyítás. A legkisebb gráf, amivel a bizonyítás működik jelenleg 553 csúcsú. Egy Polymath project próbálja megérteni mi is történik.
Az előadásban összefoglalom a klasszikus eredményeket, elmondom az új gráfot, erről sok mindent belátunk, majd vázolom hogyan is kerülnek a képbe a számítógépek.