Slumpmässiga grafers konstiga logik

The Strange Logic of Random Graphs är en bok om noll-ett-lagar för slumpmässiga grafer . Den skrevs av Joel Spencer och publicerades 2001 av Springer-Verlag som volym 22 av deras bokserie Algorithms and Combinatorics .

Ämnen

Bokens slumpmässiga grafer är genererade från Erdős–Rényi–Gilbert-modellen $G(n,p)$ där $n$ hörn ges och ett slumpmässigt val görs om att ansluta varje par av hörn med en kant, oberoende för varje par, med sannolikhet $p$ att göra en anslutning. En noll-ett-lag är ett teorem som anger att för vissa egenskaper hos grafer, och för vissa val av ${\displaystyle p},$ tenderar sannolikheten att generera en graf med egenskapen att vara noll eller ett i gränsen som ${\ displaystyle n}$ går till oändlighet.

Ett grundläggande resultat på detta område, bevisat oberoende av Glebskiĭ et al. och av Ronald Fagin , är att det finns en noll-ett-lag för $G(n,1/2)$ för varje egenskap som kan beskrivas i första ordningens logik av grafer . Dessutom är den begränsande sannolikheten en om och endast om den oändliga Rado-grafen har egenskapen. Till exempel innehåller en slumpmässig graf i denna modell en triangel med sannolikhet som tenderar mot ett; den innehåller en universell vertex med sannolikhet som tenderar mot noll. För andra val av $p$ kan andra utfall inträffa. Till exempel är den begränsande sannolikheten för att innehålla en triangel mellan 0 och 1 när $p=c/n$ för en konstant $c$ ; den tenderar till 0 för mindre val av $p$ och till 1 för större val. Funktionen $1/n$ sägs vara en tröskel för egenskapen att innehålla en triangel, vilket betyder att den skiljer värdena på $p$ med begränsande sannolikhet 0 från värdena med begränsande sannolikhet 1 .

Huvudresultatet av boken (bevisat av Spencer med Saharon Shelah ) är att irrationella krafter hos $n$ aldrig är tröskelfunktioner. Det vill säga, när $a>0$ är ett irrationellt tal , finns det en noll-ett-lag för första ordningens egenskaper för de slumpmässiga graferna $G(n, n^{-a})$ . Ett nyckelverktyg i bevisningen är Ehrenfeucht–Fraïssé-spelet .

Publik och mottagning

Även om det i huvudsak är beviset för en enda sats, riktad till specialister inom området, är boken skriven i en läsbar stil som introducerar läsaren till många viktiga ämnen inom finita modellteori och teorin om slumpmässiga grafer . Recensenten Valentin Kolchin, själv författare till en annan bok om slumpmässiga grafer, skriver att boken är "fristående, lättläst och kännetecknas av elegant skrift", och rekommenderar den till sannolikhetsteoretiker och logiker . Recensenten Alessandro Berarducci kallar boken "vackert skriven" och dess ämne "fascinerande".