(Szerző)társasan szép az élet

Dolgozunk. Többször használtam többes számot, és ez esetemben nem királyi. Könnyebben tudok dolgozni másokkal. Persze nem mindegy, kivel, az összehangolt munkához meg kell találni a számunkra megfelelő partner(eke)t. Nem mindenkire, de sokakra igaz ez: egyedül nehezebben megy. Ismerek olyat is, aki egyedül is rendkívül termékeny kutatási szempontból, de ő kisebbségben van az ismerőseim között e tekintetben.
Tehát gyorsabban megy a munka, ha megosztjuk. Általában. Most éppen hátráltat, hogy nem egyedül csinálom (bár csinálhatnám, semmi nem tart vissza, próbálkozok is), mivel időnként nem árt megkonzultálni a tények állását, és így nyáron, főleg klímaszünetben ezt nehézkes összehozni. De általában erősen motivál, hogy én is hozzátegyek, haladjak, mit szól a másik, ne mondjam már neki, hogy ötletem sincs, megakadtam.

Hogy kezdődik ez? PhD hallgatóknál általában a témavezetővel, ideálisabb esetben a témavezető más témavezetettjeivel is kezdünk együtt dolgozni (azért ideálisabb, mert szimmetrikusabb a viszony velük). Aztán megismerkedünk a témavezetőnk más társszerzőivel, szerencsés esetben velük is elkezdünk dolgozni, konferenciákra járunk, ott ismerkedünk, és számos más lehetőség is megnyílik idővel. Matematikában ideálisan 2-4 (esetleg 5) ember szokott tudni jól együtt dolgozni, egyedül sokaknak lassan megy, több ember munkáját pedig nehézkesebb összehangolni (már 2 esetén sem egyszerű, a kutatók számának növelésével egyre nehezedik, itt nem kísérleteket végzünk, ahol ki lehet osztani a jól körülírt részfeladatokat, bár ilyesmi is előfordulhat, ha esetekre bontható az adott kutatás kérdése). Időnként előfordul, hogy több szerzős cikk jelenik meg, ilyet pl. extrém esetben egy konferencián összejött társaság dobja össze és egyikük leírja, de találkoztam olyannal is, hogy közel ugyanabban az időben több szerzőtársaság hozta ki ugyanazt az eredményt, és végül közösen írták le.

De én most itthon ülök és a újabb problémával próbálok foglalkozni, de nem motivál, hogy a szerzőtársamat nehezen érem el. a szakirodalmat már elkezdtük együtt átnézni, már a problémát is kitűztük. Máskor volt olyan is, hogy villámgyorsan, napok alatt volt eredmény, amikor intenzíven dolgoztunk (más munkatársammal pedig évekig elbeszélünk egymás mellett, mert valahogy nem sikerült megtalálni a közös nyelvet, csak mostanában kezdem végre érteni, miről beszél). Megosztottuk a feladatokat, egymás eredményeit vittük előre vagy éppen cáfoltuk meg, mindenki azt a részt vállalta, amiben jó, ez nagyon gördülékenyen tud menni egy összekovácsolódott csapatban. Persze nem nyáron. Most hetekig nincs alkalmunk találkozni, így van időm töprengeni a feladaton. El-elmerengek rajta időnként, de kicsúszik a kezeim közül, mint egy nyálkás hal, pedig érdekes, nem túl nehéznek tűnő probléma. Amiből esetleg még PhD-téma is születhet. Csak meg kéne szülni valakinek...

Kikacsintás

Eddig, mint a második posztban írtam, leginkább az online problémák elutasításos változatával foglalkoztam. Most felkeltette az érdeklődésemet az ún. advice complexity (nem ismerek rá magyar kifejezést). A fogalom a bonyolultságelméletből jön, az érdekli a kutatókat, hogy adott bonyolultsági osztályba mely problémák esnek ha kaphatnak plusz biteket, és mennyit az input hosszának függvényében (akinek ez zavaros, nézze meg a linket). Az online algoritmusokba is beemelhetjük a advice string fogalmát és megfogalmazhatunk olyan kérdéseket, hogy mennyi advice bit szükséges, hogy az online algoritmus elérje az optimális költséget, vagy adott c-re c-versenyképességet érjünk el. Approximációs sémákat is megfogalmaznak: tetszőleges ε esetén 1+ε versenyképességre törekednek minél kevesebb advice bit felhasználásával.
A modell önmagában is érdekes, bár sok kérdést már megoldottak benne (k-szerverre, ládapakolásra, ütemezésre, gráfszínezésre, stb., bár még bőven hagytak nyitva is), de ha kombináljuk meglévőekkel (pl. az elutasításos modellel), akkor lehetőségek széles skálájával találjuk szembe magunkat. Még mi sem tudjuk, hol kezdjük, ez a bőség zavara :)

Beszámoló a CSM-ről

A konferencia címe CSM - The Third Conference of PhD Students in Mathematics. Nem kell hozzá sokat tudni angolul, hogy rájöjjünk, elsősorban PhD hallgató voltak ott (meg hallgatók, meg fiatal kutatók).
A konferencia fő célja, hogy a fiatal kutatópalánták első szárnypróbálgatásának helyszíne legyen, hasonlóan izguló és tapasztalatlan társaik előtt mondják el először eredményeiket, ne a szakma legjelesebb képviselőinek. Másrészt célja az egymással és egymás témájával való ismerkedés, azaz szakmai kapcsolatteremtés is. Ezt segíti, hogy némiképp témák köré szerveztük a szekciókat (általában így szokták, szervezéskor mi is odafigyeltünk erre), így közel egy időben beszéltek a hasonló témával foglalkozók, lehetőségük volt egymástól kérdezni, észrevételeket, javaslatokat tenni. Persze hasznos távolabbi területek képviselőivel is kapcsolatot tartani (éppen a napokban segítettem ki kombinatorikai bizonyítással egy differenciálegyenletekkel foglalkozó kollégámat), erre is megfelelő terep ez a konferencia.

A rendezvényen a differenciálegyenletek témája túlsúlyban volt, köszönhetően a nálunk ezzel a témakörrel nagy számban foglalkozó PhD hallgatónak és fiatal kutatónak. Volt ezen felül két-két szekciónyi algebra és geometria témájú előadás, egy sztochasztika és egy kombinatorika szekció. Bár némelyeknél érezhető volt az izgalom, a konferencia jellegéhez képest meglepően színvonalas előadásokat lehetett hallani -- bár tény, sokuknak valójában ez már nem az első konferencia előadása volt. Mivel sok előadás volt, ezeket nem részletezem, a konferencia honlapján megtalálhatóak az absztraktok, az előadások nem tartogattak ezekhez képest nagy meglepetéseket.

Az utolsó nap vége felé én is előadtam a legfrissebb eredményünket. Korábbi posztban írtam róla, hogyan készültem az előadásra, és valamennyit magáról a konferenciáról is. Az előadások 25 percesek voltak (kivéve a meghívott előadókét, akik 50-50 percet beszéltek), plusz 5 percet hagynak az előadás utáni kérdéseknek. Ezt kicsit hosszúnak tartottam, és nem voltam ezzel egyedül. Mivel nem a szűk szakterület képviselőinek beszéltem, részletesebb bevezetőre volt szükség, hogy értsék, miről beszélek, és így már nem is jutott olyan sok idő a tényleges eredményekre. Ezek felsorolásán felül azért még belefért egy rövid bizonyítás és egy ábrán szemléltetett bizonyítás vázlat.

A másik oldalba -- mint céloztam rá, a szervezők között voltam én is -- érdekes volt belelátni. Bár a sok kommunikációt igénylő feladatokat (meghívások, jelentkezések fogadása, résztvevőkkel kommunikálás, szállás, vacsora szervezése, szponzorok megkeresése, helyszín szervezése) nem láttam el, inkább szerkesztési munkákat (weblap, program, stb.), azért ezekre némi rálátásom nyílt, láttam, mennyi részletre kell figyelni, mik okozhatnak problémát, ezeket hogyan lehet orvosolni, illetve legközelebb kiküszöbölni. 

Konferenciára készülve

Beérett az első gyümölcse a legutóbbi, színezéssel kapcsolatos munkának, amiről egy korábbi posztban írtam. A héten konferenciára megyek, ott fogom előadni egyelőre a full edge modellben elért eredményeket (az összes eddigi eredmény egy cikkben is benne lesz, ez egyelőre folyamatban van). Ezeket egy absztraktban foglaltam össze, amit már a konferenciára jelentkezéskor el kellett küldeni. A konferencia hallgatóknak és PhD hallgatóknak lesz szervezve, de előadnak rajta fiatal kutatók is. Ez megint olyan típusú konferencia, amely nem szűk téma köré szerveződik (erről korábbi posztban írtam). A célja az egymással és egymás témájával való ismerkedés. Másrészt azért is különleges ez a konferencia, mert két oldalát látom: azon túl, hogy előadok rajta, szervezője is vagyok. Érdekes belelátni a részletekbe és nehézségekbe, amikkel egy konferencia szervezése jár. De mivel ez már messze esik a blog témájától, talán máshol, máskor írok róla.
Az előadás 25 perces lesz, plusz 5 percet hagynak az előadás utáni kérdéseknek. Ez kicsit hosszú, általában (legalábbis a saját mintavételezésem alapján) kevesebb időt adnak, ami nem nagyon teszi lehetővé a részletekbe menő előadást. Itt viszont lehetőség van néhány, de természetesen nem minden finomság megmutatására, ami elgondolkodtat, hogy miből mennyit és hogyan mondjak el. Csökkenti a szabadságfokot, hogy nem a szűk szakterület képviselőinek fogok beszélni, így részletesebb bevezetőre lesz szükség, hogy értsék, miről beszélek. Így már nem is jut olyan sok idő a tényleges eredményekre. De még így is belefér egy rövid bizonyítás és egy ábrán szemléltetett bizonyítás vázlat. De leginkább csak a fő eredmények felsorolására van idő. Azt szokták mondani, hogy minden előadásba kell egy bizonyítás és egy vicc, és fontos, hogy a kettőt meg lehessen különböztetni. Hozzátenném ehhez, hogy hasznos, ha az előadás szemléletes, és segíti a figyelem fenntartását, ha az egész előadás humoros, vagy legalábbis nem csak egy vicc van benne (az enyémre ez utóbbi nem fog teljesülni, remélem, az előbbi igen). Mostanában az előadásokat nem táblán tartják és az írásvetítő is elvétve kerül elő már (bár hasznos azon IS kivetíteni a definíciókat, hogy folyamatosan szem előtt legyenek, segítve a megértést), hanem diákat csinálnak, általában pdf vagy ppt formátumban. A matematikusok a latexben beamer csomag használatával generált pdf-et preferálják, én is ezt teszem. Az előadásfóliák már elkészültek, most átgondolom, melyiknél mit fogok mondani. Erre azért van szükségem, mert még nem sok ilyenfajta előadást tartottam, nagyobb gyakorlattal, ezt már nem szokták megtenni, sőt, a tapasztaltabbak a diákat is a helyszínen dobják össze nem sokkal az előadásuk előtt ;)
A konferencia után jelentkezek egy beszámolóval, utána rátérek a következő témára.

Színezzünk!

Három hónap szabadság után lássuk, hol is tartunk.

Legutóbbi nyitott problémákkal foglalkozó bejegyzésben írtam hipergráfszínezésről is. Itt is erről lesz szó, de ezennel csökkenteni fogom a nyitott kérdések számát olyanok megválaszolásával, amelyeket a közelmúltban sikerült megoldani (nem megyek részletekbe, mivel ezek publikálatlan eredmények egyelőre). Nyugalom, azért marad bőven még :)

Több modell lesz. A leírt színezések (tarka, conflict-free és a nem egyszínű) rögtön háromszorozzák ezek számát. Az egyik megközelítés, amelyet mi vizsgáltunk, azt feltételezi, hogy egy élet csak akkor látunk meg, ha minden csúcsa megérkezett, előtte semmilyen információnk nincs róla. Lehet más modelleket is definiálni (és mivel ezeket nem vizsgálták, mégiscsak bővítem a nyitott problémák körét), amelyben egy él nyomát látjuk az eddig érkezett csúcsok halmazán, esetleg tudjuk az adott élről, hogy minden csúcsa megérkezett-e már (ez így már több információ, mint amit a mi modellünkben az algoritmus kap).

Eddig még nem volt szó elutasításról. Ha az is belép a képbe, akkor megint kétféle megközelítést vehetünk:
1. full edge (teljes él) modellnek nevezzük, ha csak azokat az éleket kell helyesen színezni (az adott színezés szerint), amelyeknek egyetlen csúcsát sem utasítottuk el. Ebben a modellben a nem egyszínű színezésbeli eredmény a legérdekesebb: azt mondja, általánosságban nem lesz lényegesen több a versenyképességi hányados, mint az elutasítás nélküli esetben (n/2 felsőegészrésze). Miért érdekes ez? Mert általában rosszabb, legtöbbször egy 2-es szorzó jön be. A conflict-free színezésnél már más (az aszimptotikusan éles (n-1)/φ+1, ahol φ az aranymetszés arányszáma) korlát jött ki, mint az elutasítás nélküli esetnél, a tarkával pedig nem foglalkoztunk, mivel nem tűnt érdekesnek, gondoljuk csak meg: minden online tarka színező algoritmus úgy működik, hogy nem használja kétszer ugyanazt a színt.

2. trace (nyom) modellnek nevezzük, ha minden élnek az elfogadott csúcsokon vett nyomáról követeljük meg, hogy helyesen legyenek színezve. A modell érdekessége, hogy az előzővel ellentétben itt ha valamelyik színt kétszer használja az algoritmus, akkor a további csúcsok elfogadására kényszeríthető. Másik érdekesség, hogy itt együtt tudtuk kezelni a nem egyszínű és a conflict-free színezést, azonos (aszimptotikusan éles) korlát ((n-2)/φ+2) jött ki. Tarka színezéssel itt sem foglalkoztunk.

Rengeteg nyitott kérdés maradt az általunk vizsgált modellekben (pl. speciális hipergráfosztályokra vonatkozó korlátok), hát még azokban, amiket nem vizsgáltunk!

Gráfszínezés elutasítással

Új témába kellene kezdeni. Először -- amint erről már volt szó -- miután választottunk egy szimpatikus témát (színezés), megnézzük a szakirodalmat. Az, hogy mi a szimpatikus téma, a szakirodalom is meghatározza. Nem csak úgy, hogy az alapján ismerjük meg a kérdéseket és a technikákat, hanem azzal is, hogy látjuk, az általunk vizsgálni kívánt kérdést megoldotta-e valaki, ha nem, mekkora lépést tettek már meg a megoldás irányába. Például egy dolog, hogy kigondoltam, hogy az online klaszterezés elutasításos változatával szeretnék foglalkozni, de kiderült, hogy aminek épp nekiálltam volna, azt korábban valaki már kiszámolta. Így még mindig kevésbé fájdalmas, mint amikor már a kész cikket beküldve derül ez ki... Így hát elkanyarodtam a színezések felé, és ezek után ért a kellemes meglepetés: bár a gráfszínezés népszerű téma, ezen a területen még szinte szűz: csak egy eredmény van, Epstein és mtasi-é, amely szerint Δ+3-versenyképességet el lehet érni, de jobbat nem (Δ itt a gráf maximális foka). Az algoritmus ötlete egyszerű: amíg az összes eddigi büntetés el nem éri 1-et, elutasítunk mindent, utána pedig a mohó First Fit algoritmust futtatjuk büntetéstől függetlenül. Elsőre furcsa, de kicsit belegondolva természetes ötlet, ha nem szeretnénk, hogy az algoritmust nagyon be lehessen csapni. A másik alapötlet az elutasításos modellekben az lehet, hogy keresünk egy threshold értéket, az annál kisebb büntetésűeket elutasítjuk, a nagyobb büntetésűekre pedig valamilyen ügyes algoritmust alkalmazunk. Mivel sem gráfokra, sem hipergráfokra nincs még sok eredmény, viszont a terület eredménnyel kecsegtet, ennek érdemesebb nekivágni.

Decemberi terméketlenség

Előző hónap eleje óta nem volt új poszt, ennek több oka van. Vagyis egy: nem történt semmi. Aztán arra gondoltam, hogy mégis meg kell írni ezt. Mármint hogy nem történt semmi. Merthogy a matematikai kutatásban ez előfordul, hogy nem halad előre. És ugyan kevés idő jutott a kutatásra a szorgalmi időszak hajrája, a vizsgaidőszak kezdete és az ünnepek miatt, mégsem ez a fő ok. Hanem az, hogy néha hiába számol az ember, nem jön ki, amit szeretne. Sőt, nem jön ki semmi. Itt is ez történt. Kitalálok egy algoritmust (online színezéses probléma), próbálom elemezni. Első nekifutásra nem jön ki semmi értelmes versenyképességi hányados. Próbálom máshogy, ez sem jön ki. A harmadik megközelítés sem jobb. Ekkor váltok, felfrissülésképp alsó korlátot próbálok bizonyítani, de nem jön ki a triviális 1 korlátnál jobb (ugye minden online algoritmus legalább 1-versenyképes). Próbálom máshogy, az sem jó. Visszatérek a másik oldalra, kitalálok egy másik algoritmust, azt próbálom elemezni, és így tovább... Ezt ismételtem 3-4-szer (természetesen több nap ment rá), majd feladtam. Egy időre. Ilyenkor néha hasznos, ha pihentetjük a témát egy kicsit, majd később elővesszük, hátha addigra leülepszik bennünk a probléma és új ötletünk támad. Addig meg csinálunk valami mást. Például sorra vesszük a nyitott problémákat, hátha találunk köztük egy szimpatikusat. Később, ha visszatérek rá, beszámolok az eredményről.