Logconcave random graphs

We propose the following model of a random graph on n vertices. Let F be a distribution in R + n(n-1)/2 with a coordinate for every pair ij with 1 ≤ i,j ≤ n. Then G F,p is the distribution on graphs with n vertices obtained by picking a random point X from F and defining a graph on n vertices whose edges are pairs ij for which X ij ≤ p. The standard Erdos-Renyi model is the special case when F is uniform on the 0-1 unit cube. We determine basic properties such as the connectivity threshold for quite general distributions. We also consider cases where the X ij are the edge weights in some random instance of a combinatorial optimization problem. By choosing suitable distributions, we can capture random graphs with interesting properties such as triangle-free random graphs and weighted random graphs with bounded total weight.

Authors

• Alan M. Frieze
• Santosh S. Vempala
• Juan Vera 0001

Keywords

• random graphs