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 k￾uniform 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