Independent sets in random sparse graphs

We consider the problem of finding maximum independent sets on sparse graphs. A probabilistic analysis of this problem is presented, with the main objective being to obtain asymptotic lower and upper bounds on the size of the optimal solution. If we let n be the number of nodes in the graph, we show that with probability tending to 1 as n /rightarrow /infty, this size lies between [ D 1 n ] and [ D 2 n ], where D 1 and D 2 are specific functions of the average degree of a node. The lower bound is obtained by examining the behavior of a simple algorithm for constructing independent sets. We then extend our results to the case of random sparse hypergraphs and obtain bounds using similar methods. Finally, we consider the case of Euclidean sparse graphs. Simple asymptotically optimal strategies are presented for this model.