HOẠT ĐỘNG TRONG TUẦN

Những cấu trúc lớn xuất hiện trong đồ thị ngẫu nhiên
Báo cáo viên: Nguyễn Việt Anh

Thời gian: 9h30, Thứ 5, ngày 1/11/2018.
Địa điểm: Phòng 611- 612, nhà A6, Viện Toán học, 18 Hoàng Quốc Việt.
Tóm tắt: Cho một đồ thị ngẫu nhiên cỡ lớn, ví dụ để cho cụ thể, lấy mô hình G(n,p) của Erdos-Reyni. Một số câu hỏi quan trọng ta có thể hỏi là như sau. Tính xác suất ngưỡng để một cấu trúc lớn (lớn theo nghĩa số đỉnh của nó xấp xỉ n chẳng hạn) xuất hiện trong G(n,p). Sẽ như nào nếu thay vì một, ta quan tâm đến nhiều cấu trúc lớn khác nhau cùng xuất hiện? Tính ổn định của sự tồn tại các cấu trúc đó là như nào, theo nghĩa nếu giả sử ta xóa bớt cạnh của G(n,p) đi với quy tắc nào đó, thì phải xóa bao nhiêu cạnh thì các cấu trúc đó mới đồng loạt biến mất?

Những tiến bộ gần đây đạt được là nhờ vào một vài công cụ kĩ thuật mới mà em hi vọng sẽ kịp hiểu được phần nào khi trình bày với mọi người.

Tham khảo:

  1. Bottcher J. Large-scale structures in random graphs
  2. Balogh et al. The method of hypergraph containers
  3. Rodl, Schacht. Extremal results in random graphs (bài này mô tả những phiên bản thưa (sparse) của Regularity Lemma nổi tiếng của Szemeredi).

Trở lại