JEDNOSTKA NAUKOWA KATEGORII A+

# Wydawnictwa / Czasopisma IMPAN / Fundamenta Mathematicae / Wszystkie zeszyty

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

### Tom 185 / 2005

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

#### Streszczenie

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.

#### Autorzy

• 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

## Przeszukaj wydawnictwa IMPAN

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

Odśwież obrazek