Luận văn Phương pháp xác suất

ú ý rằng nếu k ≥ 3 và ta lấy n = b2k/2c thì (n k ) 21−( k 2) < 2 1+k2 k! . nk 2k2/2 < 1 và có 22 R(k, k) > b2k/2c, mọi k ≥ 3.  Ví dụ đơn giản này biểu thị cốt lõi của phương pháp xác suất. Để chứng minh sự tồn tại của một cách tô màu tốt chúng ta không giới thiệu một cách tô tường minh nhưng chỉ ra mà không dựng rằng nó tồn tại. Ví dụ này xuất hiện trong tài liệu của P. Erdos từ 1947. Mặc dù Szele có ứng dụng phương pháp xác suất trong một bài toán tổ hợp khác, đưa ra trong chương 3, đã có trong 1943, Erdos chắc chắn đã là người đầu tiên hiểu đầy đủ sức mạnh của phương pháp này và ứng dụng nó thành công trong nhiều năm vào các bài toán số. Ta có thể, dĩ nhiên, phát biểu rằng xác suất là công cụ thiết yếu của chứng minh ở trên. Một chứng minh đơn giản tương đương có thể bày tỏ bằng cách đếm: Chúng ta kiểm tra rằng tổng số cách tô màu hai màu của Kn lớn hơn số cách tô hai màu mà có một đơn màuKk. Hơn nữa, do phần lớn những không gian xác suất trong việc tìm hiểu những bài toán tổ hợp xét trong không gian hữu hạn, cách liệt kê này áp dụng cho hầu hết những ứng dụng của phương pháp xác suất cho toán rời rạc. Tuy nhiên, trong thực hành, xác suất là cốt lõi. Phương pháp xác suất có một khía cạnh thuật toán thú vị. Xét, ví dụ, chứng minh của Mệnh đề 2.1.1 chỉ ra rằng có một cách tô hai màu các cạch của Kn không có đơn màu K2 log2 n. Chúng ta có thể tìm cách tô màu như vậy? Vì tổng số cách tô màu là hữu hạn, vì vậy chúng ta có thể thử tất cả chúng đến khi tìm được cái mong muốn. Tuy nhiên, thủ tục này yêu cầu 2( n 2) bước, tốn rất nhiều thời gian với cỡ [= (n 2 ) ] của bài toán. Chứng minh của bài toán chỉ ra một cách tô màu dường như tốt, hiệu quả. Đó là vì với k lớn, nếu n = b2k/2c thì ( n k ) .21−( k 2) < 21+k/2 k! .( n 2k/2 )k ≤ 2 1+k/2 k!  1. Thế nên, một cách tô màu bất kỳ của Kn dường như không chứa đơn màu K2 log2 n. Điều đó có nghĩa là, vì một lý do nào đó, chúng ta phải giới thiệu một cách tô hai màu cho các cạnh của K1024 mà không chứa đơn màu K20 nào, chúng ta có thể đơn giản tạo một cách tô màu ngẫu nhiên bằng cách tung đồng xu hai mặt (1024 2 ) lần. Chúng ta sẽ nhận được một cách tô màu đáng tin: xác suất để có một đơn màu K20 nhỏ hơn 211 20! . Do đó, trong một vài trường hợp, phương pháp xác suất không xây dựng đưa ra một giải thuật hiệu quả. 23 Phương pháp xác suất là một công cụ mạnh và hiệu quả của lý thuyết Đồ thị và Tổ hợp. Nó cũng là ứng dụng hàng đầu trong Lý thuyết Số và trong Hình học Tổ hợp. Gần đây nó được ứng dụng nhiều hơn trong việc phát triển kĩ thuật giải thuật hiệu quả và trong việc tìm hiểu những bài toán máy tính khác nhau. 2.2 Lý thuyết Đồ thị Một giải đấu trên tập V của n người chơi là một sự định hướng T = (V,E) của các cạnh của đồ thị đầy đủ trên tập n đỉnh của V . Vì vậy, với mọi hai phần tử x, y của V thì hoặc (x, y) thuộc E, hoặc (y, x) thuộc E nhưng không cả hai. Cái tên "giải đấu" là tự nhiên, vì mỗi cặp tham gia đấu tay đôi và (x, y) thuộc E nếu x thắng y. Chúng ta nói T có tính chất Sk nếu mỗi tập k người chơi có một người (của V ) đánh bại tất cả k người này. Ví dụ, tam giác liên thông T3 = (V,E), ở đây V = {1, 2, 3} và E = {(1, 2), (2, 3), (3, 1)} có tính chất S1. Liệu rằng mỗi số nguyên k sẽ có giải đấu T (nhiều hơn k người chơi) có tính chất Sk? ý tưởng cơ bản (và tự nhiên) là nếu n đủ lớn như một hàm của k thì giải đấu ngẫu nhiên trên tập n người chơi của V sẽ có tính chất Sk.Một giải đấu ngẫu nhiên là như sau. Chúng ta đưa ra một giải đấu T trên V bằng cách chọn, với mỗi 1 ≤ i < j ≤ n, hoặc cạnh (i, j) hoặc cạnh (j, i), ở đây mỗi một trong hai cách chọn là tương đương. Giả sử rằng theo cách này, mỗi một trong các giải đấu trên V là bình đẳng, không gian xác suất được xét là đối xứng. Rất đáng chú ý rằng chúng ta thường dùng trong ứng dụng những không gian xác suất đối xứng. Trong trường hợp này, chúng ta đôi khi coi những phần tử của không gian như những phần tử ngẫu nhiên, mà không mô tả cụ thể phân phối xác suất. Vì vậy, ví dụ, trong chứng minh của Mệnh đề 2.1.1, những cách tô hai màu củaKn được xét thì mỗi cách tô màu là bình đẳng với nhau. Tương tự, trong chứng minh của kết quả đơn giản sau đây chúng ta tìm hiểu về giải đấu ngẫu nhiên trên V . Định lý 2.2.1 Nếu (n k ) (1 − 2−k)n−k < 1 thì có một giải đấu n đỉnh có tính chất Sk. Chứng minh. Xét một giải đấu ngẫu nhiên của tập V = {1, 2, . . . , n}. 24 Với mỗi tập conK cố định có k đỉnh của V , đặtAK là sự kiện không có đỉnh nào đánh bại mọi thành viên củaK. Rõ ràng Pr(AK) = (1−2−k)n−k. Đây là vì mỗi đỉnh cố định v ∈ V −K, xác suất để v không đánh bại mọi thành viên của K là 1− 2−k, và tất cả n− k cách chọn khác nhau có thể của v là độc lập. Kéo theo Pr( ∨ K⊂V |K|=k AK) ≤ ∑ K⊂V |K|=k Pr(AK) = ( n k ) (1− 2−k)n−k < 1. Từ đó, với xác suất dương không sự kiện AK nào xảy ra, tức là có một giải đấu n đỉnh có tính chất Sk. Gọi f(k) kí hiệu số nhỏ nhất có thể của các đỉnh của giải đấu mà có tính chất Sk. Do (n k ) < (en k )k và (1 − 2−k)n−k < e−(n−k)/2k, Định lý 1.2.1 chứng tỏ rằng f(k) ≤ k22k(ln 2)(1 +o(1)). Không khó khăn kiểm tra rằng f(1) = 3 và f(2) = 7. Theo chứng minh của Szekeres, f(k) ≥ c1k2k.  Một tập trội của đồ thị không liên thông G = (V,E) là tập U ⊆ V sao cho mọi v ∈ V − U có ít nhất một đỉnh kề trong U . Định lý 2.2.2 Cho G = (V,E) là đồ thị n đỉnh, bậc nhỏ nhất δ > 1. Thế thì G có tập trội với nhiều nhất n1+ln(δ+1) δ+1 đỉnh. Chứng minh. Lấy p ∈ [0, 1] là số tuỳ ý. Chọn một cách ngẫu nhiên và độc lập mỗi đỉnh của V với xác suất p . Lấy X là tập (ngẫu nhiên) tất cả các đỉnh được chọn và đặt Y = YX là tập mà mọi đỉnh thuộc V − X mà không có đỉnh kề trongX . Giá trị kỳ vọng củaX rõ ràng là np. Với mỗi đỉnh v ∈ V,Pr(v ∈ Y ) = Pr(v và các đỉnh kề không trongX) ≤ (1− p)δ+1. Do kỳ vọng của tổng các biến ngẫu nhiên bằng tổng các kỳ vọng (thậm chí nếu chúng không độc lập) và do biến ngẫu nhiên |Y | có thể viết như tổng các biến ngẫu nhiên chỉ số χv(v ∈ V ), với χv = 1 nếu v ∈ V và χv = 0 nếu khác, chúng ta kết luận rằng kì vọng của |X| + |Y | nhiều nhất là np+n(1− p)δ+1. Suy ra, có ít nhất một cách chọn củaX ⊆ V sao cho |X| + |YX| ≤ np + n(1 − p)δ+1. Tập U = X ∪ YX rõ ràng là tập trội mà lực lượng của nó nhiều nhất là số này. Các lập luận trên đúng với p ∈ [0, 1] tuỳ ý. Để nhận kết quả chúng ta 25 dùng tính toán sơ cấp. Để tiện ta đánh giá 1 − p ≤ e−p (điều này đúng mọi p không âm và xấp xỉ tốt khi p nhỏ) để có đánh giá đơn giản hơn |U | ≤ np+ ne−p(δ+1). Lấy đạo hàm về phải theo p và cho bằng không, giá trị nhỏ nhất của vế phải đạt tại p = ln(δ + 1)/(δ + 1). Lấy p là giá trị này trong dòng đầu của chứng minh, ta có |U | ≤ n1+ln(δ+1) δ+1 như đã nêu.  Ba ý tưởng đơn giản nhưng quan trọng được thể hiện trong chứng minh cuối. Thứ nhất là sự tuyến tính của kỳ vọng; những kết quả đẹp được thảo luận trong chương 3. Thứ hai, có lẽ, tinh tế hơn, là sự sửa đổi sau khi thực hiện lần đầu tiên. Cách chọn ngẫu nhiên không cung cấp ngay một tập trội U mong muốn; nó chỉ cung cấp tập X , tập mà sai khác một ít (bằng cách thêm vào tập YX) để đưa ra tập trội mong muốn. Thứ ba là cách chọn của p. Chúng ta muốn tạo một lựa chọn ngẫu nhiên nhưng không biết xác suất p nào được dùng. Chúng ta cứ tiến hành chứng minh, đến cuối sẽ tìm p để đạt kết quả tối ưu. ý tưởng thứ tư là phép tính tiệm cận. Để đánh giá các kết quả, tiện hơn trong nhiều tình huống dùng đánh giá 1 − p ≤ e−p, đưa ra một đánh giá sáng sủa và dễ tính hơn là tính đúng. Chúng ta muốn tiệm cận của min np+ n(1− p)δ+1 khi p chạy khắp [0, 1]. Điểm cực tiểu đúng p = 1− (δ+1)−1/δ là khó làm việc và trong nhiều trường hợp tương tự không thể tìm được cực tiểu. Tiện hơn, chúng ta đưa ra một sai khác nhỏ, 1 − p ≤ e−p, là một đánh giá đẹp. Đây là một phần nghệ thuật của phương pháp xác suất. Liệu chúng ta có bị sai khác quá nhiều? Câu trả lời phụ thuộc vào câu hỏi ban đầu. Với δ = 3 đánh giá của chúng ta đưa đến |U | ≤ 0.596n trong khi tính toán chính xác hơn đưa đến |U | ≤ 0.496n, có lẽ là khác biệt nhiều. Với δ lớn cả hai cách đưa đến tiệm cận n ln δ δ . Kết hợp điều này với vài ý tưởng của Podderyugin và Matula, chúng ta có một giải thuật rất hiệu quả để quyết định xem liệu một đồ thị không liên thông đã cho có là n 2 -cạnh kết nối. Một lát cắt trong đồ thịG = (V,E) là cách chia tập các đỉnh thành hai tập rời nhau khác rỗng V = V1 ∪ V2. Nếu v1 ∈ V1 và v2 ∈ V2, ta nói lát cắt tách v1 và v2. Cỡ của lát cắt là số các cạnh mà một đỉnh thuộc V1 còn một đỉnh thuộc V2. Thực tế chúng ta xác định lát cắt theo các cạnh này. Số cạnh-kết nối 26 của G là số nhỏ nhất các cỡ của các lát cắt. Bổ đề sau là theo Podderyugin và Matula (một cách độc lập). Bổ đề 2.2.3 ChoG = (V,E) là đồ thị bậc nhỏ nhất δ và cho V = V1∪V2 là lát cắt có cỡ nhỏ hơn δ. Thế thì mỗi tập trội U của G có đỉnh trong V1 và V2. Chứng minh. Giả sử điều này sai và U ⊆ V1. Chọn ngẫu nhiên một đỉnh của V2 và lấy v1, v2, . . . , vδ là δ đỉnh kề của nó. Với mỗi i, xác định cạnh ei của lát cắt đã cho như sau; nếu vi ∈ V1 thì ei = {v, vi} nếu không vi ∈ V2 và do U là tập trội có ít nhất một đỉnh u ∈ U sao cho {u, vi} là một cạnh; lấy u này, và đặt ei = {u, vi}. δ cạnh e1, e2, . . . , eδ là phân biệt và đều nằm trong lát cắt đã cho, trái với giả sử cỡ của nó nhỏ hơn δ. Điều này hoàn thành chứng minh.  2.3 Tổ hợp Một siêu đồ thị là một cặp H = (V,E), ở đây V là một tập hữu hạn mà các phần tử của nó gọi là các đỉnh, còn E là họ các tập con của V , gọi là các cạnh. Nó là n-đều nếu mỗi cạnh bao gồm đúng n đỉnh. Chúng ta nói H có tính chất B, hay hai sắc nếu có cách tô hai màu của V sao cho không có cạnh nào là đơn màu. Gọi m(n) là số cạnh nhỏ nhất có thể của siêu đồ thị n-đều mà không có tính chất B. Mệnh đề 2.3.1 Mỗi siêu đồ thị n-đều với ít hơn 2n−1 cạnh đều có tính chất B. Từ đóm(n) ≥ 2n−1. Chứng minh. Gọi H = (V,E) là một siêu đồ thị n-đều với ít hơn 2n−1 cạnh. Tô màu ngẫu nhiên V bởi hai màu. Với mỗi e ∈ E, gọi Ae là sự kiện e là đơn màu. Rõ ràng Pr(Ae) = 2 1−n . Từ đó Pr( ∨ e∈E Ae) ≤ ∑ e∈E Pr(Ae) < 1 và có cách tô hai màu không có cạnh đơn màu.  Cận trên tốt nhất đã biết chom(n) được tìm bằng cách dùng lập luận xác 27 suất "trên đầu của nó". Cơ bản là, các tập trở thành ngẫu nhiên và mỗi cách tô màu xác định một sự kiện. Cố định V với v điểm, ở đây chúng ta sẽ tối ưu v sau. Đặt χ là cách tô màu với a điểm cùng một màu, b = v − a điểm cùng màu kia. Gọi S ⊆ V là một n-tập được chọn đều. Khi đó Pr(S là đơn màu ứng với χ) = (a n ) + (b n )(v n ) . Chúng ta giả sử v là chẵn cho tiện. Vì (y n ) là lồi, biểu thức này nhỏ nhất khi a = b. Vậy Pr(S là đơn màu ứng với χ) ≥ p ở đây chúng ta đặt p = 2 (v/2 n )(v n ) cho tiện trình bày. Bây giờ đặt S1, . . . , Sm là các n-tập được chọn đều và độc lập,m sẽ tính sau. Với mỗi cách tô màu χ đặt Aχ là sự kiện không có Si nào đơn màu. Bởi sự độc lập của các Si, Pr(Aχ) ≤ (1− p)m. Có 2v cách tô màu nên Pr( ∨ χ Aχ) ≤ 2v(1− p)m. Khi đại lượng này nhỏ hơn 1 thì tồn tại S1, . . . , Sm để không cóAχ nào đúng; nghĩa là S1, . . . , Sm không là hai sắc và như vậym(n) ≤ m. Chúng ta trước hết dùng bất đẳng thức 1 − p ≤ e−p. Cái này đúng với mọi số dương p và các vế hoàn toàn gần nhau khi p nhỏ. Khi m = [ v ln 2 p ] thì 2v(1 − p)m < 2ve−mp ≤ 1 nên m(n) ≤ m. Bây giờ chúng ta cần tìm v để cực tiểu v/p. Chúng ta có thể xem p như là xác suất để lấy n bi trắng từ một bình chứa v/2 bi đen và v/2 trắng, lấy mẫu không hoàn lại. Khi 28 ước lượng p bởi 2−n+1, xác suất cho lấy mẫu có hoàn lại, xấp xỉ này sẽ cho m ∼ v2n−1(ln 2). Khi v nhỏ hơn, xấp xỉ này trở nên kém chính xác và vì chúng ta muốn cực tiểum, sự tương đương trở thành thiết yếu. Chúng ta dùng xấp xỉ thứ hai p = 2 (v/2 n )(v n ) = 21−n n−1∏ i=0 v − 2i v − i ∼ 2 1−ne−n 2/2v vì khi v  n3/2, ước lượng v−2i v−i = 1− iv +O( i 2 v2 ) = e− i v +O( i 2 v2 ) . Tính toán sơ cấp đưa đến v = n2/2 cho giá trị tối ưu. Điều này đưa đến kết quả sau của Erdos (1964). Định lý 2.3.2 m(n) < (1 + o(1)) e ln 2 4 n22n. Cho F = {Ai, Bi}hi=1 là họ các tập con của tập tuỳ ý. Ta gọi F là một (k, l)-hệ nếu |Ai| = k, |Bi| = l với mọi 1 ≤ i ≤ h, Ai ∩ Bi = ∅ và Ai ∩ Bj 6= ∅ với mọi i, j phân biệt, 1 ≤ i, j ≤ h. Bollobás (1965) chứng minh kết quả sau, cái có nhiều mở rộng và ứng dụng thú vị. Định lý 2.3.3 Nếu F = {(Ai, Bi)}hi=1 là một (k, l)-hệ thì h ≤ (k+l k ) . Chứng minh. Đặt X = ⋃h i=1(Ai ∪ Bi) và xét một thứ tự ngẫu nhiên pi của X . Với mỗi i, 1 ≤ i ≤ h, gọi Xi là sự kiện tất cả phần tử của Ai đứng trước tất cả phần tử của Bi trong thứ tự này. Rõ ràng Pr(Xi) = 1/ (k+l k ) . Dễ kiểm tra rằng các sự kiện Xi là đôi một xung khắc. Giả sử khẳng định sai và pi là thứ tự trong đó mọi phần tử Ai đứng trước mọi phần tử của Bi và mọi phần tử của Aj đứng trước mọi phần tử của Bj . Không mất tổng quát có thể coi phần tử cuối củaAi không xuất hiện sau phần tử cuối củaAj . Nhưng trong trường hợp này, mọi phần tử của Ai đứng trước mọi phần tử của Bj trái giả thiết Ai∩Bj 6= ∅. Từ đó cácXi là đôi một xung khắc, như đã nêu. Kéo theo 1 ≥ Pr(∨hi=1Xi) = ∑hi=1 Pr(Xi) = h/(k+lk ), hoàn thành chứng minh.  Định lý 2.3.3 đẹp, chẳng hạn xét họ F = {(A,X \A) : A ⊂ X, |A| = k}, X = {1, 2, . . . , k + l}. 29 2.4. Lý thuyết Số Tổ hợp Một nhóm con A của nhóm abel G gọi là tổng tự do nếu (A+A)∩A = ∅, tức là không có a1, a2, a3 ∈ A để a1 + a2 = a3. Định lý 2.4.1 [Erdos (1965a)] Mỗi tập B = {b1, . . . , bn} gồm n số nguyên khác không chứa tập con A tổng tự do mà cỡ |A| > 13n. Chứng minh. Lấy p = 3k + 2 là nguyên tố, thỏa mãn p > 2max1≤i≤n|bi|, và đặt C = {k+ 1, k+ 2, . . . , 2k+ 1}. Nhận thấy rằng C là tập con tổng tự do của nhóm cyclic Zp và |C| p−1 = k+1 3k+1 > 1 3 . Ta chọn ngẫu nhiên số nguyên x, 1 ≤ x < p, theo phân phối đều trên tập {1, 2, . . . , p − 1}, và xác định {d1, . . . , dn} bởi di ≡ xbi (mod p), 0 ≤ di < p. Hiển nhiên, với mỗi i cố định, 1 ≤ i ≤ n, khi x chạy khắp các số 1, 2, . . . , p − 1 thì di chạy khắp các số khác không của Zp và có Pr(di ∈ C) = |C| p− 1 > 1 3 . Từ đó, kỳ vọng của số các phần tử bi sao cho di ∈ C lớn hơn n3 . Dẫn đến, có một x, 1 ≤ x n3 , sao cho xa (mod p) ∈ C với mọi a ∈ A. A rõ ràng tổng tự do bởi nếu a1 + a2 = a3 với a1, a2, a3 ∈ A thì xa1 + xa2 ≡ xa3 (mod p), trái tính chất là C là tổng tự do của Zp. Điều này hoàn thành chứng minh.  2.5 Các cặp rời nhau Cho F là họ các tập con rời nhau của X = {1, 2, . . . , n}. Ký hiệu d(F) là số các cặp rời nhau, tức là d(F) = |{(F, F ′) : F, F ′ ∈ F, F ∩ F ′ = ∅}|. Định lý 2.5.1ChoF là họm = 2(1/2+δ)n các tập con củaX = {1, 2, . . . , n}, với δ > 0. Thế thì d(F) < m2− δ2 2 (4) 30 Chứng minh. Giả sử (4) sai và lấy độc lập t thành viên A1, A2, . . . , At của F có lặp lại ngẫu nhiên, t là số dương lớn được chọn sau. Ta chỉ ra rằng với xác suất dương |A1 ∪ A2 . . . ∪ At| > n/2 và vẫn hợp này là rời với nhiều hơn 2n/2 tập con phân biệt của X . Sự mâu thuẫn chứng tỏ (4). Thực vậy, Pr(|A1 ∪ . . . ∪At| ≤ n/2) ≤ ∑ S⊂X,|S|≥n/2 Pr(Ai ⊂ S, i = 1, . . . , t) ≤ 2n(2n/2/2(1/2+δ)n)t = 2n(1−δt). (5) Xác định v(B) = |{A ∈ F : B ∩A = ∅}|. Rõ ràng ∑ B∈F v(B) = 2d(F) ≥ 2m2−δ2/2. Lấy Y là biến ngẫu nhiên giá trị của nó là số các thành viên B ∈ F mà rời với mọi Ai(1 ≤ i ≤ t). Bởi tính lồi của zt kỳ vọng của Y thỏa mãn E[Y ] = ∑ B∈F (v(B)/m)t = 1 mt .m( ∑ v(B)t m ) ≥ 1 mt .m( 2d(F) m )t ≥ 2m1−tδ2/2. (6) Do Y ≤ m ta kết luận rằng Pr(Y ≥ m1−tδ2/2) ≥ m−tδ2/2. (7) Ta có thể kiểm tra rằng với t = [1+1/δ],m1−tδ 2/2 > 2n/2 và vế phải của (7) lớn hơn vế phải của (5). Vì vậy, với xác suất dương, |A1∪A2 . . .∪At| > n/2 và vẫn tổng này là rời với nhiều hơn 2n/2 thành viên của F . Mâu thuẫn này chứng tỏ bất đẳng thức (4) là đúng.  31 Chương 3 Sựtuyếntínhcủakỳvọng 3.1 Cơ sở Cho X1, . . . , Xn là các biến ngẫu nhiên, X = c1X1 + . . . + cnXn. Sự tuyến tính của kỳ vọng cho biết: E[X] = c1E[X1] + . . .+ cnE[Xn]. Sức mạnh của tính chất này đến từ chỗ không bị hạn chế bởi sự phụ thuộc hay độc lập của các Xi. Trong nhiều trường hợp E[X] có thể tính dễ dàng bởi sự phân tích thành các biến ngẫu nhiênXi (thường là chỉ số). Cho σ là một phép thế ngẫu nhiên của {1, . . . , n}, được chọn đều. GọiX(σ) là số các điểm bất động của σ. Để tìm E[X] ta táchX = X1 + . . .+Xn vớiXi là biến ngẫu nhiên chỉ số của sự kiện σ(i) = i. Thế thì E[Xi] = Pr[σ(i) = i] = 1/n nên E[X] = 1/n+ . . .+ 1/n = 1. Trong ứng dụng ta thường dùng rằng có một điểm của không gian xác suất mà tại đó X ≥ E[X] và mộ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