Tài liệu định lí không điểm tổ hợp và một vài vận dụng

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ LAN DUNG ĐỊNH LÍ KHÔNG ĐIỂM TỔ HỢP VÀ MỘT VÀI VẬN DỤNG 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 Thái Nguyên - 2015 Mục lục Lời cảm ơn 3 Lời nói đầu 4 1 Định lý không điểm tổ hợp 6 1.1 1.2 Định lý không điểm tổ hợp . . . . . . . . . . . . . . . . . 6 1.1.1 Định lý không điểm Hilbert . . . . . . . . . . . . 6 1.1.2 Định lý không điểm tổ hợp . . . . . . . . . . . . . 8 1.1.3 Vận dụng . . . . . . . . . . . . . . . . . . . . . . 11 Khái niệm đồ thị . . . . . . . . . . . . . . . . . . . . . . 13 1.2.1 Đồ thị và đồ thị con . . . . . . . . . . . . . . . . 13 1.2.2 Bài toán tô màu 17 . . . . . . . . . . . . . . . . . . 2 Tổng thu hẹp-phương pháp đa thức 22 2.1 Phương pháp đa thức . . . . . . . . . . . . . . . . . . . . 22 2.2 Một vài ví dụ liên quan . . . . . . . . . . . . . . . . . . . 24 2.3 Điều kiện |A + B| = |A| + |B| − 1 . . . . . . . . . . . . . 28 3 Vận dụng 30 3.1 Chứng minh Định lý Fermat, Định lý Wilson . . . . . . . 3.2 Vận dụng tổng tập hợp trong phương trình nghiệm nguyên 33 1 30 3.3 3.4 3.2.1 Một vài phương trình vô nghiệm . . . . . . . . . . 34 3.2.2 Phương trình có nghiệm . . . . . . . . . . . . . . 36 3.2.3 Điều kiện tham số của phương trình . . . . . . . 36 Phương pháp đa thức qua nghiệm . . . . . . . . . . . . . 39 3.3.1 Chứng minh số vô tỷ . . . . . . . . . . . . . . . . 39 3.3.2 Bài toán Waring về đa thức . . . . . . . . . . . . 43 Phương pháp đa thức trong bất đẳng thức . . . . . . . . 46 Kết luận 50 Tài liệu tham khảo 51 2 Lời cảm ơn Luận văn này được hoàn thành tại trường Đại học Khoa học - Đại học Thái Nguyên. Tác giả xin bày tỏ lòng biết ơn sâu sắc với PGS.TS Đàm Văn Nhỉ, người thầy đã trực tiếp hướng dẫn tận tình và động viên tác giả trong suốt thời gian nghiên cứu vừa qua. Xin chân thành cảm ơn tới các thầy, cô giáo trong Bộ môn Toán Tin, Phòng Đào tạo Khoa học và Quan hệ quốc tế, các bạn học viên lớp Cao học Toán K7D trường Đại học Khoa học - Đại học Thái Nguyên, và các bạn đồng nghiệp đã tạo điều kiện thuận lợi, động viên tác giả trong quá trình học tập và nghiên cứu tại trường. Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới gia đình và người thân luôn khuyến khích, động viên tác giả trong suốt quá trình học tập và làm luận văn. Mặc dù có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu sót và hạn chế. Tác giả mong nhận được những ý kiến đóng góp quý báu của các thầy cô và bạn đọc để luận văn được hoàn thiện hơn. Xin chân thành cảm ơn! Thái Nguyên, 2015 Vũ Lan Dung Học viên Cao học Toán K7D, Trường ĐH Khoa học - ĐH Thái Nguyên 3 Lời nói đầu Mục đích của luận văn là chứng minh lại một số định lí nổi tiếng về đa thức nhiều biến với hệ số trên một trường như Định lý không điểm của Hilbert, Định lý không điểm tổ hợp của Noga Alon và một số vận dụng phương pháp đa thức, đồng thời vận dụng các định lí này để nghiên cứu một số vấn đề trong tổ hợp và trong số học. Đây là kết quả mới còn có thể tiếp tục phát triển thêm theo hướng nghiên cứu này. Luận văn được chia thành ba chương với những nội dung chính sau đây: Chương 1 của luận văn trình bày chứng minh Định lý không điểm của Hilbert, Định lý không điểm tổ hợp. Thực chất định lí không điểm tổ hợp là một dạng mở rộng của định lí không điểm Hilbert, định lí này cho một mô tả các đa thức triệt tiêu trên một tập điểm có dạng tích Descartes. Phần cuối chương I trình bày ứng dụng của định lí này vào các bài toán tô màu đồ thị. Chương 2 của luận văn trình bày phương pháp đa thức, tổng thu hẹp các thặng dư và một vài ví dụ liên quan. Chương 3 tập trung trình bày một số vận dụng các kết quả đạt được trong toán sơ cấp như chứng minh các kết quả cổ điển của số học đó là định lí Fecmat, Wilson, bài toán Waring (cho đa thức), giải một số phương trình nghiệm nguyên, chứng minh số vô tỉ, chứng minh một số bất đẳng thức trong toán phổ thông. Để hoàn thành luận văn này, em xin bày tỏ lòng biết ơn chân thành tới PGS.TS. Đàm Văn Nhỉ đã hướng dẫn, chỉ bảo tận tình em 4 trong suốt quá trình thực hiện luận văn này. Cuối cùng em xin bày tỏ lòng biết ơn sâu sắc tới các thầy cô trong Khoa Toán, Trường Đại học Khoa học, Đại học Thái Nguyên cùng toàn thể bạn bè trong lớp đã giúp đỡ, đóng góp ý kiến trong quá trình nghiên cứu, học tập và hoàn thành luận văn. Hải Dương, ngày 25 tháng 5 năm 2015 Học viên: Vũ Lan Dung 5 Chương 1 Định lý không điểm tổ hợp 1.1 1.1.1 Định lý không điểm tổ hợp Định lý không điểm Hilbert Khái niệm vành đa thức nhiều biến trên trường K đã được trình bày trong nhiều giáo trình đại số, chẳng hạn [1]. Do vậy, chúng tôi không nhắc lại ở đây. Một trường K thỏa mãn điều kiện mọi đa thức một biến bậc dương trên K đều có nghiệm trong K được gọi là trường đóng đại số, chẳng hạn trường số phức C là trường đóng đại số, còn trường số thực R không là trường đóng đại số. Để trình bày Định lý Hilbert về không điểm, ta sẽ vận dụng kết quả, không chứng minh, sau đây.  gi (x1 , . . . , xn ) = 0 Bổ đề 1.1.1. Nếu hệ phương trình đa thức i = 1, 2, . . . , r không có nghiệm thì tồn tại các đa thức ai (x1 , . . . , xn ) ∈ C[x1 , . . . , xn ] thỏa mãn r X ai (x1 , . . . , xn )gi (x1 , . . . , xn ) = 1. i=1  fi (x1 , . . . , xn ) = 0 Xét hệ các phương trình đa thức i = 1, 2, . . . , r. 6 Giả sử đa thức g(x1 , . . . , xn ) = 6 0 thỏa mãn g(ξ1 , ξ2 , . . . , ξn ) = 0 khi (ξ1 , ξ2 , . . . , ξn ) là fi (x1 , . . . , xn ) = 0 nghiệm của hệ Khi đó ta có kết quả sau: i = 1, 2, . . . , r. Định lý 1.1.2. [Hilbert’s zero-theorem] Giả sử g(x1 , . . . , xn ) 6= 0 thỏa mãn g(ξ1 , ξ2 , . . . , ξn ) = 0 khi (ξ1 , ξ2 , . . . , ξn ) là nghiệm của hệ  fi (x1 , . . . , xn ) = 0 i = 1, 2, . . . , r. Khi đó có các đa thức bi (x1 , . . . , xn ) ∈ C[x1 , . . . , xn ] và số nguyên dương r P s s thỏa mãn g(x1 , . . . , xn ) = bi (x1 , . . . , xn )fi (x1 , . . . , xn ). i=1 Chứng minh. Ký hiệu z là biến mới. Coi các đa thức fi (x1 , . . . , xn ) như là các phần tử thuộc vành đa thức C[x1 , . . . , xn , z]. Xét hệ phương trình đa thức    fi (x) = fi (x1 , . . . , xn ) = 0    i = 1, 2, . . . , r     zg(x) − 1 = zg(x1 , . . . , xn ) − 1 = 0. Hệ này vô nghiệm. Theo Bổ đề 1.1.1, tồn tại các ai (x1 , . . . , xn , z) và b(x1 , . . . , xn , z) thuộc vành C[x1 , . . . , xn , z] để r X ai (x1 , . . . , xn , z)fi (x) + b(x1 , . . . , xn , z)(zg(x) − 1) = 1. i=1 Đồng nhất thức này vẫn đúng khi ta thay z qua r X ai x1 , . . . , xn , i=1 1 . Từ đây suy ra g(x) 1
fi (x) = 1. g(x) Nhân hai vế với một lũy thừa thích hợp của g(x) ta nhận được hệ thức r P s g(x1 , . . . , xn ) = bi (x1 , . . . , xn )fi (x1 , . . . , xn ). i=1 7 1.1.2 Định lý không điểm tổ hợp Chúng ta sẽ chứng minh hai định lý của Noga Alon, giáo sư tại Tel Aviv University, gọi là Combinatorial Nullstellensatz, được sử dụng nhiều trong Tổ hợp, Lý thuyết số, Đồ thị và Tô màu. Bổ đề 1.1.3. Giả thiết trường K có char(K) = 0. Cho đa thức khác không g(x) = g(x1 , . . . , xn ) ∈ K[x] ta ký hiệu ti = degi g(x) là bậc của g(x) theo biến xi , i = 1, . . . , n. Ký hiệu các tập con Si ⊂ K thỏa mãn |Si | > ti + 1 với i = 1, . . . , n. Nếu g(α) = 0 thỏa mãn cho mọi (α) = (α1 , . . . , αn ) ∈ S1 × S2 × · · · × Sn thì g(x) ≡ 0. Chứng minh. Ta chứng minh kết luận bằng phương pháp quy nạp theo n. Với n = 1, ta có đa thức một biến g(x1 ) bậc t1 triệt tiêu trên tập S1 với nhiều hơn t1 phần tử. Do vậy g(x1 ) ≡ 0 theo Định lý Bezout. Giả sử kết luận đúng cho tất cả các đa thức ít hơn n biến. Biểu diễn lại đa thức g(x) thành đa thức của biến xn như sau: g(x1 , . . . , xn ) = tn X gj (x1 , . . . , xn−1 )xjn ∈ K[x1 , . . . , xn−1 ][xn ]. j=1 Với mỗi bộ (γ) = (γ1 , . . . , γn−1 ) ∈ S1 × S2 × · · · × Sn−1 cố định ta có tn P g(γ, xn ) = gj (γ)xjn ≡ 0 trên tập Sn . Từ đó suy ra gj (γ) = 0 với mọi j=0 j = 0, 1, . . . , tn và mọi (γ) ∈ S1 × S2 × · · · × Sn−1 . Theo giả thiết quy nạp ta có gj (x1 , . . . , xn−1 ) ≡ 0 với mọi j = 0, 1, . . . , tn . Như vậy g(x) ≡ 0. Bổ đề đã được chứng minh. Định lý 1.1.4. [Noga Alon] Giả thiết trường K có char(K) = 0. Cho đa thức khác không g(x) = g(x1 , . . . , xn ) ∈ K[x]. Ký hiệu các tập con Q Si ⊂ K thỏa mãn |Si | > 1 và pi (xi ) = (xi − s) với i = 1, . . . , n. Nếu s∈Si g(x) triệt tiêu tại mọi nghiệm chung của p1 , . . . , pn thì tồn tại đa thức 8 q1 , . . . , qn ∈ K[x1 , . . . , xn ] thỏa mãn deg qi 6 deg g − deg pi để n X g= qi pi . i=1 Chứng minh. Đặt ti = |Si | − 1 với i = 1, . . . , n. Theo giả thiết ta có g(α) = 0 với mọi (α) ∈ S1 × S2 × · · · × Sn . Biểu diễn lại đa thức pi (xi ) = Y (xi − s) = xtii +1 − Do pi (s) = 0 nên sti +1 = ti P j=0 j=0 aij xji , aij ∈ Si , i = 1, . . . , n. j=0 s∈Si ti P ti X aij sj , aij ∈ Si , i = 1, . . . , n. Như vậy xiti +1 = aij xji trên Si với i = 1, . . . , n. Ký hiệu đa thức g ∗ (x) là đa thức nhận được từ g(x) qua việc biểu diễn g(x) như là tổ hợp của các đơn thức ti P ti +1 và lần lượt thay xi bởi aij xji . Như vậy, đa thức nhận được sau khi j=0 ∗ thay g (x) có bậc không quá ti đối với mỗi biến xi với i = 1, . . . , n và nhận được từ g(x) bởi việc trừ đi các tích dạng qi pi , trong đó đa thức qi ∈ K[x1 , . . . , xn ] với deg qi 6 deg g − deg pi . Qua những lần biến đổi, ta n Q ∗ vẫn luôn luôn có g (α) = g(α) = 0 với mọi α ∈ Si . Theo Bổ đề 1.1.3, g ∗ ≡ 0 và suy ra g = n P i=1 q i pi . i=1 Định lý 1.1.5. [Noga Alon] Giả thiết trường K có char(K) = 0. Cho đa thức khác không g(x) = g(x1 , . . . , xn ) ∈ K[x] với bậc deg g(x) = n n P Q ti , ti ∈ N. Giả thiết hệ số của đơn thức xtii khác 0. Khi đó, nếu các i=1 i=1 tập con Si ⊂ K thỏa mãn |Si | > ti + 1 với i = 1, 2, . . . , n, thì tồn tại α1 ∈ S1 , . . . , αn ∈ Sn để g(α) 6= 0. Chứng minh. Ta chỉ cần chứng minh định lý cho trường hợp |Si | = ti + 1 với i = 1, 2, . . . , n. Giả sử kết luận trên không đúng. Xét các đa thức Q pi (xi ) = (xi − s), i = 1, . . . , n. Theo Định lý 1.1.4, tồn tại các đa thức s∈Si 9 q1 , . . . , qn ∈ K[x1 , . . . , xn ] thỏa mãn deg qi 6 n Q Theo giả thiết, hệ số của i=1 n P ti −deg pi để g = i=1 n P qi pi . i=1 xtii ở trong g(x) là khác 0 và kéo theo hệ số của đơn thức như thế ở bên phải cũng khác 0. Hơn nữa, bậc của Q qi pi = qi (xi − s) không lớn hơn bậc của đa thức g(x). Nếu có một s∈Si đơn thức nào ở bên phải hệ thức g = n P qi pi với bậc deg(g) thì đơn thức i=1 đó phải chia hết cho xtii +1 . Điều này kéo theo hệ số của n Q i=1 xtii ở n P qi pi i=1 phải bằng 0. Điều mâu thuẫn này chỉ ra điều giả sử là sai. Định lý đã được chứng minh. Giả thiết K = Zp với số nguyên tố p và các tập con khác rỗng S0 , S1 , . . . , Sn ⊂ K. Cho đa thức g(x) = g(x0 , x1 , . . . , xn ) ∈ K[x]. Định nghĩa n LP Si = {s0 + s1 + · · · + sn |si ∈ Si , g(s0 , s1 , . . . , sn ) 6= 0}. i=0 Định lý 1.1.6. [Noga Alon] Giả sử |Si | = ti + 1 với i = 0, 1, . . . , n và n n P Q định nghĩa m = ti − deg(g). Nếu hệ số của đơn thức xtii trong đa i=0 i=0 thức (x0 + x1 + · · · + xn )m g(x0 , x1 , . . . , xn ) mà khác 0 thì | n LP Si | = i=0 |{s0 + s1 + · · · + sn |si ∈ Si , g(s0 , s1 , . . . , sn ) 6= 0}| > m + 1. Chứng minh. Giả sử kết luận là sai và ký hiệu E là một tập gồm m phần tử (không nhất thiết phải phân biệt) thuộc Zp sao cho E chứa tập n LP Si = {s0 + s1 + · · · + sn |si ∈ Si , g(s0 , s1 , . . . , sn ) 6= 0}. Giả sử đa i=0 thức h = h(x0 , x1 , . . . , xn ) được định nghĩa như sau: h(x0 , x1 , . . . , xn ) = Y (x0 + x1 + · · · + xn − e)g(x0 , x1 , . . . , xn ). e∈E Theo định nghĩa h(s0 , s1 , . . . , sn ) = 0 thỏa mãn với mọi (s0 , s1 , . . . , sn ) ∈ (S0 , S1 , . . . , Sn ) do bởi hoặc g(s0 , s1 , . . . , sn ) = 0 hoặc (s0 + s1 + · · · + sn − e) = 0 với mọi (s0 , s1 , . . . , sn ) ∈ (S0 , S1 , . . . , Sn ). Vì deg(h) = m + 10 deg(g) = n P i=0 ti nên hệ số của đơn thức xt00 . . . xtnn thuộc h(x) cũng chính là hệ số của đơn thức ấy thuộc đa thức (x0 +x1 +· · ·+xn )m g(x0 , x1 , . . . , xn ) khác không theo giả thiết. Theo Định lý 1.1.5, tồn tại s0 ∈ S0 , . . . , sn ∈ Sn để h(s0 , s1 , . . . , sn ) 6= 0 mâu thuẫn với kết quả h(s0 , s1 , . . . , sn ) = 0 thỏa mãn với mọi (s0 , s1 , . . . , sn ) ∈ (S0 , S1 , . . . , Sn ). Như vậy, điều giả sử là sai. 1.1.3 Vận dụng Vận dụng đầu tiên là việc chứng minh phỏng đoán của Artin vào năm 1934 và được giải quyết bởi Chevalley và được Waring mở rộng đều vào năm 1935. Định lý 1.1.7. Giả sử p là số nguyên tố và các đa thức Pi thuộc vành m P Zp [x] = Zp [x1 , . . . , xn ] với i = 1, . . . , m. Nếu n > deg Pi và các đa i=1 thức Pi có chung một không điểm (α) thì chúng còn có chung một không điểm khác nữa. Chứng minh. Giả sử kết luận trên không đúng. Xét đa thức g = g(x) = m Y [1 − Pip−1 ] −δ i=1 n Y Y (xj − a) j=1 a∈Zp ,a6=αj với δ được chọn để g(α) = 0. Chú ý rằng, g(α) = 0 khi và chỉ khi n m Q Q Q 1 0 = [1 − 0] − δ (αj − a) hay δ = Q . Ta n Q i=1 j=1 a∈Zp ,a6=αj (αj − a) cũng chú ý rằng, khi (γ) ∈ Znp và (γ) 6= (α) có δ n Q Q j=1 a∈Zp ,a6=αj m Q [1 − Pi (γ)p−1 ] = 0 và i=1 (γj − a) = 0 và như vậy g(γ) = 0, (∗), với mọi (γ) ∈ Znp . Lấy j=1 a∈Zp ti = p−1 với mọi i và chú ý rằng, hệ số của vì bậc toàn thể của đa thức m Q i=1 n Q i=1 [1−Pip−1 ] 11 xtii trong g(x) bằng −δ 6= 0 bằng (p−1) m P i=1 deg Pi < (p−1)n. Như vậy, theo Định lý 1.1.5 với việc chọn Sj = Zp , j = 1, 2, . . . , n, có b1 , . . . , bn ∈ Zp để g(b1 , . . . , bn ) 6= 0, mâu thuẫn với (∗). Điều mâu thuẫn này chỉ ra điều giả sử là sai. Định lý đã được chứng minh. Định lý dưới đây được Cauchy chứng minh vào năm 1813 và áp dụng nó để đưa ra một chứng minh mới cho một kết quả của Lagrange vào năm 1770 về biểu diễn mỗi số tự nhiên thành tổng bốn số chính phương. Davenport phát biểu lại kết quả như một tương tự mới của phỏng đoán Khintchine. Định lý 1.1.8. [Cauchy-Davenport] Với số nguyên tố p và hai tập con khác rỗng của Zp ta luôn luôn có bất đẳng thức |A + B| > min{p, |A| + |B| − 1}. Chứng minh: Nếu A ∩ B = ∅ thì kết quả đúng. Xét A ∩ B 6= ∅. Nếu |A| + |B| > p thì giao giữa A và x \ B luôn khác rỗng cho mọi x ∈ Zp . Từ đây suy ra A + B = Zp và kết quả đúng. Xét trường hợp |A| + |B| 6 p. Giả sử kết luận của định lý là sai. Khi đó |A + B| 6 |A| + |B| − 2. Giả sử C là một tập con của Zp thỏa mãn A + B ⊂ C và |C| = |A| + |B| − 2. Q Định nghĩa đa thức g = g(x, y) = (x + y − c). Theo định nghĩa của c∈C C ta có g(a, b) = 0, (∗∗), với mọi a ∈ A, b ∈ B. Đặt t1 = |A| − 1 và t2 = |B| − 1. Chú ý rằng, hệ số của xt1 y t2 trong đa thức g đúng bằng
|A|+|B|−2 là khác 0 trong Zp vì |A| + |B| − 2 < p. Bởi vậy, theo Định |A|−1 lý 1.1.5 với n = 2, S1 = A, S2 = B có a ∈ A và b ∈ B để g(a, b) 6= 0, mâu thuẫn (∗∗). Điều mâu thuẫn này chỉ ra điều giả sử là sai. Định lý đã được chứng minh. 12 1.2 Khái niệm đồ thị 1.2.1 Đồ thị và đồ thị con Trước hết ta trình bày một số khái niệm cơ bản về lý thuyết đồ thị: Đồ thị G là một tập gồm các đỉnh và các cạnh nối các đỉnh đó. Ta thường kí hiệu G = (V, E), trong đó V là tập các đỉnh và E là tập các cạnh. Đồ thị G = (V, E) được gọi là đơn đồ thị vô hướng bao gồm V là tập các đỉnh và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Đồ thị G = (V, E) được gọi là đa đồ thị vô hướng bao gồm V là tập các đỉnh và E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e1 , e2 gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh. Đồ thị G = (V, E) được gọi là đơn đồ thị có hướng bao gồm V là tập các đỉnh và E là tập các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Đồ thị G = (V, E) được gọi là đa đồ thị có hướng bao gồm V là tập các đỉnh và E là họ các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Hai cung e1 , e2 được gọi là cung lặp nếu chúng cùng tương ứng với một cặp đỉnh. Giả sử u và v là hai đỉnh của đồ thị vô hướng G và e = (u, v) là cạnh của đồ thị. Khi đó ta nói u và v kề nhau và e liên thuộc với u và v; u và v là các đỉnh đầu của cạnh e. Bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó. Kí hiệu deg(v). Giả sử u và v là hai đỉnh của đồ thị có hướng G và e = (u, v) là cung của đồ thị. Khi đó ta nói u và v kề nhau và e đi ra khỏi u và đi vào v; 13 u là đỉnh đầu, v là đỉnh cuối của cạnh e. Bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có hướng là số cung ra khỏi nó (đi vào nó). Kí hiệu deg+ (v), deg− (v). Đường đi độ dài n từ đỉnh u đến đỉnh v trên đồ thị vô hướng G = (V, E) là dãy x0 , x1 , . . . , xn . Trong đó u = x0 , v = xn , (xi , xi+1 ) inE. Hay theo cạnh (x0 , x1 ), (x1 , x2 ), . . . , (xn−1 , xn ). Khi đó u gọi là đỉnh đầu, v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu và đỉnh cuối trùng nhau gọi là chu trình. Đường đi (hay chu trình) được gọi là đơn nếu nó không đi qua một cạnh nào quá một lần. Đường đi độ dài n từ đỉnh u đến đỉnh v trên đồ thị có hướng G = (V, E) là dãy x0 , x1 , . . . , xn . Trong đó u = x0 , v = xn , (xi , xi+1 ) inE. Hay theo cung (x0 , x1 ), (x1 , x2 ), . . . , (xn−1 , xn ). Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kì của nó. Đồ thị H = (W, F ) được gọi là đồ thị con của đồ thị G = (V, E) nếu W ⊆ V và F ⊆ E. Đồ thị đơn vô hướng n đỉnh được gọi là đồ thị đầy đủ nếu hai đỉnh bất kì đều được nối với nhau bằng 1 cạnh. Kí hiệu Kn . Đồ thị đơn vô hướng n đỉnh được gọi là đồ thị vòng nếu nó có duy nhất một chu trình đơn đi qua tất cả các đỉnh. Kí hiệu Cn . Đồ thị được gọi là đồ thị phẳng nếu ta có thể vẽ nó trên một mặt phẳng mà các cạnh không giao nhau. Một giả thuyết nổi tiếng của Berge và Sauer, được chứng minh bởi Taskinov, khẳng định rằng mọi đồ thị đơn, chính quy bậc 4 đều chứa một đồ thị con chính quy bậc 3. Khẳng định này dễ thấy là sai lầm cho các đồ thị với nhiều cạnh, nhưng như trong [2] một cạnh bổ sung đủ để đảm bảo một đồ thị con chính quy bậc 3 trong trường hợp tổng quát 14 hơn này là đúng. Điều sau từ trường hợp p = 3 như chỉ ra dưới đây, có thể suy ra một cách nhanh chóng từ định lý 1.1.5. Định lý 1.2.1. Cho p là một số nguyên tố bất kỳ, đồ thị vòng G = (V, E) bất kì với bậc trung bình lớn hơn 2p − 2 và bậc cực đại lớn nhất 2p − 1 chứa một đồ thị con chính quy bậc p. Chứng minh. Cho (av,e )v∈V,e∈E kí hiệu là ma trận liên thuộc của G được định nghĩa bởi av,e = 1 nếu v ∈ e và nếu không thì av,e = 0. Kết hợp mỗi cạnh e của G với một biến xe và xét đa thức  !p−1  X Y Y − 1 − av,e xe F = (1 − se ), v∈V e∈E e∈E trên GF (p). Lưu ý rằng bậc của F là |E|, vì bậc của tích đầu tiên nhiều nhất là (p − 1)|V | < |E|, bởi giả thiết trên bậc trung bình của G. Ngoài Q ra, hệ số của xe trong F là (−1)|E|+1 6= 0. Do đó, theo định lý 1.1.5, e∈E có các giá trị xe ∈ {0, 1} sao cho F (xe : e ∈ E) 6= 0. Theo định nghĩa của F , véctơ trên (xe : e ∈ E) là khác véctơ không, vì đối với vector này P F = 0. Ngoài ra av,e xe bằng không mod p với mọi v vì nếu không F e∈E sẽ triệt tiêu tại điểm này. Do đó, trong đồ thị con bao gồm tất cả các cạnh e ∈ E mà xe = 1 các bậc chia hết p và vì bậc cực đại nhỏ hơn 2p tất cả các bậc dương chính xác bằng p. Erdos và Sauer đã phát triển bài toán ước lượng số lượng tối đa các cạnh trong một đơn đồ thị trên n đỉnh mà không chứa đồ thị con chính quy bậc 3. Họ phỏng đoán rằng, với mọi số dương  không vượt quá n1+ , với điều kiện n đủ lớn như một hàm của . Điều này đã được chứng minh bởi Pyber, bằng cách sử dụng Định lý 1.2.1. Ông đã chứng minh rằng với đồ thị đơn bất kì bất kì n đỉnh với ít nhất 200n log n cạnh chứa một đồ thị con với bậc cực đại là 5 và bậc trung bình nhỏ hơn 4. Theo định lý 1.2.1, đồ thị con này chứa một đồ thị con chính quy bậc 3. Mặt 15 khác, Pyber , Rodl và Szemeredi đã chứng minh bằng lập luận xác suất rằng có một đồ thị đơn n đỉnh với ít nhất Ω(n log log n) cạnh mà không chứa đồ thị con chính quy bậc 3. Do đó, đánh giá của Pyber không phải là tốt nhất. Vận dụng Định lý 1.1.5 ta chứng minh các kết quả sau đây: Mệnh đề 1.2.2. Cho p là một số nguyên tố và cho G = (V, E) là một đồ thị trên tập |V | > d(p − 1) đỉnh. Khi đó, có một tập con khác rỗng U của các đỉnh của G sao cho chỉ số clique của d đỉnh của G mà giao U bằng 0 mod p. Chứng minh. Với mỗi tập con I các đỉnh của G, cho K(I) kí hiệu là số bản sao của Kd trong G mà chứa I. Kết hợp mỗi đỉnh v ∈ V với một biến xv và xét đa thức F = Y (1 − xv ) − 1 + G, v∈V trong đó p−1  G= X (−1)|I|+1 K(I) Y xi  i∈I ∅6=I⊂V trên GF (p). Vì K(I) bằng không với mọi bản số I lớn hơn d, bậc của đa thức này là |V |, như bậc của G nhiều nhất là d(p − 1) < |V |. Ngoài Q ra, hệ số của xv trong F là (−1)|V | 6= 0. Do đó, theo Định lý 1.1.5 v∈V tồn tại xv ∈ {0, 1} sao cho F (xv : v ∈ V ) 6= 0. Vì F triệt tiêu trên tất cả các véctơ 0, suy ra không phải tất cả các số xv bằng không và do đó G(xv : v ∈ V ) 6= 1, theo Định lý nhỏ của Fermat suy ra X ∅6=I⊂V (−1)|I|+1 K(I) Y xi ≡ 0( mod p) i∈I Tuy nhiên, vế trái của đồng dư trên bằng số bản sao của Kd mà giao với tập U = {v : xv = 1}. Vì U khác rỗng nên mệnh đề đúng. 16 Ta kết thúc phần này với một kết quả hình học đơn giản, đã được chứng minh để trả lời câu hỏi của Komjath. Kết quả này cũng là một hệ quả đơn giản của Định lý 1.1.5. Định lý 1.2.3. Cho H1 , H2 , . . . , Hm là họ các siêu phẳng trong Rn mà phủ tất cả các đỉnh của hình lập phương đơn vị {0, 1}n . Khi đó m > n. Chứng minh. Rõ ràng, ta có thể giả sử rằng các đỉnh không phủ là các véctơ không. Đặt (ai , x) = bi là phương trình xác định Hi , trong đó x = (x1 , x2 , . . . , xn ) và (a, b) là tích trong của hai véctơ a và b. Lưu ý rằng với mọi i, bi 6= 0 vì Hi không phủ gốc tọa độ. Giả sử khẳng định là sai và m < n, xét đa thức P (x) = (−1) n+m+1 m Y j=1 n m Y Y bj (xi − 1) − [(ai , x) − bi ]. i=1 i=1 Bậc của đa thức này rõ ràng bằng n và hệ số của (−1)n+m+1 m Q n Q trong đó là i=1 bj 6= 0. Do đó, theo Định lí 1.1.5 tồn tại điểm x ∈ {0, 1}n j=1 sao cho P (x) 6= 0. Điểm này không phải tất cả là các véctơ không, như P triệt tiêu trên nó và do đó nó là một vài đỉnh khác của hình lập phương. Nhưng trong trường hợp này (ai , x) − bi = 0 với một vài i, suy ra P không triệt tiêu trên điểm này, mâu thuẫn. 1.2.2 Bài toán tô màu Trước hết ta bắt đầu với một vài khái niệm cơ bản về tô màu đồ thị. Tô màu đồ thị (graph coloring) là trường hợp đặc biệt của gán nhãn đồ thị, mà trong đó mỗi đỉnh hay mỗi cạnh hay mỗi miền của đồ thị có thể được gán bởi một màu hay một tập hợp các màu nào đó. Tô màu đồ thị có thể là: Tô màu đỉnh (vertex coloring) là gán cho mỗi đỉnh của đồ thị một màu nào đó sao cho không có hai đỉnh nào liền kề lại trùng màu nhau; 17 Tô màu cạnh (edge coloring) là gán cho mỗi cạnh của đồ thị một màu nào đó sao cho sao cho không có 2 cạnh nào trùng màu; Tô màu miền (face coloring) là gán cho mỗi miền của đồ thị phẳng một màu sao cho không có 2 miền có chung đường biên lại cùng màu. Sắc số (chromatic number) của một đồ thị là số màu ít nhất để tô các đỉnh. Sắc số của đồ thị G được kí hiệu là χ(G). Số màu cạnh (chromatic index) của một đồ thị là số màu ít nhất dùng để tô các cạnh. Số màu cạnh của đồ thị G được kí hiệu là χ0 (G). Rõ ràng số màu cạnh bằng sắc số của đồ thị đường của G. Nếu G = (V, E) là một đồ thị (hữu hạn, có hướng hoặc vô hướng) và f là một hàm gán mỗi đỉnh v của G với một số nguyên dương f (v), ta nói rằng G là f - chọn nếu với mọi phép gán các tập các số nguyên S(v) ⊂ Z với các đỉnh v ∈ V , trong đó |S(v)| = f (v) với mọi v đều tồn tại một phép tô màu đỉnh thích hợp c : V 7→ Z sao cho c(v) ∈ S(v) với mọi v ∈ V . Đồ thị G là k - chọn nếu nó f - chọn với hàm hằng f (v) ≡ k. Số lựa chọn của G, kí hiệu là ch(G) là số nguyên k nhỏ nhất sao cho G là k - chọn. Hiển nhiên, số này số nhỏ nhất của sắc số χ(G) của G. Số lựa chọn của đồ thị đường của G, kí hiệu là ch0 (G) và thường được gọi là bảng số màu cạnh của G và rõ ràng nó ít nhất bằng số màu cạnh χ0 (G) của G. Theo quan sát của các nhà nghiên cứu khác nhau, có nhiều đồ thị G mà số lựa chọn ch(G) là lớn hơn sắc số χ(G). Một ví dụ đơn giản chứng minh thực tế này là đồ thị hai phía đầy đủ K3,3 . Nếu {u1 , u2 , u3 } và {v1 , v2 , v3 } là hai lớp các đỉnh đại diện của nó và S(ui ) = S(vi ) = {1, 2, 3}\{i} thì không có phép tô màu đỉnh thích hợp cho mỗi đỉnh ω với một màu từ tập S(ω) của nó. Do đó, số lựa chọn của đồ thị này vượt quá sắc số của nó. Trong thực tế, không khó để chứng minh rằng, với k ≥ 2 bất kì, tồn tại đồ thị hai phía có số lựa chọn vượt quá k. Ngoài 18 ra, bằng cách sử dụng lập luận xác suất, ta chứng minh được rằng với mọi k tồn tại một vài c(k) hữu hạn sao cho số lựa chọn của mọi đồ thị đơn với bậc nhỏ nhất vượt quá k. Theo quan điểm này, phỏng đoán sau được đề xuất độc lập bởi các nhà nghiên cứu khác nhau bao gồm Vizing, Albertson, Collins, Tucker và Gupta. Phỏng đoán (Danh sách phỏng đoán màu). Với mọi đồ thị G thì ch0 (G) = χ0 (G). Phỏng đoán này khẳng định rằng với đồ thị đường thì số lựa chọn bằng sắc số. Nhiều kết quả thú vị trong phần này là chứng minh trường hợp đặc biệt của phỏng đoán này mà vẫn còn mở rộng. Một phiên bản tiệm cận của nó đã được chứng minh bởi Kahn bằng cách sử dụng lập luận xác suất: Với bậc cực đại của đồ thị đơn d thì ch0 (G) = (1 + o(1))d trong đó o(1) tiến tới không như d tiến tới vô cùng. Trong trường hợp này χ0 (G) bằng d hoặc d + 1 theo định lý Vizing, điều này chứng tỏ rằng bảng phỏng đoán màu là gần đúng. Đa đồ thị fG = fG {x1 , x2 , . . . , xn } của đồ thị có hướng hoặc không có hướng G = (V, E) trên tập V = {v1 , v2 , . . . , vn } có n đỉnh được định Q nghĩa bởi fG (x1 , x2 , . . . , xn ) = {(xi − xj ) : i < j, {vi , vj } ∈ E}. Đa thức này được nghiên cứu bởi các nhà nghiên cứu khác nhau, bắt đầu là Petersen năm 1891. Đồ thị con có hướng H của một đồ thị có hướng D được gọi là Eulerian nếu bán bậc ra deg− H (v) của mọi đỉnh v của H bằng với bán bậc vào deg+ H (v). Lưu ý ta không giả sử rằng H là liên thông. H là chẵn nếu nó có số cạnh chẵn, nếu không thì gọi là lẻ. Cho EE(D) và EO(D) lần lượt kí hiệu là số chẵn hoặc lẻ các đồ thị con Eulerian của D. Để thuận tiện, ta đồng ý rằng đồ thị con khác rỗng là một đồ thị con Eulerian chẵn. 19