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

• Autorzy: Saharon Shelah
• Języki publikacji: EN

Abstrakty

EN

Let Gₙ be the random graph on [n] = {1,...,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|^{α}$, where the constant α ∈ (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∖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.

Kategorie tematyczne

• 05C80: Random graphs
• 03C13: Finite structures
• 03C10: Quantifier elimination, model completeness and related topics
• 60F20: Zero-one laws

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Fundamenta Mathematicae
• Rocznik: 2005
• Tom: 185
• Numer: 3
• Strony: 211-245

Daty

wydano

2005

Twórcy

autor

Saharon Shelah

• Einstein 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.

Identyfikatory

DOI

10.4064/fm185-3-2