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.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
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