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.