Connectedness of Certain Random Graphs

L. Dubins conjectured in 1984 that the graph on vertices {1, 2, 3, ...} where an edge is drawn between verticesi andj with probability pij=λ / max(i, j) independently for each pairi andj is a.s. connected for λ=1. S. Kalikow and B. Weiss proved that the graph is a.s. connected for any λ>1. We prove Dubin’s conjecture and show that the graph is a.s. connected for anyλ>1/4. We give a proof based on a recent combinatorial result that forλ ≦ 1/4 the graph is a.s. disconnected. This was already proved for λ < 1/4 by Kalikow and Weiss. Thus λ= 1/4 is the critical value for connectedness, which is surprising since it was believed that the critical value is at λ=1.