Phương pháp xác suất

Nó cho phép ta tính trung bình của một phép đếm bằng cách cộng lần lượt từng xác suất riêng lẻ, mà không cần bận tâm các biến cố tương tác với nhau ra sao — thủ thuật hữu ích nhất trong phương pháp xác suất.

Viết $X = \sum_{i=1}^m \mathbb{1}[A_i]$ trong đó $\mathbb{1}[A_i]$ bằng $1$ nếu $A_i$ xảy ra và $0$ nếu không. Kỳ vọng vốn được định nghĩa như một tổng (hay tích phân) trên các kết quả có trọng số là xác suất, và tổng này luôn có tính cộng trên một danh sách hữu hạn các biến ngẫu nhiên — điều này đúng bất kể các biến có độc lập hay không, vì tính cộng của kỳ vọng không hề dùng tới độc lập, chỉ dùng việc ta đang cộng trên cùng một độ đo xác suất.

Cụ thể, $\mathbb{E}[X] = \mathbb{E}\left[\sum_{i=1}^m \mathbb{1}[A_i]\right] = \sum_{i=1}^m \mathbb{E}[\mathbb{1}[A_i]]$ theo tính cộng của kỳ vọng trên một tổng hữu hạn các biến ngẫu nhiên.

Cuối cùng, với bất kỳ biến chỉ báo nào, $\mathbb{E}[\mathbb{1}[A_i]] = 1 \cdot \Pr[A_i] + 0 \cdot \Pr[\overline{A_i}] = \Pr[A_i]$. Thay vào tổng trên cho đúng $\mathbb{E}[X] = \sum_{i=1}^m \Pr[A_i]$, không cần bất kỳ giả thiết nào về quan hệ giữa các $A_i$.

Khi $k$ tăng, số tập con $k$ đỉnh của một đồ thị $n$ đỉnh chỉ tăng theo đa thức của $n$, nhưng xác suất một tập con cụ thể nào đó đơn sắc lại giảm theo cấp số mũ kép của $k$. Cân bằng hai tốc độ này cho thấy số kỳ vọng các đồ thị con đầy đủ đơn sắc vẫn dưới $1$ ngay cả khi $n$ lớn theo hàm mũ của $k$ — tốt hơn nhiều so với bất kỳ cách xây dựng tay nào từng có.

Đặt $n = \lfloor 2^{k/2} \rfloor$. Từ công thức mô-men bậc nhất ở trên, $\mathbb{E}[X] = \binom{n}{k}\,2^{1-\binom{k}{2}}$. Nếu ta chỉ ra $\binom{n}{k}\,2^{1-\binom{k}{2}} < 1$, thì vì $X$ chỉ nhận giá trị nguyên không âm, phải tồn tại một cách tô 2 màu đạt $X=0$ — nếu không, luôn có $X \ge 1$, buộc $\mathbb{E}[X]\ge 1$. Một cách tô với $X=0$ hoàn toàn không có đồ thị con đầy đủ $k$ đỉnh đơn sắc.

Chặn hệ số nhị thức bằng $\binom{n}{k} \le n^k/k!$, và vì $n \le 2^{k/2}$ nên $n^k \le 2^{k^2/2}$. Thay vào công thức kỳ vọng, $\mathbb{E}[X] \le \dfrac{2^{k^2/2}\cdot 2^{1-\binom{k}{2}}}{k!}$.

Rút gọn số mũ: $\dfrac{k^2}{2} + 1 - \dfrac{k(k-1)}{2} = 1 + \dfrac{k^2 - k^2 + k}{2} = 1 + \dfrac{k}{2}$. Vậy $\mathbb{E}[X] \le \dfrac{2^{1+k/2}}{k!}$, và chỉ cần chỉ ra $k! > 2^{1+k/2}$ với mọi $k \ge 3$.

Kiểm tra điều này bằng quy nạp theo $k$. Cơ sở $k=3$: $3! = 6$ và $2^{1+3/2} = 2^{2.5} \approx 5.657$, và đúng là $6 > 5.657$. Ở bước quy nạp, giả sử $k! > 2^{1+k/2}$ đúng tại $k \ge 3$. Khi đó $(k+1)! = (k+1)\cdot k! > (k+1)\cdot 2^{1+k/2}$, và vì $k+1 \ge 4 > \sqrt2$, đại lượng này vượt $\sqrt2 \cdot 2^{1+k/2} = 2^{1+(k+1)/2}$, chính là khẳng định tại $k+1$. Vậy $k! > 2^{1+k/2}$ đúng với mọi $k \ge 3$, cho ta $\binom{n}{k}\,2^{1-\binom{k}{2}} < 1$ như mong muốn.

Do đó tồn tại một cách tô 2 màu của $K_n$ không có đồ thị con đầy đủ $k$ đỉnh đơn sắc nào, nên $R(k,k) > n = \lfloor 2^{k/2}\rfloor$. Vì $\lfloor x\rfloor + 1 > x$ với mọi số thực $x$, ta có $R(k,k) \ge \lfloor 2^{k/2}\rfloor + 1 > 2^{k/2}$, chính là $R(k,k) > 2^{k/2}$.