Hereditary Zero-One Laws for Graphs

Details Hereditary Zero-One Laws for Graphs Hereditary Zero-One Laws for Graphs

2010-06-15

arxiv.org/abs/1006.2888v1

Mathematics

Logic

Scientific paper

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 probabilities. 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.

Affiliated with

Also associated with

No associations

Rating

Hereditary Zero-One Laws for Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hereditary Zero-One Laws for Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hereditary Zero-One Laws for Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-104307