2 The Probabilistic Method The probabilistic method is a remarkable technique for proving the existence of combinatorial objects with specified properties.It is based on probability theory but,surprisingly,it can be used for proving theorems that have nothing to do with probability.The usual approach can be described as follows. We would like to prove the existence of a combinatorial object with specified properties.Unfortunately,an explicit construction of such a"good"object does not seem feasible,and maybe we do not even need a specific example;we just want to prove that something "good"exists.Then we can consider a random object from a suitable probability space and calculate the probability that it satisfies our conditions.If we prove that this probability is strictly positive then we conclude that a "good"object must exist;if all objects were "bad", the probability would be zero. Let us start with an example illustrating how the probabilistic method works in its basic form. 2.1 Ramsey Numbers The Ramsey theorem states that any sufficiently lar ge graph contains eithera (A eli tices indu ph and an a ndent sof2 set of y s inducing an oh) ra 2.1.1 Definition.The Ramsey number R(k,()is R(k,()=min [n:any graph on n vertices contains a clique of size k or an independent set of size tt. The Ramsey theorem guarantees that R(k.(is always finite.Still,the pre cise values of R(k,are unknown but for a small number of cases,and it is desirable at least to estimate R(k,)for large k and (Here we use the proba- bilistic method to prove a lower bound on R(k,k). clique =klika (uplny podgraf) independent set nezavisla mnozina 2 The Probabilistic Method The probabilistic method is a remarkable technique for proving the existence of combinatorial objects with specified properties. It is based on probability theory but, surprisingly, it can be used for proving theorems that have nothing to do with probability. The usual approach can be described as follows. We would like to prove the existence of a combinatorial object with specified properties. Unfortunately, an explicit construction of such a “good” object does not seem feasible, and maybe we do not even need a specific example; we just want to prove that something “good” exists. Then we can consider a random object from a suitable probability space and calculate the probability that it satisfies our conditions. If we prove that this probability is strictly positive, then we conclude that a “good” object must exist; if all objects were “bad”, the probability would be zero. Let us start with an example illustrating how the probabilistic method works in its basic form. 2.1 Ramsey Numbers The Ramsey theorem states that any sufficiently large graph contains either a clique or an independent set of a given size. (A clique1 is a set of vertices inducing a complete subgraph and an independent set2 is a set of vertices inducing an edgeless subgraph.) 2.1.1 Definition. The Ramsey number R(k, ℓ) is R(k, ℓ) = min {n: any graph on n vertices contains a clique of size k or an independent set of size ℓ}. The Ramsey theorem guarantees that R(k, ℓ) is always finite. Still, the pre￾cise values of R(k, ℓ) are unknown but for a small number of cases, and it is desirable at least to estimate R(k, ℓ) for large k and ℓ. Here we use the proba￾bilistic method to prove a lower bound on R(k, k). 1 clique = klika (úplný podgraf) 2 independent set = nezávislá množina