Zero-one laws for k-variable first-order logic of sparse random graphs

2018/11/16 by Andriaherimanana Sarobidy Razafimahatratra, Razafimahatratra, A. S., Maksim Zhukovskii +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1811.07026

openalex publication_date 2018/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we prove that for every positive ε, there exists an α∈(1/(k-1),1/(k-1)+ε) such that the binomial random graph G(n,n^-α) does not obey 0-1 law w.r.t. first order sentences with k variables. In contrast, for every α∈(0,1/(k-1)], G(n,n^-α) obeys 0-1 law w.r.t. this logic.

Related

• Failure of 0-1 law for sparse random graph in strong logics
• Random Graph: Stronger logic but with the zero one law
• Short monadic second order sentences about sparse random graphs
• Monadic second-order properties of very sparse random graphs
• On failure of 0-1 laws