DIMACS TR: 95-50

Zero one laws for graphs with edge probabilities decaying with distance

Author: Saharon Shelah


Let G(n) be the random graph on [n]={1,...,n} with the possible edge {i,j} having probability being p(|i-j|)=1/(|i-j|^a), 0 is less than a is less than 1 irrational. We prove that the zero one law (for first order logic) holds.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-50.ps.gz
DIMACS Home Page