Title: Log-Concave Random Graphs
Speaker: Alan Frieze
When: November 29, 16:30-17:30
Where: Wean Hall 5302
Abstract:
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 \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 a distribution with a log-concave density $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 the indicator function for the We thus obtain an interesting connection between convex geometry and random graphs.
When $f$ is down-monotone we can determine the connectivity and matching thresholds up to a constant factor. When $f$ is the indicator function for a right simplex then we can obtain more precise results on connectivity and the diameter.
If $X$ is used to define weights for an optimization problem and $f$ is “column independent” then we can whp solve the ATSP asymptotically.
Joint work with Santosh Vempala and Juan Vera
