Zero-one laws for graphs with edge probabilities decaying with distance. Part II
Volume 185 / 2005
Fundamenta Mathematicae 185 (2005), 211-245
MSC: 03C13, 05C80, 60F20, 03C10.
DOI: 10.4064/fm185-3-2
Abstract
Let $G_n$ be the random graph on $[n]=\{1,\ldots,n\}$ with the probability of $\{i,j\}$ being an edge decaying as a power of the distance, specifically the probability being $p_{|i-j|}=1/|i-j|^\alpha$, where the constant $\alpha\in (0,1)$ is irrational. We analyze this theory using an appropriate weight function on a pair $(A,B)$ of graphs and using an equivalence relation on $B\setminus A $. We then investigate the model theory of this theory, including a “finite compactness”. Lastly, as a consequence, we prove that the zero-one law (for first order logic) holds.
