Zero-one laws for graphs with edge probabilities decaying with distance. Part II

Saharon Shelah¹

¹ Einstein Institute of Mathematics The Hebrew University of Jerusalem Edmond J. Safra Campus, Givat Ram Jerusalem 91904, Israel and Department of Mathematics Rutgers, The State University of New Jersey Hill Center-Busch Campus 110 Frelinghuysen Road Piscataway, NJ 08854-8019, U.S.A.

Fundamenta Mathematicae, Tome 185 (2005) no. 3, pp. 211-245.

Résumé

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.

Détail

DOI : 10.4064/fm185-3-2

Keywords: random graph ldots probability being edge decaying power distance specifically probability being i j i j alpha where constant alpha irrational analyze theory using appropriate weight function pair graphs using equivalence relation setminus investigate model theory theory including finite compactness lastly consequence prove zero one law first order logic holds