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

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

A tale of models for random graphs

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

 Количество просмотров: Эта страница: 280 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.

 ОТПРАВИТЬ:
 Обратная связь: math-net2022_01 [at] mi-ras ru Пользовательское соглашение Регистрация посетителей портала Логотипы © Математический институт им. В. А. Стеклова РАН, 2022