Chủ đề này có 25 trả lời

[CXR]

Lời giới thiệu: POW sẽ bắt đầu với một vấn đề nho nhỏ thể hiện sự liên hệ giữa nhiều chuyên ngành khác nhau của Toán học. Chỉ số trải và chỉ số phủ là các bất biến được định nghĩa trên không gian vector các đa thức đồng bậc. Vấn đề tính 2 bất biến này bắt nguồn từ việc nghiên cứu giả thuyết dạng Cohen-Macaulay (Cohen-Macaulay type) nằm trong chuyên ngành đại số giao hoán (commutative algebra) và đại số máy tính (computational algebra). Hướng tiếp cận hiệu quả nhất về mặt thuật toán đối với bài toán tính chỉ số trải và chỉ số phủ lại mang đậm nét tổ hợp, thông qua việc nghiên cứu các phức đơn (simplicial complex).

Trước tiên tôi sẽ phát biểu bài toán, nói qua một chút về nguồn gốc của bài toán. Phần chính của thảo luận này sẽ nhằm giới thiệu hướng tiếp cận tổ hợp thông qua phức đơn đối với bài toán. Hy vọng rằng sự đơn giản của hướng tiếp cận này sẽ thúc đẩy chúng ta cùng thảo luận nhằm hiểu sâu hơn vấn đề và đi tới một lời giải hoàn chỉnh cho bài toán.

[CXR]

Phát biểu bài toán. Giả sử http://dientuvietnam...n/mimetex.cgi?S như vành đa thức n biến với hệ số thực). Với mỗi số tự nhiên http://dientuvietnam...n/mimetex.cgi?d, ký hiệu http://dientuvietnam...mimetex.cgi?S_d là tập các đơn thức bậc http://dientuvietnam...n/mimetex.cgi?d và ký hiệu http://dientuvietnam...mimetex.cgi?V_d là không gian vector (trên trường số phức) của các đa thức thuần nhất bậc http://dientuvietnam...n/mimetex.cgi?d trong http://dientuvietnam.../mimetex.cgi?S. Với mỗi không gian vector con http://dientuvietnam...n/mimetex.cgi?V của http://dientuvietnam...mimetex.cgi?V_d, gọi http://dientuvietnam...imetex.cgi?S_1V là không gian vector con của http://dientuvietnam.net/cgi-bin/mimetex.cgi?V_{d+1} sinh bởi các phần tử có dạng http://dientuvietnam.net/cgi-bin/mimetex.cgi?x_iv trong đó http://dientuvietnam.net/cgi-bin/mimetex.cgi?x_i là biến nào đó của http://dientuvietnam.net/cgi-bin/mimetex.cgi?S và http://dientuvietnam.net/cgi-bin/mimetex.cgi?v là phần tử nào đó của http://dientuvietnam.net/cgi-bin/mimetex.cgi?V.

Chỉ số trải: Chỉ số trải (phụ thuộc vào http://dientuvietnam.net/cgi-bin/mimetex.cgi?n và http://dientuvietnam.net/cgi-bin/mimetex.cgi?d) được định nghĩa bởi
http://dientuvietnam.net/cgi-bin/mimetex.cgi?V_d sao cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?S_1V trải rộng nhất ở mức có thể trong không gian vector http://dientuvietnam.net/cgi-bin/mimetex.cgi?V_{d+1}.

Chỉ số phủ: Chỉ số phủ (phụ thuộc vào http://dientuvietnam.net/cgi-bin/mimetex.cgi?n và http://dientuvietnam.net/cgi-bin/mimetex.cgi?d) được định nghĩa bởi
http://dientuvietnam.net/cgi-bin/mimetex.cgi?V_d sao cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?S_1V phủ toàn bộ không gian http://dientuvietnam.net/cgi-bin/mimetex.cgi?V_{d+1}.

Bài toán: Tính http://dientuvietnam.net/cgi-bin/mimetex.cgi?\alpha_n(d) và http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_n(d+1).

[CXR]

Ghi chú: Không gian http://dientuvietnam...mimetex.cgi?V_d là không gian các đa thức thuần nhất bậc d .. chứ không chỉ là không gian các đa thức bậc d. Cám ơn noproof đã chỉ ra chỗ chưa chính xác của định nghĩa trên

[noproof]

Ta có kết quả cho bài toán với http://dientuvietnam...mimetex.cgi?n=2, trường hợp đơn giản nhất, sau n=1 (bằng cách tương ứng mỗi đơn thức http://dientuvietnam..._2}...x_n^{i_n} với bộ http://dientuvietnam...gi?(i_1,...,i_n),...):
http://dientuvietnam.net/cgi-bin/mimetex.cgi?a_2(d)=[\dfrac{d+1}{2}]
http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_2(d+1)=[\dfrac{d+2}{2}]
[] là ký hiệu phần nguyên.
và có thể chứng minh được

Bài viết đã được chỉnh sửa nội dung bởi noproof: 23-03-2005 - 17:53

[CXR]

Ta có kết quả cho bài toán với http://dientuvietnam...mimetex.cgi?n=2, trường hợp đơn giản nhất, sau n=1 (bằng cách tương ứng mỗi đơn thức http://dientuvietnam..._2}...x_n^{i_n} với bộ http://dientuvietnam...gi?(i_1,...,i_n),...):
http://dientuvietnam.net/cgi-bin/mimetex.cgi?a_2(d)=[\dfrac{d+1}{2}]
http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_2(d+1)=[\dfrac{d+2}{2}]
[] là ký hiệu phần nguyên.
và có thể chứng minh được

noproof trình bày lời giải cho n = 2 và chứng minh chặn cho trường hợp tổng quát như đã nói được không?

[canh_dieu]

Em xin chen ngang tí.

Chặn của noproof là hơi bị đẹp cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_n(d+1) vì http://dientuvietnam...mimetex.cgi?d=1, http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_n(d+1)=n nhưng http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{C^{n-1}_{n+d}}{n}=\dfrac{n+1}{2}.

@ noproof. Hình như phải là http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_2(d+1)=\lceil\dfrac{d+2}{2}\rceil.

Bài viết đã được chỉnh sửa nội dung bởi canh_dieu: 24-03-2005 - 05:59

[CXR]

Em xin chen ngang tí.

canh_dieu tích cực thảo luận vào chứ lại dùng từ "chen ngang" để "rũ bỏ" trách nhiệm à? ...

Cái chặn tổng quát của noproof là rất đẹp. Phần chặn dưới cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_n(d+1) thì anh thấy rồi chứ còn chặn trên cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?\alpha_n(d) như thế thì chưa thấy. noproof đưa chứng minh lên đây để cùng thảo luận cái nhé

Mọi người thử xét trường hợp n = 3 xem thế nào. Trong trường hợp này vấn đề khó hơn nhiều. Đặt http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_3(d+1).
(1) Chứng minh rằng nếu với thì .
(2) Chứng minh rằng với .
(3) Chứng minh rằng và .

CXR có việc đột xuất phải đi vắng mấy ngày. Hy vọng mọi người tiếp tục thảo luận. Đầu tuần sau CXR sẽ tiếp tục.

[RongChoi]

RC d-ua do`i theo canh_dieu chen ngang ti (the nao cu~ng bi. anh CXR ma(/ng)

[quote name='canh_dieu' date='Mar 24 2005, 05:07 AM'] Em xin chen ngang tí.

Chặn của noproof là hơi bị đẹp cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_n(d+1) vì http://dientuvietnam.net/cgi-bin/mimetex.cgi?\alpha_n(d+1) hay hon vi` cha(.n cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_n(d+1) thi` kha' hie^?n nhie^n :
.

D-o*.i noproof d-ua proof nhi

[CXR]

Theo như RongChoi nói thì chặn dưới của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_n(d+1) có vẻ dễ tính nhỉ. Hay ta thử tìm chặn trên của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_n(d+1) và chặn dưới của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\alpha_n(d) xem thế nào - có khi vấn đề sẽ trở thành thú vị hơn.

Đầu tuần tới anh sẽ viết tiếp về cách tiếp cận bài toán này thông qua "phức đơn".

[noproof]

Không gian véctơ http://dientuvietnam...mimetex.cgi?V_d có một cơ sở sinh bởi các đơn thức bậc d, mà số các dơn thức bậc d là http://dientuvietnam...C^{n-1}_{n d-1}, nên http://dientuvietnam...tex.cgi?dim(V_d)=C^{n-1}_{n+d-1}.

Xét V là một không gian véctơ con của http://dientuvietnam...mimetex.cgi?V_d (chưa cần V giả thiết sinh bởi các đơn thức) số chiều k, gọi http://dientuvietnam...cgi?P_1,...,P_k là một cơ sở của V. Khi đó tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?A=\{x_iP_j:i=1,...,n;j=1,...,k\} là hệ sinh của http://dientuvietnam...metex.cgi?S_1V. Do vậy, ta có

http://dientuvietnam.net/cgi-bin/mimetex.cgi?Card(A)=n*k và A là một cơ sở của http://dientuvietnam.net/cgi-bin/mimetex.cgi?k\leq\dfrac{C^{n-1}_{n+d}}{n}.

2) Với V mà http://dientuvietnam...gi?S_1V=V_{d 1}, từ suy ra http://dientuvietnam.net/cgi-bin/mimetex.cgi?a_n(d)\leq\dfrac{C^{n-1}_{n+d}}{n}\leq\rho_n(d+1)

Với n=2, ta có http://dientuvietnam.net/cgi-bin/mimetex.cgi?X^d,x^{d-2}Y^2,....,X^{d-2r+2}Y^{2r-2}, khi đó dim V=r và http://dientuvietnam.net/cgi-bin/mimetex.cgi?dim(S_1V)=2dim(V). Vâỵ http://dientuvietnam.net/cgi-bin/mimetex.cgi?a_2(d)=[\dfrac{d+2}{2}].
b)Ta có http://dientuvietnam.net/cgi-bin/mimetex.cgi?X^{2k},X^{2k-2}Y^2,...Y^{2k}, khi đó http://dientuvietnam.net/cgi-bin/mimetex.cgi?dim(V)=k+1=&#091;\dfrac{d+3}{2}]=\dfrac{d+2}{2} và http://dientuvietnam.net/cgi-bin/mimetex.cgi?S_1V=V_{d+1}. Với d=2k+1 lẻ, xét V là không gian sinh bởi http://dientuvietnam.net/cgi-bin/mimetex.cgi?X^{2k+1},X^{2k-1}Y^2,...,XY^{2k},Y^{2k+1}. Khi đó http://dientuvietnam.net/cgi-bin/mimetex.cgi?dim(V)=k+2<\dfrac{d+2}{2}+1, và http://dientuvietnam.net/cgi-bin/mimetex.cgi?S_1V=V_{d+1}. Vậy http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_2(d+1)=k+2=&#091;\dfrac{d+3}{2}].

[CXR]

Bravo noproof .. Vậy là ta đã có lời giải hoàn toàn trong trường hợp http://dientuvietnam.net/cgi-bin/mimetex.cgi?\alpha_n(d) và chặn dưới cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_n(d+1). Vấn đề còn lại gồm:

(1) Tìm chặn dưới cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?\alpha_n(d) và chặn trên cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_n(d+1). Các chặn này có chặt không?!
(2) Chứng minh công thức của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_3(d+1) như đã có. Tìm công thức của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\alpha_3(d).
(3) Tìm công thức chính xác với (thử bắt đầu với !).

[CXR]

Bây giờ CXR sẽ thảo luận một chút về một mặt khác của vấn đề: tìm các thuật toán để tính http://dientuvietnam.net/cgi-bin/mimetex.cgi?\alpha_n(d) và http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_n(d+1).

Thuật toán đơn giản nhất có lẽ là thử tất cả các khả năng có thể. Do http://dientuvietnam...mimetex.cgi?V_d có http://dientuvietnam...mimetex.cgi?2^p khả năng (tương ứng với http://dientuvietnam...mimetex.cgi?2^p các tập con của http://dientuvietnam...mimetex.cgi?S_d). Với http://dientuvietnam...n/mimetex.cgi?n lớn, con số này sẽ là rất rất lớn ... mọi người thử viết chương trình và chạy với http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta trên một tập http://dientuvietnam...n/mimetex.cgi?n phần tử http://dientuvietnam...n/mimetex.cgi?W thỏa mãn:
(a) http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta là một phức đơn trên http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta được gọi là một mặt của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta.
(2) Nếu http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta thì chiều của http://dientuvietnam.net/cgi-bin/mimetex.cgi?F được định nghĩa bằng số phần tử của http://dientuvietnam.net/cgi-bin/mimetex.cgi?F trừ đi 1 (nghĩa là http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta được định nghĩa như sau:
http://dientuvietnam.net/cgi-bin/mimetex.cgi?x_i của http://dientuvietnam.net/cgi-bin/mimetex.cgi?W với các biến http://dientuvietnam.net/cgi-bin/mimetex.cgi?x_i của vành đa thức http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta là một phức đơn trên http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta một iđêan đơn thức trong http://dientuvietnam.net/cgi-bin/mimetex.cgi?S cho bởi
http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta được định nghĩa như sau:
http://dientuvietnam.net/cgi-bin/mimetex.cgi?I_\Delta).

Định lý (Stanley): http://dientuvietnam.net/cgi-bin/mimetex.cgi?k&#091;\Delta] là tính được nếu như ta có thể đặc tả các phần tử sinh của http://dientuvietnam.net/cgi-bin/mimetex.cgi?I_\Delta.

[CXR]

Tính http://dientuvietnam.net/cgi-bin/mimetex.cgi?\alpha_n(d)

Như đã biết, http://dientuvietnam...mimetex.cgi?S_d chứa http://dientuvietnam...mimetex.cgi?S_d là http://dientuvietnam...mimetex.cgi?S_d, xét tập các biến http://dientuvietnam...mimetex.cgi?z_i tương ứng với đơn thức http://dientuvietnam...mimetex.cgi?m_i).

Xây dựng: Ta xây dựng một phức đơn http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta trên http://dientuvietnam...n/mimetex.cgi?T như sau: tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta nếu và chỉ nếu không gian vector con http://dientuvietnam...mimetex.cgi?V_F sinh bởi các đơn thức http://dientuvietnam.net/cgi-bin/mimetex.cgi?V_d thỏa mãn điều kiện
http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta như vừa xây dựng thực sự là một phức đơn.

Nhận xét: bài toán tìm http://dientuvietnam.net/cgi-bin/mimetex.cgi?\alpha_n(d) tương đương với bài toán tìm số phần tử lớn nhất của các mặt của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta, hay tương đương với việc tính http://dientuvietnam.net/cgi-bin/mimetex.cgi?I_\Delta!!! Việc này được thể hiện qua 2 bài tập dưới đây.

Bài tập: (2) Chứng minh rằng http://dientuvietnam.net/cgi-bin/mimetex.cgi?F là một mặt của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta nếu và chỉ nếu không tồn tại 2 đơn thức http://dientuvietnam.net/cgi-bin/mimetex.cgi?M và http://dientuvietnam.net/cgi-bin/mimetex.cgi?N trong http://dientuvietnam.net/cgi-bin/mimetex.cgi?V_F sao cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?\deg LCMhttp://dientuvietnam.net/cgi-bin/mimetex.cgi?\deg là bậc).

(3) Chứng minh rằng
http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_n(d+1) không!

[RongChoi]

Ý tưởng dùng đơn phức thật là hay. Em thử làm mấy bài tập của anh CXR:
Bài tập: (1) Chứng minh rằng http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta như vừa xây dựng thực sự là một phức đơn.

Xét tập con http://dientuvietnam...n/mimetex.cgi?X
Vì http://dientuvietnam...n/mimetex.cgi?F là mặt của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta nên mọi http://dientuvietnam...tex.cgi?S_1V_F. Do đó mọi http://dientuvietnam...etex.cgi?S_1V_X, tức là : http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta.

Bài tập: (2) Chứng minh rằng http://dientuvietnam...n/mimetex.cgi?F là một mặt của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta nếu và chỉ nếu không tồn tại 2 đơn thức http://dientuvietnam...n/mimetex.cgi?M và http://dientuvietnam.net/cgi-bin/mimetex.cgi?N trong http://dientuvietnam.net/cgi-bin/mimetex.cgi?V_F sao cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?\deg LCMhttp://dientuvietnam.net/cgi-bin/mimetex.cgi?\deg là bậc).

http://dientuvietnam.net/cgi-bin/mimetex.cgi?F là một mặt của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta nếu http://dientuvietnam.net/cgi-bin/mimetex.cgi?S_1V_F. Điều này xảy ra khi và chỉ khi các phần tử http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta
Nếu với mọi M,N để http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta.

Bài tập 3 là hệ quả trực tiếp của bài 2.

[RongChoi]

Bây giờ em xin hỏi anh CXR một câu ạ.
Với bài tập 3 thì như vậy để tính http://dientuvietnam.net/cgi-bin/mimetex.cgi?k&#091;\Delta] ạ? Số phần tử của đã là cực lớn thì liệu một thuật toán như vậy có khả thi ko ạ?
Chẳng hạn, anh có chứng minh được không thể làm tốt hơn không? Có nghĩa chứng minh sự không tồn tại một thuật toán khác với độ phức tạp nhỏ hơn thuật toán của anh?

[CXR]

[quote name='RongChoi' date='Mar 31 2005, 03:30 PM'] Bây giờ em xin hỏi anh CXR một câu ạ.
Với bài tập 3 thì như vậy để tính http://dientuvietnam.net/cgi-bin/mimetex.cgi?k&#091;\Delta] ạ? Số phần tử của http://dientuvietnam.net/cgi-bin/mimetex.cgi?I_\Delta là http://dientuvietnam...etex.cgi?C^2_p. Sau đó còn phải tính chiều của vành http://dientuvietnam.net/cgi-bin/mimetex.cgi?k&#091;\Delta]. Hiện tại thì đây không phải là một bài toán đơn giản. Phần lớn các chương trình của Đại số tính toán (hay Đại số máy tính) khi tính chiều của một vành phân bậc lại đi tính hẳn cả chuỗi Hilbert-Poincaré .. vì thế độ tính toán là khá đồ sộ. Tuy nhiên, hy vọng rằng trong tương lai sẽ có thuật toán tính chiều của vành phân bậc đơn giản hơn. Tại thời điểm này, việc chuyển qua dùng phức đơn chỉ làm giảm sự tính toán hơn so với thuật toán brute force (thử tất cả các khả năng) thôi. Anh không chứng minh được đây là thuật toán đơn giản nhất

Tối nay anh sẽ đọc kỹ hơn lời giải mấy bài tập của Rongchoi, rồi tiếp tục thảo luận thuật toán tính chỉ số phủ.

Ghi chú: ý tưởng dùng phức đơn cũng có thể dùng để giải bài toán tìm tất cả các cách đặt số lớn nhất các con hậu trên một bàn cờ ô vuông sao cho chúng không ăn được nhau. Mọi người nghĩ thử xem.

[RongChoi]

Tại thời điểm này, việc chuyển qua dùng phức đơn chỉ làm giảm sự tính toán hơn so với thuật toán brute force (thử tất cả các khả năng) thôi. Anh không chứng minh được đây là thuật toán đơn giản nhất

Quả thật là ngay cả điều đơn giản này em cũng chưa thấy rõ lắm vì em cũng chưa hình dung ra độ phức tạp việc tính số chiều vành http://dientuvietnam.net/cgi-bin/mimetex.cgi?k&#091;\Delta]. Hơn nữa nếu mình dùng "brute force" thì mình cũng có thể sử dụng vài phương pháp loại trừ hơn là thử hết với mọi tập con của http://dientuvietnam...imetex.cgi?S_d. Ví dụ cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?\alpha_n(d) thì nếu đã có chặn trên chặn dưới thì giảm số đối tượng thử rất nhiều. Ngoài ra khi chọn một phần tử thì tự khắc rất nhiều các phần tử khác sẽ nghiễm nhiên bị loại bỏ,... nên độ phức tạp cũng giảm đáng kể. Một điểm nữa là, tuy trâu bò nhưng "brute force" cho ta không chỉ số chiều mà còn cho ta cách xây dựng tập http://dientuvietnam.../mimetex.cgi?V. Trong khi theo em hiểu thì cách dùng qua phức đơn không cho ta tập http://dientuvietnam.../mimetex.cgi?V?
Em bi bô tẹo chứ việc dùng phức đơn quả là rất đẹp

Ghi chú: ý tưởng dùng phức đơn cũng có thể dùng để giải bài toán tìm tất cả các cách đặt số lớn nhất các con hậu trên một bàn cờ ô vuông sao cho chúng không ăn được nhau. Mọi người nghĩ thử xem.

Em rất là quan tâm đến cái ghi chú này (hìhì, hơn là việc tính chỉ số phủ ) vì bài toán quân hậu rất quen thuộc từ hồi bé con (nhiều khi nó biến thành chò trơi đối kháng giữa hai đứa trẻ).
Ngoài ra thì liệu ý tưởng dùng phức đơn có thể dùng để giải bài toán đối ngẫu "tìm tất cả các cách đặt số nhỏ nhất các con hậu trên một bàn cờ ô vuông sao cho chúng phủ kín được bàn cờ" hay không?

[CXR]

Tính chỉ số phủ

Cũng tương tự như trước, ta xét tập các đơn thức http://dientuvietnam...imetex.cgi?S_d. Nhận xét rằng nếu http://dientuvietnam...n/mimetex.cgi?V là một không gian con sinh bởi các đơn thức của không gian vector http://dientuvietnam...mimetex.cgi?V_d sao cho http://dientuvietnam...n/mimetex.cgi?V phải chứa các đơn thức http://dientuvietnam...mimetex.cgi?W_i là không gian con của http://dientuvietnam...mimetex.cgi?V_d sinh bởi các đơn thức trong http://dientuvietnam...mimetex.cgi?W_i thỏa mãn http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta&#39; trên tập http://dientuvietnam...n/mimetex.cgi?W như sau: http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta&#39; nếu không gian http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta&#39; như đã xây dựng thực sự là một phức đơn.

Xét tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?z_i với http://dientuvietnam.net/cgi-bin/mimetex.cgi?W_i. Xây dựng phức đơn http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta trên http://dientuvietnam.net/cgi-bin/mimetex.cgi?T như sau: http://dientuvietnam.net/cgi-bin/mimetex.cgi?u là một đơn thức trong http://dientuvietnam.net/cgi-bin/mimetex.cgi?u (dễ thấy rằng http://dientuvietnam.net/cgi-bin/mimetex.cgi?V (hiển nhiên các đơn thức này nằm trong http://dientuvietnam.net/cgi-bin/mimetex.cgi?V_d).

Bài toán tính chỉ số phủ http://dientuvietnam.net/cgi-bin/mimetex.cgi?\rho_n(d+1) được giải quyết qua bài tập sau.

Bài tập: (3) Chứng minh rằng http://dientuvietnam.net/cgi-bin/mimetex.cgi?V_d trừ đi http://dientuvietnam.net/cgi-bin/mimetex.cgi?s.

Việc còn lại của vấn đề là đặc tả http://dientuvietnam.net/cgi-bin/mimetex.cgi?I_\Delta.

Bài tập: (4) Chứng minh rằng
http://dientuvietnam.net/cgi-bin/mimetex.cgi?u là và với

[CXR]

Về bài toán đối ngẫu với các quân hậu, anh chưa thử nghĩ qua. RongChoi nghĩ thử xem. Nếu cần thì msg anh email, anh sẽ email bài báo về quân hậu cho.

[RongChoi]

Em có thêm 1 câu hỏi sau liên quan đến chỉ số trải:

Gọi http://dientuvietnam...n/mimetex.cgi?F lớn hơn và chứa ( Một tập là tập trải nếu thỏa mãn điều kiện )

Gọi tương ứng là số chiều nhỏ nhất, lớn nhất của các tập trải tối đại.

Câu hỏi :
Liệu ta có thể uớc lượng được ?

Bình luận:
- Nếu chẳng may thì ta sẽ có ngay một giải thuật tính chỉ số trải chỉ với độ phức tạp do việc tìm một tập trải tối đại chỉ cần độ phức tạp .
- Nếu là nhỏ thì ta cũng sẽ có một giải thuật tính xấp xỉ chỉ số trải với sai số với độ phức tạp .
- Nếu lớn (nhiều khả năng) thì chả được gì