Thạc Sĩ Lý thuyết đồ thị và giả thuyết Erdos-Szekeres

Mục lục
1 Khái niệm đồ thị 5
1.1 Định nghĩa đồ thị . 5
1.2 Đường đi và chu trình . 6
1.3 Chu số và sắc số của đồ thị 9
1.3.1 Chu số của đồ thị . 9
1.3.2 Sắc số của đồ thị . 10
1.4 Chu trình Euler và chu trình Hamilton 17
1.4.1 Chu trình Euler 17
1.4.2 Chu trình Hamilton 20
2 Lý thuyết đồ thị, Định lý Ramsey và Giả thuyết Erd ¨ o s - Szekeres 25
2.1 Định lý Ramsey dưới ngôn ngữ đồ thị 25
2.2 Chứng minh định lí Ramsey nhờ ngôn ngữ đồ thị 28
2.3 Định lí Ramsey và chứng minh Giả thuyết Erd ¨ o s - Szekeres 34
2.3.1 Lịch sử bài toán Erd¨ os-Szekeres . 34
2.3.2 Định lí Ramsey dưới ngôn ngữ tập hợp . 37
2.3.3 Ứng dụng của Định lí Ramsey 39
2.3.4 Đánh giá cận trên và cận dưới của ES(n) 40
3 Mối quan hệ giữa lý thuyết đồ thị và giả thuyết Erd ¨ o s - Szekeres 43
3.1 Định lý Erd ¨ o s -Szekeres mở rộng cho các điểm ở vị trí lồi 45
3.2 Giả thuyết "Big Line or Big Clique" . 46
3.2.1 Tổng quát hóa của Định lý Erd ¨ o s - Szekeres . 50
3.2.2 Một số khẳng định . 55