Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Ближайшие семинары

Математический кружок
29 апреля 2014 г. 18:30, г. Долгопрудный, 115 КПМ

A tale of models for random graphs

J. Han Kim

Korea Institute for Advanced Study
Adobe PDF 850.0 Kb
Adobe PDF 117.2 Kb
Adobe PDF 15.6 Kb

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

Аннотация: Since Erdos–Renyi 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 Erdos–Renyi 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.

Материалы: a_mipt.pdf (850.0 Kb), pcmv7.pdf (117.2 Kb), triangle_free.pdf (15.6 Kb)

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