Az Erdős-Rényi gráf kritikus exponense martingálokkal

Ráth Balázs előadásának absztraktja

2007. február 22. csütörtök 16:15

 
 
Ha egy N pontú gráf éleit egymástól függetlenül 1/N valószínűséggel húzzuk be, akkor a legnagyobb összefüggő komponens mérete kb. N2/3 nagyságú. Erre a klasszikus eredményre talált új  bizonyítást (és explicit korlátokat) Asaf Nachmias és Yuval Peres. Minden eddiginél egyszerűbb bizonyításuk központi objektuma egy (a véletlen gráf szélességi bejárásából származtatható) martingál.

 
Balázs Márton, 2007.01.31