Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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

1 Answer 1

up vote 2 down vote accepted

Probability in combinatorics is often used within the framework of the probabilistic method

http://en.wikipedia.org/wiki/Probabilistic_method

One nice result that was for the first time derived with the probabilistic method is the following

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$.

So one aspect in which one can use probability in combinatorics is by showing that the probability that a given combinatorial object exists is nonzero, which in turn allows to show the existence of such an object, without explicitly constructing one.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.