Luận án tiến sĩ Toán học: Phương pháp phổ của đồ thị trong một số bài toán tổ hợp cộng tính

Luận án gồm có 4 chương được trình bày như sau: Kiến thức chuẩn bị; Một số (n, d, λ) - đồ thị; Đánh giá lực lượng của một số tập hợp trên trường và vành hữu hạn; Tập khoảng cách trên đa tạp chính quy.
Nội dung trích xuất từ tài liệu:
Luận án tiến sĩ Toán học: Phương pháp phổ của đồ thị trong một số bài toán tổ hợp cộng tính VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN TOÁN HỌC ———————————- ĐỖ DUY HIẾUPHƯƠNG PHÁP PHỔ CỦA ĐỒ THỊ TRONG MỘT SỐ BÀI TOÁN TỔ HỢP CỘNG TÍNH LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2019 VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN TOÁN HỌC ———————————- ĐỖ DUY HIẾUPHƯƠNG PHÁP PHỔ CỦA ĐỒ THỊ TRONG MỘT SỐ BÀI TOÁN TỔ HỢP CỘNG TÍNH Chuyên ngành: Cơ sở toán học cho tin học Mã số: 9.46.01.10 LUẬN ÁN TIẾN SĨ TOÁN HỌC Người hướng dẫn: PGS. TS. LÊ ANH VINH Hà Nội - 2019 Tóm tắt Trong Luận án này, chúng tôi sẽ sử dụng phương pháp phổ của đồthị để nghiên cứu về lực lượng của một số tập hợp trên không gian vectơtrên trường và vành hữu hạn như: Hàm nở hai biến, tập khoảng cách vàtập tích, tập tổng - tỉ số, tập khoảng cách trên đa tạp chính quy và tậpthể tích khối. Luận án gồm 04 chương chính: Trong Chương 1, chúng tôi nhắc lại kiến thức cơ bản liên quan đếnphương pháp đại số tuyến tính trong đồ thị: ma trận kề, phổ của đồ thị,(n, d, λ) - đồ thị, Bổ đề trộn nở. Trong Chương 2, chúng tôi nghiên cứu một số (n, d, λ) - đồ thị trênkhông gian vectơ Fnq và Znq như đồ thị tổng - tích, đồ thị tích - tổng, đồthị tổng - bình phương, đồ thị tích, đồ thị Euclid hữu hạn. Trong Chương 3, chúng tôi sử dụng pháp đồ thị để nghiên cứu mộtsố bài toán tổ hợp cộng tính. Cụ thể, chúng tôi sẽ sử dụng các đồ thị xâydựng trong Chương 2 để đánh giá một số tập hợp như tập khoảng cách,tập tích, tập thể tích khối, tập tổng - tỉ số, hàm nở hai biến trên trườngvà vành hữu hạn. Trong Chương 4, chúng tôi sử dụng phương pháp phổ của đồ thị mởrộng để nghiên cứu và đưa ra kết quả tổng quát cho tập khoảng cáchcủa một tập trên đa tạp chính quy. 3 Abstract In this thesis, we use the techniques from the spectral graph theoryto study the cardinality of some sets in vector spaces over finite fieldsand finite rings, such as the images of two-variable expanders, the dis-tance sets, the product sets, the sum - ratio sets, the volume set of boxes,and the distance sets in regular varieties. The thesis consist of four mainchapters. In Chapter 1, we recall some basic knowledge related to linear al-gebraic methods in the graph: the adjacency matrix, the spectrum ofa graph, the definition and properties of (n, d, λ) - graph, and the ex-pander mixing lemma. In Chapter 2, we study some (n, d, λ) - graphs in vector spacesoverfinite fields and finite rings, such as the sum - product graph, the prod-uct - sum graph, the sum - square graph, the product graph, and thefinite Euclidean graph. In Chapter 3, we use the expanding properties of the graphs in Chap-ter 2 to evaluate the cardinalities of distance sets, product sets, volumesets of boxes, sum - ratio sets, and images of two-variable expanders invector spaces over finite fields and finite rings. In Chapter 4, we use the directed version of the expander mixinglemma to study the distance set problem in general regular varieties. 4Lời cam đoan Tôi xin cam đoan Luận án này là tập hợp các nghiên cứu của tôi.Những kết quả trích từ các bài báo viết chung đã nhận được sự chophép sử dụng của các đồng tác giả. Các kết quả nêu trong Luận án làtrung thực và chưa từng được một ai khác công bố. 5Lời cảm ơn Tôi xin chân thành cảm ơn PGS. TS. Lê Anh Vinh, người đã dẫn dắttôi vào con đường nghiên cứu khoa học. Không chỉ là một người hướngdẫn khoa học tận tâm, chia sẻ của thầy với tôi về những buồn, vui đờithường suốt nhiều năm qua là một sự động viên, khích lệ lớn để tôivững vàng hơn trong cuộc sống. Tôi xin chân thành cảm ơn PGS. TSKH. Phan Thị Hà Dương và GS.TSKH. Ngô Đắc Tân đã góp ý để Luận án của tôi hoàn thiện hơn. Nhữnglời chia sẻ, chỉ dạy của thầy cô trong suốt quá trình làm việc, nghiên cứucủa tôi sẽ là hành trang quý báu để tôi tự tin hơn trên những chặngđường sắp tới. Tôi xin cảm ơn TS. Phạm Văn Thắng đã đồng hành cùng tôi trên conđường nghiên cứu trong suốt thời gian qua. Tôi xin cảm ơn ban lãnh đạo Viện Toán học, Phòng cơ sở toán học chotin học và Trung tâm Đào tạo sau đại học đã cung cấp cho tôi một nơilàm việc tốt, một môi trường học thuật lành mạnh để học tập, nghiêncứu trong thời gian tôi làm nghiên cứu sinh ở đây. Cuối cùng, tôi xin tỏ lòng biết ơn vô hạn tới gia đình tôi, những ngườiluôn bên cạnh và thương yêu tôi vô điều kiện. Hà Nội, ngày 27 tháng 02 năm 2019 Đỗ Duy Hiếu 6Bảng các kí hiệu 1. Cho p là một số nguyên tố lẻ, r ≥ 2 là một số tự nhiên và q = pr . | A| là lực lượng của tập hợpA. Zq là vành hữu hạn có q phần tử. Z0q là tập các phần tử không khả nghịch trên Zq . Z× q là tập các phần tử khả nghịch trên Zq . Fq là trường hữu hạn có q phần tử. F∗q là các phần tử khác 0 của trường hữu hạn Fq . 2. Cho f , g là các hàm số theo biến t. g ∈ o( f ) có nghĩa là g(t)/ f (t) → 0 khi t → ∞. f g có nghĩa là g ∈ o ( f ). f &g có nghĩa là tồn tại hằng số c > 0, sao cho f ≥ cg khi t đủ lớn. f = Θ( g) có nghĩa là tồn tại các hằng số c1 , c2 > 0 sao cho c1 f ≤ g ≤ c2 f khi t đủ lớn. 3. Cho G = (V, E) là một đồ thị. ( x, y) là một cạnh có hướng từ x đến y. { x, y} là cạnh vô hướng giữa x và y của đồ thị G. 7Mục lụcLời mở đầu ...