

Colloquium of the Steklov Mathematical Institute of Russian Academy of Sciences
September 7, 2017 16:00, Moscow, Steklov Mathematical Institute of RAS, Conference Hall (8 Gubkina)






Logic of binomial random graphs
M. E. Zhukovskii^{ab} ^{a} Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region
^{b} Peoples Friendship University of Russia, Moscow

Video records: 

MP4 
2,509.0 Mb 

MP4 
687.5 Mb 
Number of views: 
This page:  293  Video files:  65  Youtube Video:  
Photo Gallery

Abstract:
In the talk, we will focus on graph properties that can be expressed in
terms of first order and second order logics. For example, the
properties of contating a triangle and being complete are of first
order, and the properties of being connected and having even number of
vertices are of second order. Probabilities of such properties (for the
binomial, or ErdosRenyi, random graph) are of interest since 1960 when
the seminal paper of Erdos and Renyi was published. In 2001, J. Spencer
reviewed known results concerning first order properties of random
graphs in his survey "Strange logic of random graphs". A classic result
in the area called "zeroone law" states that a probability of either
firstorder property approaches 0 or 1. This result was proved in 1969
by Glebskii, Kogan, Liogon'kii and Talanov (and independently by Fagin
in 1976). Since 2001, many results concerning both first order and
second order properties were obtained. There is a number of nice
conjectures that are still open.

