Paper Info
Title
Short monadic second order sentences about sparse random graphs.
Abstract
In this paper, we study zero-one laws for the Erdos-Renyi random graph model G(n,p) in the case when p = n(-alpha) for alpha > 0. For a given class K of logical sentences about graphs and a given function p = p(n), we say that G(n,p) obeys the zero-one law (w.r.t. the class K) if each sentence phi is an element of K is either asymptotically almost surely (a.a.s.) true or a.a.s. false for G(n,p). In this paper, we consider first order properties and monadic second order properties of bounded quantifier depth k, that is, the length of the longest chain of nested quantifiers in the formula expressing the property. We call zero-one laws for properties of quantifier depth k the zero-one k-laws. The main results of this paper concern the zero-one k-laws for monadic second order (MSO) properties. We determine all values alpha > 0, for which the zero-one 3-law for MSO properties does not hold. We also show that, in contrast to the case of the 3-law, there are infinitely many values of a for which the zero-one 4-law for MSO properties does not hold. To this end, we analyze the evolution of certain properties of G(n,p) that may be of independent interest.
Year
DOI
Venue
2016
10.1137/16M1103105
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
Field
DocType
zero-one laws,monadic properties,random graphs
Discrete mathematics,Combinatorics,Random graph,First order,Monad (functional programming),Mathematics,Bounded function
Journal
Volume
Issue
ISSN
32
4
0895-4801
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Andrey B. Kupavskii16422.31
Maksim Zhukovskii224.51