The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Log-concave random graphs

Frieze, A (Carnegie Mellon)
Thursday 27 March 2008, 10:40-11:10

Seminar Room 1, Newton Institute


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.


[pdf ]




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.

Back to top ∧