A téma rövid leírása: Egy adott $n$ változós Boole-függvény értéket szerétnénk kiszámítani egy ismeretlen helyen. Ehhez persze információt kell szereznünk az inputról. Esetunkben egy kérdésünk egy bitje az inputnak. Mi az a minimális szám, ahány kérdéssel garantáltan boldogulunk? $n$ természetesen elég, hisz ennyi kérdéssel az egész inputot megismerjük. Sok függvény esetén $n$-nél kevesebb kérdés nem elég. Ezeket nevezzük zárkózottaknak.
Sok-sok zárkozott függvény ismert (lásd Bollobás: Extremal graph theory könyvének utolsó (Packing and complexity) fejezete). Igazából egész függvényosztályokról szeretnénk tudni, hogy elemei mind zárkózottak. Egy jelölt: Nem triviális, monoton gráftulajdonságok. A fentiekben leírt állítás az úgy nevezett Aandreaa-Rosenberg-Karp-sejtés. Mind a mai napig megoldatlan.
Ebben a témában a fõeredmény egy Kahn-Saks-Sturtevant cikk, amely a fenti sejtést igazolja, ha a gráf csúcsainak száma prímhatvány. A cikk topológiai módszerekkel dolgozik. Egy monoton Boole-függvény könnyen azonosítható egy szimpliciális komplexussal. A zárkózottság könnyen approximálható topológikus tulajdonságokkal, mint kollapszálhatóság, kontrahálhatóság ...
Ezt a módszert szeretném bemutatni és azt a néhány eredményt leírni, amelyek a Kahn-Saks-Sturtevant cikk után történtek.
Minden érdeklõdõt szeretettel várunk,
Péter