## 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.