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

 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 i , x j  E G gọi là iđêan cạnh 
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 x12,xx ,..., n  là vành đa thức n 
biến x12,xx ,..., n 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 , 
 maxn | Hii A 0 khi H A 0,
 mm n  
 Trong đó: aAi 
 i
 khi Hm 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 AA R j 0 j A 0. 
 jj  
 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(RII / ) reg( ) 1. 
 Bổ đề 2.4. [2] Cho u là phần tử thuần nhất bậc d của R, khi đó 
 i) reg(Rd / (u)) 1. 
 ii) reg((u)) d . 
 Bổ đề 2.5. [1, Corollary 20.19] Cho dãy khớp: 00 PMN các R-
môđun hữu hạn sinh của các đồng cấu thuần nhất. Khi đó 
 i) reg(MPN ) max reg( ),reg( ). 
 ii) reg(NPM ) max reg( ) 1,reg( ). 
 Từ dãy khớp 0 MMNN  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(MNMN ) max reg( ),reg( ). 
 Định nghĩa 2.7. [3,4,5] Đồ thị đơn hữu hạn G là một cặp VGEGVE( ), ( ) , , 
trong đó V x12,,, x 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 xij,. x i j 
 Đồ thị GVGE' ( '), (G') gọi là đồ thị con cảm sinh của G nếu VGVG '  
và EGEG '  . 
 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 FG 12,G ,...,Gs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 EGEG i . 
 i 1
 iii) Một ghép cặp M của đồ thị G là một đồ thị con của G sao cho 
 EMEG  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 mM 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à 
  GMM min{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) Ge\ 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 i , x j  E G gọi là 
iđêan cạnh của đồ thị G. 
 Kí hiệu reg GI : reg (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 xij x . Xét dãy khớp 
 RRRR
 0  0. 
 xxIGei j  \\ xx i j I G\ e xxIGe i j 
 Ta có xij x I G\ e I G và từ Hệ quả 2.6 ta nhận đƣợc 
 RRRR  
 reg max  reg ,reg . 
 x x I G\\ e x x I G e
 i j  i j 
 Kết hợp với Bổ đề 2.3 và Bổ đề 2.5 ii) ta có 
 R  RRR 
 reg max  reg 1,reg ,reg 
 I(G ) x x I G\ e x x I G \ e
  i j i j 
 121 
 TẠP CHÍ KHOA HỌC TRƢỜNG ĐẠI HỌC HỒNG ĐỨC - SỐ 51.2020 
 Ta có : xxi j  IGe \| xxyyNe i j IG e . 
 RR 
 Suy ra : reg reg 2 . 
 x x I G\ e IG
 ij e 
 R  RRR 
 Do đó, ta có : reg max  reg 2,reg ,reg . 
 I(G ) I G xx I G \ e 
  e ij 
 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à GGG12, ,..., s là 
 s
các đồ thị đơn trên cùng tập đỉnh V sao cho EGEG ii 1 . Khi đó ta có : 
 s
 reg R/ I GG  reg R/ I i . 
 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 Gred . 
 Bổ đề 3.2. Cho đồ thị G. Ta có reg(GG ) reg(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 x12, x  . Khi đó G x12, x  ,{e} . Suy ra I G x12 x . 
Á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 Ge \ 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 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 EG \{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 EGEE 12, 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 và u a,1 a . Khi đó Gu\ có dạng nhƣ sau: 
 Hình 3. 
 Theo giả thiết quy nạp ta có reg(Gu \ ) 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(GG )  1. 
 Chứng minh 
 Đặt : G . Giả sử e12, e ,..., 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 gồm ei và các cạnh của G có 
 
đỉnh là đỉnh thuộc cạnh . Khi đó ta có EGEG i . Áp dụng Bổ đề 2.13, ta có 
 i 1
 
 reg R/ I GG  reg R/ I i . 
 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 GG  reg R/ I i  . 
 i 1
 Áp dụng Bổ đề 2.3, ta nhận đƣợc 
 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