Erdős Pál több, mint 50 éves sejtését igazolták Ambrus Gergely és kutatótársai
Több, mint fél évszázadon át megoldatlan geometriai sejtést sikerült igazolnia az SZTE Bolyai Intézet, az ELKH Rényi Intézet, valamint a BME Matematikai Intézet kutatóinak. Az Ambrus Gergely, az SZTE Bolyai Intézet Geometria Tanszékének docense, intézetvezető-helyettes részvételével megvalósult projektben az elméleti matematikusok és a mesterséges intelligencia kutatóinak összefogására volt szükség: a bizonyítás a geometria, Fourier analízis, lineáris programozás, gráfelmélet, valamint a számítástudomány módszereit ötvözi. Az eredményről júliusban a tudományos ismeretterjesztés nemzetközi etalonjának számító Quanta Magazine is beszámolt [1].
A sík legfeljebb mekkora hányada színezhető ki úgy, hogy két kiszínezett pont nem lehet pontosan egység távolságra egymástól? Ezt a geometriai kérdést Leo Moser fogalmazta meg az 1960-as évek elején. Erdős Pál sejtése szerint ez a hányad nem érheti el az ¼-et. A problémával kapcsolatban számos kutatócsoport publikált már részeredményeket, amelyek a kezdeti 0.2857-es sűrűség-becslést az elmúlt 60 évben fokozatosan 0.2544-ig élesítették. Ambrus Gergely (Szegedi Tudományegyetem és Rényi Intézet), Csiszárik Adrián (Rényi Intézet és Eötvös Loránd Tudományegyetem), Matolcsi Máté (Budapesti Műszaki Egyetem és Rényi Intézet), Varga Dániel (Rényi Intézet) és Zsámboki Pál (Rényi Intézet) új eredménye szerint a kérdéses sűrűség nem haladhatja meg a 0.247-et. Az eredményt a rangos, D1-es besorolású Mathematical Programming folyóirat teszi közzé.
Az aktívan kutatott kérdéskört az évtizedek során számos módszerrel vizsgálták. Az Ambrus és Matolcsi által korábban alkalmazott megközelítés az eredeti diszkrét geometriai kérdést Fourier analízis segítségével alakítja át egy lineáris programozási problémává. Ennek köszönhetően sikerült az előzőleg ismert legerősebb becslést bizonyítaniuk, de az Erdős által sejtett 0.25-ös korlát elérése továbbra is távolinak tűnt.
A sejtés bizonyításához szükséges első áttörést az hozta, hogy a kutatók kidolgozták a korábban alkalmazott elméleti módszerek egy közös általánosítását. Ennek segítségével egy keresési feladattá redukálták a problémát: Erdős sejtésének bizonyítását egy speciális tulajdonságokkal rendelkező síkbeli ponthalmaz megtalálására vezették vissza, azonban a feladat komplexitása miatt a hagyományos matematikai megközelítések nem vezettek célra. Ezért a keresési problémát a mesterséges intelligencia módszereinek alkalmazásával oldották meg. Ehhez a Rényi Intézet nagy számítási kapacitású számítógépeit vették igénybe, amelyeket a Mesterséges Intelligencia Nemzeti Laboratórium (MILAB) biztosított. Több hónapnyi intenzív kísérletezést követően a számítógép-hálózat végül egy egy hetes keresés során talált egy 23 pontból álló alakzatot, amely alkalmas volt a sejtés bizonyítására [2].
Az intézmények és a tudományterületek közötti sikeres együttműködést a kutatók a továbbiakban is folytatják, céljuk a sík színezéseihez kapcsolódó további problémák vizsgálata.
[1] Mathematicians Solve Long-Standing Coloring Problem. Quanta Magazine. https://www.quantamagazine.org/mathematicians-break-bounds-in-coloring-problem-20230719/
[2] Gergely Ambrus, Adrián Csiszárik, Máté Matolcsi, Dániel Varga, Pál Zsámboki. The density of planar sets avoiding unit distances. https://arxiv.org/abs/2207.14179