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

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискрет. матем., 2019, том 31, выпуск 2, страницы 85–114 (Mi dm1504)  

Полноцветные раскраски случайных гиперграфов

Д. А. Кравцовa, Н. Е. Крохмальa, Д. А. Шабановbac

a МГУ имени М.В. Ломоносова
b МФТИ
c НИУ "Высшая школа экономики"

Аннотация: Работа посвящена изучению пороговой вероятности наличия полноцветной раскраски в $r$ цветов у случайного $k$-однородного гиперграфа в биномиальной модели $H(n,k,p)$, т.е. такой раскраски, что каждое ребро гиперграфа содержит вершины всех $r$ цветов. Показано, что данная пороговая вероятность при фиксированных $r<k$ и растущем $n$ отвечает разреженному случаю, т.е. случаю $p=cn/{n\choose k}$ для положительного фиксированного $c$. Найдены ее очень близкие оценки в виде ограничений $c_1(r,k)<c_2(r,k)$ значений параметра $c$, где разность $c_2(r,k)-c_1(r,k)$ экспоненциально быстро стремится к нулю при заданном $r$ и растущем $k$.

Ключевые слова: случайный гиперграф, полноцветные раскраски, пороговые вероятности, метод второго момента.

Финансовая поддержка Номер гранта
Российский научный фонд 16-11-10014
Работа выполнена в рамках исследований по гранту Российского научного фонда (проект № 16-11-10014).


DOI: https://doi.org/10.4213/dm1504

Полный текст: PDF файл (627 kB)
Первая страница: PDF файл
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.174+519.179.1+519.179.4
Статья поступила: 11.02.2018

Образец цитирования: Д. А. Кравцов, Н. Е. Крохмаль, Д. А. Шабанов, “Полноцветные раскраски случайных гиперграфов”, Дискрет. матем., 31:2 (2019), 85–114

Цитирование в формате AMSBIB
\RBibitem{KraKroSha19}
\by Д.~А.~Кравцов, Н.~Е.~Крохмаль, Д.~А.~Шабанов
\paper Полноцветные раскраски случайных гиперграфов
\jour Дискрет. матем.
\yr 2019
\vol 31
\issue 2
\pages 85--114
\mathnet{http://mi.mathnet.ru/dm1504}
\crossref{https://doi.org/10.4213/dm1504}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm1504
  • https://doi.org/10.4213/dm1504
  • http://mi.mathnet.ru/rus/dm/v31/i2/p85

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретная математика
    Просмотров:
    Эта страница:34
    Литература:4
    Первая стр.:3

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019