3
$\begingroup$

I am looking for elementary statements in graph theory that illustrate the concentration of measure phenomenon.

(Say, something bit more interesting than most of graphs have diameter 2.)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Sharp concentration of the chromatic number on random graphs, Eli Shamir and Joel Spencer (1987).

The concentration of measure phenomenon is used to prove concentration of the chromatic number for random graphs around its expected value (the chromatic number of a graph is defined as the minimal number of colors required to color all the vertices of this graph such that no two adjacent vertices have the same color). As discussed in this monograph, the approach of Shamir and Spencer has been imported into coding theory to explore concentration of measure phenomena pertaining to codes defined on graphs and iterative message-passing decoding algorithms.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .