Colloquium Mathematics - Prof. M.Noy

Title: Logic and random graphs

Abstract:
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 satisfies 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
aspects.