Sharp concentration of the chromatic number on random graphs G n, p

Eli Shamir; Joel Spencer

doi:10.1007/BF02579208

Sharp concentration of the chromatic number on random graphs G n, p

Eli Shamir, Joel Spencer

Research output: Contribution to journal › Article › peer-review

Abstract

The distribution of the chromatic number on random graphs G_{n, p} is quite sharply concentrated. For fixed p it concentrates almost surely in √n ω(n) consecutive integers where ω(n) approaches infinity arbitrarily slowly. If the average degree pn is less than n^1/6, it concentrates almost surely in five consecutive integers. Large deviation estimates for martingales are used in the proof.

Original language	English (US)
Pages (from-to)	121-129
Number of pages	9
Journal	Combinatorica
Volume	7
Issue number	1
DOIs	https://doi.org/10.1007/BF02579208
State	Published - Mar 1987

Keywords

05 C 15
60 C 05

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/BF02579208

Cite this

@article{749205a563ef4652a383ff64eb6ae982,

title = "Sharp concentration of the chromatic number on random graphs G n, p",

abstract = "The distribution of the chromatic number on random graphs Gn, p is quite sharply concentrated. For fixed p it concentrates almost surely in √n ω(n) consecutive integers where ω(n) approaches infinity arbitrarily slowly. If the average degree pn is less than n1/6, it concentrates almost surely in five consecutive integers. Large deviation estimates for martingales are used in the proof.",

keywords = "05 C 15, 60 C 05",

author = "Eli Shamir and Joel Spencer",

year = "1987",

month = mar,

doi = "10.1007/BF02579208",

language = "English (US)",

volume = "7",

pages = "121--129",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "1",

}

TY - JOUR

T1 - Sharp concentration of the chromatic number on random graphs G n, p

AU - Shamir, Eli

AU - Spencer, Joel

PY - 1987/3

Y1 - 1987/3

N2 - The distribution of the chromatic number on random graphs Gn, p is quite sharply concentrated. For fixed p it concentrates almost surely in √n ω(n) consecutive integers where ω(n) approaches infinity arbitrarily slowly. If the average degree pn is less than n1/6, it concentrates almost surely in five consecutive integers. Large deviation estimates for martingales are used in the proof.

AB - The distribution of the chromatic number on random graphs Gn, p is quite sharply concentrated. For fixed p it concentrates almost surely in √n ω(n) consecutive integers where ω(n) approaches infinity arbitrarily slowly. If the average degree pn is less than n1/6, it concentrates almost surely in five consecutive integers. Large deviation estimates for martingales are used in the proof.

KW - 05 C 15

KW - 60 C 05

UR - http://www.scopus.com/inward/record.url?scp=51649150009&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51649150009&partnerID=8YFLogxK

U2 - 10.1007/BF02579208

DO - 10.1007/BF02579208

M3 - Article

AN - SCOPUS:51649150009

SN - 0209-9683

VL - 7

SP - 121

EP - 129

JO - Combinatorica

JF - Combinatorica

IS - 1

ER -

Sharp concentration of the chromatic number on random graphs G n, p

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this