Az eddigi nyaraim közül az idei volt a legintenzívebb matekozás terén (bár az elkövetkező években valszeg ennél is intenzívebb lesz).
Az Erdős-konferenciával kezdődött, egy héttel azután, hogy hazaértem. Ez életem azon ritka eseményei közé tartozott ahol a férfi vécénél állt a sor, míg a nőire senki sem várt. Az biztos, hogy eddig ez volt a legnagyobb konferencia, amin részt vettem. Mondjuk nem voltam még túl sok konferencián, de az öt-hatszáz résztvevő, majdnem 150 meghívott előadó azt hiszem amúgy sem nagyon gyakori. Öt napig tartott, délelőttönként 9-től plenáris előadások (a hét vége felé egyre lustább lettem ezekre felkelni), délután fél hétig öt párhuzamos szekció. Nem biztos, hogy a legjob taktikát választottam, mert szünetek beiktatása nélkül ültem be az előadásokra, és ennyi idő alatt nem igazán sikerült feldolgozni őket. Terveztem, hogy utólag átnézem az érdekesebb dolgokat, de erre – természetesen – még nem került sor.
Ott találkoztam Bennyvel is, adott némi olasnivalót a nyárra, de ebből csak a pszeudorandom gráfokról szóló survey-t volt időm elolvasni, ugyanis a későbbiekben is volt elfoglaltságom bőven.
SMiki szerzett nekem egy asztalt a Rényiben, úgyhogy napközben oda jártam matekozni. Például elolvastam a regularitási lemmáról szóló survey-jét, meg kezembe nyomott egy másik, félkész cikkét is, hogy olvassam át (az extremális gráfelméletről szólt). Közben találtam egy GyAndrás-cikket az arXivon, ami megtetszett. Fel is sétáltam hozzá, és mutattam neki két kisebb hibát a cikkében. A vége az lett, hogy elkezdtem vele gondolkodni a problémán, ami egyébként t-metsző hipergráfok erős c-színezéséről szólt.
Lényegében az a kérdés, hogy igaz-e, hogy ha egy halmazrendszer bármely két tagja legalább t elemben metszi egymást, akkor ki lehet az alaphalmaz elemeit színezni rögzített (csak t-től függő) mennyiségű színnel úgy, hogy minden halmaz legalább t+1 különböző színt tartalmazzon. (És mondjuk feltesszük, hogy minden halmaz legalább t+1-elemű.) Ha létezik ilyen színszám, akkor a legkisebbet χ(t,t+1)-gyel jelöljük (és általában χ(t,c) az, amikor legalább c színt szeretnénk minden halmazba). Andrásék bebizonyították, hogy χ(2,3)=5, de nagyobb t-re nem tudjuk, hogy χ(t,t+1) egyáltalán létezik-e. Ezzel egyelőre nem sikerült haladnunk, de azt bebizonyítottam, hogy χ(3,3)=4. Sajnos az a módszer sem tűnik használhatónak a többi esetben.
Aztán egyik pénteken felhívott Miki, hogy hétfőtől lesz az Emléktábla workshop, akarok-e menni. Én meg akartam. Ott találkoztam cambridge-i ismerősökkel, meg ismerkedtem másokkal is, végül pedig egy olyan kis csoportban gondolkoztam, amiben hatból csak ketten nem Béla diákjai voltunk. Első nap egy olyan problémát sikerült kiválasztani, amelyikben egyáltalán nem haladtunk egész nap. Második naptól viszont egy egészen kellemes problémakörrel foglalkoztunk: Van egy n-csúcsú G gráf, aminek van egy „hibás” éle. Rákérdezhetünk utakra, hogy tartalmazza-e a hibás élt, a lényeg pedig, hogy azt minél kevesebb kérdéssel határozzuk meg.
Persze rengeteg változatát lehet vizsgálni ennek a problémának, és sok helyes kis eredményt kaptunk is ily módon. Az elég hamar kiderült, hogy ha felhasználhatjuk a korábbi kérdések eredményét, akkor nem nagyon érdekes a dolog, mert kb. azzal egyenértékű, hogy hány úttal fedhető le G (ezt pedig elég jól meghatározták már korábban). Ha viszont „előre leírt kérdésekkel” dolgozunk, izgalmasabbá válik minden (pl. egyik kis helyes eredményünk, hogy fákra a minimális kérdésszám n/3 és 2n/3 között lesz, ahol ez a két korlát éles).
A legfontosabb és egyben legnehezebbnek tűnő kérdés hogy mi a felső korlát általános gráfra. Azt sejtjük, hogy lineáris sok ( O(n) ) kérdés elég. Ezt sok speciális esetben beláttuk, de általában csak az O(n log n)-et sikerült bizonyítanunk.
Hát itt tartok most, és nem sokára indulok is Zürichbe, úgyhogy jó eséllyel megint valami újjal fogok foglalkozni. Kivéve persze, ha visszatérek a telítettségi kérdéshez, amit nyáron egyáltalán nem néztünk.
