Logconcave Random Graphs

Details Logconcave Random Graphs Logconcave Random Graphs

2009-01-23

arxiv.org/abs/0901.3697v1

Electronic Journal of Combinatorics 17 (2010) R108

Mathematics

Combinatorics

Scientific paper

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 i$ with 1 \le i,j \le 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} \le p. The standard Erd\H{o}s-R\'{e}nyi model is the special case when F is uniform on the 0-1 unit cube. We examine 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.

Affiliated with

Also associated with

No associations

Rating

Logconcave Random Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Logconcave Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logconcave Random Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-66161