Videolibrary
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 13:30, Moscow
 


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
Video records:
Flash Video 840.1 Mb
MP4 840.1 Mb



Abstract: 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.


Language: English

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

References
  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. Problems Inform. Transmission, 47:3 (2011), 251–268  mathnet  crossref  mathscinet  isi  scopus
  4. Problems Inform. Transmission, 50:1 (2014), 57–78  mathnet  crossref  mathscinet  zmath  isi  scopus
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024