Trong khi chuẩn bị cho các kỳ thi chọn học sinh giỏi, các bạn học sinh có lẽ đã gặp ví dụ sau nhiều lần.
Ví dụ 1. Trong mỗi nhóm sáu người luôn có ba người đôi một quen nhau hoặc đôi một không quen nhau.
Lời giải. Gọi là một người trong nhóm sáu người ta đang quan tâm. Vì với mỗi một trong năm người còn lại, sẽ quen hoặc không quen người đó, suy ra trong năm người còn lại ta tìm được ba người, gọi là , , , mà cùng quen hoặc cùng không quen họ. Giả sử mà không làm mất tính tổng quát rằng quen cả ba người , , và . Nếu trong , , và có hai người quen nhau, chẳng hạn là và thì ba người , , và đôi một quen nhau. Nếu không, , , và đôi một không quen nhau.
Chứng minh là ví dụ đầu tiên của lý thuyết Ramsey. Không khó khăn lắm ta thấy với một nhóm ít hơn sáu người thì kết luận không còn đúng.
Bây giờ cho mỗi người ứng với một đỉnh của đồ thị đầy đủ trên sáu đỉnh. Hai người được nối với nhau bởi một cạnh đỏ nếu họ quen nhau, được nối với nhau bởi một cạnh xanh nếu họ không quen nhau. Theo ví dụ trên thì với mọi cách tô các cạnh của bởi hai màu, luôn có mà các cạnh của nó mang cùng một màu. Hơn nữa, kết luận không còn đúng nếu thay bởi với . Kết quả sẽ thay đổi thế nào nếu thay bởi ? Ta xét bài toán tổng quát sau:
Bài toán.Cho một số nguyên dương . Tồn tại hay không số nguyên dương có tính chất: Với mỗi cách tô màu các cạnh của bởi hai màu, luôn có mà các cạnh mang cùng một màu. Số nguyên dương nhỏ nhất có tính chất này bằng bao nhiêu?
Với câu hỏi đầu tiên thì định lý tổng quát sau cho câu trả lời là tồn tại. Câu hỏi thứ hai rất khó, hiện tại ta không thể tính được như một hàm của trong tình huống tổng quát mà chỉ có thể ước lượng nó.
Định lý 1 (Ramsey).Cho và là hai số nguyên lớn hơn . Khi đó tồn tại số nguyên dương có tính chất: Với mỗi cách tô màu các cạnh của bởi hai màu xanh và đỏ, có đồ thị con với các cạnh xanh hoặc có đồ thị con với các cạnh đỏ. Nếu ký hiệu là số nguyên dương nhỏ nhất có tính chất này thì
mỗi khi và lớn hơn .
Các số được gọi là các số Ramsey. Phần thảo luận lúc đầu cho ta biết . Từ bất đẳng thức trên ta có thể tìm được một cận trên của các số Ramsey. Mục đính chính của bài là dùng phương pháp xác suất đưa ra một cận dưới của các số , chúng được gọi là các số Ramsey đối xứng.
Chứng minh. Ta chứng minh bằng quy nạp theo và . Lập luận đơn giản ta thu được , đều tồn tại và bằng với mọi .
Bây giờ giả sử và đều tồn tại, ở đây và là các số nguyên lớn hơn . Đặt . Xét một cách tô màu các cạnh của bởi một trong hai màu xanh và đỏ. Gọi là một đỉnh của . Mỗi một trong đỉnh còn lại của được nối với bởi một cạnh xanh hoặc đỏ. Suy ra, trong các đỉnh này có đỉnh được nối với bởi cạnh xanh, hoặc có đỉnh được nối với bởi cạnh đỏ. Ta xét tình huống thứ nhất, tình huống còn lại được lập luận hoàn toàn tương tự. Xem đỉnh như một đồ thị đầy đủ. Theo giả thiết quy nạp, trong đồ thị đầy đủ này có với các cạnh xanh hoặc với các cạnh đỏ. Nếu có với các cạnh đỏ thì ta có điều phải chứng minh, nếu có với các cạnh xanh thì thêm vào ta có đồ thị con của với các cạnh xanh, và ta cũng có điều cần chứng minh.
Định lý 2.Với mỗi số nguyên , ta có .
Chứng minh (của Paul Erdos). Xét một số nguyên thỏa mãn . Định lý sẽ được chứng minh nếu ta chỉ ra rằng tồn tại một cách tô màu các cạnh của bởi hai màu xanh và đỏ, sao cho trong không có với các cạnh cùng màu.
Tô màu mỗi cạnh của bởi một trong hai màu xanh và đỏ một cách ngẫu nhiên. Như vậy ta có một không gian xác suất rời rạc với không gian mẫu là tập tất cả các cách tô màu, và với mỗi biến cố , xác suất xảy ra bằng .
Gọi là biến cố: trong không có với các cạnh cùng màu. Ta cần chứng . Với mỗi đồ thị con đầy đủ trên đỉnh của , gọi là biến cố: có các cạnh cùng màu. Khi đó
T's Lab 