Giáo sư Vũ Hà Văn – Đại học Yale, và cũng là Ủy viện Hội đồng khoa học của Viện nghiên cứu cao cấp về Toán học Việt Nam, đã được trao giải thưởng Fulkerson năm 2012 về “Các yếu tố trong đồ thị ngẫu nhiên”, các cấu trúc và thuật toán ngẫu nhiên 33 (2008), 1-28.
Dưới đây là trích dẫn của giải Fulkerson 2012:
Sanjeev Arora, Satish Rao, và Umesh Vazirani,
Trong một đồ thị n đỉnh, làm thế nào để tìm một cách cắt-cạnh (edge-cut: một tập các cạnh mà bỏ đi thì đồ thị trở thành không liên thông) có cỡ xấp xỉ nhỏ nhất mà tỷ lệ số đỉnh ở mỗi bên bị chặn? Thuật toán Leighton-Rao năm 1999 bảo đảm việc tìm được một cách cắt sai khác một nhân tử O(log(n)) so với giá trị tối ưu, còn bài báo nhận giải thưởng đã cải tiến thành O(sqrt(log(n))).
Các kỹ thuật chứng minh dựa trên một loạt các phát triển cốt yếu trong các thuật toán xấp xỉ, trộn hai cách tiếp cận khác nhau đến bài toán phân hoạch đồ thị: phương pháp phổ dựa trên các giá trị riêng, và cách tiếp cận dựa trên quy hoạch tuyến tính và các phép nhúng khoảng cách vào các không gian chiều cao. Ý tưởng chủ chốt trong cả hai phương pháp là để trải rộng các đỉnh trong một không gian nào đó mà không kéo dài các cạnh quá nhiều, phân hoạch không gian này dẫn đến một cách phân hoạch đồ thị.
Sự đảm bảo về mặt hiệu năng cho các thuật toán đơn giản và hiệu quả của họ được chứng minh bằng thực tế hình học sau đây về cấu hình của điểm được tạo ra bởi các chương trình semidefinite (SDPs): phải tồn tại hai nhóm tách biệt rõ ràng, mỗi nhóm chứa một phân bố không đổi của các điểm. Thực tế hình học này được đưa ra từ một phân tích phức tạp mang tính toàn cầu làm cho việc sử dụng thiết yếu tập trung biện pháp – một khởi đầu quan trọng từ những phân tích cục bộ của SDPs trong các thuật toán xấp xỉ từ trước đến nay.
Anders Johansson, Jeff Kahn, và Van Vu,
“Các yếu tố trong đồ thị ngẫu nhiên”, các cấu trúc và thuật toán ngẫu nhiên 33 (2008), 1-28.
Xét một siêu đồ thị k-đều ngẫu nhiên H có n đỉnh và xác suất cạnh p. Giả sử k chia hết n. Giá trị nào của xác suất p để bảo đảm rằng với xác suất lớn, siêu đồ thị H chứa một cách phân chia hoàn hảo tập các cạnh rời nhau và chứa tất cả các đỉnh ?
Erdos và Renyi đã giải bài toán này vào năm 1966 và cho ra đáp số k=2, nhưng bài toán này nói chung vẫn còn là một vấn đề mở, được gọi là “bài toán Shamir”. Đáp số, như đã được dự đoán, chỉ là khi số lượng các siêu cạnh (hyperedges) dự kiến là O (n log n) (cho k cố định và n lớn), nhưng đến tận bây giờ vẫn không có đáp án nào gần đúng được chứng minh. Ngoài ra, kết quả của họ xác định ngưỡng để thừa nhận một cách phân vùng thành đỉnh-phân chia các bản sao của bất kỳ siêu đồ thị “l, balanced” nào.
Phương pháp chứng minh này rất mới là. Các tác giả xem xét một quá trình siêu đồ thị mà các cạnh được gỡ bỏ từng cái một từ siêu đồ thị hoàn chỉnh, và họ ước tính hiệu quả của việc loại bỏ mỗi cạnh đến số lượng các yếu tố của siêu đồ thị, bằng cách sử dụng sự bất bình đẳng tập trung. Các phương pháp tập trung căn bản thất bại trong trường hợp này, và giấy thay vì phát triển các kỹ thuật mới với một sự phụ thuộc nặng nề vào sự bất bình đẳng bắt nguồn từ dữ liệu ngẫu nhiên.
Lászlo Lovász và Balázs Szegedy,
“Giới hạn của chuỗi đồ thị dày đặc”, Tạp chí tổ hợp Lý thuyết Seri B 96 (2006), 933-957.
Nghiên cứu này cho thấy rằng đối với khoảng cách tự nhiên, các chuỗi đồ thị có một giới hạn trong không gian của các hàm đo được đối xứng từ hình vuông đơn vị đến đường thẳng đơn vị. Điều này dẫn đến một chương trình tự nhiên nghiên cứu các tính chất cực trị và xác suất của đồ thị và chuỗi đồ thị. Ví dụ, tính chất compact của không gian các hàm (modulo nhóm các song anh bảo toàn độ đo) dẫn đến bổ đề chính quy của Szemerádi, một kết quả mang tính cơ bản.
Bài báo phát triển các phương pháp mới nguyên gốc liên kết tổ hợp cực trị với lý thuyết độ đo và mang lại các công cụ quan trọng của tô pô và lý thuyết độ đo cho việc nghiên cứu các network cỡ lớn. Công trình đó dẫn đến một lĩnh vực nghiên cứu mới trong xác suất và tổ hợp cực trị, mang lại các kết quả như bổ đề chính quy cho siêu đồ thị (được tìm kiếm từ lâu) và các công cụ hé mở các quan hệ giữa số các bản sao của các đồ thị con khác nhau trong một đồ thị. Các kết quả trong bài báo cũng mở màn các hướng phát triển mới trong vật lý toán và trong tổ hợp đại số (trong lý thuyết biểu diễn, lý thuyết bất biến và hình học đại số).
Biên tập: Ngoc Tuan – The Cuong