A geometric zero-one law

DOI10.2178/JSL/1245158092MaRDI QIDQ3399185zbMATH OpenOpenAlexFDO

Authors Robert H. Gilman, Yuri Gurevich, Alexei Myasnikov

Publication date 29 September 2009

Published in Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

Cayley diagramsfinite structureGaifman graphpercolationrelational structuretreeszero-one law

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Graph theory (05C99)

Abstract: Each relational structure X has an associated Gaifman graph, which endows X with the properties of a graph. Suppose that X is infinite, connected and of bounded degree. A first-order sentence in the language of X is almost surely true (resp. a.s. false) for finite substructures of X if for every element x in X, the fraction of substructures of the ball of radius n around x which satisfy the sentence approaches 1 (resp. 0) as n approaches infinity. Suppose further that, for every finite substructure, X has a disjoint isomorphic substructure. Then every sentence is a.s. true or a.s. false for finite substructures of X. This is one form of the geometric zero-one law. We formulate it also in a form that does not mention the ambient infinite structure. In addition, we investigate various questions related to the geometric zero-one law.

Recommendations

• scientific article; zbMATH DE number 887782
• Zero-one laws for sentences with \(k\) variables
• Hereditary zero-one laws for graphs
• Sufficient conditions for zero-one laws
• An extension of 0‐1 laws

Cites work

• A logical approach to asymptotic combinatorics I. First order properties
• Percolation beyond \(\mathbb{Z}^ d\), many questions and a few answers

Cited in

(12)

• 0-1 laws for recursive structures
• A topological zero-one law and elementary equivalence of finitely generated groups
• Generic theories as a method for approximating elementary theories
• Sufficient conditions for zero-one laws
• Zero-one \(k\)-law
• ON EXTENSIONS OF PARTIAL ISOMORPHISMS
• Random \(\ell\)-colourable structures with a pregeometry
• Discrete metric spaces: structure, enumeration, and 0-1 laws
• Limit laws and automorphism groups of random nonrigid structures
• scientific article; zbMATH DE number 224189 (Why is no real title available?)
• Asymptotic probabilities of extension properties and random l-colourable structures
• A geometric Littlewood-Richardson rule

This page was built for publication: A geometric zero-one law

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