Fetching the paper…
Reading the bibliography…
The independence number of a sparse random graph G(n,m) of average degree d=2m/n is well-known to be \alpha(G(n,m))~2n ln(d)/d with high probability.
P. Erdős. Some remarks on the theory of graphs
1947
Earlier work this paper cites.
N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, E. Teller Equation of state calculations by fast computing machines
1953
Earlier work this paper cites.
G. R. Grimmett and C. J. H. McDiarmid. On colouring random graphs
1975
Earlier work this paper cites.
B. Bollobás and P. Erdős. Cliques in random graphs
1976
Earlier work this paper cites.
R. M. Karp. The probabilistic analysis of some combinatorial search algorithms
1976
Earlier work this paper cites.
D. Matula. The largest clique size in a random graph
1976
Earlier work this paper cites.
L. Kučera. Expected Behavior of Graph Coloring Algorithms
1977
Earlier work this paper cites.
R. Karp and M. Sipser. Maximum matchings in sparse random graphs
1981
Earlier work this paper cites.
S. Kirkpatrick, C. Gelatt, and M. Vecchi. Optimisation by simulated annealing
1983
Earlier work this paper cites.
H. S. Wilf. Backtrack: An expected O(1) time algorithm for the graph coloring problem
1984
Earlier work this paper cites.
M. E. Dyer and A. M. Frieze. Fast algorithms for some random NP-hard problems
1986
Earlier work this paper cites.
Y. Fu, P. W. Anderson. Applications of statistical mechanics to NP-complete problems in combinatorial optimization
1986
Cited alongside, same era.
J. S. Turner. Almost all k-colorable graphs are easy to color
1988
Cited alongside, same era.
L. Kučera. Graphs with small chromatic number are easy to color
1989
Cited alongside, same era.
A. M. Frieze. On the independence number of random graphs
1990
Cited alongside, same era.
M. R. Jerrum. Large cliques elude the Metropolis process
1992
Cited alongside, same era.
R. Motwani and P. Raghavan. Randomized Algorithms
1995
Cited alongside, same era.
S. Janson, T. Luczak and A. Ruciński. Random graphs
2000
Later among the works it cites.
B. Bollobás. Random graphs
2001
Later among the works it cites.
M. Mezard, G. Parisi and R. Zecchina. Analytic and Algorithmic Solution of Random Satisfiability Problems
2002
Later among the works it cites.
D. Gamarnik, T. Nowicki and G. Swirscsz Maximum Weight Independent Sets and Matchings in Sparse Random Graphs
2005
Later among the works it cites.
F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjianc, L. Zdeborova. Gibbs states and the set of solutions of random constraint satisfaction problems
2007
Later among the works it cites.
D. Achlioptas and A. Coja-Oghlan. Algorithmic Barriers from Phase Transitions
2008
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
M. Talagrand. Concentration of measure and isoperimetric inequalities in product spaces
1995
Cited alongside, same era.
A. Frieze and S. Suen. Analysis of two simple heuristics on a random instance of k k -SAT
1996
Cited alongside, same era.
D. Achlioptas and M. Molloy. The Analysis of a List-Coloring Algorithm on a Random Graph
1997
Cited alongside, same era.
A. M. Frieze and C. McDiarmid. Algorithmic theory of random graphs
1997
Cited alongside, same era.
Later among the works it cites.
N. Bhatnagar, A. Sly and P. Tetali. Reconstruction Threshold for the Hardcore Model
2010
Closest in time.
B. Rossman. The Monotone Complexity of k-Clique on Random Graphs
2010
Closest in time.
V. Dani and C. Moore. Independent sets in random graphs from the weighted second moment method
2011
Closest in time.
A. Montanari, R. Restrepo and P. Tetali. Reconstruction and clustering thresholds in random CSPs
2011
Closest in time.