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 precise 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 probabilistic method to prove a lower bound on R(k, k). 1 clique = klika (úplný podgraf) 2 independent set = nezávislá množina
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-tuples
2.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 simplest 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 probabilistic 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)
13 2.The Probabilistic Method 2.2.2 Definition.A hypergraph is c-colorable if its vertices can be colored with c colors so that no edge is monochromatic (at least two different colors appear in every edge). This is are 2-u 品 iform he vertices o will be the srable est possible number of edges in a -uniform hypergraph that is not 2-col 2.2.3 Definition.Let m(k)denote the smallest number of edges in a k- uniform hypergraph that is not 2-colorable. ve m(2)=3,because the smallest non -bip a tria the problem becomes much m we will prove,.m(③)=7，but the exa t valu of m(k)is unki own for k>3 Again,we can get a lower bound by probabilistic reasoning. 2.2.4 Theorem.For any k≥2， m(k≥2-1 Proof.Let us consider a k-uniform hypergraph H with less than. We will prove that it is 2-colorable. We color every vertex of H independently red or blue,with probability .The probability that the vertices s of a given edge are all red or all blue is p=2.()e.Supposing H has S]<2 edges,the probability that there exists a monochromatic edge is at most plS<p2 =1.So there is a non-zero probability that no edge is monochromatic and a proper coloring must exist. Note that for =3.we get m(3)>4.On the other hand.the smallest known aph that is not 2-colorable is the finite projective plane with 2.2.5 Definition.The Fano plane is the hypergraph H=(X,S),where X={1,2.3.45.6,7} are the points and S={1,2,31,{3.4,5,{5.6,1,{1,7,4,{2,7,51,{3,7,61,{24,6} are the edges
13 2. The Probabilistic Method 2.2.2 Definition. A hypergraph is c-colorable if its vertices can be colored with c colors so that no edge is monochromatic (at least two different colors appear in every edge). This is a generalization of the notion of graph coloring. Note that graphs are 2-uniform hypergraphs and the condition of proper coloring requires that the vertices of every edge get two different colors. Now we will be interested in the smallest possible number of edges in a k-uniform hypergraph that is not 2-colorable. 2.2.3 Definition. Let m(k) denote the smallest number of edges in a kuniform hypergraph that is not 2-colorable. For graphs, we have m(2) = 3, because the smallest non-bipartite graph is a triangle. However, the problem becomes much more difficult for larger k. As we will prove, m(3) = 7, but the exact value of m(k) is unknown for k > 3. Again, we can get a lower bound by probabilistic reasoning. 2.2.4 Theorem. For any k ≥ 2, m(k) ≥ 2 k−1 . Proof. Let us consider a k-uniform hypergraph H with less than 2k−1 edges. We will prove that it is 2-colorable. We color every vertex of H independently red or blue, with probability 1 2 . The probability that the vertices of a given edge are all red or all blue is p = 2·( 1 2 ) k . Supposing H has |S| < 2 k−1 edges, the probability that there exists a monochromatic edge is at most p|S| < p2 k−1 = 1. So there is a non-zero probability that no edge is monochromatic and a proper coloring must exist. ✷ Note that for k = 3, we get m(3) ≥ 4. On the other hand, the smallest known 3-uniform hypergraph that is not 2-colorable is the finite projective plane with 7 points, the Fano plane. 2.2.5 Definition. The Fano plane is the hypergraph H = (X, S), where X = {1, 2, 3, 4, 5, 6, 7} are the points and S = {{1, 2, 3}, {3, 4, 5}, {5, 6, 1}, {1, 7, 4}, {2, 7, 5}, {3, 7, 6}, {2, 4, 6}} are the edges. 1 2 3 4 5 6 7
2.2 Hypergraph Coloring 2.2.6 Lemma..m(3)≤7. Proof.We prove that the Fano plane is not 2-colorable.We give a quick argument using the fact that H is a projective plane,and thus for any two points,there is exactly one edge(line)containing both of them. Suppose that we have a 2-coloring A1U A2=X,A1nA2=0,where A1 is the larger color class. If|Al≥5，then A1 contains at least(⑨=l0 pairs of points..Each pair defines a unique line,but as there are only 7 lines in total,there must be two pairs of points defining the same line.So we have three points of the same color on a line If Al =4 then A contains ()=6 pairs of points.If two pairs among them define the same line,that line is monochromatic and we are done.So m尚the c or te遮d Ca.Then each point of exactly 3 lines and there are 7 lines in total,there is a line not intersecting A at all.That line is contained in A2 and thus monochromatic. Now we will improve the lower bound to establish that m(3)=7 2.2.7 Theorem.Any system of 6 triples is 2-colorable;i.e.m(3)27 Proof:Let us consider a 3-unifor is 2-colo ().6.We want tw depending on the IflX≤6，w e apply the probabilistic method.We ume that X]= efore do not a affect the ing c ondition. Then we any edge (w a triple t mak complet ly ve at most 8,an( m d we p pose tha S1 56.It he (a pair o th at In On the and tal number of vertex pairs is at leas conn are not a ew lypergrap by erging r and y into one vertex: X'=X\{,}U{z}, s'=MES:Mnd,y=0}UM\,{=):MES,Mn,0 This (X'S)is a 3-uniform hypergraph as well.IS'=SI<6.and ' X-1.so by the induction hypothesis it is 2-colorable.If we extend the coloring of X'to X so that both x and y get the color of we obtain a proper 2-coloring for (X,S)
2.2 Hypergraph Coloring 14 2.2.6 Lemma. m(3) ≤ 7. Proof. We prove that the Fano plane is not 2-colorable. We give a quick argument using the fact that H is a projective plane, and thus for any two points, there is exactly one edge (line) containing both of them. Suppose that we have a 2-coloring A1 ∪ A2 = X, A1 ∩ A2 = ∅, where A1 is the larger color class. If |A1| ≥ 5, then A1 contains at least 5 2 = 10 pairs of points. Each pair defines a unique line, but as there are only 7 lines in total, there must be two pairs of points defining the same line. So we have three points of the same color on a line. If |A1| = 4 then A1 contains 4 2 = 6 pairs of points. If two pairs among them define the same line, that line is monochromatic and we are done. So suppose that these 6 pairs define different lines ℓ1, . . . , ℓ6. Then each point of A1 is intersected by 3 of the ℓi . But since each point in the Fano plane lies on exactly 3 lines and there are 7 lines in total, there is a line not intersecting A1 at all. That line is contained in A2 and thus monochromatic. ✷ Now we will improve the lower bound to establish that m(3) = 7. 2.2.7 Theorem. Any system of 6 triples is 2-colorable; i.e. m(3) ≥ 7. Proof: Let us consider a 3-uniform hypergraph H = (X, S), |S| ≤ 6. We want to prove that H is 2-colorable. We will distinguish two cases, depending on the size of X. If |X| ≤ 6, we apply the probabilistic method. We can assume that |X| = 6, because we can always add vertices that are not contained in any edge and therefore do not affect the coloring condition. Then we choose a random subset of 3 vertices which we color red and the remaining vertices become blue. The total number of such colorings is 6 3 = 20. For any edge (which is a triple of vertices), there are two colorings that make it either completely red or completely blue, so the probability that it is monochromatic is 1 10 . We have at most 6 edges, and so the probability that any of them is monochromatic is at most 6 10 < 1. For |X| > 6, we proceed by induction. Suppose that |X| > 6 and |S| ≤ 6. It follows that there exist two vertices x, y ∈ X that are not “connected” (a pair of vertices is connected if they appear together in some edge). This is because every edge produces three connected pairs, so the number of connected pairs is at most 18. On the other hand, the total number of vertex pairs is at least 7 2 = 21, so they cannot be all connected. Now if x, y ∈ X are not connected, we define a new hypergraph by merging x and y into one vertex: X′ = X \ {x, y} ∪ {z}, S ′ = {M ∈ S: M ∩ {x, y} = ∅} ∪ {M \ {x, y} ∪ {z}: M ∈ S, M ∩ {x, y} 6= ∅}. This (X′ , S′ ) is a 3-uniform hypergraph as well, |S ′ | = |S| ≤ 6, and |X′ | = |X|−1, so by the induction hypothesis it is 2-colorable. If we extend the coloring of X′ to X so that both x and y get the color of z, we obtain a proper 2-coloring for (X, S). ✷
15 2.The Probabilistic Method 2.3 The Erdos-Ko-Rado Theorem 2.3.1 Definition.A family F of sets is intersecting if for all A,BF, A∩B≠0. 2.3.2 Theorem (The Erdos-Ko-Rado Theorem).If X]=n,n 2k, and F is an intersecting family of k-element subsets of X,then s) Clearly,this is tight,because a family of all the k-element subsets containing a particular point is intersecting and the number of such subsets is().(This configuration is sometimes called a sunflower and the theorem is referred to as the Sunflower Theorem.) 2.3.3 Lemma.Consider X ={0,1,...,n-1)with addition modulo n and define A.={s,s +1,...,s+k-1)X for 0ss n.Then for n z 2k,any intersecting family F()contains at most k of the sets A.. Proof.If Ai E F,then any other A.F must be one of the set only one set from each pair can appear in F. Proof of the theorem.We can assume that X={0,1,...,n-1}andF() is an intersecting family.For a permutation o:X-X,we define (As)={a(s,a(s+1),(8+k-1), by the permut by the lemma at mos are inTherefore,if we choose random s and a independently po(A,)∈刀≤ (the underlying probability space here is the product n]x S with the uniform measure,where S is the set of all permutations on In)).But this choice of (A)is equivalent to a random choice of a k-element subset of X,so P(4)∈刀=只 and
15 2. The Probabilistic Method 2.3 The Erd˝os–Ko–Rado Theorem 2.3.1 Definition. A family F of sets is intersecting if for all A, B ∈ F, A ∩ B 6= ∅. 2.3.2 Theorem (The Erd˝os–Ko–Rado Theorem). If |X| = n, n ≥ 2k, and F is an intersecting family of k-element subsets of X, then |F| ≤ n − 1 k − 1 ! . Clearly, this is tight, because a family of all the k-element subsets containing a particular point is intersecting and the number of such subsets is n−1 k−1 . (This configuration is sometimes called a sunflower and the theorem is referred to as the Sunflower Theorem.) 2.3.3 Lemma. Consider X = {0, 1, . . . , n − 1} with addition modulo n and define As = {s, s + 1, . . . , s + k − 1} ⊆ X for 0 ≤ s < n. Then for n ≥ 2k, any intersecting family F ⊆ X k contains at most k of the sets As. Proof. If Ai ∈ F, then any other As ∈ F must be one of the sets Ai−k+1, . . . , Ai−1 or Ai+1, . . . , Ai+k−1. These are 2k − 2 sets, which can be divided into k − 1 pairs of the form (As, As+k). As n ≥ 2k, As ∩ As+k = ∅, and only one set from each pair can appear in F. ✷ Proof of the theorem. We can assume that X = {0, 1, . . . , n−1} and F ⊆ X k is an intersecting family. For a permutation σ: X → X, we define σ(As) = {σ(s), σ(s + 1), . . . , σ(s + k − 1)}, addition again modulo n. The sets σ(As) are just like those in the lemma, only with the elements relabeled by the permutation σ, so by the lemma at most k of these n sets are in F. Therefore, if we choose random s and σ independently and uniformly, P[σ(As) ∈ F] ≤ k n (the underlying probability space here is the product [n] × Sn with the uniform measure, where Sn is the set of all permutations on [n]). But this choice of σ(As) is equivalent to a random choice of a k-element subset of X, so P[σ(As) ∈ F] = |F| n k and |F| = n k ! P[σ(As) ∈ F] ≤ n k ! k n = n − 1 k − 1 ! . ✷