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 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:239
Video files:78



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: https://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
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024