## Independent sets in sparse random graphs

(1/10) A solution of this and many related problems has been given by Bayati - Gamarnik - Tetali.

Fix 1 < a < >\infty. Consider the random graph G(n,a/n); so there are n vertices, and each possible edge is present with probability a/n. An independent set in a graph is a set of vertices, no two of which are linked by an edge. Let X_n be the maximal size of an independent set in G(n,a/n) Then it is natural to believe
n^{-1} EX_n \to c(a)
since by considering isolated vertices we have a lower bound e^{-a}> for the limit.

History. Mentioned in talks in the 1990s and posed in the 2003 postscript version of Open Problems but (for some reason) not later copied into this HTML.