Chứng minh Định lýWeierstrass theo Phương pháp Xác suất

t điểm tại đó X ≤ E[X]. Ta nêu các kết quả với mục đích bày tỏ phương pháp cơ bản này. Kết quả sau của Szele (1943) nhiều lần được xem là cách dùng đầu tiên của phương pháp xác suất. Định lý 3.1.1 Có một giải đấu T với n người chơi và ít nhất n! 12n−1 đường Hamilton. Chứng minh. Trong một giải đấu ngẫu nhiên gọi X là số đường Hamilton. Với mỗi phép thế σ gọi Xσ là biến ngẫu nhiên chỉ số mà σ đưa đến một 32 đường Hamilton, tức là thoả mãn (σ(i), σ(i+ 1)) ∈ T với mọi 1 ≤ i < n. Thế thì X = ∑ Xσ và E[X] = ∑ E[Xσ] = n!2 −(n−1). Vì vậy, một giải đấu nào đó có ít nhất E[X] đường Hamilton.  3.2 Các đồ thị tách Định lý 3.2.1 Cho G = (V,E) là một đồ thị có n đỉnh và e cạnh. Thế thì G chứa một đồ thị hai nhánh với ít nhất e/2 cạnh. Chứng minh. Gọi T ⊆ V là một tập con ngẫu nhiên cho bởi Pr[x ∈ T ] = 1/2, các cách chọn này là độc lập. Đặt S = V − T . Gọi một cạnh {x, y} là cắt ngang nếu có đúng một trong hai đỉnh x, y ở trong T . Gọi X là số các cạnh cắt ngang, ta phân tích X = ∑ {x,y}∈E Xxy với Xxy là biến ngẫu nhiên chỉ số mà {x, y} là cắt ngang. Thế thì E[Xxy] = 1/2 nên E[X] = ∑ {x,y}∈E E[Xxy] = e/2. Vậy X ≥ e/2 với một T nào đó và tập các cạnh cắt ngang tạo nên một đồ thị hai nhánh.  Một không gian xác suất chặt chẽ hơn đưa đến một cải tiến nhỏ. Định lý 3.2.2 Nếu G là một đồ thị có 2n đỉnh và e cạnh thì nó chứa một đồ thị hai nhánh với ít nhất en 2n−1 cạnh. Nếu G là một đồ thị với 2n + 1 đỉnh và e cạnh thì nó chứa một đồ thị con hai nhánh với ít nhất e(n+1) 2n+1 cạnh. Chứng minh. Khi G có 2n đỉnh lấy T được chọn đều từ trong các tập con 33 n-phần tử của V . Cạnh tùy ý {x, y} có xác suất n2n−1 để là cắt ngang và phần cuối của chứng minh như trước. Khi G có 2n+ 1 phần tử chứng minh tương tự bẳng cách chọn T đều từ các tập con n phần tử của V .  Đây là một ví dụ phức tạp hơn. Gọi V = V1 ∪ . . . ∪ Vk với Vi là các các tập rời nhau cỡ n. Gọi h : [V ]k → {−1,+1} là cách tô hai màu các k-tập. Một k-tập E là cắt ngang nếu nó chứa đúng một điểm từ mỗi Vi. Cho S ⊆ V đặt h(S) = ∑ h(E), tổng quét hết các k-tập E ⊆ S. Định lý 3.2.3 Giả sử h(E) = +1 với mọi tập cắt ngang E. Thế thì có một S ⊆ V mà |h(S)| ≥ cknk, ở đây ck là hằng số dương, độc lập với n. Bổ đề 3.2.4 Gọi Pk kí hiệu tập tất cả các đa thức thuần nhất f(p1, . . . , pk) bậc k mà các hệ số có giá trị tuyệt đối nhiều nhất là một, p1p2 . . . pk có hệ số 1. Thế thì với mọi f ∈ Pk, tồn tại p1, . . . , pk ∈ [0, 1] với |f(p1, . . . , pk)| ≥ ck, ở đây ck dương và độc lập với f . Chứng minh. Đặt M(f) = max p1,...,pk∈[0,1] |f(p1, . . . , pk)|. Cho f ∈ Pk,M(f) > 0 khi f không là đa thức không. Vì Pk là compact và M : Pk → R là liên tục,M phải có giá trị nhỏ nhất ck. Chứng minh [Định lý 3.2.3] Xác định ngẫu nhiên S ⊆ V bằng cách: Pr[x ∈ S] = pi, x ∈ Vi, những cách chọn này là độc lập, pi đã biết. ĐặtX = h(S). Với mỗi k-tập E đặt XE = { h(E) nếu E ⊆ S 0 nếu khác. 34 Nói E có kiểu (a1, . . . , ak) nếu |E ∩ Vi| = ai, 1 ≤ i ≤ k. Với những E này E[XE] = h(E) Pr[E ⊆ S] = h(E)pa11 . . . pakk . Kết hợp các số hạng bởi kiểu: E[X] = ∑ a1+...+ak=k pa11 . . . p ak k . ∑ E có kiểu (a1,...,ak) h(E). Khi a1 = . . . = ak = 1 mọi h(E) = 1 bởi giả thiết nên∑ E có kiểu (1,...,1) h(E) = nk. Với những kiểu khác có ít hơn nk số hạng, mỗi cái ±1, nên | ∑ E có kiểu (a1,...,ak) h(E)| ≤ nk. Vậy E[X] = nkf(p1, . . . , pk), ở đây f ∈ Pk, như định nghĩa trong Bổ đề 3.2.4. Bây giờ chọn p1, . . . , pn ∈ [0, 1] với |f(p1, . . . , pk)| ≥ ck. Thế thì E[|X|] ≥ E[X] ≥ cknk. Giá trị cụ thể nào đó của |X| sẽ vượt quá hoặc bằng kỳ vọng của nó. Vậy có một tập cụ thể S ⊆ V mà |X| = |h(S)| ≥ cknk.  3.3 Hai kết quả nhanh Định lý 3.3.1 Có một cách tô hai màu củaKn với nhiều nhất( n a ) 21−( a 2) 35 đơn màuKa. Chứng minh [gợi ý] Lấy một cách tô màu ngẫu nhiên. Gọi X là số các đơn màu Ka và tìm E[X]. Với cách tô màu nào đó giá trị của X nhiều nhất kỳ vọng này.  Định lý 3.3.2 Có một cách tô hai màu củaKm,n với nhiều nhất( m a )( n b ) 21−ab các đơn màuKa,b. Chứng minh [gợi ý] Lấy một cách tô màu ngẫu nhiên. Gọi X là số các đơn màuKa,b và tìm E[X]. Với X nào đó sẽ lớn nhất là kỳ vọng này.  3.4 Vectơ cân bằng Sau đây |v| là chuẩn Euclide thông thường. Định lý 3.4.1Cho v1, . . . , vn ∈ Rn, mọi |vi| = 1. Thế thì tồn tại e1, . . . , en = ±1 sao cho |e1v1 + . . .+ envn| ≤ √ n, và cũng tồn tại e1, . . . , en = ±1 sao cho |e1v1 + . . .+ envn| ≥ √ n. Chứng minh. Lấy e1, . . . , en được chọn đều và độc lập từ {−1,+1}. Đặt X = |e1v1 + . . .+ envn|2 Thế thì X = n∑ i=1 n∑ j=1 eiejvi.vj. 36 Vì vậy E[X] = n∑ i=1 n∑ j=1 vi.vjE[eiej]. Khi i 6= j,E[eiej] = E[ei].E[ej] = 0. Khi i = j, e2i = 1 nênE[e2i ] = 1. Vậy E[X] = n∑ i=1 vi.vi = n. Vậy có những e1, . . . , en = ±1 cụ thể để X ≥ n và X ≤ n. Lấy căn bậc hai hoàn thành chứng minh.  Kết quả sau bao gồm Định lý 3.4.1 ứng với trường hợp p1 = . . . = pn = 1/2. Định lý 3.4.2 Cho v1, . . . , vn ∈ Rn, mọi |vi| ≤ 1. Lấy p1, . . . , pn ∈ [0, 1] tuỳ ý và đặt ω = p1v1 + . . . + pnvn. Thế thì tồn tại e1, . . . , en ∈ {0, 1} để, với v = e1v1 + . . .+ envn, ta có |ω − v| ≤ √ n 2 . Chứng minh. Chọn các ei độc lập với Pr[ei = 1] = pi,Pr[ei = 0] = 1− pi. Chọn ngẫu nhiên ei đưa đến v ngẫu nhiên và biến ngẫu nhiên X = |ω − v|2 Ta tường minh X = | n∑ i=1 (pi − ei)vi|2 = n∑ i=1 n∑ j=1 vi.vj(pi − ei)(pj − ej) nên có E[X] = n∑ i=1 n∑ j=1 vi.vj‘E[(pi − ei)(pj − ej)] 37 Cho i 6= j, E[(pi − ei)(pj − ej)] = E[pi − ei]E[pj − ej] = 0. Cho i = j, E[(pi − ei)2] = pi(pi − 1)2 + (1− pi)p2i = pi(1− pi) ≤ 1 4 , (E[(pi − ei)2] = Var[ei]). Vậy E[X] = n∑ i=1 pi(1− pi)|vi|2 ≤ 1 4 n∑ i=1 |vi|2 ≤ n 4 và chứng minh tiếp tục như Định lý 3.4.1.  3.5 Đèn nhấp nháy Định lý 3.5.1 Cho aij = ±1 với mọi 1 ≤ i, j ≤ n. Thế thì tồn tại xi, yj = ±1, 1 ≤ i, j ≤ n sao cho n∑ i=1 n∑ j=1 aijxixj ≥ (√ 2 pi + o(1) ) n3/2. Kết quả này có một ứng dụng thú vị. Cho một mảng nìn các bóng đèn được chọn, mỗi cái hoặc bật (aij = +1) hoặc tắt (aij = −1). Giả sử mỗi dòng và mỗi cột có một sự chuyển sao cho nếu sự chuyển được xảy ra (xi = −1 cho dòng i và yj = −1 cho cột j) tất cả đèn ở hàng này sẽ chuyển: bật thành tắt và tắt thành bật. Thế thì có thời điểm số đèn bật trừ đi số đèn tắt ít nhất là ( √ 2 pi + o(1))n3/2. Chứng minh [Định lý 3.5.1] Quên các x. Lấy y1, . . . , yn = ±1 được chọn độc lập, đều và đặt Ri = n∑ j=1 aijyj, 38 R = n∑ i=1 |Ri|. Cố định i. Giá trị của aijyj là +1 hoặc −1 với xác suất 1/2 và giá trị của chúng (quét qua j) là độc lập. Vậy Ri có phân phối Sn - phân phối của tổng n biến ngẫu nhiên {−1,+1} đều, độc lập - nên E[|Ri|] = E[|Sn|] = (√ 2 pi + o(1) ) √ n. Tiệm cận này tìm bằng cách ước lượng Sn bởi √ nN , N là phân phối chuẩn thông thường theo định lý giới hạn trung tâm và dùng tính toán sơ cấp. (Mặt khác, có thể: E[|Sn|] = n21−n ( n− 1 b(n− 1)/2c ) và dùng công thức Stirling). Bây giờ áp dụng sự tuyến tính của kỳ vọng cho R, E[R] = n∑ i=1 E[|Ri|] = (√ 2 pi + o(1) ) n3/2. Có tồn tại y1, . . . , yn = ±1 để R đạt ít nhất giá trị này. Cuối cùng, lấy xi với dấu giống như Ri để có n∑ i=1 xi n∑ j=1 aijyj = n∑ i=1 xiRi = n∑ i=1 |Ri| = R ≥ (√ 2 pi + o(1) ) n3/2.  39 Chương 4 Bổđềđịaphương 4.1 Bổ đề Trong chứng minh kiểu xác suất của một kết quả tổ hợp, ta thường phải chỉ ra rằng xác suất của một sự kiện nào đó là dương. Tuy nhiên, nhiều chứng minh cho thấy xác suất để các sự kiện đang xét xảy ra không chỉ dương mà còn lớn. Thực tế, nhiều chứng minh xác suất cho thấy các sự kiện đúng với xác suất cao, xác suất dần tới một khi số chiều của bài toán tăng. Chẳng hạn, xét xác suất cho trong chương 1 rằng cho mỗi k ≤ 1 có một giải đấu trong đó cho mọi tập k người chơi có một người đánh bại tất cả người đó. Chứng minh chỉ rõ rằng cho mỗi k cố định nếu số người chơi n đủ lớn thì thì hầu hết các giải đấu của n người chơi thỏa mãn tính chất này; nghĩa là, xác suất để một giải đấu ngẫu nhiên với n người chơi có tính chất mong muốn dần tới 1 khi n dần tới vô cùng. Mặt khác, có một trường hợp tầm thường trong đó ta có thể chỉ ra sự kiện nào đó xảy ra với xác suất dương, dù rất nhỏ. Thực vậy, nếu chúng ta có n sự kiện độc lập lẫn nhau và mỗi sự kiện đúng với xác suất ít nhất p > 0, thì xác suất để tất cả các sự kiện đúng hiển nhiên ít nhất là pn, nó là dương dù có lẽ là lũy thừa nhỏ với số mũ n. Thật tự nhiên để dự đoán rằng từ trường hợp độc lập có thể tổng quát cho những trường hợp mà sự phụ thuộc là hiếm, và đưa ra một cách tổng quát hơn để chứng minh rằng các sự kiện nào đó là đúng với xác suất dương, dù nhỏ. Một cách tổng quát như thế là, thực sự, có thể, và được phát biểu trong bổ đề sau, gọi là Bổ đề Địa phương Lovász. Bổ đề đơn giản này, được chứng minh đầu tiên trong Erdos và Lovász (1975), là một công cụ mạnh hàng đầu, vì nó cung cấp một cách để đối phó với các sự kiện hiếm. 40 Bổ đề 4.1.1 [Bổ đề địa phương; Trường hợp tổng quát] Cho A1, A2, . . . , An là các sự kiện của một không gian xác suất tùy ý. Một đồ thị có hướng D = (V,E) trên tập các đỉnh V = {1, 2, . . . , n} được gọi là đồ thị có hướng phụ thuộc vào các sự kiệnA1, A2, . . . , An nếu cho mỗi i, 1 ≤ i ≤ n, sự kiện Ai là độc lập với mọi sự kiện {Aj : (i, j) /∈ E}. Giả sử rằngD = (V,E) là đồ thị có hướng phụ thuộc vào các sự kiện nêu trên và giả sử rằng có các số thực x1, x2, . . . , xn sao cho 0 ≤ xi < 1 và Pr(Ai) ≤ xi ∏ (i,j)∈E(1− xj) với mọi 1 ≤ i ≤ n. Thế thì Pr(∧ni=1Ai) ≥ ∏ni=1(1 − xi). Đặc biệt, với xác suất dương, không có sự kiện Ai nào đúng. Chứng minh. Trước hết chúng ta chứng minh, bằng quy nạp cho s, rằng cho S ⊆ {1, 2, . . . , n}, |S| = s < n nào đó và i /∈ S nào đó, Pr(Ai| ∧ j∈S Aj) ≤ xi. (8) Điều này chắc chắn đúng cho s = 0. Giả sử rằng nó đúng cho mọi s′ < s, chúng ta chứng minh nó cho s. Đặt S1 = {j ∈ S : (i, j) ∈ E}, S2 = S \ S1. Thế thì Pr(Ai| ∧ j∈S Aj) = Pr(Ai ∧ ( ∧ j∈S1 Aj)| ∧ l∈S2 Al) Pr( ∧ j∈S1 Aj)| ∧ l∈S2 Al) . (9) Để đánh giá tử thức nhận xét rằng do Ai là độc lập với các sự kiện {Al : l ∈ S2}, Pr(Ai ∧ ( ∧ j∈S1 Aj)| ∧ l∈S2 Al) ≤ Pr(Ai| ∧ l∈S2 Al) = Pr(Ai) ≤ xi ∏ (i,j)∈E (1− xj). (10) Mẫu thức, mặt khác, có thể được đánh giá dựa theo giả thiết quy nạp. Thực vậy, giả sử S1 = {j1, j2, . . . , jr}. Nếu r = 0 thì mẫu thức là 1 và dẫn đến 41 (8). Trường hợp khác Pr(Aj1 ∧Aj2 ∧ . . . ∧Ajr| ∧ l∈S2 Al) = (1− Pr(Aj1| ∧ l∈S2 Al)).(1− Pr(Aj2|Aj1 ∧ ∧ l∈S2 Al)). . . . . . . .(1− Pr(Ajr|Aj1 ∧Aj2 ∧ . . . ∧Ajr−1 ∧ ∧ l∈S2 Al)) ≥ (1− xj1)(1− xj2) . . . (1− xjr) ≥ ∏ (i,j)∈E (1− xj). (11) Kết hợp (10) và (11) vào (8), chúng ta kết luận rằngPr(Ai| ∧ j∈S Aj) ≤ xi, hoàn thành chứng minh quy nạp. Bây giờ dễ dàng suy ra khẳng định của Bổ đề 4.1.1, vì Pr( n∧ i=1 Ai) = (1− Pr(A1)).(1− Pr(A2|A1)). . . . . . . .(1− Pr(An| n−1∧ i=1 Ai)) ≥ n∏ i=1 (1− xi), (12) hoàn thành chứng minh.  Hệ quả 4.1.2 [Bổ đề Địa phương; Trường hợp đối xứng] Cho các sự kiện A1, A2, . . . , An trong một không gian xác suất tùy ý. Giả sử rằng mỗi sự kiện Ai là độc lập với tập tất cả các sự kiệnAj khác ngoại trừ nhiều nhất d, và rằng Pr(Ai) ≤ p cho mọi 1 ≤ i ≤ n. Nếu ep(d+ 1) ≤ 1 (13) thì Pr( ∧n i=1Ai) > 0. Chứng minh. Nếu d = 0 thì kết quả là tầm thường. Nếu khác, theo giả thiết có một đồ thị có hướngD = (V,E) phụ thuộc vào các sự kiệnA1, A2, . . . , An trong đó cho mỗi i, |{j : (i, j) ∈ E}| ≤ d. Bây giờ kết quả suy ra từ Bổ đề 4.1.1 bằng cách lấy xi = 1/(d+ 1)(< 1) cho mọi i và tính chất cho d ≥ 1 nào đó, (1− 1 d+1) d > 1/e.  42 Như được chỉ ra bởi Shearer vào 1985, đáng để chú ý rằng hằng số 'e' là tốt nhất có thể trong bất đẳng thức (13). Cũng chú ý rằng chứng minh của Bổ đề 5.1.1 chỉ ra rằng kết luận vẫn còn đúng nếu thay các giả thiết Ai độc lập với các {Aj : (i, j) /∈ E} và Pr(Ai) ≤ xi ∏ (i,j)∈E(1 − xj) bởi giả thiết yếu hơn Pr(Ai| ∧ j∈S2 Aj) ≤ xi ∏ (i,j)∈E(1 − xj), cho mỗi i và mỗi S2 ⊂ {1, 2, . . . , n} \ {j : (i, j) ∈ E}, điều này có ích trong một số áp dụng. Trong các mục sau chúng ta giới thiệu các áp dụng khác nhau của Bổ đề Địa phương để nhận một số kết quả tổ hợp. Không có chứng minh của kết quả nào mà không sử dụng Bổ đề Địa phương. 4.2 Tính chất B và các tập đa sắc của các số thực Nhắc lại rằng một siêu đồ thịH = (V,E) có tính chấtB (tức là hai sắc), nếu có một cách tô màu cho V bằng hai màu sao cho không có cạnh f ∈ E nào là đơn màu. Định lý 4.2.1 Cho H = (V,E) là một siêu đồ thị trong đó mỗi cạnh có ít nhất k phần tử, và giả sử rằng mỗi cạnh củaH giao với nhiều nhất d cạnh khác. Nếu e(d+ 1) ≤ 2k−1 thìH có tính chất B. Chứng minh. Tô màu mỗi đỉnh v của H , độc lập và ngẫu nhiên, hoặc xanh hoặc đỏ (với xác suất bằng nhau). Cho mỗi cạnh f ∈ E, đặt Af là sự kiện rằng f là đơn màu. Rõ ràng Pr(Af) = 2/2 |f | ≤ 1/2k−1. Hơn nữa, rõ ràng là mỗi sự kiện Af là độc lập với tất cả các sự kiện Af ′ khác cho mọi cạnh f ′ mà không giao f . Bây giờ kết quả suy ra từ Hệ quả 4.1.2.  Định lý 4.2.2 Chom và k là hai số nguyên dương thỏa mãn e(m(m− 1) + 1)k(1− 1 k )m ≤ 1. (14) Thế thì, cho mọi tập S củam số thực nào đó có một k-cách tô màu sao cho mỗi phép tịnh tiến x+ S (cho x ∈ R) là đa sắc. Chú ý rằng (14) đúng mỗi khim > (3 + o(1))k log k. 43 Chứng minh. Chúng ta trước hết cố định một tập hữu hạn X ⊆ R và chỉ ra sự tồn tại của một k-cách tô màu sao cho mỗi phép tịnh tiến x + S (cho x ∈ X) là đa sắc. Đây là một hệ quả dễ của Bổ đề Địa phương. Thật vậy, đặt Y = ∪x∈X(x + S) và cho c : Y → {1, 2, . . . , k} là một cách tô k màu của Y nhận được theo cách chọn, cho mỗi y ∈ Y , độc lập và ngẫu nhiên, c(y) ∈ {1, 2, . . . , k} theo phân phối đều trên {1, 2, . . . , k}. Cho mỗi x ∈ X , lấy Ax là sự kiện rằng x + S là không đa sắc (ứng với c). Rõ ràng Pr(Ax) ≤ k(1 − 1k)m. Hơn nữa, mỗi sự kiện Ax là độc lập với tất cả các sự kiện Ax′ khác trừ ra những sự kiện mà (x + S) ∩ (x′ + S) 6= ∅. Vì có nhiều nhất m(m − 1) sự kiện như vậy, kết quả mong muốn suy ra từ Hệ quả 4.1.2. Bây giờ chúng ta có thể chỉ ra sự tồn tại của một cách tô màu của tập gồm tất cả các số thực với tính chất mong muốn, bởi một lập luận compact chuẩn. Do một không gian rời rạc với k điểm là compact (tầm thường), Định lý Tikhonov (cái mà tương đương với tiên đề chọn) chứng tỏ rằng một tích tùy ý của các không gian như thế là compact. Đặc biệt, không gian của tất cả các hàm từ R vào {1, 2, . . . , k}, với tích tôpô thông thường, là compact. Trong không gian này cho mọi x ∈ R cố định, tập Cx của tất cả các cách tô màu c, sao cho x + S là đa sắc, là đóng. (Thực tế, nó là vừa đóng vừa mở, do một cơ sở của các tập mở là tập của tất cả các cách tô màu mà giá trị của chúng là trong một số hữu hạn của các vị trí). Vì chúng ta đã chứng minh ở trên, giao của một số hữu hạn các tập Cx nào đó là khác rỗng. Vì vậy suy ra, từ tính compact, rằng giao của tất cả các tập Cx là không rỗng. Một cách tô màu nào đó trong giao này có tính chất như trong kết luận của Định lý 4.2.2.  4.3 Cận dưới cho các số Ramsey Tìm ra cận dưới cho các số Ramsey bởi Erdos vào 1947 là một trong những áp dụng đầu tiên của phương pháp xác suất. Bổ đề Địa phương cung cấp một cách để cải tiến những cận dưới này. Chúng ta nhận được, trước tiên, cận dưới cho số Ramsey chéoR(k, k). Xét một cách tô hai màu các cạnh củaKn. Cho mỗi tập S của k đỉnh của Kn, gọi AS là sự kiện rằng đồ thị đầy đủ trên S là đơn màu. Rõ ràng Pr(AS) = 2 1−(k2) . Hiển nhiên mỗi AS là độc lập với các 44 sự kiện AT , trừ khi chúng thỏa mãn |S ∩T | ≥ 2, do ít nhất thì các đồ thị đầy đủ tương ứng có chung một cạnh. Do đó chúng ta có thể áp dụng Hệ quả 4.1.2 với p = 21−( k 2) và d = (k 2 )( n k−2 ) để kết luận: Mệnh đề 4.3.1 Nếu e( (k 2 )( n k−2 ) + 1).21−( k 2) n. Một tính toán ngắn đưa đến R(k, k) > √ 2 e (1 + o(1))k2k/2, chỉ cải tiến một nhân tử 2 so với áp dụng phương pháp xác suất trực tiếp. Dù cải tiến này là nhỏ nhưng điều đó không khiến phải băn khoăn; Bổ đề Địa phương là công cụ mạnh nhất cho những trường hợp sự phụ thuộc giữa các sự kiện là hiếm, điều không xảy ra với trường hợp đang xét. Thực vậy, tổng số các sự kiện đang xét là K = (n k ) , và bậc ngoài lớn nhất d trong đồ thị có hướng phụ thuộc là(k 2 )( n k−2 ) . Cho k lớn và n lớn hơn nhiều, ta có d > K1−O(1/k), như thế sự phụ thuộc là nhiều. Mặt khác, nếu ta xét những tập S nhỏ, chẳng hạn, những tập có cỡ 3, chúng ta nhận thấy rằng mỗi cái trong tổng số K = (n 3 ) của chúng chung nhau một cạnh với chỉ 3(n − 3) ≈ K1/3. Điều này cho biết rằng Bổ đề Địa phương có lẽ đáng chú ý hơn để cải tiến cho các số Ramsey không chéo R(k, l), đặc biệt khi một tham số là nhỏ. Tất nhiên ở đây chúng ta phải áp dụng dạng không đối xứng của Bổ đề Địa phương. Chúng ta xét một ví dụ, theo Spencer (1977), số Ramsey R(k, 3). Chúng ta tô hai màu các cạnh của Kn độc lập và ngẫu nhiên, mỗi cạnh được tô màu xanh với xác suất p. Cho mỗi tập T ba đỉnh, gọi AT là sự kiện rằng tam giác trên T là màu xanh. Tương tự, cho mỗi tập k đỉnh S, gọi BS là sự kiện đồ thị đầy đủ trên S màu đỏ. Rõ ràng Pr(AT ) = p 3 và Pr(BS) = (1− p)( k 2) . Xây dựng một đồ thị có hướng phụ thuộc vào các sự kiện AT và BS bằng cách nối hai đỉnh bằng các cạnh, với cả hai hướng, nếu và chỉ nếu đồ thị đầy đủ tương ứng chung một cạnh. Rõ ràng, mỗi AT -nút của đồ thị phụ thuộc là kề với 3(n − 3) < 3n AT ′-nút và với nhiều nhất là (n k ) BS-nút. Tương tự, mỗi BS-nút là kề với(k 2 ) (n− k) < k2n/2 AT -nút và với nhiều nhất (n k ) BS′-nút. Ta suy ra từ Bổ đề Địa phương (Bổ đề 4.1.1) rằng nếu ta có thể tìm thấy một 0 < p < 1 và hai số thực 0 ≤ x < 1 và 0 ≤ y < 1 sao cho p3 ≤ x(1− x)3n(1− y)(nk) 45 và (1− p)(k2) ≤ y(1− x)k2n/2(1− y)(nk) thì R(k, 3) > n. Vấn đề của chúng ta là tìm số lớn nhất có thể k = k(n) để có một cách chọn p, x và y như thế. Một tính toán sơ cấp chỉ ra rằng cách chọn là tốt nhất khi p = c1n −1/2, k = c2n1/2 logn, x = c3/n3/2 và y = c4 en 1/2 log2 n . Điều này đưa đến R(k, 3) > c5k 2/ log2 k. Lập luận tương tự đưa đến R(k, 4) > k5/2+o(1). Cả hai trường hợp đều yêu cầu một khối lượng tính toán lớn. Tuy nhiên, gái có công chồng chẳng phụ; đánh giá R(k, 3) > c5k 2/ log2 k tốt hơn so với cận dưới của Erdos (1961) với những lập luận rất phức tạp. Cái này được cải tiến bởi Kim (1995) tới R(k, 3) > c6k 2/ log k. Đánh giá bên trên cho R(k, 4) là tốt nhất so với tất cả các đánh giá khác được biết mà không dùng Bổ đề Địa phương. 4.4 Một kết quả hình học Một họ các hình cầu đơn vị mở F trong không gian Euclide ba chiều R3 được gọi là một phủ cơ số k của R3 nếu một điểm tùy ý x ∈ R3 thuộc ít nhất k hình cầu. Một phủ cơ số 1 được gọi đơn giản là một phủ. Một phủ cơ số k F được gọi là tách được nếu có một phân hoạch thành (các họ đôi một rời nhau) F1 và F2, mỗi họ là một phủ của R3. Mani-Levitska và Pach (1988) xây dựng một phủ cơ số k không tách được, cho số nguyên k ≥ 1 tùy ý, bởi các hình cầu đơn vị mở. Mặt khác chúng ta chứng minh được rằng một phủ cơ số k của R3 trong đó không có điểm nào bị phủ bởi nhiều hơn c2k/3 hình cầu là tách được. Điều này tiết lộ một tính chất thú vị: khó tách các phủ mà phủ các điểm nào đó của R3 nhiều lần hơn là tách các phủ mà mỗi điểm bị phủ bởi cùng một số hình cầu. Phát biểu chính xác của Định lý Mani-Levitska và Pach là như sau. Định lý 4.4.1 Cho F = {Bi}i∈I là một phủ cơ số k của một không gian Euclide ba chiều bởi các hình cầu đơn vị mở. Giả sử, thêm nữa, rằng không có điểm nào của R3 được chứa trong nhiều hơn t thành viên của F. Nếu e.t3218/2k−1 ≤ 1 thì F là tách được. 46 Chứng minh. Xác định một siêu đồ thị vô hạnH = (V (H), E(H)) như sau. Tập các đỉnh củaH , V (H), đơn giản là F = {Bi}i∈I . Cho mỗi x ∈ R3 đặt Ex là tập của các hình cầu Bi ∈ F mà chứa x. Tập các cạnh củaH , E(H), đơn giản là tập các Ex, với cách hiểu rằng khi Ex = Ey cạnh chỉ lấy một lần. Chúng ta khẳng định rằng mỗi cạnh Ex giao với ít hơn t 3218 cạnh Ey khác của H . Nếu x ∈ Bi tâm của Bi là trong khoảng cách một từ x. Bây giờ nếu Bj ∩ Bi 6= ∅ tâm của Bj là trong khoảng cách ba từ x nên Bj nằm hoàn toàn trong hình cầu bán kính bốn tâm tại x. Một Bj như thế phủ đúng 4−3 = 2−6 thể tích của hình cầu đó. Vì không có đỉnh nào bị phủ nhiều hơn t lần có thể có nhiều nhất 26t hình cầu như thế. Không khó để kiểm tra rằngm hình cầu trong R3 cắt R3 thành ít hơnm3 thành tố liên thông do đó có nhiều nhất (26t)3 Ey phân biệt giao với Ex. Bây giờ, xét, siêu đồ thị con hữu hạn L nào đó của H . Mỗi cạnh của L có ít nhất k đỉnh, và nó giao với nhiều nhất d < t3218 cạnh khác của L. Do, theo giả thiết, e(d + 1) ≤ 2k−1, Định lý 4.2.1 (cái mà là một hệ quả đơn giản của bổ đề địa phương), chứng tỏ rằng L là hai sắc. Điều này có nghĩa là ta có thể tô màu các đỉnh của L xanh và đỏ sao cho không có cạnh nào của L là đơn màu. Do điều này đúng cho L hữu hạn nào đó, một lập luận về sự compact, lập luận như trong Định lý 4.2.2, chỉ ra rằng H là hai sắc. Cho một cách tô hai màu của H mà không có cạnh nào đơn màu, chúng ta đơn giản lấy F1 là tập tất cả các hình cầu màu xanh, và F2 là tập tất cả các hình cầu màu đỏ. Rõ ràng, mỗi Fi là một phủ của R3, hoàn thành chứng minh định lý.  4.5 Số arboricity tuyến tính của đồ thị Một rừng tuyến tính là một rừng (tức là một đồ thị không có vòng) trong đó mỗi thành phần liên thông là một đường. Số arboricity tuyến tính la(G) của đồ thị G là số nhỏ nhất các rừng tuyến tính trong G, mà hợp của chúng là tập của tất cả các cạnh của G. Khái niệm này được giới thiệu bởi Harary. Giả thuyết sau, biết đến như là Giả thuyết số arboricity tuyến tính, được nảy sinh trong Akiyama, Exoo và Harary (1981). Giả thuyết 4.5.1 [Giả thuyết số arboricity tuyến tính] Số arboricity tuyến tính 47 của mọi đồ thị d-chính quy là d(d+ 1)/2e. Chú ý rằng mỗi đồ thị đầy đủ d-chính quy có nd/2 cạnh, và mỗi rừng tuyến tính trong nó có nhiều nhất n− 1 cạnh, có ngay bất đẳng thức la(G) ≥ nd 2(n− 1) > d 2 . Do la(G) là một số nguyên nó đưa đến la(G) ≥ d(d+ 1)/2e. Điều khó của Giả thuyết 4.5.1 nằm ở bất đẳng thức ngược lại: la(G) ≤ d(d+ 1)/2e. Cũng chú ý rằng mỗi đồ thị G với bậc lớn nhất ∆ là một đồ thị con của một đồ thị ∆-chính quy (cái mà có thể có nhiều đỉnh cũng như cạnh hơn G), Giả thuyết số arboricity tuyến tính tương đương với phát biểu rằng số arboricity tuyến tính của mọi đồ thị bậc lớn nhất ∆ nhiều nhất là d(∆ + 1)/2e. Mặc dù Giả thuyết này nhận được sự quan tâm lớn, kết quả tổng quát tốt nhất liên quan đến nó, được chứng minh mà không dùng lập luận xác suất, là la(G) ≤ d3∆/5e cho ∆ chẵn và la(G) ≤ d(3∆ + 2)/5e cho ∆ lẻ. Trong phần này chúng ta chứng minh rằng cho mỗi  > 0 có một ∆0 = ∆0() sao cho cho mọi ∆ ≥ ∆0(), số arboricity tuyến tính của mọi đồ thị với bậc lớn nhất ∆ nhỏ hơn là (12 + )∆. Kết quả này xuất hiện trong Alon (1988) và chứng minh của nó liên quan mật thiết đến Bổ đề Địa phương. Từ kết quả cho đồ thị có hướng chuyển sang đồ thị vô hướng là rất tiện lợi. Một đồ thị có hướng d-chính quy là một đồ thị có hướng trong đó bậc trong và bậc ngoài của mọi đỉnh đúng là d. Một rừng có hướng tuyến tính là một rừng trong đó mọi thành tố liên thông là một đường có hướng. Số arboricity tuyến tính có hướng dla(G) của một đồ thị có hướng G là số nhỏ nhất các rừng có hướng tuyến tính củaG. Bản có hướng của Giả thuyết số arboricity tuyến tính, được phát biểu đầu tiên trong Nakayama và Peroche (1987) là: Giả thuyết 4.5.2 Cho mọi đồ thị có hướng d-chính quyD, dla(D) = d+ 1. Chú ý rằng do các cạnh của một đồ thị vô hướng 2d-chính quy (liên thông) tùy ý G có thể được định hướng dọc theo một vòng Euler, sao cho đồ thị định 48 hướng kết quả là d-chính quy, sự đúng đắn của Giả thuyết 4.5.2 cho d sẽ chuyển sang Giả thuyết 4.5.1 cho 2d. Dễ dàng chứng minh được một đồ thị tùy ý với n đỉnh và bậc lớn nhất d chứa một tập độc lập với cỡ ít nhất là n/(d+ 1). Chúng ta có Mệnh đề sau. Mệnh đề 4.5.3 Cho H = (V,E) là một đồ thị với bậc lớn nhất d, và cho V = V1 ∪ V2 ∪ . . . ∪ Vr là một phân hoạch của V thành r các tập đôi một rời nhau. Giả sử mỗi tập Vi có lực lượng |Vi| ≥ 2ed, ở đây e là cơ số của logarithm tự nhiên. Thế thì có một tập các đỉnh độc lậpW ⊆ V (tức là dồ thị cảm sinh của V trênW không có cạnh nào), mà chứa một đỉnh từ mỗi Vi. Chứng minh. Rõ ràng ta có thể giả sử rằng mỗi tập Vi có lực lượng là đúng g = d2ede (nếu khác, đơn giản thay mỗi Vi bởi tập con có lực lượng g của nó, và thayH bởi đồ thị con cảm sinh của nó trên hợp của r các tập mới này). Chúng ta lấy độc lập và ngẫu nhiên từ mỗi Vi một đỉnh đơn theo phân phối đều. Lấy W là tập ngẫu nhiên của các đỉnh được lấy. Để hoàn thành chứng minh chúng ta chỉ ra rằng với xác suất dươngW là một tập các đỉnh độc lập trongH . Cho mỗi cạnh f củaH , đặtAf là sự kiện rằngW chứa cả hai đỉnh cuối của f . Rõ ràng, Pr(Af) ≤ 1/g2. Hơn nữa, nếu các đỉnh cuối của f nằm trong Vi và trong Vj , thì sự kiệnAf là độc lập với tất cả các sự kiện tương ứng với các cạnh mà các đỉnh cuối của chúng không nằm trong Vi∪Vj . Từ đó, có một đồ thị có hướng phụ thuộc vào các sự kiện trên trong đó bậc lớn nhất là ít hơn 2gd, và do e.2gd.(1/g2) = 2ed/g < 1, theo Hệ quả 4.1.2, chúng ta kết luận rằng với xác suất dương không có sự kiện Af nào đúng. Nhưng điều này chứng tỏ rằngW là một tập độc lập chứa một đỉnh từ mỗi Vi, hoàn thành chứng minh.  Định lý 4.5.4 Cho G = (U, F ) là một đồ thị có hướng d-chính quy, chu vi có hướng g ≥ 8ed. Thế thì dla(G) = d+ 1. Chứng minh. Như đã biết, F có thể phân hoạch thành d đồ thị con dẫn xuất 1-chính quy đôi một rời nhau F1, F2, . . . , Fd của G. [Đây là một hệ quả dễ 49 của Định lý Hall-Konig; cho H là một đồ thị hai nhánh mà hai lớp đỉnh của nó A,B là hai bản sao của U , trong đó u ∈ A nối với v ∈ B nếu và chỉ nếu (u, v) ∈ F . Do H là d-chính quy các cạnh của nó có thể phân chia thành d các tương xứng hoàn hảo, cái mà tương ứng với d đồ thị con dẫn xuất 1-chính quy của G.] Mỗi Fi là một hợp của các vòng có hướng các đỉnh rời nhau Ci1, Ci2, . . . , Ciri. Gọi V1, V2, . . . , Vr là các tập của các cạnh của tất cả các vòng {Cij : 1 ≤ i ≤ d, 1 ≤ j ≤ ri}. Rõ ràng các tập V1, V2, . . . , Vr là một phân hoạch của tập F chứa tất cả các cạnh của G, và do điều kiện chu vi, |Vi| ≥ g ≥ 8ed cho mọi 1 ≤ i ≤ r. Gọi H là đồ thị đường của G, nghĩa là, đồ thị mà tập đỉnh của nó là tập F gồm các cạnh của G, trong đó hai cạnh là kề nhau nếu và chỉ nếu chúng có chung một đỉnh trong G. Rõ ràng H là (4d− 2)-chính quy. Vì lực lượng của mỗi Vi ít nhất là 8ed ≥ 2e(4d− 2), nên có, theo Mệnh đề 4.5.3, một tập độc lập của H mà chứa một thành viên từ mỗi Vi. Nhưng điều này có nghĩa là có một tương xứngM trong G, chứa ít nhất một cạnh từ mỗi vòng Cij của các 1-nhân tố F1, F2, . . . , Fd. Do đó M,F1 \M,F2 \M, . . . , Fd \M là d+ 1 các rừng có hướng trongG (mỗi một trong đó là một tương xứng) mà phủ tất cả các cạnh của nó. Vậy dla(G) ≤ d+ 1. Vì G có |U |.d cạnh và mỗi rừng tuyến tính có hướng có thể có nhiều nhất là |U | − 1 cạnh, dla(G) ≥ |U |d/(|U | − 1) > d. Vì vậy dla(G) = d+ 1, hoàn thành chứng minh.  Bổ đề 4.5.5 Cho G = (V,E) là một đồ thị có hướng d-chính quy, và p là một số nguyên thỏa mãn 10 √ d ≤ p ≤ 20√d. Thế thì, có một cách tô p màu các đỉnh của G bởi các màu 0, 1, . . . , p − 1 với tính chất sau; cho mỗi cạnh v ∈ V và mỗi màu i, số N+v,i = |{(v, u) ∈ E : u có màu i}| và N−v,i = |{(u, v) ∈ E : u có màu i}| thỏa mãn: |N+(v, i)− d p | ≤ 3 √ d p √ log d, |N−(v, i)− d p | ≤ 3 √ d p √ log d. (15) 50 Chứng minh. Gọi f : V → {0, 1, . . . , p − 1} là một cách tô p màu ngẫu nhiên các đỉnh của V bởi p màu, ở đây cho mỗi v ∈ V , f(v) ∈ {0, 1, . . . , p − 1} được chọn theo phân phối đều. Cho mỗi đỉnh v ∈ V và mỗi màu i, 0 ≤ i < p, gọi A+v,i là sự kiện rằng sốN+v,i của các lân cận của v trong G mà màu của nó là i sẽ không thỏa mãn bất đẳng thức (15). Rõ ràng, N+v,i là một biến ngẫu nhiên Nhị thức với kỳ vọng d/p và phương sai chuẩn√ d p (1− d p ) < √ d p . Vậy, theo ước lượng chuẩn cho phân phối Nhị thức, cho mọi v ∈ V và 0 ≤ i < p, Pr(A+v,i) < 1/d 4. Tương tự, nếu gọi A−v,i là sự kiện số N − v,i vi phạm (15) thì Pr(A−v,i) < 1/d 4. Rõ ràng, mỗi sự kiệnA+v,i hoặcA − v,i là độc lập với tất cả các sự kiệnA + u,j hoặc A−u,j cho mọi đỉnh u ∈ V mà không có lân cận chung với v trong G. Do đó, có một đồ thị có hướng phụ thuộc vào tất cả các sự kiện của chúng ta ở trên với bậc lớn nhất ≤ (2d)2.p. Do e 1 d4 ((2d)2p + 1) < 1, Hệ quả 4.1.2 (dạng đối xứng của Bổ đề Địa phương) chứng tỏ rằng với xác suất dương không sự kiện A+v,i hoặc A − v,i nào đúng, nghĩa là có một cách tô p màu thỏa mãn (15) cho mọi v ∈ V và 0 ≤ i < p, hoàn thành chứng minh.  Bây giờ chúng ta đã sẵn sàng để đối phó với đồ thị có hướng chính quy tổng quát. Gọi G = (V,E) là một đồ thị có hướng d-chính quy tùy ý. Trong suốt các lập luận chúng ta giả sử, mỗi khi cần đến, rằng d là đủ lớn. Lấy p là một số nguyên tố thỏa mãn 10 √ d ≤ p ≤ 20√d (đã biết luôn có một số nguyên tố nằm giữa n và 2n với mọi n). Theo Bổ đề 4.5.5 có một cách tô màu các đỉnh f : V → {0, 1, . . . , p − 1} thỏa mãn (15). Cho mỗi i, 0 ≤ i < p, gọi Gi = (V,Ei) là đồ thị con có hướng dẫn xuất của G xác định bởi Ei = {(u, v) ∈ E : f(v) ≡ f(u) + i (mod p)}. Theo bất đẳng thức (15) bậc trong lớn nhất ∆−i và bậc ngoài lớn nhất ∆ + i trong mỗi Gi nhiều nhất là d p + 3 √ d p √ log d. Hơn nữa, cho mỗi i > 0, độ dài của mọi vòng có hướng trongGi chia hết cho p. Như vậy, chu vi có hướng gi củaGi ít nhất là p. Do mỗiGi có thể trở thành, do thêm vào các đỉnh và cạnh, đồ thị có 51 hướng ∆i-chính quy với cùng chu vi gi và bậc ∆i = max(∆ + i ,∆ − i ), và do gi > 8e∆i (cho tất cả d đủ lớn), chúng ta kết luận, theo Định lý 4.5.4, rằng dlaGi ≤ ∆i + 1 ≤ dp + 3 √ d p √ log d + 1 cho mọi 1 ≤ i < p. Cho G0, chúng ta chỉ cần áp dụng bất đẳng thức tầm thường dlaG0 ≤ 2∆0 ≤ 2 d p + 6 √ d p √ log d nhận bằng cách, chẳng hạn, nhúngG0 như một đồ thị con của đồ thị∆0-chính quy, tách các cạnh của đồ thị này vào ∆0 các đồ thị con 1-chính quy, và phá mỗi đồ thị con dẫn xuất 1-chính quy này thành hai rừng có hướng liên thông. Hai bất đẳng thức cuối, kết hợp với giả thiết rằng 10 √ d ≤ p ≤ 20√d, chứng tỏ dla(G) ≤ d+ 2d p + 3 √ pd √ log d+ 3 √ d p √ log d+ p− 1 ≤ d+ c.d3/4(log d)1/2. Như vậy chúng ta vừa chứng minh: Định lý 4.5.6 Có một hằng số tuyệt đối c > 0 sao cho với mọi đồ thị có hướng d-chính quy G, dla(G) ≤ d+ c.d3/4(log d)1/2. Định lý 4.5.7 Có một hằng số tuyệt đối c > 0 sao cho với mọi đồ thị vô hướng d-chính quy G, dla(G) ≤ d 2 + c.d3/4(log d)1/2. 4.6 Bước chuyển Latin Trong mục này chúng ta trình bày một áp dụng thú vị, theo Erdos và Spencer (1991). Gọi A = (aij) là một ma trận cấp n ì n với các phần tử nguyên. 52 Một phép thế pi được gọi là một bước chuyển Latin của A nếu các phần tử aipi(i) (1 ≤ i ≤ n) đều phân biệt với nhau. Định lý 4.6.1 Giả sử k ≤ (n−1)/(4e) và giả sử không có số nguyên nào xuất hiện trong nhiều hơn k phần tử của A, Thế thì A có một Bước chuyển Latin. Chứng minh. Gọi pi là một phép thế ngẫu nhiên của {1, 2, . . . , n}, được chọn theo phân phối đều trong số tất cả n! phép thế. Kí hiệu bởi T tập tất cả các bộ bốn có thứ tự (i, j, i′, j′) thỏa mãn i < i′, j 6= j′ và aij = ai′j′. Cho mỗi (i, j, i′, j′) ∈ T , kí hiệu Aiji′j′ là sự kiện pi(i) = j và pi(i′) = j′. Sự tồn tại của Bước chuyển Latin tương đương với phát biểu rằng không có sự kiện nào trong số các sự kiện này là đúng với xác suất dương. Chúng ta xác định một đồ thị có hướng đối xứng G trên tập đỉnh T bằng cách tạo (i, j, i′, j′) kề với (p, q, p′, q′) nếu và chỉ nếu {i, i′} ∩ {p, p′} 6= ∅ hoặc {j, j′} ∩ {q, q′} 6= ∅ hoặc aj = apq. Như vậy, hai bộ bốn mà không kề nhau nếu và chỉ nếu bốn ô {i, i′}, {p, p′}, {j, j′}, {q, q′} nằm ở bốn hàng và bốn cột phân biệt của A và aj 6= apq. Bậc lớn nhất của G là nhỏ hơn 4nk; thực vậy, với một (i, j, i′, j′) ∈ T đã cho có nhiều nhất 4n cách chọn (s, t) với hoặc s ∈ {i, i′} hoặc t ∈ {j, j′}, và với mỗi cách chọn (s, t) này có ít hơn k cách chọn cho (s′, t′) 6= (s, t) với ast = as′t′. Mỗi bộ bốn (s, t, s′, t′) như thế có thể viết duy nhất dạng (p, q, p′, q′) với p < p′. Do e.4nk. 1 n(n−1) ≤ 1, kết quả mong muốn suy ra từ chú ý đối với bản đối xứng của Bổ đề Địa phương, nếu chúng ta chỉ ra được Pr(Aiji′j′| ∧ S Apqp′q′) ≤ 1 n(n− 1) (16) cho (i, j, i′, j′) ∈ T tùy ý và tập S tùy ý của các thành viên của T mà không kề với (i, j, i′, j′) trong G. Bởi đối xứng, chúng ta có thể giả sử rằng i = j = 1, i′ = j′ = 2 và các giá trị của p và q không là 1 hoặc 2. Chúng ta gọi một phép thế pi tốt nếu nó thỏa mãn ∧ S Apqp′q′, và gọi Sij là tập tất cả các phép thế tốt pi thỏa mãn pi(1) = i và pi(2) = j. Chúng ta khẳng định rằng |S12| ≤ |Sij| cho tất cả i 6= j. Thực vậy, trước hết giả sử rằng i, j > 2. Cho mỗi pi ∈ S12 tốt xác định một phép thế pi∗ như sau. Giả sử pi(x) = i, pi(y) = j. Thế thì xác định pi∗(1) = i, pi∗(2) = j, pi∗(x) = 1, 53 pi∗(y) = 2 và pi∗(t) = pi(t) cho tất cả t 6= 1, 2, x, y. Chúng ta có thể kiểm tra dễ dàng rằng pi∗ là tốt, do các ô (1, i), (2, j), (x, 1), (y, 2) không là thành phần của (p, q, p′, q′) ∈ S. Như vậy pi∗ ∈ Sij , và do ánh xạ pi → pi∗ là đơn ánh |S12| ≤ |Sij|, như đã khẳng định. Tương tự chúng ta có thể xác định một đơn ánh chỉ ra rằng |S12| ≤ |Sij| thậm chí khi {1, 2} ∩ {i, j} 6= ∅ . Nó suy ra rằng Pr(A1122 ∧ ∧ S Apqp′q′) ≤ Pr(A1i2j ∧ ∧ S Apqp′q′) cho tất cả i 6= j và như thế Pr(A1122| ∧ S Apqp′q′) ≤ 1 n(n− 1). Bởi tính đối xứng, điều này chứng tỏ (16) và hoàn thành chứng minh.  4.7 Khía cạnh giải thuật Cho (n, d) là những số nguyên dương. Chúng ta mô tả bài toán (n, d) như sau: cho các tập A1, . . . , AN ⊆ Ω với mọi |Ai| = n, sao cho không có tập Ai nào giao với nhiều hơn d tập Aj khác, tìm một cách tô hai màu của Ω sao cho không có tập Ai nào đơn màu. Khi e(d + 1) < 2 n−1 , Định lý 4.2.1 khẳng định bài toán có lời giải. Chúng ta có thể tìm một cách tô màu trong số lần đa thức (của N khi n, d cố định)? Beck đưa ra câu trả lời khẳng định với một số giả thiết nghiêm ngặt hơn. Chúng ta giả sử Ω có dạng Ω = {1, . . . ,m},m ≤ Nn, và danh sách các cấu trúc dữ liệu ban đầu bao gồm danh sách các phần tử của các tập Ai và danh sách cho mỗi i các j mà j ∈ Ai. Chúng ta gọi G kí hiệu đồ thị phụ thuộc với các đỉnh là các tập Ai và Ai, Aj kề nhau nếu chúng giao nhau. Định lý 4.7.1 Cho n, d như thế, đặt D = d(d − 1)3 có tồn tại một phân tích n = n1 + n2 + n3 với 16D(1 + d) < 2n1, 16D(1 + d) < 2n2, 2e(1 + d) < 2n3. 54 Thế thì có một giải thuật ngẫu nhiên với số lần chạy trung bình O(N(lnN)c) cho bài toán (n, d), ở đây c là một hằng số (chỉ phụ thuộc vào n và d). Chứng minh. Bước Một. Trong suốt bước này, các điểm hoặc đỏ, xanh, không màu hoặc giữ lại. Chúng ta xếp các điểm j ∈ Ω thành dãy, tô màu chúng đỏ hoặc xanh ngẫu nhiên, tung một đồng xu. Sau khi mỗi j được tô màu chúng ta kiểm tra tất cả Ai 3 j. Nếu bây giờ Ai có n1 điểm trong một màu và không có điểm nào trong màu khác ta gọiAi là nguy hiểm. Tất cả các k ∈ Ai không màu bây giờ được xem là giữ lại. Khi các điểm giữ lại k được chọn trong dãy chúng sẽ không bị tô màu mà đơn giản là bỏ qua. Khi kết thúc Bước Một các điểm là đỏ, xanh hay giữ lại. Chúng ta nói một tập Ai sống sót nếu chúng không chứa các điểm cả xanh và đỏ. Kí hiệu S ⊆ G tập ngẫu nhiên của các tập sống sót. Khẳng định 4.7.2 Tất cả các thành tố C của G|S có cỡ O(lnN), hầu chắc chắn. Chứng minh. Một Ai ∈ S có thể là nguy hiểm hay, có thể, nhiều điểm của nó được giữ lại vì tập các lân cận của nó đã nguy hiểm. Xác suất để một Ai cụ thể trở thành nguy hiểm nhiều nhất là 2 1−n1 do khi tô màu n1 điểm đầu tiên thì chúng phải cùng màu. (Chúng ta có bất đẳng thức do n1 điểm của Ai phải được tô màu trước khi chúng bị giữ lại.) Gọi V là một tập độc lập trong G; nghĩa là, tập mà các Ai là đôi một rời nhau. Thế thì xác suất để tất cả các Ai ∈ V trở thành nguy hiểm nhiều nhất là (21−n1)|V |. Bây giờ lấy V ⊆ G như vậy mà khoảng cách của tất cả các Ai ∈ V ít nhất là bốn, khoảng cách được tính là độ dài đường ngắn nhất trong G. Chúng ta khẳng định rằng Pr[V ⊆ S] ≤ (d+ 1)|V |(21−n1)|V |. Đây là vì cho mỗi Ai ∈ V có nhiều nhất d + 1 cách chọn cho một lân cận nguy hiểmAi′, đưa đến (d+ 1) |V | cách chọn choAi′. Vì cácAi cách nhau ít nhất bốn nên Ai′ không thể là kề và có xác suất để tất cả chúng là nguy hiểm nhiều nhất là (21−n1)|V |, như đã khẳng định. Gọi T ⊆ G là một 4-cây nếu khoảng cách giữa tất cả cácAi ∈ T với nhau là ít nhất bốn và sao cho, vẽ một cung giữaAi, Aj và nếu khoảng cách giữa chúng 55 đúng là bốn thì đồ thị kết quả là liên thông. Chúng ta trước hết đánh giá số các 4-cây có cỡ u. Đồ thị khoảng cánh bốn xác định trên T phải chứa một cây. Có ít hơn 4j cây (theo nghĩa đẳng cấu) trên j đỉnh, bây giờ cố định một cái. Chúng ta có thể dán nhãn cây 1, . . . , u sao cho mỗi j > 1 là kề với một i < j nào đó. Bây giờ xét số các (A1, . . . , Au) mà đồ thị khoảng cách bốn của nó tương ứng với cây này. Có N cách chọn cho A1. Với Ai đã chọn cho tất cả i < j tập Aj phải có khoảng cách bốn từ Ai trong G và có nhiều nhất D điểm như vậy. Vậy số các 4-cây có cỡ u nhiều nhất là 4uNDu−1 < N(4D)u. Cho 4-cây T cụ thể nào đó chúng ta có Pr[T ⊆ S] ≤ [(d + 1)21−n1]u. Vậy số kì vọng các 4-cây T ⊆ S nhiều nhất là N [8D(d+ 1)2−n1]u. Vì số hạng trong ngoặc nhỏ hơn 1/2 theo giả thiết, cho u = c1 lnN số hạng này là o(1). Như vậy G|S sẽ không chứa 4-cây có cỡ lớn hơn c1 lnN hầu chắc chắn. Chúng ta đang muốn đánh giá cỡ của các thành tố C trong G|S. Một 4-cây T trong một thành tố C phải có tính chất rằng mỗi Ai ∈ C nằm trong khoảng cách ba của một Aj ∈ T . Có ít hơn d3 (một hắng số) Ai trong khoảng cách ba củaAj nào đó dã cho sao cho c1 lnN ≥ |T | ≥ |C|d−3 nên, |C| ≤ c2 lnN chứng minh khẳng định. Trong số thời gian tuyến tính trung bình Bước Một sẽ thành công. Bây giờ cố định các điểm đỏ hoặc xanh. Bỏ qua các tập chứa cả các điểm màu đỏ và màu xanh. Cho mỗi Ai sống sót cố dịnh một tập con Bi gồm n − n1 điểm giữ lại. Bây giờ tô màu các điểm giữ lại sao cho không có Bi nào đơn màu là xong. Bi tách vào các thành tố có cỡ O(lnN) và tô màu mỗi thành tố này riêng biệt là xong. Trong Bước Hai chúng ta áp dụng phương pháp của Bước Một đối với mỗi thành tố của Bi. Bây giờ chúng ta gọi một tập Bi là nguy hiểm nếu nó chứa đúng n2 điểm cùng một màu và các điểm khác được giữ lại. Bước Hai tốn thời gian trung bình O(lnM) để tô màu một thành tố cỡM , vậy một thời gian trung bình O(N) để tô màu tất cả các thành tố. (Để thành công chúng ta yêu cầu rằng một thành tố cỡM bị phá thành các thành tố cỡ c2 lnM . Để tránh tầm thường, nếuM < ln lnN thì chúng ta bỏ qua Bước Hai với thành tố tương ứng.) Khi kết thúc Bước Hai (vẫn trong thời gian tuyến 56 tính!) có một họ các tập sống sót hai lần Ci ⊂ Bi ⊂ Ai có cỡ n3, thành tố lớn nhất của chúng có cỡ O(ln lnN). Chúng ta vẫn cần tô màu O(N) thành tố cỡ O(ln lnN) này, mỗi thành tố có cỡ n3. Theo Bổ đề Địa Phương (hay trực tiếp theo Định lý 4.2.1), mỗi thành tố này có thể là hai sắc. Chúng ta đã tìm được một cách tô hai màu bằng cách tô màu nhiều chặng! Kiểm tra tất cả các cách tô hai màu của một thành tố có cỡM tốn O(M2nM) lần, ứng với O((lnN)c) trong trường hợp của chúng ta. Làm điều này cho tất cả các thành tố tốn O(N(lnN)c) lần. Đến đây hoàn thành cách tô màu.  57 Chương 5 ChứngminhđịnhlýWeierstrasstheophươngphápxácsuất Trong giải tích cơ sở ta biết nếu một hàm số thực f(x) có đạo hàm mọi cấp trong lân cận của điểm x = 0 thì có thể biểu diễn nó thành chuỗi lũy thừa dạng ∑∞ n=0 anx n . Gọi K là bán kính hội tụ của chuỗi lũy thừa này thì chuỗi hội tụ với mọi |x| ≤ R, (0 0 cho trước, ta có thể lấy một tổng riêng đủ lớn của chuỗi là Pn(x) = ∑n k=0 akx k (là một đa thức bậc n) sao cho |Pn(x)− f(x)| < , |x| ≤ R. Tuy nhiên nếu f không có đạo hàm mọi cấp thì không tồn tại biểu diễn của f thành dạng chuỗi lũy thừa như trên. Nhưng với f là hàm liên tục trên [a, b] ta vẫn có thể xấp xỉ đều f bởi các đa thức trên đoạn [a, b] một cách tùy ý gần. Khẳng định này là một kết quả của một định lý cơ sở quan trọng trong giải tích: Định lý xấp xỉ Weierstrass. Chương này trình bày phương pháp chứng minh định lý quan trọng đó theo công cụ xác suất và cũng cho một đánh giá về tốc độ hội tụ của xấp xỉ. Xin chú ý rằng cách dùng xác suất ở đây khác với phương pháp xác suất trình bày trong những chương trước. 5.1 Một số kiến thức xác suất cơ sở chuẩn bị Trong toàn bộ chương này ta giả sử (Ω,F,Pr) là không gian xác suất và các biến ngẫu nhiên xét đến là xác định trên Ω và nhận giá trị trong R. Biến ngẫu nhiên nhị thức Biến ngẫu nhiên X gọi là nhị thức B(n, p), p ∈ [0, 1] (chính xác là biến ngẫu nhiên có phân phối nhị thức B(n, p)) nếu như phân bố xác suất của nó 58 có dạng Pr(X = k) = ∫ {ω:X(ω)=k} Pr(dω) = ( n k ) pk(1− p)n−k, trong đó k = 0, 1, . . . , n. Hàm đặc trưng của biến ngẫu nhiên nhị thức Cho X là biến ngẫu nhiên, hàm đặc trưng ϕ(t) của X được định nghĩa như sau: ϕ(t) = E[eitX], t ∈ R (kỳ vọng lấy theo độ đo xác suất Pr). VớiX là biến ngẫu nhiên nhị thức ta có ϕ(t) = E[eitX] = n∑ k=0 eitk Pr(X = k) = n∑ k=0 eitk ( n k ) pk(1− p)n−k = n∑ k=0 ( n k ) (peit)k(1− p)n−k = [peit + (1− p)]n. Vậy hàm đặc trưng của biến ngẫu nhiên nhị thức là ϕ(t) = [peit + q]n, q = 1− p. (17) Nếu X1, . . . , Xn là các biến ngẫu nhiên độc lập và có cùng phân phối nhị thức B(1, p) thì ∑n k=1Xk là biến ngẫu nhiên nhị thức B(n, p). Thật vậy, đặt Sn = n∑ k=1 Xk, ta có hàm đặc trưng của Sn là ϕSn(t) = E[e itSn] = E[eit ∑n k=1Xk] = E[eitX1 . . . eitXn] = E[eitX1] . . . E[eitXn] = (peit + q)n 59 (biến đổi sau cùng ở trên là do các Xi độc lập và có cùng phân phối). Từ đó suy ra Sn có phân phối nhị thức B(n, p). Các số đặc trưng của biến ngẫu nhiên nhị thức Cho X là biến ngẫu nhiên nhị thức B(n, p), ta có ϕ(t) = E[eitX] = (peit + q)n ≡ ϕn(t) ϕ′(t) = E[iXeitX] = npieit(peit + q)n−1 = npieitϕn−1(t) Suy ra ϕ′(0) = iE[X] = inp nên E[X] = np. Tiếp tục lấy đạo hàm cấp hai, ta được ϕ′′(t) = E[(iX)2eitX] = −npeit[ϕn−1(t) + (n− 1)peitϕn−2(t)] do đó ϕ′′(0) = −E[X2] = −np[1 + (n− 1)p] Suy ra E[X2] = np+ n(n− 1)p2. Từ đó tính được phương sai của X là Var[X] = E[X2]− [EX]2 = np+ n(n− 1)p2 − (np)2 = np(1− p) = npq. Vậy kỳ vọng và phương sai của X cho bởi E[X] = np,Var[X] = npq. Tất nhiên ta cũng có thể tính trực tiếp công thức trên theo định nghĩa kỳ vọng và phương sai. 60 5.2 Định lý xấp xỉ Trong mục con này ta chứng minh định lý xấp xỉ bằng phương pháp xác suất. Kí hiệu: C([a, b],R) là không gian các hàm thực liên tục trên [a, b], P([a, b],R) là không gian các đa thức thực trên [a, b], và chuẩn sử dụng trên chúng là chuẩn đều ||.||u, tức là ||f ||u = sup x∈[a,b] f(x) = max x∈[a,b] f(x), với f ∈ C([a, b],R). Có thể thấy P([a, b],R) ⊂ C([a, b],R). Định lý xấp xỉ phát biểu như sau. Định lý 5.2.1 (xấp xỉ Weierstrass) Cho f ∈ C([a, b],R) và  > 0. Khi đó tồn tại đa thức P ∈ P([a, b],R) sao cho ||P − f ||u = max x∈[a,b] |P (x)− f(x)| < . Định lý xấp xỉ cũng có thể phát biểu dạng: Không gian P([a, b],R) là trù mật trong C([a, b],R). Chứng minh. Không mất tổng quát ta chỉ cần chứng minh định lý trong trường hợp đoạn [a, b] là [0, 1]. Vì nếu không chỉ cần sử dụng phép đổi biến t = x− a b− a , x ∈ [a, b]. Cho f ∈ C([0, 1],R). Vì f liên tục trên [0, 1] nên nó liên tục đều và bị chặn trên [0, 1]. Từ đó với mỗi  > 0, tồn tại δ > 0 sao cho ∀x, x′ ∈ [0, 1], |x− x′| < δ : |f(x)− f(x′)| <  2 và tồn tạiM > 0 dể ||f ||u = max x∈[0,1] |f(x)| ≤M. 61 Với mỗi x ∈ [0, 1], gọi Bxn là biến ngẫu nhiên nhị thức B(n, x), n ∈ N. Từ bất đẳng thức Chebyschev ta có với mỗi n, Pr(|Bxn − E[Bxn]| > n2/3) ≤ x(1− x) n1/3 < 1 n1/3 nên với  và δ ở trên, tồn tại n ∈ N sao cho Pr(|Bxn − E[Bxn]| > n2/3) <  4M (18) và 1 n1/3 < δ. (19) Đặt bn(x) ≡ E[f( Bxn n )] = n∑ k=0 f( k n ) ( n k ) xk(1− x)n−k, x ∈ [0, 1]. (20) Khi đó |bn(x)− f(x)| = |E[f( Bxn n )− f(x)]| ≤ E[|f(B x n n )− f(x)|] = ∫ {ω:|Bxn−nx|≤n2/3} |f(B x n(ω) n )− f(x)|Pr(dω) + ∫ {ω:|Bxn−nx|>n2/3} |f(B x n(ω) n )− f(x)|Pr(dω) ≤ ∫ {ω:|Bxn−nx|≤n2/3} |f(B x n(ω) n )− f(x)|Pr(dω) +2M Pr(|Bxn − nx| > n2/3). Để ý (19) ta có {ω : |Bxn − nx| ≤ n2/3} = {ω : | Bxn(ω) n − x| ≤ 1 n1/3 < δ}. 62 Kết hợp với (18) suy ra |bn(x)− f(x)| <  2 Pr(|Bxn − nx| ≤ n2/3) +  2 ≤ . Do đó ||bn − f ||u = max x∈[0,1] |bn(x)− f(x)| < . Đây là điều phải chứng minh.  Chú ý rằng đa thức xác định theo công thức (20) gọi là đa thức Bernstein bậc n của f(x). Từ định lý trên ta thấy với f ∈ C([0, 1],R) thì dãy các đa thức {bn(x)}∞n=1 ⊂ P([0, 1],R) là hội tụ theo chuẩn đều đến f , nghĩa là P([0, 1],R) là trù mật trong C([0, 1],R). Từ điều này thì E[f( Bxn n )]→ f(x), n→∞ đều theo x ∈ [0, 1]. Ngoài ra, có thể thấy f( Bxn n )→ f(x), n→∞ (h.c.c). Thật vậy, tiến hành n phép thử độc lập. Gọi biến ngẫu nhiên Xxi = { 1, nếu phép thử thứ i thành công 0, nếu phép thử thứ i thất bại thì Xxi là biến ngẫu nhiên nhị thức B(1, x) và khi đó có thể xem Bxn = n∑ i=1 Xxi thể hiện cho số lần thành công trong n lần thực hiện đó và Bxn là biến ngẫu nhiên nhị thức B(n, x). Do đó theo luật mạnh số lớn ta có 1 n n∑ i=1 Xxi = Bxn n → E[Xx1 ], n→∞ (h.c.c). Trong đó E[Xx1 ] = Pr(X x 1 = 1) = x. 63 Vì thế với f ∈ C([0, 1],R), x ∈ [0, 1], ta có f( Bxn n )→ f(x), n→∞ (h.c.c) 5.3. Một đánh giá về tốc độ hội tụ của đa thức Bernstein Định lý xấp xỉ Weierstrass của dãy hàm {bn(x)}∞n=1 về hàm liên tục f ∈ C([0, 1],R) đều trên [0, 1] không cho ta thông tin về tốc độ hội tụ. Mục con này cho ta một đánh giá về tốc độ hội tụ. Cho f ∈ C([a, b],R). Khi đó, với bất kỳ δ > 0, môđun liên tục của f trên [a, b] là đại lượng ω(δ) ≡ sup |x−x′|<δ |f(x)− f(x′)|, x, x′ ∈ [a, b]. Chúng ta có định lý sau về môđun liên tục. Định lý 5.3.1 (a) Nếu 0 < δ1 ≤ δ2 thì ω(δ1) ≤ ω(δ2). (b) Điều kiện cần và đủ để f liên tục đều trên [a, b] là lim δ→0 ω(δ) = 0. (c) ∀λ > 0, ω(λδ) ≤ (λ+ 1)ω(δ). Chứng minh. Thấy rằng (a) và (b) là hiển nhiên. Với λ > 0 đã cho, tồn tại n ∈ N : n ≤ λ < n+ 1. Từ tính chất (a) suy ra ω(λδ) ≤ ω[(n+ 1)δ]. Lấy x, x′ ∈ [a, b] sao cho x < x′ và |x − x′| ≤ (n + 1)δ. Chia đoạn [x, x′] thành n + 1 phần bằng nhau, độ dài mỗi phần là x ′−x n+1 với các điểm chia yi = x+ i x′ − x n+ 1 , i = 0, 1, . . . , n+ 1. 64 Khi đó |f(x)− f(x′)| = | n∑ i=0 [f(yi+1)− f(yi)]| ≤ n∑ i=0 |[f(yi+1)− f(yi)]| ≤ (n+ 1)ω(δ), (vì |yi+1 − yi| = 1n+1|x′ − x| ≤ δ, i = 0, 1, . . . , n). Suy ra ω[(n+ 1)δ] = sup |x−x′|≤(n+1)δ |f(x)− f(x′)| ≤ (n+ 1)ω(δ). Từ đó ω(λδ) ≤ ω[(n+ 1)δ] ≤ (n+ 1)ω(δ). ≤ (λ+ 1)ω(δ).  Tiếp theo là kết quả về tốc độ hội tụ của đa thức Bernstein. Định lý 5.3.2 Cho f ∈ C([0, 1],R) và bn(x) là đa thức Bernstein của f . Khi đó ||bn − f ||u = max x∈[0,1] |bn(x)− f(x)| ≤ 3 2 ω( 1√ n ), với ω(δ) là môđun liên tục của f trên [0, 1]. Chứng minh. Ta có |bn(x)− f(x)| = |E[f( Bxn n )− f(x)]| ≤ E[|f(B x n n )− f(x)|] = n∑ k=0 |f(k n )− f(x)| ( n k ) xk(1− x)n−k ≤ n∑ k=0 ω(|x− k n |) ( n k ) xk(1− x)n−k. 65 áp dụng Định lý 5.3.1(c), ω(|x− k n |) = ω(n1/2|x− k n |n−1/2) ≤ (1 + n1/2|x− k n |)ω(n−1/2). Vì thế |bn(x)− f(x)| ≤ n∑ k=0 (1 + n1/2|x− k n |)ω(n−1/2) ( n k ) xk(1− x)n−k ≤ ω(n−1/2)[1 + n1/2 n∑ k=0 |x− k n | ( n k ) xk(1− x)n−k]. Sử dụng bất đẳng thức Cauchy-Schwarz ta có n∑ k=0 |x− k n | ( n k ) xk(1− x)n−k = n∑ k=0 |x− k n |( ( n k ) xk(1− x)n−k)1/2( ( n k ) xk(1− x)n−k)1/2 ≤( n∑ k=0 (x− k n )2 ( n k ) xk(1− x)n−k)1/2( n∑ k=0 ( n k ) xk(1− x)n−k)1/2 =( x(1− x) n )1/2 ≤ ( 1 4n )1/2. Suy ra |bn(x)− f(x)| ≤ ω(n−1/2)(1 + n1/2( 1 4n )1/2), nên |bn(x)− f(x)| ≤ 3 2 ω(n−1/2), ∀x ∈ [0, 1].  Hệ quả 5.3.3 Nếu f là một hàm liên tục Lipschitz Lip(K, α) trên [0, 1] (nghĩa là |f(x)− f(x′)| ≤ K|x− x′|α, ∀x, x′ ∈ [0, 1], α > 0) thì |bn(x)− f(x)| ≤ 3 2 Kn−α/2. 66 Chứng minh. Từ điều kiện Lipschitz ta có ω(δ) ≤ Kδα. Sử dụng Định lý 5.3.2 suy ra |bn(x)− f(x)| ≤ 3 2 Kn−α/2, ∀x ∈ [0, 1].  Để kết thúc, ta nêu một ví dụ. Ta có hàm f(x) = √ x là Lip(1, 1/2) với x ≥ 0. Từ Hệ quả 5.3.3 trên suy ra |bn(x)− √ x| ≤ 3 2n1/4 , ∀x ∈ [0, 1]. trong đó bn(x) = n∑ k=0 ( k n )1/2 ( n k ) xk(1− x)n−k, x ∈ [0, 1]. 67 Kết luận Luận văn đã làm được những việc sau: • Trình bày cơ sở về đồ thị. • Giải một số bài toán bằng Phương pháp Xác suất cơ bản để làm rõ về phương pháp. • Trình bày Phương pháp Xác suất kết hợp với tính chất của kỳ vọng của các biến ngẫu nhiên. • Trình bày về kĩ thuật áp dụng Bổ đề Địa phương. • Dùng kĩ thuật Xác suất để chứng minh định lý Weierstrass. Một số vấn đề cần tiếp tục nghiên cứu: • Tìm lời giải cho các bài toán thuộc nhiều lĩnh vực khác nhau. • Những ứng dụng thực tế của Phương pháp Xác suất, chẳng hạn như trong Khoa học Máy tính, trong đó đặc biệt quan tâm đến việc xây dựng các giải thuật để tìm các cấu trúc có tính chất mong muốn. 68 Tài liệu tham khảo [1] Noga Alon, Joel H. Spencer (2000), The Probabilistic Method, John Wiley & Sons Inc, New York. [2] Béla Bollobás (1998), Modern Graph Theory, Springer, New York. [3] Nguyễn Viết Phú, Nguyễn Duy Tiến (2004), Cơ sở Lý thuyết Xác suất, Nhà xuất bản Đại học Quốc gia Hà Nội, Hà Nội. [4] Nguyễn Duy Tiến, Vũ Viết Yên (2006), Lý thuyết Xác suất, Nhà xuất bản Giáo dục, Việt Nam. [5] Đặng Hùng Thắng (2008), Thống kê và ứng dụng, Nhà xuất bản Giáo dục, Việt Nam. [6] Nguyễn Hắc Hải (2007), Xác suất & Thống kê, Bộ Giáo dục và Đào tạo (Giáo trình điện tử), Hà Nội. [7] Nguyễn Hữu Ngự (2001), Lý thuyết Đồ thị, Nhà xuất bản Đại học Quốc gia Hà Nội, Hà Nội. 69