The isolated-vertices conjecture for logconcave random graphs

Let FF be a distribution in the positive orthant with a down-monotone logconcave density. For each coordinate ee, write E(Xe2)=σe2{\sf E}(X_e^2)=\sigma_e^2, and let σmin=mineσe\sigma_{\min}=\min_e\sigma_e and σmax=maxeσe\sigma_{\max}=\max_e\sigma_e. Let GF,pG_{F,p} denote the random graph generated from FF with parameter pp. The isolated-vertices conjecture. There exists a constant c0c_0 such that, if

p<c1σminlnnn,p < \frac{c_1\sigma_{\min}\ln n}{n},

then GF,pG_{F,p} has isolated vertices with high probability. The conjecture concerns the gap between the theorem's lower connectivity threshold of order σmin/n\sigma_{\min}/n and its upper threshold of order σmaxlnn/n\sigma_{\max}\ln n/n; the source notes that it was incorrectly claimed as a theorem in an early version, while its resolution is not established in the supplied text.

Sources & referencesView supporting material

Primary source

Alan Frieze, Santosh Vempala and Juan Vera, “Logconcave Random Graphs”, arXiv:0901.3697 (2009).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.