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!
