Élet és Tudomány, 2013. január-június (68. évfolyam, 1-26. szám)
2013-01-25 / 4. szám
INTERJÚ KUN GÁBORRAL SOK SZÍNNEL SZÍNEZHETŐ Ha Kun Gábor kutatási területei közötti kapcsolatokat egy gráfon ábrázolnánk, feltehetőleg sok színre lenne szükségünk, hogy elkerüljük az azonos színű szomszédos csúcsokat. A harminchárom éves matematikust Lovász László, Szabó Csaba és Szemerédi Endre jelölése alapján idén Junior Príma Díjjal jutalmazták. A jelölők neve sokat elárul: mind a gráfelmélethez, mind az algebrához, mind a diszkrét matematikához kötődnek kutatásaik. A doktori disszertációjában megfogalmazott fontos eredményeinek köszönhetően 2012-es hazatérése előtt többek között Princetonban és Cambridge-ben kutathatott. — Sakkozni sokáig jobban szerettem, mint matematikával foglalkozni. Az átlag, három-ötórás matematikaversenyek csak az adott időkereten belül voltak izgalmasak. Persze élveztem, kivettem egy szabadnapot az iskolából, elmentem, valamit ügyeskedtem, esetleg kaptam valami díjat, lógtam is és örültek is nekem. Ha félidőben kész voltam az összes OKTV-feladattal, akkor visszamentem az iskolába focizni. Ezek nem kötöttek le annyira, a sakk viszont nagyon izgalmas volt már akkor is: azon komolyan dolgoztam és tanultam, sakkmester lettem, még most is járok versenyekre. — Mikor kezdte el jobban érdekelni a matematika? — Amikor a Középiskolai Matematikai Lapokkal kezdtem foglakozni, ahol egy hónap volt a feladatokra. Ott komolyan törtem a fejem. Aztán az egyetemen már első évben későbbi témavezetőm, Szabó Csaba mondott három problémát. Azok közül egy nagyon tetszett, melynek többféle tanult dologhoz, algebrához, topológiához és kombinatorikához is köze volt. Elég nagy szabadságom volt benne, így azzal szívesen foglalkoztam. — Ez a több területet érintő érdeklődés végül komoly eredménnyel záruló doktorihoz vezetett, melyben eldöntési problémákkal foglalkozott. Mit takar ez a problémakör? — Ez a Constraint Satisfaction Problem problémacsalád olyan kérdésekkel foglalkozik, melyekben véges sok változóhoz akarunk véges sok lehetséges értékből egyet-egyet hozzárendelni bizonyos feltételek teljesítése mellett. Ilyen típusú probléma az is, hogy egy adott gráf színezhető-e három színnel, vagy hogy egy lineá- μS^2-ris egyenletrendszer megoldható-e a héttel való osztási maradékok körében. — Milyen részproblémát sikerült megoldania? — Az régen ismert dolog, hogy vannak olyan gráfok, melyeknek nagy a kromatikus számuk — azaz sok szín szükséges ahhoz, hogy a csúcsokat úgy színezhessük ki, hogy a szomszédos csúcsok különböző színűek legyenek — és nincs bennük rövid kör. Azt is tudtuk eddig, hogy ha van egy akármilyen gráf, akkor azt „át lehet gyúrni” egy másik gráfba, amiben már nem lesz rövid kör, és pontosan akkor lesz k színnel színezhető, ha az eredeti k színnel volt színezhető. De ezt az „átgyúrást’csak olyan algoritmussal tudták megcsinálni, mely véletlent használt. Nekem ebből sikerült a véletlent kivennem, azaz lényegében konstrukciót adtam erre az eljárásra. Ráadásul a konstrukcióm általánosabban is működik minden ilyen jellegű problémára. Eldöntési problémák... 108 ■ Élet és Tudomány • 2013/4