Majdnem megoldották a Happy End-problémát

Középen a legendás Erdős Pál, a jobbján Klein Eszterrel, a balján Szekeres Györggyel

Habár nem (csak) a szerelemről, hanem a matematikáról szól, a mögötte álló sztoriban vannak hollywoodi elemek.

Ki gondolná, hogy egy ártalmatlannak tűnő geometriapélda szerelemhez és élethosszig tartó házassághoz vezethet? A „Happy End"-ről valószínűleg kevesen asszociálnak a matematikára, pedig ezúttal arról lesz szó: egy általános iskolai ismeretekkel is könnyen megérthető problémáról, amely hiába hangzik egyszerűnek, nyolcvan év után csak most jutottak egy fontos lépéssel közelebb a megoldásához, s amely egy regényes fordulattal segített összekötni két fiatal magyar tudós életét.

Szekeres György és Klein Eszter házasságában egy geometriapéldának is szerepe volt Forrás: University of St. Andrews

Történetünk az 1930-as évek elején kezdődött, abban az időben, amikor jórészt az újrainduló Középiskolai Matematikai és Fizikai Lapoknak (KöMaL) és az inspiráló professzorok által vezetett, rendkívül színvonalas egyetemi képzésnek köszönhetően a 20. század nagy magyar tudósgenerációjának fiatal tagjai addig nem látott lelkesedéssel fordultak a matematika felé. Közülük többen hetente összejártak beszélgetni és politizálgatni, vasárnaponként pedig a Budai-hegyekbe kirándultak, ahová olykor a tanáraik, például Fejér Lipót és Neumann János is elkísérte őket, amikor itthon volt.

Gyakran találkoztak a Városligetben is, az Anonymus-szobor melletti padnál.

Ezért kezdtek el „Anonymus-csoport"-ként hivatkozni magukra: az elnevezésnek a növekvő antiszemitizmus közepette volt némi politikai felhangja is, ráadásul a Horthy-rendszerben minden nyilvános csoportosulást gyanakodva figyeltek, úgyhogy az egyetemisták ülésein az egykori tagok egyike, Vázsonyi Endre visszaemlékezései szerint a rendőrség is sokszor megjelent.

A városligeti Anonymus-szobor Forrás: Wikimedia Commons

Happy start

A társaság mindenekelőtt a később a század egyik legnagyobb matematikusává fejlődő Erdős Pál (a róla írt portrénkat itt olvashatják), valamint Turán Pál köré szerveződött. 1932 végén vették fel maguk közé a 22 éves Klein Esztert, aki az egyik beszélgetés során érdekes geometriai tétellel állt elő: elegánsan igazolta, hogy a síkon bárhogy veszünk fel öt „általános helyzetű" pontot – ez egyszerűen azt jelenti, hogy semelyik három nem esik egy egyenesre –, mindig lesz közöttük négy, amely konvex négyszöget alkot.

Egy alakzat akkor konvex, ha bármely két pontját összekötő szakasz az alakzat belsejében halad, vagyis konyhanyelven az összes pontja „látható" az összes többiből. A téglalap például konvex, a „nyílhegy" nem – az ilyen alakzatokat konkávnak nevezzük.

Az eredeti Happy End-probléma

Klein Eszter bizonyítása rendkívül egyszerű. Az öt általános helyzetű pont ún. konvex burka öt-, négy- vagy háromszög lehet. Az első két esetben (lásd az ábrát!) egyértelmű a helyzet, hiszen a konvex burok tetszőleges négy pontja konvex négyszöget alkot. A harmadik esetben az öt pont közül kettőnek a háromszög belsejében kell lennie: ezek azzal a két ponttal együtt, amely az őket összekötő egyenes egyik oldalára esik, biztosan konvex négyszöget alkotnak.

Az Anonymus-csoportnak tagja volt Szekeres György, egy 21 éves, műegyetemi vegyészmérnök-hallgató is, akinek maga Klein Eszter történetesen éppúgy tetszett, mint a bizonyítása. Erdőssel együtt továbbgondolták a problémát:

vajon hány általános helyzetű pont esetében igaz a síkon, hogy biztosan van közöttük öt, amely konvex ötszöget alkot?

Egyik társuk, Makai Endre Turánnal együtt rövidesen rájött, hogy a válasz kilenc. Nyolc nem feltétlenül elég, ahogy az alábbi ellenpéldán is látszik; mi magunk is könnyedén leellenőrizhetjük, hogy bármilyen módon választunk öt pontot közülük, azok mindenképpen konkáv ötszöget formáznak.

És mi a helyzet a hat, illetve úgy általában az n-szöggel? Amint Szekeres még abban az évben bebizonyította, bármely n ≥ 4 pozitív egész számra létezik egy olyan n-től függő ES(n) legkisebb pozitív egész szám, hogy ES(n) darab általános helyzetű pont között biztos lesz n darab olyan, amely konvex n-szöget alkot.

De vajon mekkora ES(n) értéke? Az előbbiekben már volt szó róla, hogy ES(4) = 5 és ES(5) = 9, azt pedig csak tíz évvel ezelőtt, számítógépes segítséggel sikerült igazolni, hogy ES(6) = 17, vagyis 17 általános helyzetű pont esetén mindig lesz 6 olyan, amely konvex hatszöget alkot. n > 6 esetére azonban az ES(n) értéke máig ismeretlen.

Középen a legendás Erdős Pál, a jobbján Klein Eszterrel, a balján Szekeres Györggyel Forrás: Flickr/University of Newcastle

Illetve nem egészen. Az Anonymus-csoport tagjai már abban az évben előálltak egy sejtéssel: úgy gondolták,

ES(n) = 2^n-2+1,

ám ezt nem sikerült bebizonyítaniuk.

Hamar felismertük, hogy egyszerű okoskodással nem sokra megyünk, és a társaság új típusú geometriai problémára bukkant, melyre mohón rávetettük magunkat"

– idézi Szekerest Erdős népszerű életrajzi könyve, A prímember. „Az, hogy a feladat Epszitől (ez volt Klein Eszter beceneve) eredt, nekem külön ösztönzést adott." Miután Szekeres és Klein 1937 júniusában összeházasodtak, Erdős tréfásan „Happy End-problémának" nevezte el a feladatot. Máig így ismerik. „Emlékszem az esküvő napjára" – mondogatta Szekeres szerint Erdős, akinek nagyjából mindenről a matematika jutott eszébe. „Egy nappal azután történt, hogy Vinogradov bebizonyította a páratlan Goldbach-sejtést."

A pénzdíj sem segített

Erdősnek és Szekeresnek azt jóval később, 1960-ban sikerült igazolnia, hogy ES(n) legalább a fenti képletben szereplő érték, de azt nem, hogy pontosan annyi.

Andrew Suk, Happy End Forrás: UIC

A felső becslés terén pedig gyakorlatilag nyolcvanegy éve, 1935-ben publikált közös dolgozatuk óta nem született nagyságrendi előrelépés, holott Erdős – aki ösztönzésképpen előszeretettel tűzött ki pénzdíjat az általa érdekesnek tartott problémák megoldására – már világhírű matematikusként előbb 500, majd később Ronald Graham 1000 dollárt ajánlott a bizonyításért.

Az eddigi felsőkorlátok mind 4ⁿ nagyságrendűek voltak, de nemrég fontos fordulat történt: Andrew Suk, a University of Illinois at Chicago fiatal kutatója, a magyar Pach János volt tanítványa áttörést ért el, amikor ezt lejjebb szorította. Konkrétan ezt sikerült bizonyítania, mégpedig a probléma előéletéhez képest meglehetősen röviden, pár oldalban, ráadásul a jelek szerint klasszikus kombinatorikus geometriai módszerekkel:

megfelelően nagy n-ek esetén.

A Happy End-probléma felvetése hozzájárult az általános jellegének köszönhetően széles körben alkalmazható Ramsey-tételnek, a kombinatorika egyik legfontosabb tételének az újrafelfedezéséhez, miközben két fiatal tudós sorsát is egy életre összekötötte. A házaspár a zsidóüldözés elől először Sanghajba menekült, ahol Szekeres egy gyárban vegyészmérnökként dolgozott, majd a 2. világháború végén az amerikai légierőnél állt munkába. Habár matematikusi végzettsége nem volt,

1948-tól az adelaide-i, majd a sydney-i egyetemen kapott matematikaprofesszori állást,

és évtizedeken át foglalkozott kombinatorikával, korán nyitott a számítástudomány felé, sőt szerepe volt a fekete lyukak leírását segítő koordinátarendszer kidolgozásában is. „Úgy látszik, nekem eklektikus ízlésem van" – mondta a Fizikai Szemle szerint még 1999-ben. „Nem ragadtam teljesen semmihez hozzá, de hát ez magyaroknál gyakran megesik."

Klein Eszter szintén egy sydney-i egyetemen adott órákat, és a középiskolás diákok matematikaképzését segítette. Két gyermekük született, ám az igazán hollywoodi fordulat a történetükben az, hogy még a halál sem tudta elválasztani őket: 2005. augusztus 28-án, 94 illetve 95 évesen alig egy óra különbséggel távoztak az élők sorából egy adelaide-i szanatóriumban, ahol az utolsó heteiket töltötték.