# What are the relationships between combinatorics and randomness?

I was just reading the impressive paper by Tim Gowers The Two Cultures of Mathematics when I noticed the various connections between combinatorics and randomness. As a non-mathematician, it is not intuitively obvious to me what is the scope of relationship between them, apart from the idea that combinatorics involves counting and counting is needed for preliminary probability (I work in machine learning).

What are the major results that connect combinatorics and randomness, and how do they connect?

-
Didn't that article itself include some examples? In any case, Gowers included a few pages about this at some length in his recent Abel prize introduction. –  Henning Makholm Mar 22 '12 at 14:32
@HenningMakholm: It did. I am most familiar with the concentration of measure, given my background, but being outside the field I can neither say I know which are important and which are not nor can I say that I can identify if there are other results of similar importance. Thanks for the interesting link. –  Muhammad Alkarouri Mar 22 '12 at 14:39

For every $k$ and $g$ there exist a graph $G$ of girth $g$ (length of minimal cycle) such that the chromatic number of $G$ is at least $k$.