Independent Sets in Random Graphs from the Weighted Second Moment Method

DOI10.1007/978-3-642-22935-0_40zbMath1343.05135arXiv1011.0180MaRDI QIDQ3088119

Moore, Cristopher, Varsha Dani

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.0180

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

The largest hole in sparse random graphs, Two-Point Concentration of the Independence Number of the Random Graph, On the independence number and Hamiltonicity of uniform random intersection graphs, Spin systems on Bethe lattices, Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract), Random Instances of Problems in NP – Algorithms and Statistical Physics

Cites Work

• On the independence number of random graphs
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• On independent sets in random graphs
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs