Về chứng minh giả thuyết Erdös-Szekeres cho trường hợp n=6

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

HOÀNG MINH HIẾU

VỀ CHỨNG MINH GIẢ THUYẾT ERDöS-SZEKERES

CHO TRƯỜNG HỢP

n  6

LUẬN VĂN THẠC SĨ TOÁN HỌC

T N n - 2016

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

HOÀNG MINH HIẾU

VỀ CHỨNG MINH GIẢ THUYẾT ERDöS-SZEKERES

CHO TRƯỜNG HỢP

n  6

LUẬN VĂN THẠC SĨ TOÁN HỌC

C n n àn : P ươn p p To n sơ cấp

Mã số: 60 46 01 13

NGƯỜI HƯ NG D N KHOA HỌC

PGS.TS. TẠ DUY PHƯỢNG

T N n - 2016

i

Mục lục

Mục lục............................................................................................................................i

Danh mục hình..............................................................................................................ii

LỜI MỞ ĐẦU...............................................................................................................1

Chương 1: Tổng quan về giả thuyết Erdös-Szekeres.............................................3

1.1. Giả thuyết Erdös-Szekeres......................................................................... 3

Chương 2: Chứng minh giả thuyết Erdös–Szekeres cho trường hợp

n  6 .29

2.1. Chứng minh giả thuyết Erdös–Szekeres cho

n  6

trong một trường hợp

riêng................................................................................................................. 30

2.2 Chứng minh bằng máy tính giả thuyết Erdös-Szekeres cho trường hợp

n  6

51

2.2.1 Tổ hợp lồi ............................................................................................... 51

2.2.2. Chứng minh bằng máy tính giả thuyết Erdös-Szekeres cho trường hợp

n  5 ............................................................................................................... 55

2.2.3.Chứng minh bằng máy tính giả thuyết Erdös-Szekeres cho trường hợp

n  6 ............................................................................................................... 60

Kết luận........................................................................................................................65

Tài liệu tham khảo......................................................................................................66

ii

Danh mục hình

Hình 1.1: Mọi tập năm điểm ở vị trí tổng quát luôn tồn tại bốn điểm là đỉnh của một

tứ giác lồi.........................................................................................................................3

Hình 1.2: Các ngũ giác ABCDM, ABCDN, ABCDP, ABCDQ không lồi ................6

Hình 1.3a: Các ngũ giác ABCQM, ABCQN, ABCQP không là các ngũ giác lồi 6

Hình 1.3b: Các ngũ giác ABDPM, ABDPN, ABDPQ không lồi................................7

Hình 1.3c: Các ngũ giác ADCNQ, ADCNP, ACDNM không lồi...............................7

Hình 1.3d: Các ngũ giác BCDMN, BCDMP, BCDMQ không lồi.............................7

Hình 1.4a: Các ngũ giác ABCPM, ABCPN không lồi ................................................8

Hình 1.4b: Các ngũ giác DABQM, DABQN không lồi...............................................8

Hình 1.4c: Các ngũ giác ADCMP, ADCMQ không lồi..............................................9

Hình 1.4d: Các ngũ giác BCDNP, BCDNQ không lồi ...............................................9

Hình 1.5: Các ngũ giác ABCMN, ABDMN, BCDPQ không lồi ...............................10

Hình 1.6a: Các ngũ giác ABPQM, ABPQN không lồi...............................................10

Hình 1.6b: Các ngũ giác BCQMN BCQMP không lồi..............................................10

Hình 1.6c: Các ngũ giác CDMNP, CDMNQ không lồi.............................................11

Hình 1.6d: Các ngũ giác CDMNP, CDMNQ không lồi ............................................11

Hình 1.7a: Các ngũ giác ANCQM, ANCQP không là các ngũ giác lồi...................11

Hình 1.7b: Các ngũ giác ANCQM, ANCQP không là các ngũ giác lồi....................12

Hình 1.8a: Các ngũ giác ANQDM, AMPDQ không lồi ...........................................12

Hình 1.8b: Các ngũ giác ANQDM, AMPDQ không lồi.............................................13

Hình 1.9a: Các ngũ giác ANQDM, AMPDQ không lồi.............................................13

Hình 1.9b: Các ngũ giác BQDMN, BPDNQ không lồi ............................................14

iii

Hình 1.10a: Các ngũ giác ANPQM, BPQMN không lồi...........................................14

Hình 1.10b: Các ngũ giác CQMNP, DMNPQ không lồi..........................................15

Hình 1.11a: Các ngũ giác ABCMN, ABDMN không lồi...........................................15

Hình 1.11b: Các ngũ giác BCDPQ, ACDPQ không lồi...........................................16

Hình 1.12a: Các ngũ giác ABQMN, ABPMN không lồi...........................................16

Hình 1.12b: Các ngũ giác CDNPQ, CDMPQ không lồi..........................................17

Hình 1.13a: Cấu hình (9;0)..........................................................................................18

Hình 1.13b: Cấu hình (8;1)..........................................................................................18

Hình 1.13c: Cấu hình (7;2)...........................................................................................18

Hình 1.14a: Cấu hình (6;3)...........................................................................................18

Hình 1.14b: Cấu hình (5;4)..........................................................................................18

Hình 1.14c: Cấu hình (4;5)...........................................................................................18

Hình 1.15a: Cấu hình (4;4;1).......................................................................................18

Hình 1.15b: Cấu hình (4;3;2).......................................................................................18

Hình 1.16a: Cấu hình (3;6)...........................................................................................19

Hình 1.16b: Cấu hình (3;5;1).......................................................................................19

Hình 1.17a: Cấu hình (3;4;2).......................................................................................19

Hình 1.17b: Cấu hình (3;3;3).......................................................................................19

Hình 1.18.......................................................................................................................20

Hình 1.19.......................................................................................................................21

Hình 1.20.......................................................................................................................22

Hình 1.21.......................................................................................................................24

Hình 1.22.......................................................................................................................25

iv

Hình 1.23.......................................................................................................................26

Hình 2.1.........................................................................................................................33

Hình 2.2.........................................................................................................................33

Hình 2.3.........................................................................................................................35

Hình 2.4.........................................................................................................................37

Hình 2.5.........................................................................................................................38

Hình 2.6.........................................................................................................................41

Hình 2.7.........................................................................................................................43

Hình 2.8.........................................................................................................................44

Hình 2.9.........................................................................................................................45

Hình 2.10.......................................................................................................................46

Hình 2.11.......................................................................................................................47

Hình 2.12.......................................................................................................................48

Hình 2.13.......................................................................................................................50

1

LỜI MỞ ĐẦU

Năm 1932, Esther Klein đã có nhận xét sau đây:

Từ năm điểm bất kì cho trước trên mặt phẳng ở vị trí tổng quát (không

có ba điểm nào thẳng hàng), bao giờ cũng tìm được bốn điểm tạo thành tứ

giác lồi.

Esther Klein cũng đặt bài toán:

Cho

n

là một số tự nhiên. Hỏi số điểm tối thiểu

ESn

ở vị trí tổng quát

trên mặt phẳng là bao nhiêu để có thể từ đó lấy ra

n

điểm là đỉnh của đa giác lồi

n

cạnh?

Năm 1935, Paul Erdös và György Szekeres [7] đã phát biểu:

Giả thuyết Erdös–Szekeres (1935, [7]) Với mỗi số tự nhiên

n  3,

mọi

tập có tối thiểu

 

2 ES 2 1 n

n



 

đ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 n cạnh.

Giả thuyết Erdös–Szekeres cũng được gọi là Bài toán Erdös–Szekeres.

Mặc dù giả thuyết Erdös–Szekeres đã được phát biểu cách đây 80 năm,

nhưng mới chỉ có câu trả lời khẳng định cho ba trường hợp:

n  4

(E. Klein,

1932, [6]);

n  5

(Đoàn Hữu Dũng, 1967, [1]; Kalbfleisch J. D., Kalbfleisch

J. G., and Stanton R. G. , 1970, [9] ; Bonice, 1974, [2],... ) và

n  6

(G.

Szekeres and L. Peters, 2006, [14], chứng minh bằng máy tính; K.

Dehnhardt, H. Harborth, and Z. Lángi, 2009, [5] cho một trường hợp riêng).

Luận văn Về chứng minh giả thuyết Erdös-Szekeres cho trường hợp

n  6

có mục đích chính là trình bày chứng minh giả thuyết Erdös-Szekeres

cho trường hợp

n  6,

dựa trên hai bài báo [5] và [14].