Independent Sets in Random Graphs from the Weighted Second Moment Method
From MaRDI portal
Publication:3088119
DOI10.1007/978-3-642-22935-0_40zbMath1343.05135arXiv1011.0180OpenAlexW2963741050MaRDI 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
Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (6)
Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ 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 ⋮ Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract) ⋮ Spin systems on Bethe lattices
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
This page was built for publication: Independent Sets in Random Graphs from the Weighted Second Moment Method
