Hereditary Zero-One Laws for Graphs

2010/06/15 by Mor Doron, Saharon Shelah, Doron, Mor +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #DNA and Biological Computing #FOS: Mathematics #Limits and Structures in Graph Theory #Logic (math.LO) #math.CO #math.LO

paper · pdf · doi:10.48550/arxiv.1006.2888

published as in: {Fields of logic and computation} (2010) 581--614

arxiv created 2010/06/15 · openalex publication_date 2010/06/15 · arxiv updated 2010/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Related

• Random Graph: Stronger logic but with the zero one law
• On failure of 0-1 laws
• Failure of 0-1 law for sparse random graph in strong logics
• Universal Zero-One k--Law
• Zero-one laws for k-variable first-order logic of sparse random graphs