### Hereditary Zero-One Laws for Graphs

by Doron and Shelah. [DoSh:953]

Fields Logic and Computation: Essays dedicated to Yuri Gurevich on Occasion his 70th Birthday, 2010

We consider the random graph M^n_{bar {p}} on the set
[n], were the probability of {x,y} being an edge is
p_{|x-y|}, and bar {p}=(p_1,p_2,p_3,...) is a series of
probabilitie. We consider the set of all bar {q} derived
from bar {p} by inserting 0 probabilities to bar {p}, or
alternatively
by decreasing some of the p_i . We say that bar {p}
hereditarily satisfies the 0-1 law if the 0-1 law (for first
order logic) holds in M^n_{bar {q}} for any bar {q}
derived from bar {p} in the relevant way described above.
We
give a necessary and sufficient condition on bar {p} for it
to hereditarily satisfy the 0-1 law.

Back to the list of publications