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

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





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








Большой семинар кафедры теории вероятностей МГУ
8 сентября 2010 г. 16:45, г. Москва, ГЗ МГУ, ауд. 16-24
 


Случайные гиперграфы и задачи экстремальной комбинаторики

Д. А. Шабанов

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

Аннотация: Теория случайных графов и гиперграфов – это одна из наиболее активно развивающихся областей современной вероятностной комбинаторики. В докладе мы остановимся на классических моделях случайных графов, восходящих к работам П. Эрдеша и А. Реньи, а также на их естественных обобщениях – моделях случайных гиперграфов. Напомним одну из таких моделей.
Пусть $K_N^{(n)}$ – полный $n$-однородный гиперграф на $N$ вершинах (т.е. совокупность всех $n$-элементных подмножеств множества из $N$ элементов), тогда случайный гиперграф $H(N,n,p)$ есть подгиперграф $K_N^{(n)}$, полученный путем случайного включения ребер $K_N^{(n)}$: каждое ребро независимо от других включается в $H(N,n,p)$ с вероятностью $p$ и не включается с вероятностью $1-p$. Одним из наиболее важных открытий, сделанных Эрдешем и Реньи, является феномен пороговых вероятностей для многих теоретико-графовых свойств случайного графа. Эффект состоит в том, что с ростом параметра $p$ предельная вероятность обладания случайным графом (гиперграфом) некоторым свойством очень быстро «перескакивает» с 0 до 1 при переходе через эту пороговую вероятность.
В докладе будет рассказано об оценках пороговой вероятности для свойства случайного гиперграфа $H(N,n,p)$ быть $r$-раскрашиваемым. Данные оценки опираются на результаты экстремальной комбинаторики о достаточных условиях $r$-раскрашиваемости $n$-однородных гиперграфов, доказательства которых, в свою очередь, также основаны на применении вероятностной техники.

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