Bài giảng Định lý Ramsey - Toán rời rạc thầy Trần Vĩnh Đức | Trường Đại học Bách khoa Hà Nội

Lý thuyết Ramsey, theo tên của nhà toán học ngườiAnh, Frank Plumpton Ramsey. Tài liệu được sưu tầm, giúp bạn ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!

18 9 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Toán rời rạc (BKHN)

Trường: Đại học Bách Khoa Hà Nội

Thông tin:

27 trang 2 tháng trước

Tác giả:

Profile Lân Nguyễn
Định lý Ramsey
Trần Vĩnh Đức
HUST
Khẳng định
Trong số 6 người luôn có ba người đôi một quen nhau hoặc ba
người đôi một lạ nhau.
11
Order from disorder:
Ramsey’s theorem
Paul Erd˝os (1913–1996), a famous 20th century mathematician
and arguably one of the main creators of contemporary discrete
mathematics, liked to tell the following story. X-rays were discov-
ered by Wilhelm Conrad R¨ontgen in 1895. But the British physicist
Sir William Crookes observed a similar effect earlier: photographic
plates became black mysteriously when stored near a tube nowadays
called by Crookes’ name. He noticed this and issued a directive to the
technicians that henceforth the plates were to be stored elsewhere.
The moral of this story is twofold. First, Fortune favors explorers
who are prepared for the discovery (and Erd˝os used to emphasize
this point). And second, key discoveries often have very modest and
seemingly trifling origins. Great theories often begin with effects that
are almost imperceptible. But we have to be ready.
Mathematics and computer science also have their discoveries,
which often first manifest themselves inconspicuously, as seemingly
irrelevant curiosities. In this chapter we discuss one such peculiarity,
concerning graphs with a mere 6 vertices.
We begin with the following popular form of the result. Six people
meet at a party. Some of them know each other, some of them don’t,
perhaps because they see one another for the first time. The party
may look according to one of the following schemes, for example:
party 50 years
after graduation
lonely hearts
party
party of
admirers
meeting of two
mafia bosses
Bài tập
Hãy chứng minh rằng trong 9 người luôn có 3 người đôi một quen
nhau hoặc 4 người đôi một không quen nhau.
Lý thuyết Ramsey
Hình: F. P. Ramsey (1903-1930)
Lý thuyết Ramsey, theo tên
của nhà toán học người
Anh, Frank Plumpton
Ramsey.
Khẳng định
Trong sáu người bất kỳ luôn tồn tại ba người sao cho hoặc là họ
quen nhau từng đôi một hoặc họ không quen nhau từng đôi một.
Viết lại khẳng định trên một cách ngắn gọn dùng ký hiệu ”mũi
tên” như sau:
K
6
→ K
3
, K
3
với ý nghĩa
▶
K
6
= “6 đối tượng và 15 cặp không thứ tự để thể hiện quan
hệ (quen hoặc lạ) giữa các đối tượng này”
▶
K
3
, K
3
= “Ba đối tượng quen nhau từng đôi một”, “Ba đối
tượng không quen nhau từng đôi một”
Ký hiệu K
n
K
n
= “một tập n đối tượng và mọi cặp không thứ tự
(cạnh) các đối tượng này”
Ký hiệu mũi tên
▶
Nếu ta xem mỗi cặp không thứ tự như một cạnh. Cặp đối
tượng quen nhau xem như cạnh tô màu xanh. Cặp đối tượng
không quen nhau như các cạnh tô màu đỏ.
▶
Vậy
K
6
→ K
3
, K
3
có nghĩa là
“Dù có tô xanh đỏ các cạnh của K
6
ta luôn tìm được
một K
3
có toàn cạnh đỏ hoặc một K
3
toàn cạnh xanh”
Chứng minh K
6
→ K
3
, K
3
▶
Xét một đối tượng p của K
6
. Vì có 5 cạnh liên quan đến p có
mầu đỏ hoặc xanh nên có ít nhất 3 cạnh cùng màu. Ta giả sử
3 cạnh này cùng màu đỏ. (Nếu màu xanh ta lập luận tương
tự.) Có ba đối tượng a, b, c nối với p qua ba cạnh đỏ này.
▶
Bây giờ, nếu tồn tại một cạnh nối giữa
a − b hoặc a − c hoặc b − c có màu đỏ,
vậy ta được một K
3
đỏ.
▶
Nếu không thì ta được K
3
xanh liên
quan đến a, b, c.
p
a
b
c
K
5
→ K
3
, K
3
Khẳng định
K
5
→ K
3
, K
3
là sai vì có cách tô màu cạnh K
5
không tạo ra K
3
đỏ hoặc K
3
xanh.
Câu hỏi
Giả sử K
n
→ K
a
, K
b
. Giải thích tại sao K
p
→ K
a
, K
b
với mọi
p > n.
Câu hỏi
▶
Chứng minh rằng K
b
→ K
2
, K
b
.
▶
Chứng minh rằng K
b−1
→ K
2
, K
b
.
Câu hỏi
Chứng minh rằng K
11
→ K
3
, K
4
.
Định lý (Ramsey)
Với hai số nguyên m ≥ 2 và n ≥ 2, luôn tồn tại một số nguyên
dương p sao cho
K
p
→ K
m
, K
n
.
Cho trước số nguyên m và n, luôn có số nguyên dương
p sao cho, nếu tô màu xanh hoặc đỏ lên cạnh của K
p
thì
luôn tìm được hoặc một K
m
đỏ hoặc một K
n
xanh.
Rõ ràng, với mọi q ≥ p ta luôn có
K
p
→ K
m
, K
n
⇒ K
q
→ K
m
, K
n
.
Số Ramsey
▶
Số nguyên p nhỏ nhất sao cho
K
p
→ K
m
, K
n
gọi là số Ramsey.
▶
Số Ramsey p này được ký hiệu là r(m, n).
Ví dụ
Ta có r(3, 3) = 6 vì
K
6
→ K
3
, K
3
và K
5
→ K
3
, K
3
.
Câu hỏi
Giải thích tại sao ta luôn có r(a, b) = r(b, a).
Bài tập
Tính các số Ramsey sau
1. r(2, n) = r(n, 2)
2. r(3, 4) = r(4, 3)
3. r(3, 5) = r(5, 3)
Định lý (Ramsey, dạng đơn giản)
Với hai số nguyên m ≥ 2 và n ≥ 2, luôn tồn tại một số nguyên
dương p sao cho
K
p
→ K
m
, K
n
Chứng minh định lý Ramsey
▶
Ta chỉ ra sự tồn tại của r(m, n) bằng quy nạp theo cả m và n.
▶
Bước cơ sở:
▶
Nếu m = 2 thì r(2, n) = n,
▶
nếu n = 2 thì r(m, 2) = m.
Bước quy nạp
▶
Giả sử rằng m ≥ 3 và n ≥ 3 và tồn tại cả
r
(
m
,
n
−
1)
và
r
(
m
−
1
,
n
)
.
▶
Đặt
p = r(m − 1, n) + r(m, n − 1)
▶
Ta sẽ chỉ ra rằng K
p
→ K
m
, K
n
.
Chứng minh K
p
→ K
m
, K
n
▶
Xét một điểm x của K
p
. Đăt R
x
là tập điểm nối với x bằng
một cạnh màu đỏ, và B
x
là tập điểm nối với x bởi một cạnh
màu xanh.
▶
Vậy
|R
x
| + |B
x
| = p − 1
= r(m − 1, n) + r(m, n − 1) − 1
chỉ ra rằng
1. |R
x
| ≥ r(m − 1, n), hoặc
2. |B
x
| ≥ r(m, n − 1).
| 1/27
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

Định lý Ramsey Trần Vĩnh Đức HUST 11 Order from disorder: Ramsey’s theorem
Paul Erd˝os (1913–1996), a famous 20th century mathematician
and arguably one of the main creators of contemporary discrete
mathematics, liked to tell the following story. X-rays were discov-
ered by Wilhelm Conrad R¨ontgen in 1895. But the British physicist
Sir William Crookes observed a similar effect earlier: photographic
plates became black mysteriously when stored near a tube nowadays
called by Crookes’ name. He noticed this and issued a directive to the
technicians that henceforth the plates were to be stored elsewhere.
The moral of this story is twofold. First, Fortune favors explorers
who are prepared for the discovery (and Erd˝os used to emphasize
this point). And second, key discoveries often have very modest and
seemingly trifling origins. Great theories often begin with effects that
are almost imperceptible. But we have to be ready.
Mathematics and computer science also have their discoveries,
which often first manifest themselves inconspicuously, as seemingly
irrelevant curiosities. In this chapter we discuss one such peculiarity,
concerning graphs with a mere 6 vertices.
We begin with the following popular form of the result. Six people Khẳng meet at a định
party. Some of them know each other, some of them don’t, pe Trong rhaps số b 6 người ecause luôn they scó ee ba người one đôi anothermột for quen the nhau first hoặc time. ba The party người may lo đôi ok một lạ nhau.
according to one of the following schemes, for example: party 50 years lonely hearts party of meeting of two after graduation party admirers mafia bosses Bài tập
Hãy chứng minh rằng trong 9 người luôn có 3 người đôi một quen
nhau hoặc 4 người đôi một không quen nhau. Lý thuyết Ramsey Lý thuyết Ramsey, theo tên
của nhà toán học người Anh, Frank Plumpton Ramsey.
Hình: F. P. Ramsey (1903-1930) Khẳng định
Trong sáu người bất kỳ luôn tồn tại ba người sao cho hoặc là họ
quen nhau từng đôi một hoặc họ không quen nhau từng đôi một.
Viết lại khẳng định trên một cách ngắn gọn dùng ký hiệu ”mũi tên” như sau:
K6 → K3, K3 với ý nghĩa
▶ K6= “6 đối tượng và 15 cặp không thứ tự để thể hiện quan
hệ (quen hoặc lạ) giữa các đối tượng này”
▶ K3, K3 = “Ba đối tượng quen nhau từng đôi một”, “Ba đối
tượng không quen nhau từng đôi một” Ký hiệu Kn
Kn = “một tập n đối tượng và mọi cặp không thứ tự
(cạnh) các đối tượng này” Ký hiệu mũi tên
▶ Nếu ta xem mỗi cặp không thứ tự như một cạnh. Cặp đối
tượng quen nhau xem như cạnh tô màu xanh. Cặp đối tượng
không quen nhau như các cạnh tô màu đỏ. ▶ Vậy
K6 → K3, K3 có nghĩa là
“Dù có tô xanh đỏ các cạnh của K6 ta luôn tìm được
một K3 có toàn cạnh đỏ hoặc một K3 toàn cạnh xanh”
Chứng minh K6 → K3, K3
▶ Xét một đối tượng p của K6. Vì có 5 cạnh liên quan đến p có
mầu đỏ hoặc xanh nên có ít nhất 3 cạnh cùng màu. Ta giả sử
3 cạnh này cùng màu đỏ. (Nếu màu xanh ta lập luận tương
tự.) Có ba đối tượng a, b, c nối với p qua ba cạnh đỏ này. a
▶ Bây giờ, nếu tồn tại một cạnh nối giữa
a − b hoặc a − c hoặc b − c có màu đỏ, p
vậy ta được một K b 3 đỏ.
▶ Nếu không thì ta được K3 xanh liên c quan đến a, b, c.
K5 ̸→ K3, K3 Khẳng định
K5 → K3, K3
là sai vì có cách tô màu cạnh K5 không tạo ra K3 đỏ hoặc K3 xanh. Câu hỏi
Giả sử Kn → Ka, Kb. Giải thích tại sao Kp → Ka, Kb với mọi p > n. Câu hỏi
▶ Chứng minh rằng Kb → K2, Kb.
▶ Chứng minh rằng Kb−1 ̸→ K2, Kb. Câu hỏi
Chứng minh rằng K11 → K3, K4. Định lý (Ramsey)
Với hai số nguyên m ≥ 2 và n ≥ 2, luôn tồn tại một số nguyên dương p sao cho Kp → Km, Kn.
Cho trước số nguyên m và n, luôn có số nguyên dương
p sao cho, nếu tô màu xanh hoặc đỏ lên cạnh của Kp thì
luôn tìm được hoặc một Km đỏ hoặc một Kn xanh.
Rõ ràng, với mọi q ≥ p ta luôn có Kp → Km, Kn ⇒ Kq → Km, Kn. Số Ramsey
▶ Số nguyên p nhỏ nhất sao cho Kp → Km, Kn gọi là số Ramsey.
▶ Số Ramsey p này được ký hiệu là r(m, n). Ví dụ
Ta có r(3, 3) = 6 vì
K6 → K3, K3 và K5 ̸→ K3, K3. Câu hỏi
Giải thích tại sao ta luôn có r(a, b) = r(b, a). Bài tập Tính các số Ramsey sau
1. r(2, n) = r(n, 2)
2. r(3, 4) = r(4, 3)
3. r(3, 5) = r(5, 3)
Định lý (Ramsey, dạng đơn giản)
Với hai số nguyên m ≥ 2 và n ≥ 2, luôn tồn tại một số nguyên dương p sao cho Kp → Km, Kn
Chứng minh định lý Ramsey
▶ Ta chỉ ra sự tồn tại của r(m, n) bằng quy nạp theo cả m và n. ▶ Bước cơ sở:
▶ Nếu m = 2 thì r(2, n) = n,
▶ nếu n = 2 thì r(m, 2) = m. Bước quy nạp
▶ Giả sử rằng m ≥ 3 và n ≥ 3 và tồn tại cả r(m, n − 1) và
r(m − 1, n) . ▶ Đặt
p = r(m − 1, n) + r(m, n − 1)
▶ Ta sẽ chỉ ra rằng Kp → Km, Kn.
Chứng minh Kp → Km, Kn
▶ Xét một điểm x của Kp. Đăt Rx là tập điểm nối với x bằng
một cạnh màu đỏ, và Bx là tập điểm nối với x bởi một cạnh màu xanh. ▶ Vậy
|Rx| + |Bx| = p − 1
= r(m − 1, n) + r(m, n − 1) − 1 chỉ ra rằng
1. |Rx| ≥ r(m − 1, n), hoặc
2. |Bx| ≥ r(m, n − 1).