Zeroone laws for sentences with k variables
Maksim Evgen'evich Zhukovskii, Andriaherimanana Sarobidy Razafimahatratra · Доклады Академии наук · 2019
We consider the k variable fragment of first order logic on graphs. We claim that, for α≤1κ-1, the random graph G(n, n-α) obeys zeroone law w.r.t. this logic. Moreover, for every ε > 0 , there exists α∈1κ-1,1κ-1+ε such that G(n, n-α) does not obey the law.