Hôm nay, mình sẽ bắt đầu bằng các ví dụ cơ bản và những cách tiếp cận cơ bản đầu tiên.
Số Ramsey $R(k,m)$ là số tự nhiên $n$ nhỏ nhất sao cho trong bất kì một cách tô màu các cạnh đồ thị đầy đủ $K_n$ bởi hai màu xanh và đỏ thì hoặc tồn tại một đồ thị con đơn sắc đỏ $K_k$ hoặc tồn tại một đồ thị con đơn sắc xanh $K_m.$ Năm $1929,$ Ramsey chỉ ra rằng $R(k,m)$ là một số hữu hạn với mỗi $k$ và $n.$ Mệnh đề dưới đây được cho ta một chặn dưới của số Ramsey.
Mệnh đề 1. Nếu $\binom{n}{k} \cdot 2^{1-\binom{k}{2}} < 1$ thì $R(k,k) > n.$ Do đó $R(k,k) > [2^{k/2}]$ với mọi $k \ge 3.$ Ở đây $[x]$ là phần nguyên của $x.$
Chứng minh. Ta sẽ tiếp cận bài toán này bằng phương pháp xác suất.
Xét một cách tô màu ngẫu nhiên các cạnh của $K_n$ bởi hai màu thu được bằng cách tô màu các cạnh một cách độc lập bởi hai màu xanh và đỏ với xác suất như nhau. Với một tập $R$ cố định gồm $k$ đỉnh, gọi $A_R$ là biến cố được sinh bởi đồ thị con của $K_n$ trên $R$ là đơn sắc (tức tất cả các cạnh hoặc đều được tô đỏ hoặc đều được tô xanh). Rõ ràng ta có
$$ Pr(A_R) = \dfrac{2}{2^{\binom{k}{2}}} = 2^{1- \binom{k}{2}}.$$
Vì có tất cả $\binom{n}{k}$ cách chọn $R$ nên xác suất để có một biến cố $A_R$ xuất hiện là
$$ \binom{n}{k} 2^{1 - \binom{n}{k}} < 1.$$
Điều này dẫn tới, tất cả các $A_R$ đều không xuất hiện có thể xảy ra với một xác suất dương, tức là không có đồ thị con đơn sắc $K_k$ của $K_n.$ Điều này dẫn tới $R(k,k) > n.$
Chú ý với $k \geq 3$ và lấy $n = [2^{k/2}]$ thì ta có
$$ \binom{n}{k} 2^{1-\binom{k}{2}} < \frac{2^{1+\frac{k}{2}}}{k!} \cdot \frac{n^k}{2^{k^2/2}} < 1$$
và do đó $R(k,k) > [2^{k/2}]$ với mọi $k \geq 3.$
Nhận xét: Về cơ bản cách giải trên có thể thực hiện lại dưới dạng phương pháp đếm trong tổ hợp. Tuy nhiên, nó được sử dụng một cách sáng tạo hơn và trong thực tế nó là một công cụ mạnh khi chúng ta có các kết quả về xác suất như kì vọng hay các hàm moment.
Tiếp theo, chúng ta sẽ sử dụng phương pháp xác suất vào lý thuyết đồ thị để chứng minh một vài kết quả cơ bản.
Một giải đấu trên tập $V$ có $n$ người chơi là một tập định hướng $T = (V,E)$ gồm các cạnh của đồ thị đầy đủ trên tập hợp $V.$ Theo định nghĩa được xác định đồ thị đầy đủ thì với hai phần tử $x$ và $y$ bất kì của $V$ thì hoặc $(x,y) \in E$ hoặc $(y,x) \in E$ nhưng cả hai không cùng thuộc $E.$ Cái tên giải đấu là tự nhiên, khi chúng ta có thể xem các phần tử của một tập $V$ như là các người chơi, hai phần tử $(x,y)$ là một trận đấu khi và chỉ khi $x$ đánh bại $y.$
Chúng ta nói $T$ có tính chất $S_k$ nếu với mọi tập hợp gồm $k$ người chơi, luôn tồn tại một người chơi khác đánh bại tất cả $k$ người chơi đó.
Một câu hỏi được đặt ra bởi Erdos vào năm 1963:
"Liệu có phải với mọi số k hữu hạn luôn tồn một giải đấu $T$ (có nhiều hơn $k$ đỉnh) sao cho $T$ có tính chất $S_k$?"
Vì tính hữu hạn nên chúng ta có thể cảm nhận được tính chất này đúng.
Ta sẽ chứng minh tính chất trên bởi mệnh đề sau.
Mệnh đề 2. Cho $n$ và $k$ là hai số tự nhiên thỏa mãn $\binom{n}{k}(1-2^{-k})^{n-k} < 1.$ Khi đó tồn tại một giải đấu trên $n$ người chơi có tính chất $S_k.$
Chứng minh. Xét một giải đấu ngẫu nhiên trên tập $V = \{ 1, 2, \dots, n \}.$ Với mỗi tập con $K$ cố định của $V$ với $|K| = k,$ gọi $A_k$ là biến cố: "Không có người chơi nào đánh bại tất cả các người chơi trong $K$". Vì với mọi $v \in V - K$ cố định thì xác suất để $v$ không đánh bại tất cả các người chơi trong $K$ là $1-2^{-k}$ nên theo tính độc lập ta có
$$ Pr(A_K) = (1 - 2^{-k})^{n-k}.$$
Đều này dẫn tới
$$Pr\left( \bigcup_{K \subset V, |K| = k } A_K \right) \leq \sum_{S \subset V, |K| =k} Pr(A_K) = \binom{n}{k}(1 - 2^{-k})^{n-k} < 1. $$
Điều này chứng tỏ, với một xác suất dương thì không có biến cố $A_K$ nào xuất hiện. Do đó, tồn tại một giải đấu trên $n$ người chơi có tính chất $S_k.$
Về cơ bản, cách tiếp cận của Mệnh đề 2 và Mệnh đề 1 là như nhau. Tuy nhiên ở Mệnh đề 2, chúng ta bắt đầu sử dụng nhiều hơn một chút của lý thuyết xác suất. Ví dụ tiếp theo sẽ là một cách tiếp cận mới, bằng việc sử dụng Kỳ vọng của một biến ngẫu nhiên. Để bắt đầu, chúng ta nhắc lại định nghĩa tập thống trị (dominating set) của một đồ thị.
Định nghĩa. Một tập thống trị của đồ thị vô hướng $G = (V,E)$ là một tập $U \subset V$ sao cho mọi đỉnh $v \in V - U$ có một đỉnh kề trong $U.$
Ta có định lý sau.
Định lý 3. Cho $G = (V,E)$ là một đồ thị có $n$ đỉnh và bậc của mỗi đỉnh không nhỏ hơn $\delta > 1.$ Khi đó $G$ có một tập thống trị có không quá $n \cdot \dfrac{ 1 + \ln(\delta + 1)}{\delta + 1}$ đỉnh.
Chứng minh. Xét $ p \in [0,1]$ là một số tùy ý. Lấy một cách ngẫu nhiên, độc lập mỗi cạnh đỉnh của $V$ với xác suất $p.$ Gọi $X$ là tập hợp (ngẫu nhiên) của các định được chọn và $Y = Y_X$ là một tập hợp ngẫu nhiên gồm tất cả các định thuộc $V - X$ sao cho nó không có đỉnh kề trong $X.$ Rõ ràng $|X|$ là phân bố nhị thức nên $E(|X|) = np.$ Với mỗi $v \in V$ cố định, ta có
$$ Pr(v \in Y) = Pr ( v \text{ và lân cận của } v \text{ không thuộc } Y) \leq (1-p)^{1+\delta}.$$
Sử dụng tính tuyến tính của kì vọng, chú ý rằng biến ngẫu nhiên $|Y|$ có thể viết thành tổng của $n$ biến ngẫu nhiên $\chi_v (v \in V)$ trong đó $\chi_v = 1$ nếu $v \in Y$ và $\chi_v = 0$ nếu ngược lại. Từ đây ta thu được
$$ E(|X| + |Y| ) = E(|X|) + E(|Y|) = np + \sum_{ v \in V} E(\chi_v) \leq np + n(1-p)^{1+\delta}.$$
Điều này dẫn tới, tồn tại ít nhất một cách chọn $X \subset V$ sao cho $|X| + |Y_X| \leq np + n(1-p)^{1+\delta}.$
Đặt $U = X \cup Y_X,$ thì rõ ràng $U$ là một tập thống trị của $G$ với lực lượng không vượt quá $np + n(1-p)^{1+\delta}.$
Chú ý rằng vì $p$ được chọn tùy ý nên ta sẽ chọn $p$ sao cho $np + n(1-p)^{1+\delta}$ đạt giá trị nhỏ nhất. Bằng đạo hàm và tính toán trực tiếp, ta thu được $np+n(1-p)^{1+\delta}$ nhỏ nhất khi
$$ p = \frac{\ln(1+\delta)}{1 + \delta}.$$
Thay $p$ vào ta thu được $|U|$ không vượt quá $n \cdot \frac{1 + \ln(1+\delta)}{1 + \delta}.$
Nhận xét. Phía trên là các ví dụ đầu tiên trong việc sử dụng phương pháp xác suất để chứng minh các định lý và mệnh đề trong tổ hợp. Nó là các ví dụ đơn giản nhưng chứa các ý tưởng quan trọng trong việc tiếp cận vấn đề.
Các Blog tiếp theo của mình sẽ tiếp tục trình bày về phương pháp này với các vấn đề sâu hơn. Cũng như sử dụng các công cụ mạnh hơn của xác suất để giải quyết các bài toán tổ hợp trong hình học tổ hợp cũng như tổ hợp cộng tính.
