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

Tom 185 / 2005

Saharon Shelah Fundamenta Mathematicae 185 (2005), 211-245 MSC: 03C13, 05C80, 60F20, 03C10. DOI: 10.4064/fm185-3-2


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.


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

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek