Skip to ContentSkip to Navigation
Research Bernoulli Institute Calendar

Colloquium Mathematics - Prof. M.Noy

When:Tu 26-02-2019 16:00 - 17:00
Where:5161.0293 Bernoulliborg

Title: Logic and random graphs

A well-known theorem from the 1960s says that for any property of
graphs A expressible in first order logic, the probability that a
random graph with N vertices satis
es A tends either to 0 or to 1 as N
goes to infinity. This result has been widely extended in several
directions, either considering logics with more expressive power, or
different models of random graphs. In the talk we will survery several
results in the area, including recent ones on planar graphs and graphs
on surfaces. The talk will be self-content with respect to the logic