Probabilistic combinatorics front page

a repository of mathematical know-how

Probabilistic combinatorics front page

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[QUICK DESCRIPTION]

Probabilistic combinatorics has two rather distinct flavours. The first is the study of the typical behaviour of random combinatorial objects, such as a graph with $n$ vertices where each edge is chosen randomly and independently with probability $p$. The second is the use of random constructions to prove statements that do not mention probability, a classic example being Erd\H{o}s's proof that the Ramsey number $R(k,k)$ is at least $2^{k/2}$ (which is Example 2 in the article on [[averaging arguments]] or Example 1 on [[Applying the probabilistic method|the use of the probabilistic method]]). This page contains links to several articles: some are general articles about the probabilistic method, while others are about particular methods that have been developed to estimate probabilities in situations where they are hard to determine.

=== The use of the probabilistic method ===

[[Applying the probabilistic method|What is the probabilistic method and when can it be applied?]] [cut] Brief summary || This article discusses a few well-known and relatively straightforward applications of the probabilistic method, and attempts to explain how to recognise situations where the probabilistic method can be used. Many applications of the probabilistic methods require one to prove highly non-trivial estimates for probabilities: methods for obtaining such estimates are discussed in other articles (see below). [/cut]

[[Useful heuristic principles for guessing probabilistic estimates]] [cut] Brief summary || If you are hoping to use the probabilistic method as part of a long and complicated proof, you will probably want to begin by producing a plausible sketch of the argument before you go into the technical details. For this purpose it is very useful to be able to guess upper (and sometimes lower) bounds for the probabilities of various complicated events. This article discusses heuristic principles that can help one do this, and illustrates them with examples. [/cut]

[[Unusual choices of probability distribution]] [cut] Brief summary || For many uses of the probabilistic method, it is obvious what the best way is of choosing a random structure or substructure. However, there are some applications where a non-obvious choice is what is needed.[/cut]

=== Techniques for estimating and bounding probabilities ===

[[Averaging arguments]]

[[The second-moment method]]

[[How to use martingales]]

[[How to use the Lov\'asz local lemma]]

[[How to use Talagrand's inequality]]

[[How to use Janson's inequality]]

[[Stein's method]]

[[How to use correlation inequalities]]

[[How to use the inclusion-exclusion principle]]

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Probabilistic combinatorics front page

Recent articles

Active forum topics

Recent comments