Name
Abstract | ||
|---|---|---|
In this paper we establish a substantially improved lower bound on the k-color ability threshold of the random graph G(n, m) with n vertices and m edges. The new lower bound is approximately 1.39 less than the 2k*ln(k)-ln(k) first-moment upper bound (and approximately 0.39 less than the 2k*ln(k)-ln(k)-1 physics conjecture). By comparison, the best previous bounds left a gap of about 2+ln(k), unbounded in terms of the number of colors [Achlioptas, Naor: STOC 2004]. Furthermore, we prove that, in a precise sense, our lower bound marks the so-called condensation phase transition predicted on the basis of physics arguments [Krzkala et al.: PNAS 2007]. Our proof technique is a novel approach to the second moment method, inspired by physics conjectures on the geometry of the set of k-colorings of the random graph. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/FOCS.2013.48 | foundations of computer science |
Keywords | DocType | Volume |
lower bound mark,random graph,novel approach,n vertex,physics conjecture,k-colorability threshold,previous bound,k-color ability threshold,physics argument,m edge,moment method,set theory | Conference | abs/1304.1063 |
ISSN | Citations | PageRank |
0272-5428 | 20 | 0.86 |
References | Authors | |
19 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amin Coja-Oghlan | 1 | 543 | 47.25 |
| Dan Vilenchik | 2 | 143 | 13.36 |