Nội dung

TẠP CHÍ KHOA HỌC TRƢỜNG ĐẠI HỌC HỒNG ĐỨC - SỐ 51.2020 CHỈ SỐ CHÍNH QUY CASTELNOUVO-MUMFORD CỦA IĐÊAN CẠNH VÀ KÍCH THƢỚC NHỎ NHẤT CỦA GHÉP CẶP CỰC ĐẠI CỦA ĐỒ THỊ ĐƠN Lê Quang Huy1 TÓM TẮT Bài báo trình bày chứng minh chi tiết về chặn trên của chỉ số chính quy Castelnouvo-Mumford của iđêan cạnh với đồ thị đơn G cho trước theo kích thước nhỏ nhất ứng với ghép cặp cực đại của G. Từ khóa: Chỉ số chính quy, iđêan cạnh, ghép cặp, đồ thị đơn. 1. ĐẶT VẤN ĐỀ  Cho G là một đồ thị đơn và iđêan I (G)  xi x j x , x   E G  gọi là iđêan cạnh i j của G. Nhƣ vậy với mỗi đồ thị đơn G ta luôn xác định đƣợc một iđêan đơn thức tƣơng ứng. Việc đánh giá mối liên hệ và sự tƣơng tác giữa G và I(G) nhƣ thế nào là vấn đề đƣợc nhiều ngƣời quan tâm. Có hai hƣớng thông dụng tiếp cận về vấn đề này là cấu trúc của đồ thị G ảnh hƣởng nhƣ thế nào đến tính chất của iđêan I(G) và các bất biến của đồ thị G có tác động nhƣ thế nào đến các bất biến của iđêan I(G). Trong bài báo này, tác giả tiếp cận theo hƣớng thứ hai về chặn trên bất biến chỉ số chính quy của iđêan I(G) ứng với đồ thị G là kích thƣớc nhỏ nhất của ghép cặp cực đại trong đồ thị G. Bài báo và trình bày chi tiết các chứng minh cho chặn trên chỉ số chính quy của I(G) theo kích thƣớc nhỏ nhất của ghép cặp cực đại trong đồ thị G. Các kết quả này đƣợc trình bày sơ lƣợc trong [4,5] dƣới dạng nhận xét và gợi ý. Ngoài phần giới thiệu, bài báo chia thành hai mục. Mục 2 giới thiệu một số kiến thức cơ bản về đồ thị, iđêan cạnh, chỉ số chính quy. Mục 3 đƣa ra các kết quả chính về chặn trên chỉ số chính quy của I(G) theo kích thƣớc nhỏ nhất của ghép cặp cực đại của đồ thị G, trong các trƣờng hợp G là đồ thị hình sao (Định lý 3.5), G là đồ thị chứa một cạnh là ghép cặp cực đại kích thƣớc 1 của G (Định lý 3.8) và cuối cùng là đồ thị G tổng quát (Định lý 3.9). 2. IĐÊAN C NH CỦA ĐỒ THỊ Trong mục này, chúng ta luôn giả thiết R  K  x1 , x2 ,..., xn  là vành đa thức n biến x1 , x2 ,..., xn trên trƣờng K vô hạn, m là iđêan thuần nhất cực đại của R và A là môđun phân bậc hữu hạn sinh trên R . Các kiến thức cơ bản đƣợc trình bày trong [1,2] và các kiến thúc cơ bản về đồ thị đƣợc trình bày trong [3,4,5]. 1 Khoa Khoa học Tự nhiên, Trường Đại học Hồng Đức 119 TẠP CHÍ KHOA HỌC TRƢỜNG ĐẠI HỌC HỒNG ĐỨC - SỐ 51.2020 Định nghĩa 2.1 [1, Section 1] Chỉ số chính quy Casteluovo-Mumford (chính quy) của A là số reg( A) : max ai  A  i | i  0, i i  max n | H m  An  0 khi H m  A  0, Trong đó: ai  A   khi H mi  A  0.   Với cách tiếp cận sử dụng dãy tự do tối tiểu, chỉ số chính quy đƣợc xây dựng nhƣ sau: Định nghĩa 2.2. [1, Proposition 1.1 và Theorem 1.2] Cho dãy tự do tối tiểu của E đƣợc xác định nhƣ sau: 0  R   j   pj  A j   R   j   0 j  A  A  0. j Khi đó chỉ số chính quy đƣợc xác định là: reg(A) : max  j  i | ij  A  0 . Từ định nghĩa thứ hai của chỉ số chính quy ta nhận đƣợc các kết quả sau: Bổ đề 2.3. [2] Cho I là iđêan thuần nhất của R, khi đó ta có: reg( R / I )  reg( I ) 1. Bổ đề 2.4. [2] Cho u là phần tử thuần nhất bậc d của R, khi đó i) reg( R / (u))  d 1. ii) reg((u))  d . Bổ đề 2.5. [1, Corollary 20.19] Cho dãy khớp: 0  P  M  N  0 các Rmôđun hữu hạn sinh của các đồng cấu thuần nhất. Khi đó i) reg(M )  max reg( P), reg( N ) . ii) reg( N )  max reg( P) 1, reg( M ) . Từ dãy khớp 0  M  M  N  N  0, kết hợp với kết quả i) trong bổ đề trên ta nhận đƣơc kết quả sau: Hệ quả 2.6. Cho M, N là các R-môđun phân bậc hữu hạn sinh. Khi đó, ta có reg(M  N )  max reg(M ), reg( N ) . Định nghĩa 2.7. [3,4,5] Đồ thị đơn hữu hạn G là một cặp V (G), E(G)   V , E  , trong đó V   x1 , x2 , , xn  gọi là tập đỉnh và E là tập cạnh bao gồm các tập con có 2 phần tử của V có dạng  xi , x j   i  j  . Đồ thị G '  V (G '), E (G')  gọi là đồ thị con cảm sinh của G nếu V  G '  V  G  và E  G '  E  G  . Trong bài báo này, ta luôn giả sử đồ thị G là đồ thị đơn. Định nghĩa 2.8. [3,4,5] Cho đồ thị G = (V, E). i) xi gọi là một đỉnh cô lập của G nếu nó không thuộc bất kì cạnh nào của G. 120 TẠP CHÍ KHOA HỌC TRƢỜNG ĐẠI HỌC HỒNG ĐỨC - SỐ 51.2020 ii) Cho F  G1 , G 2 ,..., G s  là một họ các đồ thị con của G. F gọi là một phủ s cạnh của G nếu E  Gi   E  G . i 1 iii) Một ghép cặp M của đồ thị G là một đồ thị con của G sao cho E  M   E  G  và mọi cặp cạnh của M đôi một rời nhau. Kích thƣớc của một ghép cặp M đƣợc kí hiệu bởi m  M  là số cạnh của M. Một ghép cặp M gọi là cực đại nếu không thể bổ sung thêm cạnh khác của đồ thị G để tạo thành một ghép cạnh mới của G. Kích thƣớc nhỏ nhất của ghép cặp cực đại của đồ thị G đƣợc kí hiệu là   G   min{m  M  | M là ghép cặp cực đại của đồ thị G} . Định nghĩa 2.9. [4,5] Cho đồ thị G = (V, E). Gọi e là một cạnh của G. i) N  e   x V | y  e sao cho {x, y}  E G  gọi là lân cận mở (gọi tắt là lân cận) của e. ii) N e  N  e  {e} gọi là lân cận đóng của e. Định nghĩa 2.10. [4,5] Cho đồ thị G = (V, E). Gọi e là một cạnh của G. i) G \ e là đồ thị nhận đƣợc từ G bằng cách xoá đi cạnh e, nghĩa là G \ e  V  G  , E  G \ e   E  G  \ e . ii) Ge là đồ thị con của G có tập đỉnh là V  Ge   G \ N e.  Định nghĩa 2.11. [3,4,5] Cho đồ thị G, I (G)  xi x j x , x   E G  gọi là i j iđêan cạnh của đồ thị G. Kí hiệu reg  G  : reg  I (G)  . Bồ đề 2.12. [4, Theorem 3.5] Cho đồ thị G và e là một cạnh của G. Khi đó ta có reg(G)  max 2, reg  G \ e  , reg  Ge   1 . Chứng minh Giả sử e   xi x j  . Xét dãy khớp 0 R R R R    0.   xi x j   I G \ e   xi x j  I G \ e   xi x j   I G \ e  Ta có  xi x j   I  G \ e   I  G  và từ Hệ quả 2.6 ta nhận đƣợc   R  R  R    R      reg   max reg , reg    .     xi x j  I G \ e   I G \ e      xi x j       Kết hợp với Bổ đề 2.3 và Bổ đề 2.5 ii) ta có     R   R    R  R     reg   1, reg , reg      max reg    xi x j    I(G)   I  G \ e       xi x j   I  G \ e     121 TẠP CHÍ KHOA HỌC TRƢỜNG ĐẠI HỌC HỒNG ĐỨC - SỐ 51.2020 Ta có :  xi x j   I  G \ e   xi x j  y | y  N  e   I  Ge   .    R  R   reg  Suy ra : reg   I  G    2 .   xi x j   I  G \ e   e       R   R   R    R    , reg  Do đó, ta có : reg    2, reg    .   max reg     xi x j   I  Ge    I(G)   I G \ e         Vậy : reg(G)  max 2, reg  G \ e  , reg  Ge   1 . Bổ đề 2.13. [4, Corollary 3.7] hoặc [6, Theorem 2]) Giả sử G và G1 , G2 ,..., Gs là các đồ thị đơn trên cùng tập đỉnh V sao cho E  G   s i 1 E  Gi  . Khi đó ta có : s reg  R/ I  G     reg R/ I Gi   . i 1 3. CHỈ SỐ CHÍNH QUY CỦA IĐÊAN C NH Bài toán chặn trên chỉ số chính quy theo kích thƣớc nhỏ nhất của ghép cặp cực đại trong G lần lƣợt đƣợc chứng minh cho các lớp đồ thị hình sao, đồ thị chứa ít nhất một ghép cặp cực đại có kích thƣớc 1 và từ đó ta có thể khái quát hoá chứng minh cho trƣờng hợp đồ thị G tổng quát (Xem [4] và [5]). Trƣớc hết ta cần đến khái niệm đồ thị rút gọn. Định nghĩa 3.1. Cho G là đồ thị. Đồ thị nhận đƣợc từ G bằng cách bỏ đi tập điểm cô lập của G gọi là đồ thị rút gọn của G. Kí hiệu G red . Bổ đề 3.2. Cho đồ thị G. Ta có reg(G)  reg(G red ) . Do đó, trong mục này không mất tính tổng quát, ta luôn giả sử đồ thị G không có điểm cô lập Bồ đề 3.3. Cho đồ thị G có duy nhất một cạnh. Khi đó reg(G)  2. Chứng minh Giả sử G có cạnh e   x1 , x2  . Khi đó G  x1 , x2  ,{e} . Suy ra I  G    x1 x2  . Áp dụng: Bổ đề 2.4 ii), ta nhận đƣợc reg(G)  2. Định nghĩa 3.4. Đồ thị G có tất cả các cạnh chung một đỉnh gọi là đồ thị hình sao. Hình 1. Đồ thị hình sao 6 cạnh 122 TẠP CHÍ KHOA HỌC TRƢỜNG ĐẠI HỌC HỒNG ĐỨC - SỐ 51.2020 Định lý 3.5. Cho G là đồ thị hình sao. Khi đó reg(G)  2. Chứng minh Ta chứng minh quy nạp theo số cạnh của G. Giả sử G có m cạnh. Với m = 1, theo Bổ đề 3.3, ta có reg(G)  2. Giả sử đúng đến m-1 cạnh, ta cần chứng minh đúng đến m cạnh. Theo Bổ đề 2.12, reg(G)  max 2, reg  G \ e  , reg  Ge   1 . Từ giả thiết quy nạp, ta nhận đƣợc reg  G \ e   2 . Mặt khác, vì Ge là đồ thị rỗng, nên reg  Ge   0 . Vậy reg( G)  max 2,2,1  2 . Đồ thị hình sao là đồ thị có các cạnh đều là các ghép cặp cực đại có kích thƣớc 1. Trong phần tiếp theo, ta quan tâm đến đồ thị tổng quát hơn so với đồ thị hình sao, đồ thị chứa ít nhất một cạnh là ghép cặp cực đại có kích thƣớc 1. Mệnh đề 3.6. Giả sử cạnh e  a, b là một ghép cặp cực đại có kích thƣớc 1 của đồ thị G. Khi đó, các cạnh của đồ thị G luôn chứa đỉnh a hoặc đỉnh b, nghĩa là G có dạng Hình 2. Chứng minh Giả sử G có cạnh e’ không chứa đỉnh a hoặc đỉnh b, khi đó {e, e’} lập thành một ghép cặp mới có kích thƣớc 2, mâu thuẫn với {e} là ghép cặp cực đại của G. Định lý 3.7. Cho đồ thị G. Giả sử cạnh e  a, b là một ghép cặp cực đại có độ lớn 1 của đồ thị G. Khi đó reg(G)  2. 123 TẠP CHÍ KHOA HỌC TRƢỜNG ĐẠI HỌC HỒNG ĐỨC - SỐ 51.2020 Chứng minh Ta quy nạp theo số cạnh của tập cạnh E  G  \{e} . Giả sử G có một cạnh, khi đó theo Bổ đề 3.3 ta có reg(G)  2. Giả sử G có nhiều hơn một cạnh khi đó đồ thị có dạng nhƣ Hình 2. Ta chia tập cạnh của G thành hai phần E  G   E1  E2 , trong đó, E1 là tập cạnh mà mỗi cạnh chứa đỉnh a và E2 là tập cạnh mà mỗi cạnh chứa đỉnh b. Gọi u là một cạnh của G. Không mất tính tổng quát, ta có thể giả sử u thuộc tập cạnh E1 và u  a, a1 . Khi đó G \ u có dạng nhƣ sau: Hình 3. Theo giả thiết quy nạp ta có reg(G \ u)  2. Đồ thị Gu là đồ thị chỉ gồm các đỉnh độc lập nhƣ sau Hình 4. Áp dụng Bổ đề 3.2 ta có reg(Ge )  0 . Theo Bổ đề 2.12, ta có reg(G)  max 2, reg  G \ u  , reg  Gu   1  2. 124 TẠP CHÍ KHOA HỌC TRƢỜNG ĐẠI HỌC HỒNG ĐỨC - SỐ 51.2020 Vậy định lý đƣợc chứng minh xong. Vận dụng các kết quả trên, ta chứng minh đƣợc kết quả chính của bài báo nhƣ sau: Định lý 3.8. Giả sử G là một đồ thị đơn. Khi đó ta có reg(G)    G   1. Chứng minh Đặt  :   G  . Giả sử e1 , e2 ,..., e  là một ghép cặp cực đại của G. Gọi Gi là đồ thị con cảm sinh của G, trong đó các cạnh của Gi gồm ei và các cạnh của G có  đỉnh là đỉnh thuộc cạnh ei . Khi đó ta có E  Gi   E  G . Áp dụng Bổ đề 2.13, ta có i 1  reg  R/ I  G     reg  R/ I  Gi  . i 1 Theo Định lý 3.7, ta có reg(Gi )  2 , kết hợp với Bổ đề 2.3 suy ra reg  R/ I  Gi    1 . Do vậy  reg  R/ I  G     reg  R/ I  Gi     . i 1 Áp dụng Bổ đề 2.3, ta nhận đƣợc reg(G)    G   1. 4. KẾT LUẬN Bài toán chặn trên chỉ số chính quy theo kích thƣớc nhỏ nhất của ghép cặp cực đại trong G lần lƣợt đƣợc chứng minh cho các lớp đồ thị hình sao, đồ thị chứa ít nhất một ghép cặp cực đại có kích thƣớc 1 và từ đó ta có thể khái quát hoá chứng minh cho trƣờng hợp đồ thị G tổng quát. TÀI LIỆU THAM KHẢO [1] D. Eisenbud (1995), Commutative Algebra with a View toward Algebraic Geometry, Springer-Verlag. [2] D. Eisenbud), S. Goto (1984), Linear free resolutions and minimal multi-plicity, J. Algebra, 88, 89-133. [3] Herzog, Jürgen, Hibi, Takayuki (2011), Monomial ideals, Springer Press, New York. [4] H.H. Tai (2014), Connections Between Algebra, Combinatorics, and Geometry, Springer Press, New York , 76, 251-276. [5] R. Woodroofe (2014), Matchings, Coverings, and Castelnouvo-Mumford regularity, Joural of Commutative Algera, 6 (2), 287-303. 125 TẠP CHÍ KHOA HỌC TRƢỜNG ĐẠI HỌC HỒNG ĐỨC - SỐ 51.2020 CASTELNOUVEO-MUMFORD REGULARITY OF EDGE IDEAL AND THE MINIMUM SIZE OF A MAXIMAL MATCHING OF SIMPLE GRAPHS Le Quang Huy ABSTRACT This paper gives a detail proof of the upper bound of regularity of edge ideal of simple graphs in term of the minimum size of a maximal matching of simple graphs. Key words: Regularity, edge ideal, matching, simple graph. * Ngày nộp bài: 7/10/2020; Ngày gửi phản biện: 21/10/2020; Ngày duyệt đăng: 28/10/2020 * Bài báo này là kết quả nghiên cứu từ đề tài cấp cơ sở mã số ĐT-2019- của Trường Đại học Hồng Đức. 126