Extremal combinatorics deals with questions about how big or small a certain mathematical object or family of objects can be to satisfy certain restrictions. The probabilistic method entails solving extremal problems using one of the following theorems: The expectation is a linear functional. A random variable cannot always be strictly greater (nor always strictly smaller) than its expectation. For a proof of existence of an object with a certain property within a finite set of objects it is enough to prove that the probability of existence of such an object is positive.
The following theorems which use the probabilistic method are stated and proved: In any set of nonzero integers there is a sum-free subset with the size of at least one third of the original set. There is a tournament with $n$ players and at least $n!/2^{n-1}$ Hamiltonian paths. If $n \geq k^{2}2^{k+1}$, then there is a tournament of $n$ players in which for every $k$ players there is a player who defeated them all. A graph with $n$ vertices with a minimum degree $d$ has a dominating set with at most $n\frac{1+\ln(d+1)}{d+1}$ vertices. The crossing number of a graph with $n$ vertices and $e \geq 4n$ edges is greater or equal to $n\frac{1+\ln(d+1)}{d+1}$. The crossing number theorem is followed by the Szemerédi-Trotter theorem, one of its corollaries, and Beck's theorem.
|
