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

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






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


Zero-one $k$-laws and extended zero-one $k$-laws for random distance graphs

S. Popova

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Видеозаписи:
Flash Video 840.1 Mb
MP4 840.1 Mb

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



Аннотация: Studying zero-one laws for random graphs was initiated by Glebskii Y. et al. in [1]. In this work the authors proved the zero-one law for Erdös-Rényi random graph $G(n,p)$. Later S. Shelah and J. Spencer expanded the class of functions $p(n)$, for which $G(n,p)$ follows the zero-one law (see [2]). Zero-one laws for random distance graphs have been considered for the rst time by M. Zhukovskii (see [3]). In [4] we studied the zero-one law for a more general model of random distance graphs.
Let $\{G_n=(V_n, E_n)\}^{\infty}_{n-1}$ be a a sequence of distance graphs and $p=p(n)$ be a function of $n$. The random distance graph $G(G_n,p)$ is the probabilistic space $(\Omega_{G_n}, F_{G_n}, P_{G_{n}p})$, where
\begin{gather*} \Omega_{G_n}=\{G=(V,E):V=V_n, E \subseteq E_n\}, \\ F_{G_n}=2^{\Omega_{G_n}}, F_{G_{n,p}}(G)=p^{|E|}(1-p)^{|E_n|-|E|}. \end{gather*}
We say sequence $G(G_n, p)$ follows zero-one $k$-law if for any first-order property $L$ with quantier depth at most $k$ the probability $P_{G_{n},p}(L)$ of the event "$G(G_n,p)$ possesses property $L$" tends either to $0$ or to $1$ as $n \to \infty$. We say sequence $G(G_n, p)$ follows extended zero-one $k$-law if for any first-order property $L$ with quantier depth at most $k$ any partial limit of the sequence $\{P_{G_{n},p}(L)\}^{\infty}_{n=1}$ equals either $0$ or $1$.
We obtain conditions on the sequence $\{G_n\}^{\infty}_{n=1}$ under which one of the following three mutually exclusive cases occurs:
  • zero-one k-law holds;
  • zero-one k-law doesn't hold, but extended zero-one k-law holds;
  • extended zero-one k-law doesn't hold.


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

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

Список литературы
  1. Y. V. Glebskii, D. I. Kogan, M. I. Liagonkii, V. A. Talanov, “Range and degree of realizability of formulas the restricted predicate calculus”, Cybernetics, 5 (1969), 142154  crossref  scopus
  2. S. Shelah, J. H. Spencer, “Zero-one laws for sparse random graphs”, J. Amer. Math. Soc., 1 (1988), 97115  crossref  mathscinet  zmath
  3. М. Е. Жуковский, “О последовательности случайных дистанционных графов, подчиняющейся закону нуля или единицы”, Пробл. передачи информ., 47:3 (2011), 39–58  mathnet  mathscinet; Problems Inform. Transmission, 47:3 (2011), 251–268  crossref  mathscinet  isi  scopus
  4. С. Н. Попова, “Закон нуля или единицы для случайных дистанционных графов с вершинами в $\{-1,0,1\}^n$”, Пробл. передачи информ., 50:1 (2014), 64–86  mathnet  mathscinet  zmath; Problems Inform. Transmission, 50:1 (2014), 57–78  crossref  mathscinet  zmath  isi  scopus
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024