skip to content

Log-concave random graphs

Presented by: 
A Frieze [Carnegie Mellon]
Thursday 27th March 2008 - 10:40 to 11:10
INI Seminar Room 1

We propose the following model of a random graph on n vertices. Let F be a multi-dimensional distribution with a coordinate for every pair ij with i,j in [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(i,j) < p. The standard Erdos-Renyi model is the special case when F is uniform on the 0-1 unit cube. We determine some basic properties such as the connectivity threshold for the case where F is down-monotone and has a log-concave density. We also consider cases where the X(i,j) 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.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons