Egy permutációcsoport minimális foka az a szám, hogy minden az egységelemtõl különbözõ elem legalább annyi pontot mozgat el. A minimális fokra vonatkozóan már a múlt században született alsó becslés, ha a csoportról kikötjük, hogy primitív, és erõsebb becslés, ha G 2-tranzitív is, (és nem tartalmazza A_n-et). Primitív, de nem 2-tranzitív csoportra (uniprimitív csoportok) Babai adott éles becslést 1981-ben, konstanstól eltekintve legalább gyök n a minimális fok. Ennek a bizonyításnak a Pyber által egyszerûsített változatát ismertetem. A bizonyítás csak elemi gráfelméletet használ, miután koherens konfigurációkra átfogalmazza a problémát. A kapott becslésbõl, a Lovász lokális lemma felhasználásával kijön az is, hogy minden uniprimitív n-edfoku permutációcsoportnak van 4*gyök n*logn-nél kisebb bázisa (egy olyan ponthalmaz, amit csak az egységelem hagy pontonként fixen). A bázismeretnek jelentõsége van a különbözõ számításoknál, hiszen a szerint már meg tudjuk különböztetni a csoportelemeket, hogy a bázist mibe viszik (igy például minimális generátorrendszer-keresõ algoritmusoknál elég csak ezt "számontartani"). Ez alapján nyerünk egy felsõ becslést uniprimitív permcsoportok rendjére is.

A permutációcsoportok állítólag attól élik reneszánszukat, hogy a véges egyszerû csoportok klasszifikációját elfogadva rengeteg új dolgot lehetett róluk bizonyítani. Az ismertetendõ bizonyításoknak viszont épp az a szépségük, hogy bepillantást engednek a "színfalak mögé", és klasszifikació nélkül hoznak ki hasonló - vagy valamivel gyengébb - aszimptotikus becsléseket.

Minden érdeklõdõt szeretettel várunk,

Péter