What is … the random graph?

Video

Abstract

The Random graph can be defined on the set of natural numbers: For each pair (i,j) a flip coin 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.

We will define the graph and use it to show the so called 0-1-laws.

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.

The Random graph has been studied in different setups, under different angles and in different disciplines. If there is time left, I will present some results in Combinatorics. That is, we will consider colorings of edges and vertices of the Random Graph.

Comments