Luận văn Công thức Euler - Poincaré trong hình học lồi

Đặc trưng Euler-Poincaré. Trong chương này chúng tôi trình bày định nghĩa của hàm định giá, các đặc trưng Euler-Poincaré, từ đó đưa ra công thức Euler - Poincaré trong hình học lồi. Mặc dù đã có nhiều cố gắng, nhưng do thời gian và trình độ còn hạn chế nên bản luận văn không tránh khỏi những thiếu sót nhất định. Tác giả rất mong nhận được ý kiến đóng góp của quý độc giả để bản luận văn này được hoàn thiện hơn. Thái Nguyên, ngày 22 tháng 5 năm 2017 Tác giả Phạm Thị Phương Thảo 3Lời cảm ơn Luận văn này được thực hiện tại trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành dưới sự hướng dẫn của TS. Hoàng Lê Trường. Tác giả xin trân trọng bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy, người đã tận tình chỉ bảo, hướng dẫn, động viên khích lệ và tạo điều kiện thuận lợi cho tác giả trong suốt quá trình học tập và nghiên cứu luận văn. Qua bản luận văn này, tác giả xin gửi lời cảm ơn tới Ban Giám hiệu trường Đại học Khoa học - Đại học Thái Nguyên, Ban chủ nhiệm khoa Toán - Tin, cùng các giảng viên đã tham gia giảng dạy và tạo mọi điều kiện tốt nhất để tác giả học tập và nghiên cứu trong suốt thời gian qua. Tác giả cũng xin cảm ơn gia đình, bạn bè, đồng nghiệp và tất cả mọi người đã quan tâm, động viên và giúp đỡ để tác giả có thể hoàn thành luận văn của mình. Tác giả xin chân thành cảm ơn! 4Danh mục các hình vẽ Hình 1.1: Một số hình ảnh đa diện . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . trang 9 Hình 1.2: Hình vuông xác định bởi (1.2) . . . . . . . . . . . . . . . . . . . . . . . . trang 10 Hình 1.3: Lần lượt là hình có chiều Q bằng 2 và chiều bằng 3 . . . trang 12 Hình 1.4: Chóp tứ giác . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. trang 17 Hình 1.5: Sơ đồ đếm các mặt của chóp tứ giác . . . . . . . . . . . . . . . . . . trang 17 Hình 1.6: Dàn các mặt của một kim tự tháp vuông . . . . . . . . . . . . .. trang 18 5Chương 1 Kiến thức chuẩn bị Trong chương này, chúng tôi định nghĩa các đối tượng ứng với các mối liên hệ giữa hình học lồi và tổ hợp. Chúng ta bắt đầu vấn đề đếm các tập cỡ d sao cho các phần tử thuộc tập [n]. Những tập như thế được gọi là d-đa tập con của [n]. Với mọi tập như vậy tương ứng với một d-bộ (m1,m2, . . . ,md) ∈ Zd sao cho 1 ≤ m1 ≤ m2 ≤ . . . ≤ md ≤ n. Nếu chúng ta bỏ qua tính nguyên của mj thì ta sẽ có một đối tượng hình học. Đối tượng hình học đó chính là nghiệm của hệ d + 1 bất phương trình tuyến tính n4d = {x ∈ Rd : 1 ≤ x1 ≤ x2 ≤ . . . ≤ xd ≤ n}. Những d-đa tập con chính xác là các điểm nguyên trong n4d. Tập n4d là một khối đa diện. Tập đó được xác định bởi một số hữu hạn các bất đẳng thức tuyến tính. Khối đa diện là một lớp các đối tượng hình học mà nhiều tính chất liên quan đến lĩnh vực đếm trong tổ hợp. Đối tượng chính của luận văn là đếm số mặt của khối đa diện cho trước. Tập các mặt có dạng một tập có thứ tự, được phân loại theo chiều và việc đếm các mặt trong cùng một chiều sẽ dẫn chúng ta đến một công thức nổi tiếng đó là công thức Euler - Poincaré. 61.1. Tập lồi Trong tiết này, chúng ta sẽ đưa ra các khái niệm và tính chất cơ bản liên quan đến tập lồi. Các đối tượng hình học của chúng ta sẽ được xây dựng thông qua khái niệm nửa không gian. Định nghĩa 1.1 Với các số thực a1, . . . , an và a = (a1, . . . , an) 6= 0, mặt phẳng afin là tập có dạng H= = H := {x ∈ Rd : 〈a,x〉 = b}, với a ∈ Rd\{0}, b ∈ R. Ở đây 〈 ., . 〉 là kí hiệu tích vô hướng trong Rd. Chúng ta gọi H là một siêu phẳng tuyến tính nếu 0 ∈ H hoặc là tương đương với b = 0. Bởi vì 0 ∈ H khi và chỉ khi b = 〈a,0〉 = 0. Phần bù Rn \H có hai phần rời nhau H> := {x ∈ Rn : a1x1 + . . .+ anxn > b} và H< := {x ∈ Rn : a1x1 + . . .+ anxn < b}. Các phần rời nhau này được gọi là nửa không gian afin mở xác định bởi H, và được kí hiệu lần lượt là H> và H<. Tương tự, tập H≥ := {x ∈ Rn : a1x1 + . . .+ anxn ≥ b}, và H≤ := {x ∈ Rn : a1x1 + . . .+ anxn ≤ b} được gọi là nửa không gian afin đóng xác định bởi H, và được kí hiệu lần lượt là H≥ và H≤ Định nghĩa 1.2 Một tập hợp P ⊆ Rn được gọi là một đa diện nếu nó là giao của một số hữu hạn các nửa không gian afin đóng. Lưu ý rằng đa diện là một tập đóng trong Rn theo tô pô thông thường nhưng có thể không là tập bị chặn. Ví dụ một nửa không gian afin đóng là đa diện không không bị chặn. Chúng ta nhận xét tầm thường rằng, tất cả không gian con afin, bao gồm Rd và ∅ là đa diện. Chúng ta gọi một đa diện P là thực sự nếu nó không là không gian afin. 7Định nghĩa 1.3 Một tập lồi S trong Rn là một tập trong Rn sao cho với mọi x1,x2 ∈ S và λ ∈ [0, 1], ta có λx1 + (1− λ)x2 ∈ S. Ví dụ 1.1 i) Trong R2, các hình đa lồi, hình tròn, hình elip là các tập lồi. Trong R3 thì khối đa diện, hình cầu là các tập lồi. ii) Hình cầu B = {x ∈ Rn : ‖x‖ ≤ 1} là tập lồi. Thật vậy, với mọi x,y ∈ B và λ ∈ [0, 1], ta có ‖(1− λ)x + λy‖ ≤ ‖(1− λ)x‖+ ‖λy‖ = (1− λ)‖x‖+ λ‖y‖ ≤ (1− λ) + λ = 1. Do đó (1− λ)x + λy ∈ B. iii) Hình cầu B(a, r) = {x ∈ Rn : ‖x − a‖ ≤ r} là một tập lồi (ở đây a ∈ Rn và r ≥ 0). Thật vậy, với mọi x,y ∈ B(a, r) và mọi λ ∈ [0, 1] ta có ‖λx + (1− λ)y− a‖ = ‖λ(x− a) + (1− λ)(y− a)‖ ≤ λ‖x− a‖+ (1− λ)‖y− a‖ ≤ λr + (1− λ)r = r. Do đó (1− λ)x + λy ∈ B(a, r). iv) Siêu phẳng afin H := {x ∈ Rd : 〈a,x〉 = b} là tập lồi. Thật vậy, cho x,y ∈ H, Khi đó ta có 〈a,x〉 = b và 〈a,y〉 = b Do đó với moi 0 ≤ λ ≤ 1, ta có 〈a, λx + (1− λ)y〉 = λ〈a,x〉+ (1− λ)〈a,y〉 = λb+ (1− λ)b = b. Vậy λx + (1− λ)y ∈ H và H là tập lồi. v) Tương tự iv), chúng ta có H> = {x ∈ Rn : 〈a,x〉 > b} và 8H< = {x ∈ Rn : 〈a,x〉 < b} là tập lồi. Bổ đề 1.1 Giao hữu hạn các tập lồi là tập lồi. Chứng minh. Giả sử P1, . . . , Pn là các tập lồi. Cho x,y ∈ n⋂ i=1 Pi. Khi đó x,y ∈ Pi với mọi i = 1, . . . , n. Do đó ta có λx + (1− λ)y ∈ Pi với mọi 0 ≤ λ ≤ 1. Từ đó, λx + (1− λ)y ∈ n⋂ i=1 Pi. Vậy n⋂ i=1 Pi là tập lồi.  Định nghĩa 1.4 Với một tập hữu hạn X = {u1, . . . ,us} ⊆ Rn, ta gọi conv(X) = { s∑ i=1 riui | 0 ≤ ri ∈ R, s∑ i=1 ri = 1} là bao lồi của X. Ví dụ 1.2 Bao lồi của hai điểm x1 và x2 trong R2 là đoạn thẳng. Bao lồi của ba điểm x1, x2, x3 không thẳng hàng trong R3 là hình tam giác. Bổ đề 1.2 Với một tập hữu hạn X ⊆ Rn, bao lồi conv(X) của X là tập lồi. Chứng minh. Giả sử X = {u1, . . . ,us}. Cho x,y ∈ conv(X). Khi đó x = s∑ i=1 riui và y = s∑ i=1 siui, trong đó 0 ≤ ri ∈ R, s∑ i=1 ri = 1 và 0 ≤ si ∈ R, s∑ i=1 si = 1. Khi đó λx + (1− λ)y = λ( s∑ i=1 riui) + (1− λ)( s∑ i=1 siui) = s∑ i=1 (λri + (1− λ)si)ui. 9Mặt khác ta có s∑ i=1 (λri + (1− λ)si) = λ( s∑ i=1 ri) + (1− λ)( s∑ i=1 ri) = λ+ (1− λ) = 1. Do đó λx + (1− λ)y ∈ conv(X). Vậy conv(X) là tập lồi  Định nghĩa 1.5 Một tập con khác rỗng P của Rn được gọi là khối đa diện nếu tồn tại một tập con hữu hạn X ⊂ Rn sao cho conv(X) = P . Chú ý rằng khối đa diện là đa diện nhưng một đa diện có thể không là khối đa diện. Ví dụ nón là đa diện nhưng không là khối đa diện. Chúng ta biết rằng P là khối đa diện khi và chỉ khi P là đa diện và P là tập bị chặn. Ví dụ 1.3 Hình lăng trụ, hình chóp, hình lập phương, kim tự tháp, . . . là các đa diện. Hình 1.1: Một số hình ảnh đa diện Định lý 1.1 Cho Q ⊆ Rd là một đa diện. Khi đó tồn tại các siêu phẳng Hi = {x ∈ Rd : 〈ai,x〉 = bi}, với i ∈ [k] sao cho Q = k⋂ i=1 H≤i = {x ∈ Rd : 〈ai,x〉 ≤ bi với mọi 1 ≤ i ≤ k}. (1.1) 10 Từ Định lý 1.1, chúng ta có thêm một phương thức mô tả đa diện. Chúng ta gọi một nửa không gian H≤j là không rút gọn được nếu ⋂ i 6=j H≤i 6= Q. Hơn nữa, chúng ta có duy nhất một họ các nửa không gian không rút gọn được để mô tả một đa diện. Bằng cách sắp xếp pháp tuyến của các siêu mặt như các hàng của một ma trận A ∈ Rk×d và cho b := (b1, b2, . . . , bk). Khi đó chúng ta có thể viết lại Q = {x ∈ Rd : Ax ≤ b} Ví dụ 1.4 Cho khối đa diện Q là bao lồi của các điểm A = (1, 0, 0), B = (0, 1, 0), C = (0, 1, 1) và D = (1, 0, 1). Hình 1.2 là mô tả hình học của Q. Cho ma trận A =  1 1 0 −1 −1 0 −1 0 0 0 −1 0 0 0 −1 0 0 1  , cho b := (1,−1, 0, 0, 0, 1) và x := (x1, x2, x3). Khi đó, chúng ta có thể mô tả lại khối đa diện Q như sau Q = {x ∈ R3 : Ax ≤ b}. (1.2) x3 x2 x1 1 1 1 Hình 1.2: Hình vuông xác định bởi (1.2) 11 Định nghĩa 1.6 Bao afin aff(Q) của một đa diện Q ⊆ Rd là không gian con afin nhỏ nhất của Rd chứa Q. Bổ đề 1.3 Cho đa diện Q ⊆ Rd. Khi đó aff(Q) = ⋂ {H siêu phẳng trong Rd : Q ⊆ H}. (1.3) Chứng minh. Vì H là không gian con afin và Q ⊆ H, bởi định nghĩa bao afin nên aff(Q) ⊆ H. Do đó aff(Q) ⊆ ⋂ {H siêu phẳng trong Rd : Q ⊆ H}. Vì aff(Q) là không gian con afin chứa Q nên aff(Q) = ⋂ {H siêu phẳng trong Rd : Q ⊆ H}.  Định nghĩa 1.7 Cho không gian afin H := {x ∈ Rd : 〈a,x〉 = b} với a ∈ Rd \ {0}, b ∈ R. Khi đó không gian vectơ ~H liên kết với không gian afin H là ~H := {x ∈ Rd : 〈a,x〉 = 0} Chiều của không gian afin H là chiều của không gian vector liên kết của H, tức là dimH = dim ~H. Nếu dimH = m ta gọi H là không gian afin chiều m hay m-phẳng. Chiều của đa diện Q là chiều của bao afin aff(Q), kí hiệu dimQ := dim aff(Q). Khi chiều Q bằng n thì ta gọi Q là n-đa diện. Nếu đa diện Q có chiều d thì ta nói rằng Q có chiều đầy đủ. Ví dụ 1.5 i) Cho dimH = 0 ta gọi H là không gian afin chiều 0 hay 0-phẳng tương ứng một điểm. 12 Cho dimH = 1 ta gọi H là không gian afin chiều 1 hay 1-phẳng tương ứng là một đường thẳng Cho dimH = 2 ta gọi H là không gian afin chiều 2 hay 2-phẳng tương ứng là một mặt phẳng Cho dimH = (n−1) ta gọiH là không gian afin chiều n−1 hay n−1-phẳng tương ứng là một siêu phẳng ii) Khi chiều của đa diện Q bằng 2 thì ta gọi Q là tam giác, khi chiều của đa diện Q bằng 3 thì ta gọi Q là tứ diện. Hình 1.3: Lần lượt là hình đa diện có chiều Q bằng 2 (tam giác) và chiều Q bằng 3 (tứ diện) iii) Hình vuông được xác định bởi ví dụ 1.4 có bao afin là {x ∈ R3 : x1 + x2 = 1} và như vậy số chiều của nó bằng 2. Cho Q là một đa diện được xác định bởi Q = k⋂ i=1 H≤i = {x ∈ Rd : 〈a,x〉 ≤ bi, với mọi 1 ≤ i ≤ k}. Khi đó phần trong của đa diện Q được định nghĩa là {x ∈ Rd : 〈ai,x〉 < bi, với mọi 1 ≤ i ≤ k.} (1.4) 13 Đặt I(Q) := {1 ≤ i ≤ k : 〈ai,x〉 = bi, với mọi x ∈ Q}. Khi đó phần trong tương đối của Q được định nghĩa là Q◦ := {x ∈ Q : 〈ai,x〉 < bi, với mọi i /∈ I(Q)} = aff(Q) ∩ {x ∈ Rd : 〈ai,x〉 < bi, với mọi i /∈ I(Q)}. Khi Q = Q◦ thì ta goi Q là đa diện mở tương đối. Biên của Q là ∂Q := Q \Q◦. Ví dụ 1.6 Cho Q là hình vuông được xác định trong ví dụ 1.4. Khi đó phần trong tương đối của Q làx ∈ R 3 : x1 + x2 = 1,  −1 0 0 0 −1 0 0 0 −1 0 0 1   x1x2 x3  <  0 0 0 1   Định nghĩa 1.8 Không gian con tuyến tính lineal(Q) của Q là không gian con cực đại theo nghĩa bao hàm sao cho tồn tại q ∈ Q mà q + lineal(Q) ⊆ Q. Ví dụ 1.7 x ∈ R3 : [ 1 −1 −1 −1 −1 1 ] x1x2 x3  ≤ [ 0 0 ] là một cạnh với không gian tuyến tính {x ∈ R3 : x1 = x3, x2 = 0} là một đường thẳng. Nếu lineal(Q) = {0} chúng ta gọi Q nhọn hoặc không đường thẳng. Định nghĩa 1.9 Cho tập con hữu hạn X = {v1, . . . ,vs} trong Rn. Một nón đa diện C(X) trong Rn được định nghĩa là C(X) = pos(v1, . . . ,vs) := { s∑ i=1 λivi : λi ≥ 0 } . 14 Mọi nón đa diện có biểu diễn thay thế là một tập có dạng C(X) = {x ∈ Rn : Ax ≤ 0}, trong đó A là ma trận cỡ d× n. 1.2. Mặt Định nghĩa 1.10 Cho một đa diện P ⊆ Rn, b ∈ R, và một vector a ∈ Rn. Một siêu phẳng H = {x ∈ Rd : 〈a,x〉 = b} là một giá phẳng của đa diện P nếu P ∩H 6= ∅ và (P ⊆ H≤ hoặc P ⊆ H≥). Một mặt của P là một tập có dạng P ∩H, trong đó H là một giá phẳng của P . Nói cách khác, tập facea(P ) = {x ∈ P | 〈x, a〉 ≤ 〈y, a〉, với mọi y ∈ P}. được gọi là một mặt của P . Bổ đề sau sẽ cho chúng ta thấy các mặt lại là các đa diện. Bổ đề 1.4 Với mỗi tập hợp X = {u1, . . . ,us} ⊆ Rn và w ∈ Rn, đặt λ = min{w · ui | 1 ≤ i ≤ s}, Xw = {ui ∈ X | w · ui = λ}. Khi đó facew(P ) = conv(Xw), trong đó P = conv(X) và w · u := 〈w,u〉. Chứng minh. Đầu tiên, ta chỉ ra λ = min{w · u | u ∈ P}. Cho u ∈ P . Khi đó ta có u = s∑ i=1 riui, với 0 ≤ ri ∈ R, s∑ i=1 ri = 1. Lấy tích vô hướng hai vế của biểu thức trên với vector w thì w · u = s∑ i=1 ri(w · ui) ≥ s∑ i=1 riλ = λ. Do đó min{w·u | u ∈ P} ≥ λ. Mặt khác, ta có λ = min{w·ui | 1 ≤ i ≤ s}. Do đó tồn tại uj ∈ X sao cho λ = w ·uj. Do X ⊂ P nên λ ≥ min{w ·u | u ∈ P}. Vậy λ = min{w · u | u ∈ P}. 15 Bằng cách thay đổi các chỉ số nếu cần thiết, ta có thể giả sử rằng Xw = {u1, . . . ,ur}. Cho u ∈ conv(Xw). Khi đó, u = r∑ i=1 siui, với 0 ≤ si ∈ R, r∑ i=1 si = 1. Lấy tích vô hướng hai vế của biểu thức trên với vector w thì w · u = r∑ i=1 si(w · ui) = r∑ i=1 siλ = λ. Mặt khác, u ∈ conv(Xw) ⊂ conv(X) nên u ∈ conv(X) = P. Do đó u ∈ P và w · u = λ = min{w · v | v ∈ P}. Vì vậy w · u ≤ w · v với mọi v ∈ P . Khi đó u ∈ facew(P ). Do đó ta có conv(Xw) ⊆ facew(P). Ngược lại, cho u ∈ facew(P ). Khi đó ta có w · u = λ. Do u ∈ P , ta có u = s∑ i=1 riui, với 0 ≤ ri ∈ R, s∑ i=1 ri = 1. Lấy tích vô hướng hai vế của biểu thức trên với vector w thì λ = w · u = s∑ i=1 ri(w · ui) Vì Xw = {u1, . . . ,ur}, ta có w · ui = λ với mọi i = 1, . . . , r và w · ui > λ với mọi i = r + 1, . . . , s. Do đó ta có λ = s∑ i=1 ri(w · ui) = λ r∑ i=1 ri + s∑ i=r+1 ri(w · ui). Mặt khác ∑r i=1 riλ = λ( ∑r i=1 ri) = λ(1− ∑s i=r+1 ri) (vì s∑ i=1 ri = 1). Suy ra λ = r∑ i=1 riλ+ λ s∑ i=r+1 ri. Do đó ta có s∑ i=r+1 ri(w · ui − λ) = 0. 16 Chú ý rằng w · ui > λ và ri ≥ 0 với mọi i = r + 1, . . . , s, nên từ đẳng thức trên chúng ta có ri = 0 với mọi i = r + 1, . . . , s. Do đó ta có u = r∑ i=1 riui ∈ conv(Xw). Vì vậy facew(P ) = conv(Xw).  Nhận xét 1.1 Từ Bổ đề 1.4, facew(P ) là một đa diện. Ngoài ra, facew(P ) là một đa diện vì nó là giao của P với siêu phẳng x ·w = min{x ·w | x ∈ P}. Vậy mặt F của P lại là một đa diện nên chúng ta có thể nói về chiều của mặt F . Tức là chiều của mặt F là chiều của đa diện F . Chúng ta coi P là một mặt và F là mặt thực sự nếu F 6= P . Chúng ta xem ∅ là một mặt. Mặt chiều 0 của P được gọi là đỉnh của P . Mặt chiều 1 của đa diện P được gọi là cạnh và mặt chiều d− 1 là siêu mặt của đa diện P . Tập các mặt của một d-đa diện P (bao gồm cả ∅) cùng với quan hệ bao hàm sẽ thiết lập một tập sắp thứ tự. Tập đó được gọi là dàn các mặt Φ(Q). Để kí hiệu quan hệ sắp thứ tự toàn phần của các mặt của một đa diện P , ta viết F  G với F và G là mặt của P sao cho F ⊆ G. Trong kí hiệu này, F ≺ G có nghĩa là F là một mặt thực sự của G. Dàn các mặt Φ(Q) đựơc phân loại theo chiều và một quan hệ quan trọng trên dàn các mặt Φ(Q) là f -vector. Cụ thể chúng ta đặt fk = fk(P ) := số mặt của P có chiều k. là số mặt có chiều k của đa diện P . Khi đó f(P ) := (f0, f1, . . . , fd−1) được gọi là f -vector của đa diện P . Ví dụ 1.8 Cho hình chóp tứ giác Q = SABCD. 17 A D C B S Hình 1.4: Chóp tứ giác (SABCD) (SAB) (SBC) (SCD) (SAD) (ABCD) SA SB AB SC BC SD ADCD S A C DB Hình 1.5: Sơ đồ đếm số mặt của hình chóp tứ giác Khi đó: Số mặt của hình chóp có chiều bằng 3 gồm SABCD tức là f3 = 1. Số mặt của hình chóp có chiều bằng 2 gồm các mặt phẳng (SAB), (SBC), (SCD), (SAD), (ABCD), tức là f2 = 5. 18 Số mặt của hình chóp có chiều bằng 1 gồm SA, SB, SC, SD, AB, BC, CD, AD tức là f1 = 8. Số mặt của hình chóp có chiều bằng 0 gồm S,A,B,C,D tức là f0 = 5. Vậy f -vector của hình chóp tứ giác Q là f(Q) = (5, 8, 5, 1). Ví dụ 1.9 Cho kim tự tháp vuông ta có dàn các mặt như sau Hình 1.6: Các dàn mặt của một kim tự tháp vuông Bổ đề 1.5 Cho một đa diện Q. Với mọi điểm p ∈ Q có duy nhất một mặt F của Q mà p ∈ F ◦. Điều này tương đương, chúng ta có hợp rời sau Q = ⊎ FQ F ◦. Chứng minh. Bao hàm ⊇ là hiển nhiên. Ta cần chứng minh bao hàm ⊆. Bởi Định lý 1.1, giả sử Q là giao của nửa siêu phẳng không rút gọn được Q = k⋂ j=1 H≤j , và p ∈ Q. Sau khi đánh số lại các nửa siêu phẳng, ta có thể giả sử p ∈ H=1 , . . . , H=m và p ∈ H<m+1, . . . , H<k , 19 với 0 ≤ m < k. Do đó F := m⋂ j=1 H=j ∩ k⋂ j=m+1 H≤j là một mặt của Q có phần trong F ◦ = m⋂ j=1 H=j ∩ k⋂ j=m+1 H<j chứa p.  Bổ đề 1.6 Cho F = facew(P ) là một mặt của đa diện lồi P và cho F ′ = facev(F ) là một mặt của đa diện lồi F . Khi đó F ′ là một mặt của P . Hơn nữa, với một  > 0 đủ nhỏ, ta có F ′ = facew+v(P ). Chứng minh. Giả sử rằng một tập hữu hạn X thỏa mãn P = conv(X). Cho λ = min{w ·u | u ∈ X}, Xw = {u ∈ X | u ·w = λ}, λ′ = min{v ·u | u ∈ Xw} và Xw,v = {u ∈ Xw | v · u = λ′}. Cho  là một số thực thỏa mãn điều kiện 0 <  < min{|λ−w · a| | a ∈ X −Xw} max{|λ′ − v · a| | a ∈ X −Xw} . Từ Bổ đề 1.4, ta có F = facew(P ) = conv(Xw) và F ′ = facev(F ) = conv(Xw,v). Hơn nữa, với mọi u ∈ Xw,v, ta có w · u + v · u = λ + λ′. Do đó, đủ để chỉ ra rằng với u ∈ Xw,v và a ∈ X −Xw,v, ta có w · u + v · u < w · a + v · a. Trường hợp 1. a ∈ Xw, ta có (w + v) · (u− a) = w · (u− a) + v · (u− a) = 0 + v · (u− a) < 0 Trường hợp 2. a 6∈ Xw và v · (u− a) ≤ 0, ta có (w + v) · (u− a) = w · (u− a) + v · (u− a) ≤ w · (u− a) < 0. 20 Trường hợp 3. a 6∈ Xw và v · (u− a) < 0, ta có (w + v) · (u− a) = w · (u− a) + v · (u− a) ≤ w · (u− a) + Av · (u− a) < 1 2 w · (u− a) < 0 Do đó ta có (w+ v) · (u− a) < 0 với mọi u ∈ Xw,v và a ∈ X −Xw,v. Do đó F ′ = facew+v(P ).  21 Chương 2 Đặc trưng Euler-Poincaré 2.1. Hàm định giá Bây giờ chúng ta sẽ đi đến một khái niệm quan trọng cho phép liên hệ hình học với tổ hợp, là đặc trưng Euler-Poincaré. Chúng ta tiếp cận với các đặc trưng Euler-Poincaré của đa diện thông qua phân tích đa diện thành các đa diện đặc biệt, mà chúng ta gọi là khối đa diện. Định nghĩa 2.1 Một tập S ⊆ Rd là đa lồi nếu nó là hợp rời hữu hạn của các đa diện mở tương đối S = P1 ∪ P2 ∪ . . . ∪ Pk, trong đó P1, P2, . . . , Pk ⊆ Rd là đa diện mở tương đối. Ví dụ 2.1 Một đa diện là đa lồi, bởi Bổ đề 1.5, bởi vì đa diện là hợp rời hữu hạn của các mặt mở của đa diện. Chúng ta kí hiệu PCd là họ các đa lồi trong Rd. Tập này là vô hạn và là tập có thứ tự với quan hệ bao hàm. Hơn nữa tập PCd có phần tử nhỏ nhất và lớn nhất lần lượt là ∅ và Rd. Giao và hợp hữu hạn các đa lồi lại là đa lồi nên tập PCd là dàn phân phối. Định nghĩa 2.2 Một ánh xạ Φ từ PCd đến một nhóm Abel là một định giá 22 nếu Φ(∅) = 0 và Φ(S ∪ T ) = Φ(S) + Φ(T )− Φ(S ∩ T ) (2.1) với mọi S, T ∈ PCd. Khi đó ta có định lý sau Định lý 2.1 Tồn tại một định giá X : PCd −→ Z sao cho X (P ) = 1 với mọi khối đa diện đóng khác rỗng P ⊂ Rd. Nhắc lại rằng khối đa diện đóng là một đa diện và là tập đóng với tô pô thông thường và cũng là tập bị chặn. Định lý là không tầm thường. Thật vậy, nếu P ⊂ Rd là một d–đa diện và H = {x ∈ Rd : 〈a, x〉 = b} là một siêu phẳng sao cho H ∩ P ◦ 6= ∅. Vậy P1 := {x ∈ P : 〈a, x〉 b} là các đa diện khác rỗng sao cho P1 ∩ P2 = ∅ và như vậy X (P ) = X (P1) + X (P2). Vì vậy, nếu X là một định giá thỏa mãn các điều kiện của Định lí 2.1, thì tất yếu X (P1) = 0. Mục tiêu của phần này là xây dựng một định giá X thỏa mãn điều kiện của Định lý 2.1. Tính chất (2.1) sẽ là chìa khóa để đơn giản hóa việc tính toán của X (S) cho tập đa lồi tùy ý. Nếu S = P1 ∪ P2 ∪ . . . ∪ Pk, với mỗi Pi ⊆ Rd là một đa diện mở tương đối. Lặp lại quá trình (2.1), chúng ta được công thức bù trừ X (S) = ∑ i X (Pi)− ∑ i<j X (Pi ∩ Pj) + . . . (2.2) = ∑ ∅6=I⊆[k] (−1)|I|−1X (PI) (2.3) với PI := ∩i∈IPi. Đặc biệt, giá trị của X (S) không phụ thuộc vào cách phân tích của S như là hợp rời của đa diện mở tương đối. 23 Sau đây là một cách để xây dựng các đa lồi. Giả sử H := {H1, H2, . . . , Hn} là tập hữu hạn các siêu phẳng trong Rd Hi := {x ∈ Rd : 〈ai,x〉 = bi} Kí hiệu H>i := {x ∈ Rd : 〈ai,x〉 > bi} là các nửa không gian mở được xác đỉnh bởi Hi. Tương tự, chúng ta định nghĩa H<i và H = i := Hi. Với mọi σ = (σ1, σ2, . . . , σn) ∈ {}n chúng ta kí hiệu Hσ := H σ1 1 ∩Hσ22 ∩ . . . ∩Hσnn (2.4) là một khối đa diện mở tương đối. Khi đó đặt PC(H) = {S | tồn tại σ1, . . . , σk ∈ {}n sao cho Hσi 6= ∅ với mọi i = 1, . . . , k và S = Hσ1 ⊎ Hσ2 ⊎ . . . ⊎ Hσk} ⊆ PCd. Chú ý rằng Hσ1 ∩Hσ2 = ∅ với mọi σ1 6= σ2 ∈ {}n. Do đó S ∈ PC(H) có biểu diễn duy nhất qua Hσ. Với mọi σ ∈ {}n chúng ta kí hiệu X (H, Hσ) := (−1)dimHσ . Khi đó với mọi S ∈ PC(H), tồn tại duy nhấtHσi 6= ∅ với mọi i = 1, . . . , k và S = Hσ1 ⊎ Hσ1 ⊎ . . . ⊎ Hσk . Do đó X (H, S) := k∑ j=1 (−1)dimHσj . Bổ đề 2.1 Với kí hiệu như vừa nêu trên. Ta có hàm X (H, ·) : PC(H)→ Z, S 7→∑kj=1(−1)dimHσj là hàm định giá. Chứng minh. Cho S, T ∈ PCd(H). Khi đó tồn tại duy nhất σ1, . . . , σk ∈ {}n sao cho 24 Hσi 6= ∅ với mọi i = 1, . . . , k và S = Hσ1 ⊎ . . . ⊎ Hσs T = Hσt ⊎ . . . ⊎ Hσk S ∩ T = Hσt ⊎ . . . ⊎ Hσs với 1 ≤ t, s ≤ k. (Nếu s < t thì S ∩ T = ∅). Khi đó, S ∪ T = Hσ1 ⊎ . . . ⊎ Hσk Do đó X (H, S ∪ T ) = k∑ j=1 (−1)dimHσj = s∑ j=1 (−1)dimHσj + k∑ j=t (−1)dimHσj − s∑ j=t (−1)dimHσj = X (H, S) + X (H, T )−X (H, S ∩ T ).  2.2. Công thức Euler-Poincaré Trong mục này chúng ta sẽ đưa ra chứng minh Định lý 2.1. Chúng ta bắt đầu với bổ đề sau. Bổ đề 2.2 Cho S là đa diện mở tương đối chiều d trong Rd và H là siêu phẳng trong Rd sao cho H ∩ S 6= ∅. Khi đó H ∩ S là đa diện mở tương đối chiều d− 1. Chứng minh. Bởi định nghĩa đa diện mở tương đối, nên chúng ta chỉ cần chứng minh dimH ∩ S = d− 1. Thật vậy, từ định nghĩa của bao afin, ta có aff(H ∩ S) = aff(S) ∩ H 25 Do đó ta có ~aff(H ∩ S) = ~aff(S) ∩ H = ~aff(S) ∩ ~H. Từ dãy khớp sau của các không gian vector 0→ ~aff(S) ∩ ~H → ~aff(S)⊕ ~H → ~aff(S) + ~H = Rd → 0 ta nhận được dimS ∩H = dim ~aff(S) ∩ ~H = dim ~aff(S) + dim ~H − dimRd = dimS + (d− 1)− d = dimS − 1.  Bổ đề 2.3 Giả sử H1,H2 là hai tập siêu phẳng trong Rd và giả sử S ∈ PC(H1) ∩ PC(H2) thì X (H1, S) = X (H2, S). Chứng minh. Chúng ta chỉ cần chứng minh X (H1, S) = X (H1 ∪ {H}, S) trong đó H ∈ H2 \ H1 (2.5) Bởi vì lặp lại (2.5) ta có X (H1, S) = X (H1 ∪H2, S) và tương tự, X (H2, S) = X (H1 ∪H2, S) mà ta phải chứng minh. Một cách làm đơn giản hơn, chúng ta chỉ cần chứng minh (2.4) cho S = Hσ với mọi σ. Thật vậy, từ phép biểu diễn S = Hσ1 unionmultiHσ2 unionmulti . . . unionmultiHσk , chúng ta được X (H1, S) = X (H1, Hσ1) + X (H1, Hσ2) + . . .+ X (H1, Hσk). Do đó, giả sử S = Hσk ∈ PC(H1) và H ∈ H2 \ H1. Có ba khả năng S liên quan đến H. Trường hợp dễ là S∩H = S và S∩H = ∅. Trong cả hai trường hợp S là một đa lồi thực sự trong PCd(H1 ∪ {H}) và X (H1 ∪ {H}, S) = (−1)dimS = X (H1, S) Trường hợp chú ý duy nhất là ∅ 6= S ∩H 6= S. Vì S là đa diện mở tương đối, S := S ∩H> đều khác rỗng và là các đa diện mở tương 26 đối có chiều dimS và S= := S ∩H= là đa diện tương đối mở chiều dimS − 1 bởi Bổ đề 2.2. Vì thế, S = S là một cách biểu diễn của S như là một phần tử của PC(H1∪{H}), và như vậy X (H1 ∪ {H}, S) = X (H1 ∪ {H}, S) = (−1)dimS + (−1)dimS−1 + (−1)dimS = (−1)dimS = X (H1, S).  Cách chứng minh trên của Bổ đề 2.3 là phổ biến khi làm việc với hàm định giá. Tính chất 2.1 của hàm định giá cho phép chúng ta làm mịn hơn các tập đa lồi bằng cách cắt chúng bởi các siêu phẳng và nửa không gian mở. Rõ ràng không tồn tại tập hữu hạn các siêu phẳng H sao cho PCd = PC(H). Tuy nhiên mệnh đề sau cho chúng ta thấy chúng ta có thể hạn chế sự quan tâm tới tập PC(H) với H nào đó. Mệnh đề 2.1 Cho S ∈ PCd là một tập đa lồi. Khi đó tồn tại một tập các siêu phẳng H sao cho S ∈ PC(H). Chứng minh. Dễ thấy, ta có thể viết S = P1 ∪ P2 ∪ . . . ∪ Pk, với Pi là các đa diện mở tương đối. Với mọi Pi, tồn tại tập hữu hạn các siêu phẳng Hi := {H1, H2, . . . , Hm} sao cho Pi = ∩jHσjj với σj ∈ {}m. Do đó Pi ∈ PC(Hi). Vậy S ∈ PC(H1 ∪H2 ∪ . . . ∪Hk).  Chúng ta có thể phát biểu nội dung của Mệnh đề 2.1 như sau. Cho hai sắp xếp siêu phẳng H1 và H2, H1 ⊆ H2 ⇒ PC(H1) ⊆ PC(H2) Theo ngôn ngữ trừu tượng hơn, PCd là hợp của PC(H) với tất cả sắp xếp siêu phẳng H. Tức là PCd = ⋃ H là sắp xếp siêu phẳng PC(H). 27 Mệnh đề 2.2 Tồn tại một định giá duy nhất X : PCd −→ Z sao cho với mọi tập đa lồi S ∈ PCd, X (S) = X (H, S), với mọi sắp xếp siêu phẳng H mà S ∈ PC(H). Chứng minh. Với S ∈ PCd, Bổ đề 2.3, chúng ta có thể định nghĩa X (S) := X (H, S). với mọi sắp xếp siêu phẳng H sao cho S ∈ PC(H). Từ mệnh đề 2.1 chắc chắn có một H sao cho S ∈ PC(H). Chúng ta có ngay kết luận rằng X (P ) = X (H, P ) = (−1)dimP với một đa diện mở tương đối khác rỗng P . Nhưng tính duy nhất của định giá được suy ta từ việc chúng ta có thể viết tập đa lồi như là một hợp duy nhất của nhiều đa diện mở tương đối.  Hệ quả 2.1 Nếu P là một đa diện mở tương đối khác rỗng thì X (P ) = (−1)dimP . Hàm định giá X trong Mệnh đề 2.2 là đặc trưng Euler, và trong phần còn lại của luận văn này, chúng ta nói đến đặc trưng Euler của P khi viết X (P ). Chứng minh cho kết luận của chúng ta về Định lí 2.1 rằng X (P ) = 1 với bất kì P là khối đa diện đóng khác rỗng. Trước tiên chúng ta cần lưu ý rằng X (H, Hσ) = (−1)dim(Hσ) cho ta một cách rõ ràng về cách tính đặc trưng Euler của một khối đa diện