Видеотека
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления






Workshop on Extremal Graph Theory
6 июня 2014 г. 11:00, г. Москва, Московский офис Яндекса, ул. Льва Толстого, д. 16
 


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

M. Zhukovskii

Yandex
Видеозаписи:
Flash Video 818.2 Mb
MP4 818.2 Mb

Количество просмотров:
Эта страница:239
Видеофайлы:78



Аннотация: 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$.

Язык доклада: английский

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

Список литературы
  1. S. Shelah, J.H. Spencer, “Zero-one laws for sparse random graphs”, J. Amer. Math. Soc., 1 (1988), 97–115  crossref  mathscinet  zmath
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024