RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
Video Library
Archive
Most viewed videos

Search
RSS
New in collection





You may need the following programs to see the files






Workshop on Extremal Graph Theory
June 6, 2014 11:00, Moscow
 


Zero-one $k$-laws for $G(n,n^{-\alpha})$

M. Zhukovskii

Yandex
Video records:
Flash Video 818.2 Mb
MP4 818.2 Mb

Number of views:
This page:108
Video files:58


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

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

Abstract: We study asymptotical behavior of the probabilities of first-order properties for Erdős–Rényi random graphs $G(n,p(n))$ with p$(n)=n^{-\alpha}$, $\alpha \in (0,1)$. The following zero-one law was proved in 1988 by S. Shelah and J. H. Spencer [1]: if $\alpha$ is irrational then for any first-order property $L$ either the random graph satisfies the property $L$ asymptotically almost surely or it doesn't satisfy (in such cases the random graph is said to obey zero-one law. When $\alpha \in (0,1)$ is rational the zero-one law for these graphs doesn't hold.
Let $k$ be a positive integer. Denote by $L_k$ the class of the first-order properties of graphs defined by formulae with quantifier depth bounded by the number $k$ (the sentences are of a finite length). Let us say that the random graph obey zero-one law, if for any first-order property $L \in L_k$ either the random graph satisfies the property $L$ almost surely or it doesn't satisfy. Since 2010 we prove several zero-one $k$-laws for rational $\alpha$ from $I_k=(0, 1/(k-2)] \cup [1-1/(2^{k-1}), 1)$. For some points from $I_k$ we disprove the law. In particular, for $\alpha \in (0, 1/(k-2)) \cup (1-1/2^{k-2}, 1)$ zero-one $k$-law holds. If $\alpha \in \{1/(k-2), 1-1/2^{k-2}\}$, then zero-one law does not hold (in such cases we call the number $\alpha$ $k$-critical).
We also disprove the law for some $\alpha \in [2/(k-1), k/(k+1)]$. From our results it follows that zero-one 3-law holds for any $\alpha \in (0,1)$. Therefore, there are no 3-critical points in $(0,1)$. Zero-one $4$-law holds when $\alpha \in (0,1/2) \cup (13/14,1)$. Numbers $1/2$ and $13/14$ are $4$-critical. Moreover, we know some rational $4$-critical and not $4$-critical numbers in $[7/8,13/14)$. The number $2/3$ is $4$-critical. Recently we obtain new results concerning zero-one $4$-laws for the neighborhood of the number $2/3$.

Language: English

Website: http://tech.yandex.ru/events/workshops/msk-jun-2014/talks/1911

References
  1. S. Shelah, J.H. Spencer, “Zero-one laws for sparse random graphs”, J. Amer. Math. Soc., 1 (1988), 97–115  crossref  mathscinet  zmath


SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Contact us:
 Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020