Mécs Anna - Sokdimenziós történetek

Vannak sokdimenziós emberek. Lételemük, hogy egyszerre tartoznak sok helyre, és egyszerre kívülállók is mindenhol. Szeretik sok oldalról megvizsgálni a kérdéseket. Ezeket az embereket és történeteiket szeretném itt megmutatni.

Sejteni és bizonyítani
Interjú Pach Jánossal


Rögtön a táblához pattan, rajzolja a pontokat és a robotok mozgását. Pach János igazi világjáró matematikus: hosszú időn keresztül Amerikában kutatott, jelenleg Svájc az egyik székhelye. De az év nagy részét igyekezett mindig itthon tölteni. Meghívott előadó a matematikusok soron következő világkongresszusán, Szöulban. Pach Zsigmond Pál történész fiaként, Turán Pál és Sós Vera matematikusok unokaöccseként tudósközegben nőtt fel.

Janos_Pach_GD09.jpgPach János a tábla előtt van igazán elemében
Forrás: http://en.wikipedia.org/wiki/Janos_Pach

Szerinte jelentősebb eredményeit jórészt a szerencsének köszönheti. Annak, hogy harminc évvel ezelőtt – részben a számítógépes technológiák fejlődése következtében – újszerű, izgalmas kérdések merültek fel a kombinatorikus geometriában. Ezek megoldásában nagyon hasznosnak bizonyultak azok a geometriai és kombinatorikus módszerek, melyeket pályája kezdeten Erdős Páltól, Simonovits Miklóstól és Fejes Tóth Lászlótól tanult. A témakör robbanásszerű fejlődésnek indult.

Megjelent: Élet és Tudomány, 2013. október 18.
Szerző: Mécs Anna


A családi közegből ered, hogy mindig is szeretett furcsa jelenségeken töprengeni?

Édesapámat évtizedeken keresztül foglalkoztatta, hogy a XVI. században miért kanyarodott el a közép- és kelet-európai fejlődés a nyugat-európaitól, hogyan kerültünk a perifériára. Ugyanazzal az olthatatlan kíváncsisággal bogarászott a levéltárban, és próbálta megoldani a vámnaplók és oklevelek adatainak összevetésekor tapasztalt rejtélyeket, ellentmondásokat, ahogy egy matematikus elemez egy problémát. Cikkeiben, könyveiben mindig tételeket igyekezett megfogalmazni, melyeket több pontból álló bizonyítás követett. Nagyon nagyra tartotta a matematikát, ahol a bizonyítások cáfolhatatlanok.  Lenyűgöztek azok a kérdések, melyeket megosztott velem, és főképp az a tény, hogy évtizedekig tartó kutatással és a „tiszta ész erejével” közel lehet jutni a kérdések megoldásához.

pachturan.jpgKét Pál: Pach Zsigmond Pál és Turán Pál

Rögtön matematikai kérdéseket választott?

Nem matematika tagozatos osztályba jártam, a középiskolai anyagban sok szépet, amibe bele lehetett volna szeretni, nem találtam. Matematikatanárom ragyogó ember volt, de erezni lehetett, hogy ötvenhatos tevékenysége miatt csak büntetésből tették tanárnak. Szép matematikai kérdésekkel főképp a Középiskolai Matematikai Lapok feladatrovatában találkoztam, de a KÖMAL fizika feladatait is rendszeresen oldogattam.  A hatvanas években felnőve leginkább a fizika érdekelt. Nem is csoda, hiszen minden űrhajó fellövése szenzáció volt, élőben láthattuk a Holdra szállást, elkezdődött az atomenergia széleskörű felhasználása, megépültek az első gyors számítógépek. Az újságokban csillagközi térről, nagy vörös óriásokról, táguló univerzumról lehetett olvasni. Azt gondoltam, ha nagy leszek, atomfizikus leszek.

Mikor jött a váltás?

Nem jött a váltás.

Még most se?

Ha megkérdezné, mi szeretnék lenni, ma is azt válaszolnám – persze nem teljesen komolyan –, hogy atomfizikus. Volt egy barátom, aki fizikaszakra járt, ő azt mondta, hogy úgy kezdik az oktatást az első órán, hogy vegyünk egy differenciálható operátort. Semmit nem értett az egészből. Azt javasolta, hogy ha a fizika érdekel, akkor menjek matematikaszakra, azt megtanulom, és utána ő egy nyár alatt elmagyarázza, amit fizikából tudni kell.  Sajnos nem tudta betartani az ígéretét, mert meghalt. Ettől függetlenül se leszek már fizikus, mert belegabalyodtam a matematikába: annyi érdekeset és szépet találtam benne, hogy most már nem szabadulok.

Mikor kezdett igazán matematikussá válni?

Az egyetem utolsó évében. Előtte elmentem egy fél évre Leningrádba, ahol megtanultam oroszul, de matematikával szinte semmit nem foglalkoztam. Hogy is tettem volna, hiszen életemben először kollégiumban laktam, maga volt a szabadság! Amikor visszajöttem, lelkiismeret-furdalásom támadt. Kellene írni egy szakdolgozatot, de nincs miből. Elkezdtem komolyan dolgozni. Csupa olyan problémát kaptam – főleg Simonovits Miklóstól, aki Erdős Pál közeli munkatársa volt –, amelyek Erdőstől származtak. Ezek közül megoldottam néhányat. Az egyikre – ez szokása volt – százdolláros pénzdíjat tűzött ki. Nagyon büszke voltam, amikor megkaptam.

Ekkor figyelt fel magára?

Nem egyszerűen felfigyelt! Ha környezetében bárki egy szép tételt bizonyított, még ha apróságról volt is szó, Erdős őszintén fellelkesült, töprengeni kezdett a kérdésen, és rögtön mondott néhány kapcsolódó problémát. Ennek azért volt nagy jelentősége számomra, mert – akármennyire is tudós családból származom – halvány gőzöm nem volt arról, hogy mit jelent, hogy az ember kutat.  Mi egy eredmény? Valamit bebizonyítottam, jó, valószínűleg más még nem bizonyította be. De kit érdekel ez? Olyan, mint egy gimnáziumi versenyfeladat? Vagy mint egy nehéz zárthelyi példa? Esetleg csak azért nem gondolkodott a kérdésen senki, mert annyira jelentéktelen? Erdős akkoriban keveset járt Magyarországra. Így leveleztünk. Ez különös súlyt adott a dolognak. Érkezik egy boríték Ausztráliából szép bélyegekkel – a büdös életben nem kaptam onnan levelet –, Erdős három héttel ezelőtt megírta – csak nekem! –, hogy kivel vacsorázott, hogy megkapta, amit küldtem, kifejti, hogy miért találta érdekesnek, további ötleteket ad, majd megtoldja néhány új tétellel és problémával.

erdos1.jpegErdős és egy epszilonnyi Pach
Forrás: http://gilkalai.wordpress.com/2010/11/20/janos-pach-guth-and-katzs-solution-of-erdos-distinct-distances-problem/

Mi volt az első jelentős eredménye?

Az egyik első probléma, ami belelkesített, tulajdonképpen nem is Erdőstől származott, hanem egy jó barátjától, Stanislaw Ulamtól. Az az érzésem, hogy azért csináltam meg én először, mert mások épp az ellenkezőjét akarták bizonyítani: azt, hogy létezik egy olyan megszámlálható síkbarajzolható gráf – olyan gráf, amely lerajzolható úgy, hogy élei nem metszik egymást –, amely részgráfként minden ilyen gráfot tartalmaz.

Az egyetem után a mai Rényi Alfréd Matematikai Kutatóintézetbe került. Mennyire tudta előre, hogy hogyan folyik a munka egy kutatóintézetben?

El sem tudtam képzelni! Valami olyasmire gondoltam, hogy adnak egy fontos problémát, és azt mondják: tessék ezt megoldani! Ha nem sikerül, izzadva meg kell jelennem a főnökök előtt. Hál’ istennek a Rényi Intézet akkor is, most is a béke szigete volt. Kollégaim nagy része nemzetközi hírű matematikus, és mindenki olyan kérdésekkel foglalkozik, amivel csak akar. „Sejt és bizonyít” – Erdős kedvenc kifejezésével élve. Különleges szerencsének tekintem, hogy Fejes Tóth László diszkrét geometriai osztályára kerültem. Nem csak nagyszerű ember volt és világhírű geométer, de jó pedagógus is. Első találkozásunkkor mondott négy gyönyörű, kombinatorikai színezetű problémát, melyekről sejthette, hogy érdekelni fognak. Ezek közül a későbbiekben hármat sikerült megoldanom. Előtte alig tudtam valamit geometriából, e téren szinte minden tudásomat Fejes Tóth László szemináriumain szereztem.

Hosszú ideig dolgozott a Courant Intézetben, New Yorkban. Miben volt más, mint a Rényi?

A Rényi Intézet a diszkrét matematika fellegvára, a Courant Intézet pedig az alkalmazott matematikában tartozik a világ legjobb kutatóközpontjai közé. A differenciálegyenletek elméletében, a sztochasztikus és numerikus módszerekben, a statisztikus fizikában, olyan területeken, melyek nagyon hasznosak autók és repülőgépek tervezésénél, a folyadékok áramlása során fellépő turbulenciák leírásánál, a meteorológiában, vagy éppen tőzsdei elemzéseknél. Ezen a téren rengeteg a számítógéppel elvégzendő szimulációs munka. Ez kicsit távolabb esik attól a matematikai kultúrától, amiben felnőttem.

Akkor mit keresett ott?

 A nyolcvanas években Jack Schwartz volt a Courant Intézet egyik igazgatója. Igazi polihisztor, aki egyaránt értett az operátorok elméletéhez, a számítógépes nyelvekhez, a közgazdaságtanhoz, a relativitáselmélethez, a zenéhez, a pszichoanalízishez és még ki tudja hány dologhoz. Egy lépéssel mindig a kora előtt járt. Akkoriban egy robotikai laboratóriumot hozott létre robotok mozgásának tervezésére. Micha Sharirral közösen alkottak egy matematikai modellt, amely izgalmas matematikai kérdések tucatjait vetette fel. Ismét szerencsém volt. Kiderült, hogy az Erdős-féle kombinatorika, extremális halmazelmélet és gráfelmélet – amit én Magyarországon megtanultam – nagyszerűen alkalmazhatóak ezen a területen. Sikerült megoldanom Schwartz es Sharir néhány problémáját, így meghívtak a Courant Intézetbe. Ott bábáskodhattam egy új tudományág születésénél, melyet – egy Eli Goodman és Richard Pollack által akkortájt indított folyóirat címe után – Discrete & Computational Geometry-nek szokás nevezni.

Hogyan kapcsolódik össze a diszkrét matematika és a robotika?

Kezdjük Erdős egyik klasszikus problémájával! Adott n pont a síkban. Legfeljebb hány pontpár távolsága lehet egységnyi? Rengetegen foglalkoztak ezzel. A ma ismert legjobb felső korlátot  ami n4/3  Spencer, Szemerédi és Trotter bizonyították 1983-ban, de ez valószínűleg lényegesen javítható.

A robotikai kérdés mi volt?

Legegyszerűbb formájában a következő: adott egy egységnyi sugarú kör alakú robot és n akadály a síkon. Szeretnénk eldönteni, hogy eljuthat-e a robot egy adott kiindulási helyzetből egy adott véghelyzetbe anélkül, hogy akadályba ütközne, és ha igen, akkor milyen útvonalon. A robotot helyettesíthetjük a középpontjával. Ha minden akadályt kiterjesztünk egy egységnyi sugarú „burokkal”, akkor a kérdés úgy fogalmazható, hogy összeköthető-e a kezdőpont a végponttal egy olyan vonallal, amely a kiterjesztett akadályok mindegyikét elkerüli. Nem nehéz belátni, hogy az ezt a problémát megoldó leggyorsabb algoritmus lépésszáma lényegében arányos azon „speciális” pontok maximális számával, melyek a kiterjesztett akadályok egyesítésének határán vannak, és legalább két kiterjesztett akadályhoz tartoznak. Sikerült bebizonyítanunk, hogy konvex akadályok esetén ez a maximum legfeljebb konstansszor n. Így egyúttal majdnem lineáris lépésszámú algoritmust is adtunk a probléma megoldására.

motion-planning-L_1.gifRobotok mozgásának tervezése S kiindulópontból T végpontba.
Forrás: http://www.cs.sunysb.edu/~algorith/files/motion-planning.shtml

Hogy jön ide Erdős kérdése?

Az egységtávolság-problémát is átfogalmazhatjuk: tartsuk meg az n pontot, és minden pont köré rajzoljunk egy egységsugarú kört! Mire vagyunk kíváncsiak? Hogy a pontok és a körök között legfeljebb hány érintkezés lehet. A robot útjának tervezésénél is egy ilyen típusú kérdésre jutottunk. Ott arra voltunk kíváncsiak, hogy a kiterjesztett akadályok határgörbéi között legfeljebb hány „speciális” érintkezési pont lehet.

Az ilyen típusú eredményeket mennyire használják a gyakorlatban?

Ma már inkább csak koncepcionálisan. A mérnökök alapvetően más elvek szerint dolgoznak: egyszerűbb és robosztusabb megoldásokat keresnek. Nem zavarja őket, ha egy módszer az esetek egy nagyon kicsi százalékában nem működik.

Van olyan eredménye, amit mégis alkalmaztak?

Van. Vegyünk egy n csúcsú síkbarajzolható gráfot. Fáry régi tétele, hogy minden ilyen gráf egyenes szakaszokkal is lerajzolható. Kiköthetjük-e azt is, hogy minden csúcs egy viszonylag kicsi, egész koordinátájú pontra essen? A kérdés Rosenstiehltól es Tarjantól származik, akik azt sejtették, hogy nem. Úgy vélték, a legtöbb síkgráf lerajzolásához kénytelenek vagyunk olyan pontokat is használni, melyek koordinátái exponenciálisan nagyok. Tévedtek. Pollackkal és de Fraysseix-vel közösen beláttuk, hogy egy 2n-szer n-es méretű rács mindig elegendő, ráadásul találtunk egy gyors rajzoló algoritmust is, melyet mára beépítettek a legtöbb gráfrajzolási programcsomagba. A kérdés jelentőségét az adja, hogy a digitális képernyők csak diszkrét koordinátájú pontokat képesek megjeleníteni.

racsra_rajzolhato.pngA síkgráf rácsra rajzolása.
Forrás: http://en.wikipedia.org/wiki/File:Nested_triangle_graph_grid.svg

Turán tréfásan azt mondta, hogy abból, hogy valaki hogyan pingpongozik, kiderül, hogy milyen ember.

Én leginkább mindig forgózni szerettem. Izgalmas, gyors játék, remek szórakozás, és sokan játszhatják egyszerre. A legjobbakat is megviccelheti egy csusza vagy egy ravasz pörgetés, miközben a gyengébbek előtt is nyílik lehetőség arra, hogy lecsapjanak egy-egy ziccert. A kutatásban is kedvelem az együttműködést. Több szem többet lát! Rám inspirálóan hat, ha az általam vizsgált kérdésen más is gondolkodik. A matematikában szerencsére mindenkinek terem babér, nem csak az Erdős-kaliberű géniuszoknak. Ha igazán foglalkoztat bennünket egy kérdés, és elég kitartóan dolgozunk, akkor előbb-utóbb bejön egy „ziccer”, találunk valami érdekeset, szépet, fontosat.

A bejegyzés trackback címe:

https://csanna.blog.hu/api/trackback/id/tr725676732

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.

Brendel Mátyás · http://ateistaklub.blog.hu/ 2013.12.05. 21:30:37

A síkgráf rácsra rajzolásának gyakorlati jelentőségénél számomra az azért bökkenő, hogy az éleket is ki kell rajzolni a rácsra, és ez esetben nem sok jelentősége van annak, hogy a csúcsok pontosan rácspontra esnek-e.

Mécs Anna · http://csanna.blog.hu/ 2013.12.07. 22:10:11

@Brendel Mátyás: Csak a csúcsok koordinátái számítanak, hiszen azokkal az éleket is tudod reprezentálni (hiszen egy-egy csúcspárral meghatározhatsz egy élt)

Peter Dubovitz 2013.12.10. 17:36:49

Sejteni es bizonyítani? Es ecsém, miért nem:
Sejteni És bizonyítani?

Mécs Anna · http://csanna.blog.hu/ 2013.12.10. 21:14:08

@Peter Dubovitz: köszönöm, ecsém, a kedves figyelmeztetést. Javítottam az elgépelést.

Sokdimenziós történetek

Vannak sokdimenziós emberek. Lételemük, hogy egyszerre tartoznak sok helyre, és egyszerre kívülállók is mindenhol. Szeretik sok oldalról megvizsgálni a kérdéseket. Ezeket az embereket és történeteiket szeretném itt megmutatni. Ez a blog azoknak szól, akik nem csak egydimenziósak.

süti beállítások módosítása