Véletlen multigráfok limeszeinek időfejlődése

2008. november 20. csütörtök 17:15

Rögzített, pozitív élsűrűségű, csúcs-felcserélhető véletlen multigráfok sorozata eloszlásban konvergál, amint n, a csúcsszám végtelenhez tart, ha tetszőleges fix k-ra az első k csúcs által feszített véletlen részgráf eloszlásban konvergál.

A dinamika: egy lépésben egy egyenletesen választott él egyik végpontját átkötjük, az új végpontot a "linear preferential attachment" szabályai szerint választjuk.

A gráflimesz időfejlődését két különböző időskálán figyeljük:

• ha X_n(t)=A(t*n², i, j), ahol A(T, i, j) az adjacenciamátrix (i, j)-edik eleme a T-edik lépés után, akkor X_n(t) egy születési-halálozási folyamathoz konvergál, amint n tart végetlenhez.
• ha Y_n(t)=(1/n)*D(t*n³, i), ahol D(T, i) az i-edik csúcs fokszáma a T-edik lépés után, akkor Y_n(t) egy C.I.R. folyamathoz konvergál, amint n tart végtelenhez.