  RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  Video Library Archive Most viewed videos Search RSS New in collection

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  Видео не загружается в Ваш браузер: Активируйте JavaScript в Вашем браузере Установите Adobe Flash Player Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080 Сообщите администратору портала о данной ошибке

Abstract: We study asymptotical behavior of the probabilities of first-order properties for Erdős–Ré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 : 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   SHARE:       Contact us: math-net2020_02 [at] mi-ras ru Terms of Use Registration Logotypes © Steklov Mathematical Institute RAS, 2020