Hereditary zero-one laws for graphs

DOI10.1007/978-3-642-15025-8_29MaRDI QIDQ3586023zbMATH OpenOpenAlexFDO

Authors S. Shelah, Mor Doron

Publication date 3 September 2010

Published in Fields of Logic and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.2888

zbMATH Keywords

random graphszero-one laws

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Random graphs (graph-theoretic aspects) (05C80)

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

Recommendations

• Zero-one laws for graphs with edge probabilities decaying with distance. Part I
• Zero-one \(k\)-law
• When Does the Zero-One Law Hold?
• On the Very Weak 0–1 Law for Random Graphs with Orders
• Zero-one laws with variable probability

Cites work

• Convergence in homogeneous random graphs

Cited in

(2)

• A geometric zero-one law
• On the Very Weak 0–1 Law for Random Graphs with Orders

This page was built for publication: Hereditary zero-one laws for graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586023)