Report

Colorings of graphs and Ramsey’s theorem •A proper coloring of a graph G is a function from the vertices to a set C of colors such that the ends of every edge have distinct colors. If |C|=k, then we say G is k-colored. •The Chromatic number (G) of a graph G is the minimal number of colors such that G is colorable. If (G) = 2, then G is a bipartite graph, which has no odd cycle. • “Four Color Theorem” (Appel and Haken, 1977) states that if G is planar, then (G) ≤ 4. Applications of graph coloring: Scheduling Final Exams: How can the final exams at a university be scheduled so that no student has two exams at the same time? Frequency Assignments: Suppose no two TV stations can operate within 220km on the same channel. How can the assignment of channels be modeled by graph coloring? Index Register: In efficient compilers the execution of loops is speeded up when frequently used variables are stored temporarily in index registers in the CPU, instead of regular memory. For a given loop, how many index registers are needed? ........ p2. Thm 3.1.(Brooks’s Theorem) Let d 3 and let G be a graph where all vertices have degree ≤ d such that Kd+1 is not a subgraph of G. Then (G) ≤ d. Pf: We prove by contradiction and with the re-coloring technique. Let G be a counterexample with the minimum number of vertices. Let x be a vertex with neighbors x1,…, xl, l ≤ d. Let H= G – {x}. Then H has a d-coloring, since G is a minimal graph without d-coloring. Let 1,…, d be the colors. If one of the colors is not used in x’s neighbors, then we’re done. Why? Thus l=d and assume xi has color i. Let Hij be a subgraph of H with colors i and j. xi and xj must be in the same connected component of Hij (say Cij). Why? p3. Can the first i have 2 neighbors with j? H=G-{x} 1 1 2 2 <= d-2 l l<=d? d x i i j j i j j i Is it possible? p4. j k i i k k j i Moreover, the component is a simple path from xi to xj in Hij. Since if 2 neighbors of xi in H had the same color j, then the other neighbors of xi in H would have at most d-2 different colors. Then we could recolor xi, which is impossible. Why? Suppose y is the first vertex on the path from xi to xj in Cij with deg 3. Then the neighbors of y in H use at most d-2 colors, so we can recolor y such that xi and xj are not connected in Hij, which is impossible. Why? Thus no such y exists and Cij is a path. Suppose z is in Cij and Cik but it is not xi. Then z has two neighbors with color j and two with color k. Again the neighbor of z in H use at most d-2 colors. Re-coloring z, we have another contradiction. So Cij Cik ={xi}. p5. By the assumption that G has no Kd+1 as subgraph, there are 2 neighbors of x, say x1 and x2, that are not adjacent. Let a be the neighbor of x1 with color 2. Interchange the colors 1 and 3 on C13. Thus a is in x1 C13 C’23 and is also in C’12. x3 Thus C’12 C’23 {x2}. a x C23 Contradiction! C12 x2 p6. Proof 2 of Brooks Theorem: Problem 3A: Fix d≥ 3. Let H be a simple graph with all degree ≤ d which cannot be d-colored and which is minimal subject to these properties. (1) Show that H is connected after deleting a vertex. (2) Then show that if partition V(H) into sets X and Y with |Y| ≥ 3, then there are at least 3 vertices a, b, c in Y each of which is adjacent to at least one vertex in X. Proof 2: Let d and H as in Problem 3A. If H is not complete, there are vertices x1,xn-1,xn so that x1 is adjacent to xn-1 and xn but the last two are not adjacent. x1 xn-1 xn Number the rest n-3 vertices such that each xk, k>1 is adjacent to at least one of xi with i< k. I.e. when x1,...,xk have been chosen k< n-2, choose xk+1 to be any vertex other than xn-1 or xn adjacent to one of x1,..xk. Why possible? p7. Proof 2 of Brooks Theorem: Once the above is done, d-color the vertices starting at the end of the sequence– assigning xn and xn-1 the same color. x1 x2 xk xk+1 xn-1 xn Inductively and finally, there is one color available If x ,..., xn have been colored properly, then xk for x1. Why?k+1 connects to at most d-1 of them. p8. Thm 3.2. If the edges of Kn are colored red or blue, and ri, i=1,…, n, denotes the number of red edges with vertex i as an endpoint, and if T is the number of monochromatic triangles, then n 1 n T= r ( n 1 r ). 3 Pf: 2 i i 1 i .. ri red edges Corollary: n T 3 n 2 n 1 2 ( 2 ) . i Ramsey number N( p, q; 2):至少需要幾人，其中才會有 p個人彼此都認識或有q個人彼此都不認識? N( 3, 2; 2) =3. N( 3, 3; 2) =6. Why? Ramsey number N( p, q; 2):至少需要幾人，其中才會有 p個人彼此都認識或有q個人彼此都不認識? Claim: N(p,q;2) ≤ N(p-1,q; 2) + N(p,q-1; 2). Proof: •Let n = N(p-1,q; 2) + N(p,q-1; 2). Consider a graph with n vertices and v be one of the vertices. •Color the edges of the graph with red and blue colors By induction the red neighbors has p vertices with in an arbitrary way. blue edges only or q-1 vertices with red edges only. Red neighbors >= N(p,q-1;2). v or Similarly, by induction, the blue neighbors has p-1 vertices with blue edges only or q vertices with red edges only. Blue neighbors >= N(p-1,q;2). Ramsey number N( p, q; 2):至少需要幾人，其中才會有p個人 彼此都認識或有q個人彼此都不認識? •By observing the binomial coefficients C(n,k), we know C(n,k)= C(n-1,k) + C(n-1, k-1). •By the claim, we have N(p,q;2) ≤ N(p-1,q; 2) + N(p,q-1; 2). •We prove Thm 3.4. N(p,q;2) ≤ C(p+q-2, q-1). By induction, assume N(p-1,q; 2) ≤ C(p+q-3, q-1) and N(p,q-1; 2) ≤ C(p+q-3, q-2). •Then N(p,q;2) ≤ N(p-1,q; 2) + N(p,q-1; 2) ≤ C(p+q-3, q-1) + C(p+q-3, q-2) = C(p+q-2, q-1) What is the value of N(p,q:2) in general? N(3,4;2) ≤ 9, by Thm 3.4 and Problem 3C. To show the equality holds, we find a coloring on K8 0 without red K3 and blue K4. 7 • Similarly, we have (Problem 3D) N(4,4;2)=18, N(3,5;2)=14. 6 2 3 5 • With a lot more work, it is known that: N(3,6;2)=18, N(3,7;2)=23, N(3,8; 2)=28 N(3,9;2)=36, N(4,5;2)=25. There is no other larger N(p,q;2) value known! 1 4 "Imagine an alien force, vastly more powerful than us landing on Earth and demanding the value of N(5, 5;2) or they will destroy our planet. In that case, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they asked for N(6, 6;2), we should attempt to destroy the aliens". - Paul Erdős p14. p, 1 2 q 3 4 5 6 7 8 9 10 已知的Ramsey Numbers 1 1 1 1 1 1 1 1 1 1 1 2 1 2 3 4 5 6 7 8 9 10 3 1 3 6 9 14 18 23 28 36 40–43 4 1 4 9 18 25 35–41 49–61 56–84 73–115 92–149 5 1 5 14 25 43–49 58–87 80–143 101–216 125–316 143–442 6 1 6 18 35–41 58–87 102–165 113–298 127–495 169–780 179–1171 7 1 7 23 49–61 80–143 113–298 205–540 216– 1031 233–1713 289–2826 8 1 8 28 56–84 101– 216 127–495 216– 1031 282– 1870 317–3583 ≤ 6090 9 1 9 36 73– 115 125– 316 169–780 233– 1713 317– 3583 565–6588 580– 12677 1 0 1 1 0 40– 43 92– 149 143– 442 179–1171 289– 2826 ≤ 6090 580–12677 798– 23556 p15. By Thm 3.4 we know N(p,p:2) ≤ 22p-2. Thm3.5. N(p,p;2) 2p/2. Kp Pf: Randomly color a Kn. There are 2 C(n,2) different ways of coloring the edges blue or red. C(n,2)-C(p,2)+1 colorings for which Fix a subgraph Kp. There are 2 Kp is monochromatic. C(n,2)-C(p,2)+1 colorings that some K There are at most C(n, p) 2 p is monochromatic. If this number is less than the total number of colorings, then there exist colorings with no monochromatic Kp. p p/2, then Since C(n,p) < n /p!, if n< 2 C(n, p) 2 C(n,2)-C(p,2)+1 < 2C(n,2) . -C(p,2)+1< (np/p!) 2-C(p,2)+1 Because C(n, p) 2 < (2p*p/p!) 2-C(p,2)+1 < 1. Thm 3.6. (Lovász Local lemma) Let G be some dependency graph for the events A1,…, An. Suppose that Pr[Ai] ≤ p, i=1,…,n and that every vertex of G has degree ≤ d. If 4dp < 1, then A i 0. Pf: First show that for every subset {i 1 , ..., i m }, P r[A i1 | A i 2 ...A i m ] 1 2d . For convenience take i j = j. It is trivial for m = 1 and for m = 2 w e have: P r[A 1 | A 2 ] p 1-p 1 / 4d 1 1 / 4d 1 4d 1 1 . 2d p17. P r[A 2 ...A q | A q+ 1 ...A m ] 1 P r[A 2 ... A q | A q+ 1 ...A m ] W e proceed by induc tion on m . q 1 toP2,3,..., r[A i | Aqq+ 1only. ...A m ] 1 S uppose 1 is adjacent i= 2 W e have P r[A 1 | A 2 ...A m ] P r[A 1 ...A n ] P r[A 1 ] 1 q 1 1 / 2. 2d P r[A 1 A 2 ...A q | A q+ 1 .. .A m ] . P r1[A ...A1 ...A P r[A A 2 2A...A + 1r[A m ] n] 3 ] q | A qP ... P r[A 1 ] P r[A 1 A 2 ] P r [ A 1 ...A n-1 ] 1 P r[A 1 A 2 ] T he num erat or is at m ost P r[A 1 | A q+ 1 . ..A m ] P r[A 1 ] . P r[A 1 ] P r[A 2 | A 1 ] P r[A 3 | A 1 A 2 ] ... P r[ A n | A 14d ...A n-1 ] B y i nduction hypothesis, the denom inator is at least q 1- P r[A i | A q+ 1 ...A m ] 1 i= 2 q 1 1 / 2. 2d T hus w e p rove the claim . n N ow P r[A 1 ...A n ] i= 1 P r[A i | A 1 ...A i-1 ] (1 1 2d ) 0. n Thm 3.7. N(p,p;2)c p 2p/2, where c is a constant. Pf. Consider Kn and color the edges randomly. For any set S of k vertices let AS be the event that the subgraph on S is monochromatic. Pr[ AS ] = 21-C(k,2). Let T be another k-set. AS and AT are dependent iff |S T| 2, i.e. the subgraphs on S and T share at least one common edge. The degree d is at most C(k,2) C(n, k-2). 1-C(k,2)C(k,2)C(n, k-2)<1, then none of A will If 4 2 S happen. k/2. By some calculation, we have n < c k 2 This means we will need larger n to have any AS happen. Let k=p. we prove the Thm. □ p19. F. R. Ramsey (1902-1928) a logician Thm 3.3. (Ramsey’s theorem 1930) Let r 1 and qi r, i=1,2,…,s be given. There exists a minimal positive number N(q1,…,qs; r) such that: Let S be a set with n elements. Suppose that all C(n,r) r-subsets of S are divided into s mutually exclusive families T1,…, Ts (colors). Then if n N(q1,…,qs; r) there is an i [s] and some qi-subset of S for which every r-subset of these qi is in Ti. We will show the case when s=2. (a) N(p,q;1)= p+q-1, Why? (b) N( p, r; r)=p and N( r, q; r)=q, for p, q r. p20. Proof of Thm 3.3. By induction on r, we assume it is true for up to r-1. Use induction on p+q, using (b). Define p1=N( p-1, q; r) and q1=N( p, q-1; r). Let S be a set with n elements, where n 1+ N(p1, q1; r-1). Let the r-subsets of S be colored with red and blue colors. Let a be an arbitrary element of S and S’=S-{a}. Define a coloring of the (r-1)-subsets of S’ by giving any (r1)-subset X S’ the same color as X {a}. By ind hyp, S’ either has a subset A of size p1 such that all its (r-1)-subsets are red or a subset B of size q1 with all its (r-1)subsets colored blue. WLOG, suppose the first case happens. Then A has N(p-1, q;r) elements. p21. A has N(p-1, q; r) elements. There are two possibilities. (1) A has a subset of q elements with all its r-subsets blue, in which we are done. (2) A has a subset A’ of size p-1 with all its r-subsets red. The set A’ {a} also has this property, since A’ A. This proves the theorem and we have: N(p, q; r) ≤ N( p1, q1; r-1) +1 = N( N(p-1, q; r) , N(p, q-1; r) ; r-1) +1. □ Taking r=2, we can obtain N(p, q; 2) ≤ N(p-1, q; 2) + N(p, q-1; 2). N(p, q; r) ≤ N( N(p-1, q; r), N(p, q-1; r); r-1) +1. r-1 N(p-1, q; r) elements. a r-1 N(p,q-1;r) elements. N(p, q; 2) ≤ N(p-1, q; 2) + N(p, q-1; 2). p-1 q-1 Problem 3C: The equality cannot hold, if the right hand side are both even. q p deg=N(p-1,q;2)+N(p,q-1;2)-1 p23. An application of Ramsey’s Theorem Theorem 3.8: For a given n, there is an integer N(n) such that any collection of N> N(n) points in the plane, no three on a line, has a subset of n points forming a convex n-gon. Proof: (1) 觀察平面上n個點，其中任何三點不共線。這n點 將形成凸n邊型若且唯若 其中任意四點形成凸四邊型。 (2)令N(n)=N(n,n;3) 。然後將這N(n)個點由1 編號並將任意三點形成的三角型塗上紅色如 果這三點的編號由小到大是順時鐘方向；否則 塗成藍色。由N(n,n;3)的定義知存在n個點，其中任意三個點形 成的三角型都是紅色的。 2 1 7 3 1 5 p24. 考慮這n個點中的任意4點，試問可否產生下列情形?也 就是說點d是否可以落在一紅色的三角型? b 其中假設 a < b < c。 c d 由圖可知 a < d < c， a 因為三角型adc為紅色。同理 a < b < d。 但由此可推論出 b < d < c，這表示 三角型bdc應當塗成藍色。 故得到矛盾。所以得知不可能有上述的情況發生， 也就是說任意四點都會形成凸四邊型。 由(1)得知這n個點會形成一凸n邊型。 p25.