RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Межкафедральный семинар МФТИ по дискретной математике
29 апреля 2014 г. 18:30–20:00, г. Долгопрудный, г. Долгопрудный, МФТИ, Корпус Прикладной математики, ауд. 115
 


A tale of models for random graphs

Джеонг Хан Ким

Количество просмотров:
Эта страница:249
Youtube Video:





Аннотация: Since Erdős and Rényi introduced random graphs in 1959, two closely related models for random graphs have been extensively studied. In the G(n,m) model, a graph is chosen uniformly at random from the collection of all graphs that have n vertices and m edges. In the G(n,p) model, a graph is constructed by connecting each pair of two vertices randomly. Each edge is included in the graph G(n,p) with probability p independently of all other edges. Researchers have studied when the random graph G(n,m) (or G(n,p), resp.) satisfies certain properties in terms of n and m (or n and p, resp.). If G(n,m) (or G(n,p), resp.) satisfies a property with probability close to 1, then one may say that a `typical graph’ with m edges (or expected edge density p, resp.) on n vertices has the property. Random graphs and their variants are also widely used to prove the existence of graphs with certain properties. In this talk, a well-known problem for each of these categories will be discussed. First, a new approach will be introduced for the problem of the emergence of a giant component of G(n,p), which was first considered by Erdős–Rényi in 1960. Second, a variant of the graph process G(n,1),G(n,2),…,G(n,m),… will be considered to find a tight lower bound for Ramsey number R(3,t) up to a constant factor. No prior knowledge of graph theory is needed in this talk.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020