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

Volume 185 / 2005

Saharon Shelah 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.

Authors

  • Saharon ShelahEinstein 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.
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image