probabilistic method
The probabilistic method was pioneered by Erdős Pál (known to Westerners as Paul Erdős) and initially used for solving problems in graph theory
, but has acquired ever wider applications. Broadly, the probabilistic method is somewhat the opposite of extremal graph theory. Instead of considering how a graph can behave in the most extreme case, we consider how a collection
of graphs behave “on average”, whereby we can formulate a probability space
. The fruits reaped by this method are often raw existence theorems
, usually deduced from the fact that the nonexistence of whatever of graph would a zero probability. For instance, by means of the probabilistic method, Erdős proved the existence of a graph of arbitrarily high girth and chromatic number
, a very counterintuitive result. Graphs tend to get enormous as the chromatic number and girth increase, thereby severely hindering necessary computations to explicitly construct them, so an existence theorem is most welcome.
In all honesty, probabilistic proofs are nothing more than counting proofs in disguise, since determining the probabilities of interest will invariably involve detailed counting arguments. In fact, we could remove from any probabilistic proof any mention of a probability space, although the result may be significanltly less transparent. Also, the advantage of using probability is that we can employ all the machinery of probability theory. Markov chains, martingales
, expectations (http://planetmath.org/ExpectedValue), probabilistic inequalities, and many other results, all become the tools of the trade in dealing with seemingly static objects of combinatorics and number theory
.
References
- 1 Noga Alon and Joel H. Spencer. The probabilistic method. John Wiley & Sons, Inc., second edition, 2000. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0996.05001Zbl 0996.05001.
- 2 Paul Erdős and Joel Spencer. Probabilistic methods in combinatorics. Academic Press, 1973. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0308.05001Zbl 0308.05001.
| Title | probabilistic method |
|---|---|
| Canonical name | ProbabilisticMethod |
| Date of creation | 2013-03-22 13:05:53 |
| Last modified on | 2013-03-22 13:05:53 |
| Owner | bbukh (348) |
| Last modified by | bbukh (348) |
| Numerical id | 15 |
| Author | bbukh (348) |
| Entry type | Topic |
| Classification | msc 05C80 |
| Classification | msc 11K99 |
| Related topic | GraphTheory |
| Related topic | ProofOfCrossingLemma |
| Related topic | RamseysTheorem2 |