Independent sets in random graphs from the weighted second moment method

Varsha Dani, Cristopher Moore

We prove new lower bounds on the likely size of a maximum independent set in a random graph with a given average degree. Our method is a weighted version of the second moment metho…