Independent sets in random graphs from the weighted second moment method
classification
💻 cs.CC
cond-mat.stat-mechmath.COmath.PR
keywords
independentmethoddegreemomentrandomsecondweightedaverage
read the original abstract
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 method, where we give each independent set a weight based on the total degree of its vertices.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.