✦ LIBER ✦

A Sharp Threshold for k-Colorability

✍ Scribed by Dimitris Achlioptas; Ehud Friedgut

Book ID: 101271621
Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 162 KB
Volume: 14
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(1999010)14:1<63::aid-rsa3>3.0.co;2-7

No coin nor oath required. For personal study only.

✦ Synopsis

Let k be a fixed integer and f n, p denote the probability that the random k Ž . Ž . graph G n, p is k-colorable. We show that for k G 3, there exists d n such that for any k ⑀ ) 0, d n y ⑀ d n q ⑀

Ž . Ž .

📜 SIMILAR VOLUMES

A randomized algorithm for k-colorabilit

A randomized algorithm for k-colorability

✍ Janez Žerovnik 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 692 KB

This note is a report of testing a straightforward generalization of the randomized 3-coloring algorithm of Petford and Welsh (1989) on the decision problems of 4-and lo-coloring. We observe similar behavior, namely the existence of critical regions. Experimentally, the average time complexity for

Random k ‐SAT: Two Moments Suffice to Cr

Random k ‐SAT: Two Moments Suffice to Cross a Sharp Threshold

✍ Achlioptas, Dimitris; Moore, Cristopher 📂 Article 📅 2006 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 257 KB

The property of having a k -regular subg

The property of having a k -regular subgraph has a sharp threshold

✍ Shoham Letzter 📂 Article 📅 2012 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB

Sharp load thresholds for cuckoo hashing

✍ Nikolaos Fountoulakis; Konstantinos Panagiotou 📂 Article 📅 2012 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB

Sharp metastability threshold for two-di

Sharp metastability threshold for two-dimensional bootstrap percolation

✍ Alexander E. Holroyd 📂 Article 📅 2003 🏛 Springer 🌐 English ⚖ 267 KB

Sharp Threshold for Hamiltonicity of Ran

Sharp Threshold for Hamiltonicity of Random Geometric Graphs

✍ Díaz, Josep; Mitsche, Dieter; Pérez, Xavier 📂 Article 📅 2007 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 154 KB