Hajnal Péter: Expanderek
Egy páros gráf (I es O azonos meretû színosztályokkal) (n,d,c)-expander, ha |I|=n, G maximális foka d, és I minden nem túl nagy (legfeljebb I méretének fele) R részhalmazának szomszédsága legalább c-szerese R méretének. A teljes gráf például egy nagyon jó expander (c viszonylag nagy), de d is nagy. Léteznek olyan páros gráfsorozatok, ahol n->\infty, d konstans és c 1-nél nagyobb konstans.
Ilyen gráfsorozatok konstruálása nagyon fontos téma, rengeteg alkalmazással. A konstrukciók nem elemiek, igen mély eszközöket igényelnek. Errõl nem lesz szó (a szeminárium következõ elõadásának egyik célja ezeknek a nem elemi eszközöknek a vázolása).
Csupán az alaperedményeket bizonyítjuk és néhány alkalmazásra világítunk rá. Ami remélhetõleg lesz:
Minden érdeklõdõt szeretettel várunk.
Péter