Apie mato koncentraciją grafų sandaugoje
Straipsniai
Matas Šileikis
Institute of Mathematics and Informatics
Publikuota 2009-12-20
https://doi.org/10.15388/LMR.2009.78
PDF

Reikšminiai žodžiai

grafų sandauga
diskrečios izoperimetrinės nelygybės
mato koncentracija
nepriklausomų atsitiktinių dydžių sumos
uodegų tikimybės
didieji nuokrypiai

Kaip cituoti

Šileikis , M. (2009) “Apie mato koncentraciją grafų sandaugoje”, Lietuvos matematikos rinkinys, 50(proc. LMS), pp. 443–448. doi:10.15388/LMR.2009.78.

Santrauka

Bollobás ir Leader[1] parodė, jog tarp n jungių k-osios eilės grafų sandaugų didžiausių amato koncentraciją  turi n-matės gardelės grafas. Jei aibė A turi pusę grafų sandaugos viršūnių, tai viršūnių, esančių nuo  A ne arčiau kaip per t, skaičius yra aprėžtas tikimybe P(X1 + . . . + X\geq   t), kur Xi – tam tikri paprasti n.v.p. atsitiktiniai dydžiai. Bollobás ir Leader naudodami momentų generuojančią funkciją gavo eksponentinį  įvertį. Naudodami kiek subtilesnę techniką  `(plg. [3]), mes pagerinome įverčio eilę, įterpdami trūkstamą daugiklį.  

PDF

Atsisiuntimai

Nėra atsisiuntimų.