Forthcoming seminars
Seminar calendar
List of seminars
Archive by years
Register a seminar

Forthcoming seminars

You may need the following programs to see the files

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. Zhukovskiiab

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:724
Video files:220
Youtube Video:

M. E. Zhukovskii
Photo Gallery

Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке

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 Erdos-Renyi, 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 "zero-one law" states that a probability of either first-order 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.

SHARE: FaceBook Twitter Livejournal
Contact us:
 Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020