Monadic second-order properties of very sparse random graphs (Q2404656)

This article extends results about zero-one laws, in particular zero-one restricted to quantifier rank \(k\), for graphs to very sparse graphs and to monadic second-order logic (MSO). The main results give almost complete information about when such zero-one laws hold and when they do not. The Ehrenfeucht game is a major tool in the proofs. In order to prove the main results, the authors establish bounds on the number of equivalence classes of the relation ``the graphs \(G\) and \(H\) satisfy the same MSO-sentences of quantifier rank at most \(k\)''.