The probabilistic method is used for nonconstructive proofs of existence of combinatorial objects with certain properties. We present the basic ideas of randomized algorithms and show their connection to the probabilistic method. Proofs using the probabilistic method often lead to randomized algorithms for such objects. Several ways of using the probabilistic method are shown, including the basic method, alteration, the use of linearity of expectation and the second-moment method. There is at least one example for each method. We present Ramsey numbers, hypergraph coloring and tournaments. In the example of the maximum cut problem, we present the randomized algorithm and its derandomization. We prove Erdős’ theorem, which states that there exists a graph with arbitrarily large girth and arbitrarily large chromatic number. Lastly, we introduce the idea of random graphs, their threshold functions and find the threshold function for containing a given subgraph.
|
