É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 elke­rü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ön­hető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 matematikaver­senyek csak az adott időkereten belül voltak izgalmasak. Persze élveztem, kivettem egy szabadnapot az iskolá­ból, elmentem, valamit ügyesked­tem, 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 visszamen­tem 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 tanul­tam, sakkmester lettem, még most is járok versenyekre. — Mikor kezdte el jobban érdekelni a matematika? — Amikor a Középiskolai Matemati­kai Lapokkal kezdtem foglakozni, ahol egy hónap volt a feladatokra. Ott komolyan törtem a fejem. Az­tá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 kombinatori­kához is köze volt. Elég nagy sza­badsá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ön­­tési problémákkal foglalkozott. Mit takar ez a problémakör? — Ez a Constraint Satisfaction Prob­lem problémacsalád olyan kérdések­kel foglalkozik, melyekben véges sok változóhoz akarunk véges sok lehetséges ér­tékből egyet-egyet hoz­zárendelni bizonyos fel­tételek teljesítése mellett. Ilyen típusú probléma az is, hogy egy adott gráf színezhető-e három szín­nel, vagy hogy egy lineá- μS^2-­ris egyenletrendszer meg­oldható-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ön­böző színűek legyenek — és nincs bennük rövid kör. Azt is tudtuk eddig, hogy ha van egy akármi­lyen gráf, akkor azt „át lehet gyúr­ni” egy másik gráfba, amiben már nem lesz rövid kör, és pontosan ak­kor 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 eb­ből sikerült a véletlent kivennem, azaz lényegében konstrukciót ad­tam 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

Next