## the random graph?

Who?
Stefanie Frick (FU Berlin)
When?
2008/10/24
Where?
at FU Berlin
The random graph can be defined on the set of natural numbers: For each pair $(i,j)$ a coin flip decides whether or not the two numbers are connected with an edge. The resulting graph is universal in the sense that every countable graph is contained as an induced subgraph.
If the probability that a graph on $n$ nodes has a given property converges to 1 (for increasing $n$), we say that the property applies 'almost for all'. If the probability converges to 0, we say the property applies 'almost never'. The 0-1-law states the rather surprising fact that for all first order order statements always one of the two cases applies. The elegant and for a general audience accessible proof will be presented. It combines logical arguments (Gödelian completeness, compactness) with probabilistic considerations.