ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ HẰNG
VỀ SỰ TỒN TẠI LỤC GIÁC LỒI RỖNG
TRONG BÀI TOÁN ERD
˝
OS
LUẬN VĂN THẠC SỸ TOÁN HỌC
THÁI NGUYÊN-2015
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ HẰNG
VỀ SỰ TỒN TẠI LỤC GIÁC LỒI RỖNG
TRONG BÀI TOÁN ERD
˝
OS
Chuyên ngành: Phương pháp toán sơ cấp
Mã số: 60 46 01 13
LUẬN VĂN THẠC SỸ TOÁN HỌC
Người hướng dẫn khoa học
PGS.TS. TẠ DUY PHƯỢNG
THÁI NGUYÊN-2015
Mục lục
Mở đầu iii
1 Tổng quan bài toán Erd
˝
os về đa giác lồi rỗng 1
1.1 Giới thiệu và xây dựng kết quả chính . . . . . . . . . . . . 1
1.2 Phương pháp chứng minh . . . . . . . . . . . . . . . . . . . 3
1.3 Định nghĩa và kí hiệu . . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . 7
2.7.3 Cấu hình dạng (8,6,1) . . . . . . . . . . . . . . . . . 52
2.7.4 Cấu hình dạng (8,5,1) . . . . . . . . . . . . . . . . . 58
Kết luận 63
ii
Mở đầu
Giả thuyết Erd
˝
os-Szekeres được đề cập từ rất sớm (vào năm 1935):
Mọi tập không ít hơn 2
n−2
+1 điểm trên mặt phẳng ở vị trí tổng quát
(không có ba điểm nào thẳng hàng) đều chứa n điểm là đỉnh của một
đa giác lồi.
Bất chấp sự cố gắng của hàng trăm nhà toán học đã nghiên cứu và
viết hàng trăm bài báo, giả thuyết Erd
˝
os-Szekeres mới chỉ được chứng
minh trọn vẹn cho các trường hợp n = 3, 4, 5. Gần đây, năm 2006,
trường hợp n = 6 đã được chứng minh bởi Szekeres và Peters nhờ
máy tính. Sau đó, năm 2009, ba nhà toán học là Knut Dehnhardt,
Heiko Harboth và Zsolt Lángi đã đưa ra một chứng minh thuần túy
toán học cho một trường hợp riêng của trường hợp n = 6.
Năm 1978, Erd
˝
os đã phát biểu một bài toán mới, đó là bài toán Erd
˝
os
về đa giác lồi rỗng: Cho n là một số tự nhiên bất kỳ, tồn tại hay không
số nguyên dương nhỏ nhất E(n) sao cho từ mọi tập chứa tối thiểu
E(n) điểm ở vị trí tổng quát trên mặt phẳng đều có thể chọn ra được
Thái Nguyên, ngày 10 tháng 4 năm 2015
Nguyễn Thị Hằng
iv
Chương 1
Tổng quan bài toán Erd
˝
os về đa
giác lồi rỗng
1.1 Giới thiệu và xây dựng kết quả chính
Năm 1935 Erd
˝
os-Szekeres đã phát biểu bài toán sau đây.
Bài toán 1(Erd
˝
os-Szekeres) Cho số nguyên n ≥ 3, hãy tìm một
số nguyên dương nhỏ nhất g(n) sao cho từ một tập hợp bất kỳ các
điểm trên mặt phẳng ở vị trí tổng quát và chứa tối thiểu g(n) điểm
thì có thể chọn ra một tập hợp con có n điểm là đỉnh của một đa giác
lồi n cạnh.
Năm 1978 Erd
˝
os đã phát biểu một dạng khác của bài toán trên.
Bài toán 2 (Erd
˝
os-Szekeres) Cho số nguyên bất kì n ≥ 3, hãy tìm
số nguyên dương nhỏ nhất h(n) sao cho từ mọi tập điểm X trên mặt
phẳng ở vị trí tổng quát và chứa tối thiểu h(n) điểm có thể chọn ra
một tập hợp gồm n điểm mà các phần tử của nó là đỉnh của một n
giác lồi và rỗng. Nghĩa là n giác lồi này không chứa một điểm nào
bên trong X.
+1.
Hình 1: Mọi tập hợp từ năm điểm đều chứa tứ giác lồi
Bất đẳng thức g(n) ≤
2n − 4
n − 2
+ 1 đã được nhiều lần làm tốt lên.
Đã có ba kết quả liên tiếp vào năm 1998. Kết quả đầu tiên thuộc về hai
vợ chồng F.Chung và R.Graham: g(n) ≤
2n − 4
n − 2
(xem [9]). Kết quả
thứ hai thuộc về Kleitman và Pachter là g(n) ≤
2n − 4
n − 2
+ 7 − 2n
(xem [10]). Và cuối cùng đánh giá tốt thứ ba thì thuộc về Tóth và Valtr
g(n) ≤
2n − 5
n − 3
+2 (xem [11]). Trong năm 2005 thì Tóth và Vailtr thay
đánh giá trên bằng đánh giá g(n) ≤
os-Szekeres có thể xem trong bài báo tổng quan
của Soltan [5].
1.2 Phương pháp chứng minh
Ta nói rằng một tập hữu hạn điểm trên mặt phẳng chỉ chứa k-giác đã
cho nếu như từ tập đó có thể chọn được tập hợp k điểm là các đỉnh của
một k-giác.
Hình 2: Định nghĩa các tập H, I, J, K
Để chứng minh Định lý 1 cần khẳng định rằng trong một tập hợp bất kì
trên mặt phẳng ở vị trí tổng quát mà có số điểm lớn hơn hoặc bằng 463
3
thì phải tồn tại lục giác lồi rỗng. Ta cố định một tập điểm bất kì, ta nhận
xét rằng tập điểm X chứa tối thiểu X một bát giác lồi. Quan hệ bao hàm
trong tập hợp tất cả các bát giác lồi tạo nên tập hợp X là một quan hệ
chặt. Bởi vậy luôn luôn có thể nói về các bát giác nhỏ nhất kể các điểm
từ trong X. Chọn một trong chúng và kí hiệu tập đỉnh của chúng là tập
H. Kí hiệu I
= (conv(H)\H) ∩ X là tập tất cả các điểm của X nằm bên
trong bao lồi của H. Hoặc I
là rỗng (khi đó ta có bát giác rỗng). Hoặc là
conv(I
) chứa đa giác lồi là một đoạn (2-giác) hoặc là một điểm (1-giác).
Ta kí hiệu I là tập tất cả các đỉnh (I = ∂(conv(I
)) ∩ X). Nếu |I| > 2
thì có thể xây dựng J
= (conv(I)\I) ∩ X như là tập hợp tất cả các điểm
dạng của tập X, thì ta hiểu X có một bát giác lồi, tương ứng với nó thì
X có một dạng đã cho.
Để chứng minh sự tồn tại của lục giác lồi rỗng trong tập hợp X thì đầu
tiên chúng ta xét tập con H
= conv(H) ∩ X. Ta có bổ đề sau:
Bổ đề (Valtr) Cho X, H, I, J, K như trong định nghĩa ở trên. Nếu
|H| ≥ 7 và trong X không có lục giác lồi rỗng thì K = ∅.
Câu nói "như trong bổ đề" nói chung không hoàn toàn là chính xác bởi vì
từ trước tới nay ta luôn luôn giả thiết rằng |H| = 8. Nhưng rõ ràng trong
định nghĩa về các bao lồi lồng nhau trong Hình 2 thì có thể cho cả trường
hợp |H| = 8.
Từ Bổ đề ta suy ra ngay sự tồn tại lục giác lồi rỗng trong mọi tập hợp
dạng (8, i, j, k, ), khi k > 0. Bởi vậy tiếp theo chúng ta chỉ xét các trường
hợp (8, i, j, 0, 0, 0, ). Để cho ngắn gọn chúng ta sẽ nói chỉ về các trường
hợp đó là cấu hình dạng (8, i, j). Tất cả các trường hợp đó sẽ gồm 43 cấu
hình bởi vì i và j có thể thay đổi trong miền giới hạn: 0 ≤ i ≤ 2 hoặc
3 ≤ i ≤ 7 và 0 ≤ j ≤ 7.
5
Theo ý tưởng, mỗi trường hợp trong 43 trường hợp cần phải xét riêng.
Nhưng mà chúng ta có thể chia tất cả tập hợp này ra thành 7 lớp để với
mỗi lớp đó có thể áp dụng cách tiếp cận riêng để chứng minh. Trong 6 lớp
đầu tiên chúng ta sử dụng phương pháp nào đó để khẳng định sự tồn tại
của lục giác lồi rỗng trong tập H
. Trong lớp thứ 7 thì chúng ta cần sử
dụng nhiều thông tin hơn về tập X. Trong trường hợp này thì ta gọi là
trường hợp đặc biệt và nó thuộc vào cấu hình dạng
(8, 7, 3), (8, 6, 2), (8, 6, 1), (8, 5, 1)
Ta có định lí sau.
(Z) là nửa mặt phẳng mở tương ứng với nửa đường thẳng XY, chứa
điểm Z. Xích lồi là tập hợp các đỉnh liên tiếp của một đa giác lồi.
Xích lồi AB C đã cho xác định 3-sector (xem Hình 5 bên trái)
(ABC) = (P
AB
(C) ∩ P
BC
(A))\conv({A, B, C}).
Xích lồi ABCD xác đinh 4-sector (xem Hình 5 ở giữa)
(ABCD) = ((ABC) ∩ (BCD)\conv({A, B, C, D}).
Xích lồi ABCDE xác định 5-sector hay miền cấm của ngũ giác (xem Hình
5 bên phải)
(ABCDE) = ((ABCD) ∩ (BCDE)\conv({A, B, C, D, D}).
Ta nói rằng điểm được xác định từ một đa giác lồi đã cho bởi một đường
thẳng chứa cạnh của đa giác đó nếu đa giác đó được đặt trong nửa mặt
phẳng khác tương ứng với đường thẳng đó. Mọi miền cấm của ngũ giác
cũng là tập hợp các điểm được xác định từ ngũ giác ấy bởi đúng một
đường thẳng (xem Hình 5 trong đó đường thẳng AE).
Tập các điểm tách khỏi đa giác bởi một đường thẳng cụ thể nào đó, thí
dụ, đường thẳng P Q được gọi là 2-sector và kí hiệu là (P Q).
Ta sẽ nói rằng, điểm được tách khỏi đa giác bởi hai đường thẳng trên cạnh
của chúng đồng thời nếu điểm ấy được xác định từ đa giác bởi cả hai đường
thẳng đã cho, nghĩa là điểm ấy nằm trong giao của hai 2-sector tương ứng.
Ngược lại, điểm tách khỏi đa giác bởi hai đường thẳng chứa các cạnh của
nó nếu nó tách khỏi đa giác bởi chỉ 1 trong 2 đường thẳng ấy, tức là nằm
7
trong hợp của các 2-sector tương ứng.
Giả sử có một cấu hình (8, i, j), i ≥ 3.
Mệnh đề 1. Các tính chất sau đây được thỏa mãn:
(a) Mọi đường thẳng chứa cạnh của i-giác tách khỏi nó đúng ba đỉnh của
xét.
Hình 7: (i,3)-phân bố dạng [a
1
, b
1
, a
2
, b
2
, a
3
, b
3
]
Giả sử đầu tiên với j = 3. Ba đường thẳng đi qua các cạnh của tam
giác chia mặt phẳng ngoài tam giác ra thành sáu phần, trong đó ba phần
của chúng có dạng "tam giác", ba phần còn lại có dạng "tứ giác". Ta nói
rằng cấu hình mà cấu tạo từ i-giác và tam giác là (i, 3)- phân bố dạng
9
[a
1
b
1
a
2
b
2
a
3
b
2
b
2
a
3
b
3
a
1
b
1
] hoặc (i, 3)-phân bố dạng [a
1
b
3
a
3
b
2
a
2
b
1
]. Nhưng như
vậy không sai khác về mặt nguyên tắc các khả năng có thể viết của các
đỉnh. Cách viết này từ quan điểm của chúng ta là tương đương và do đó
sau này chúng ta sẽ sử dụng cách viết bất kì trong số đó. Ở đây, điều quan
trọng cần nhấn mạnh là mọi cách viết cố định sẽ bắt đầu từ a
i
, có nghĩa
k
, k = 1; 4. Với mỗi một trong ba
trường hợp này, các đỉnh b
1
; b
2
; b
3
; b
4
được xác định một cách duy nhất với
sự chính xác đến vị trí mà chúng ta đưa vào kí hiệu B
1
; B
2
; B
3
; B
4
. Ngầm
hiểu rằng, các miền và số lượng các đỉnh trong chúng đã được sắp theo
10
thứ tự (theo chiều kim đồng hồ).
Khi đại lượng phân bố các đỉnh b
1
; b
2
; b
3
; b
; b
3
; b
4
có thể coi như được sắp xếp như trong Hình 8 và Hình 9. Xét
"miền phụ" A
, A, A
, A
3
, A
4
(xem Hình 9 giữa). Kí hiệu a
, a, a
, a
3
, a
4
là
số đỉnh của i-giác trong miền tương ứng. Chúng ta lấy các số nguyên không
âm bất kì a
1
, a
2
với điều kiện
a
1
ta đưa các đỉnh khác của nó vào trong miền A
∪ A và A ∪ A
. Như vậy
chúng ta đã thực hiện các bước làm như để chỉ ra, nhưng chúng không có
ý nghĩa.
Cuối cùng giả sử tứ giác không phải hình thang. Trường hợp này được
biểu diễn trên Hình 9 bên phải. Ở đây một lần nữa không hạn chế tổng
quát, xuất hiện các miền phụ A
2
, A
(1)
, , A
(5)
, trong đó tương ứng có
11
a
2
, a
(1)
, , a
(5)
đỉnh của i-giác. Chọn số nguyên không âm bất kì a
1
, a
4
, a
3
có tính chất
(5)
.
Hình 10: Xác định cuối cùng các số a
i
và b
i
Sắp đặt các số trên như trong Hình 10 bên phải. Nói cách khác chúng ta
đưa a
1
đỉnh của i-giác từ tập A
(1)
∪ ∪ A
5
vào miền A
(1)
∪ A
(2)
; đặt a
4
đỉnh vào miền A
(2)
∪ A
(3)
∪ A
(4)
, a
3
đỉnh còn lại chúng ta đưa vào miền
A
(4)
3
b
3
a
4
b
4
]. Như vậy giống như trong
trường hợp (i, 3) phân bố, dạng ở đây được xác định một cách không duy
nhất. Thứ nhất là có sự tự do trong việc lựa chọn cách đánh số của các
đại lượng a
i
, b
i
. Thứ hai là các số a
i
có thể nhận các giá trị thỏa mãn các
hạn chế đã cho. Ngoài ra , như trước đây chúng ta sẽ viết liên tiếp a
i
, b
i
mỗi một lần đều bắt đầu từ vị trí a
1
nào đó.
Hình 11: Ví dụ về xác định không duy nhất dạng phân bố
12
Hình 11, bên trái biểu diễn cấu hình tạo thành từ lục giác và tứ giác. Nó
có thể mô tả, ví dụ như (6, 4)-phân bố dạng [2, 0, 1, 0, 1, 1, 0, 1] (xem Hình
11 giữa). Có thể coi nó như (6, 4)-phân bố dạng [1, 0, 2, 0, 1, 1, 0, 1] (xem
Hình 11 phải). Tất nhiên tồn tại một số cách giải thích khác nhưng với
Hình 13: Cấu hình (8,2,0)
15
Gọi hai điểm nằm trong bát giác là P ; Q. Kẻ một đường thẳng đi qua
hai điểm P, Q. Vì các điểm ở vị trí tổng quát nên không có bất kì đỉnh nào
của bát giác nằm trên đường thẳng P Q. Đường thẳng P Q chia đa giác lồi
8 đỉnh thành hai nửa mặt phẳng. Theo nguyên lý Diriclet sẽ có ít nhất 4
đỉnh nằm trong nửa mặt phẳng có bờ là P Q. Khi đó bốn đỉnh ấy cùng với
hai điểm P và Q tạo thành lục giác lồi rỗng.
2.2.3 Cấu hình dạng (8,3,0)
Hình 14: Cấu hình (8,3,0)
Trong trường hợp này chúng ta kẻ 3 đường thẳng, mỗi đường thẳng chứa
một cạnh của tam giác trong cùng P QR và kí hiệu a
1
, a
2
, a
3
, b
1
, b
2
, b
3
là số
đỉnh của bát giác nằm trong các miền tương ứng (xem mục 1.3.2 và Hình
14). Như thế:
a
1
+ a
2
0 ≤ b
i
≤ 2 (1 ≤ i ≤ 3).
16
Cộng tất cả lại chúng ta được:
2
3
i=1
(a
i
+ b
i
) ≤ 15.
Điều này có nghĩa là
a
1
+ a
2
+ a
3
+ b
1
+ b
2
+ b
3
≤ 7.
Vô lý.
Vậy tồn tại lục giác lồi rỗng.
2
+ b
2
+ a
3
≤ 3, 0 ≤ b
1
+ b
3
≤ 1.
Cộng tất cả chúng lại ta được
4
i=1
(a
i
+ b
i
) ≤ 7.
Vô lý.
Vậy tồn tại lục giác lồi rỗng.
17
2.2.5 Cấu hình dạng (8,5,0)
Hình 16: Cấu hình (8,5,0)
Giả sử trong tập H
= conv(H) ∩ X không có lục giác lồi rỗng, trong đó
H là bát giác lồi, X là tập tất cả các điểm ban đầu. Khi đó ngũ giác bao
lồi của I (ngũ giác nằm trong bát giác) sinh ra các miền cấm trong đó các
đỉnh của bát giác không thể nằm trong miền đó (xem Hình 16, trong đó
.
2.3 Trường hợp với một điểm ở trong
Xét các cấu hình dạng (8, 3, 1), (8, 4, 1), (8, 7, 1), mỗi cấu hình được xét
riêng
18
2.3.1 Cấu hình dạng (8,3,1)
Hình 17: Cấu hình (8,3,1)
Trong trường hợp này toàn bộ không gian xung quanh ∆ABC được chia
bởi 3 miền (AXB), (BXC) và (AXC), mỗi miền đó là 3-sector (X-là điểm
nằm bên trong tam giác)(xem Hình 17). Khi đó hoặc là trong một miền ấy
có nhiều hơn 2 đỉnh của bát giác và tồn tại lục giác lồi rỗng trong cấu hình
đang xét hoặc là trong mỗi miền (AXB), (BXC), (AXC) thì có không
nhiều hơn 2 đỉnh của bát giác. Điều này không thể xảy ra.
2.3.2 Cấu hình dạng (8,4,1)
Hình 18: Cấu hình (8,4,1)
19
Copyright: Tài liệu đại học ©