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 the￾refore 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). ✷