2.2 Hypergraph Coloring 12 2.1.2 Theorem.For anyk≥3， R(k,)>22-1 Proof.Let us consider a random graph G(n,1/2)on n vertices where every pair of vertices forms an edge with probability independently of the other edges.(We can imagine flipping a coin for every potential edge to decide whether it should appear in the graph.)For any fixed set of k vertices,the probability that they form a clique is p=2(的 The same focrence of an indepepdent set nd there are( an inde dent set might a we use the fact that th their ma1.1.3, and w get Pc,e orepe月≤2(（份2r6句 It remains to chooseso that the last plest estimate(n,we find tha h certainly holds whenever n<24/2-1.Therefore,there are graphs on [22- vertices that contain neith er a clique of size k nor an independent set of size k. This implies R(k.)>2/ Let i fine s in the proof,the lo we bound But a result even slightly better e powerfu. par no lowe nown o f the form c with a con e best upper bound is about 4 One might object that the of a probability space is artificial here and the pro 1 ing obj bject try prove t at iti 111 good is ind possib e suc pr cou ore sophis pr pr c fo apler than counting argur the prob abilis s to use many results of probability theory-a mature ma e probabilistic method has provided th only known 1t10m, for others,i ided accessible proofs in cases 2.2 Hypergraph Coloring 2.2.1 Definition .A k-uniform hy graph is a pair(X.S)where X is the set of vertices and S()is the set dges (k-tuples2.2 Hypergraph Coloring 12 2.1.2 Theorem. For any k ≥ 3, R(k, k) > 2 k/2−1 . Proof. Let us consider a random graph G(n, 1/2) on n vertices where every pair of vertices forms an edge with probability 1 2 , independently of the other edges. (We can imagine flipping a coin for every potential edge to decide whether it should appear in the graph.) For any fixed set of k vertices, the probability that they form a clique is p = 2−( k 2 ) . The same goes for the occurrence of an independent set, and there are ￾n k
k-tuples of vertices where a clique or an independent set might appear. Now we use the fact that the probability of a union of events is at most the sum of their respective probabilities (Lemma 1.1.3), and we get P[G(n, 1/2) contains a clique or an indep. set of size k] ≤ 2 n k ! 2 −( k 2 ) . It remains to choose n so that the last expression is below 1. Using the sim￾plest estimate ￾n k
≤ n k , we find that it is sufficient to have 2n k < 2 k(k−1)/2 . This certainly holds whenever n ≤ 2 k/2−1 . Therefore, there are graphs on ⌊2 k/2−1 ⌋ vertices that contain neither a clique of size k nor an independent set of size k. This implies R(k, k) > 2 k/2−1 . ✷ Let us remark that, by using finer estimates in the proof, the lower bound for R(k, k) can be improved a little, say to 2k/2 . But a result even slightly better than this seems to require a more powerful technique. In particular, no lower bound is known of the form c k with a constant c > √ 2, although the best upper bound is about 4k . One might object that the use of a probability space is artificial here and the same proof can be formulated in terms of counting objects. In effect, we are counting the number of bad objects and trying to prove that it is less than the number of all objects, so the set of good objects must be nonempty. In simple cases, it is indeed possible to phrase such proofs in terms of counting bad objects. However, in more sophisticated proofs, the probabilistic formalism becomes much simpler than counting arguments. Furthermore, the probabilis￾tic framework allows us to use many results of probability theory—a mature mathematical discipline. For many important problems, the probabilistic method has provided the only known solution, and for others, it has provided accessible proofs in cases where constructive proofs are extremely difficult. 2.2 Hypergraph Coloring 2.2.1 Definition. A k-uniform hypergraph is a pair (X, S) where X is the set of vertices and S ⊆ ￾X k
is the set of edges (k-tuples of vertices)