|
Фундаментальная и прикладная математика, 2013, том 18, выпуск 3, страницы 77–115
(Mi fpm1518)
|
|
|
|
Эта публикация цитируется в 7 научных статьях (всего в 7 статьях)
Раскраски частичных систем Штейнера и их приложения
А. Б. Купавскийa, Д. А. Шабановb a Московский физико-технический институт (государственный университет)
b Московский государственный университет им. М. В. Ломоносова
Аннотация:
В работе рассматриваются экстремальные задачи о раскрасках частичных систем Штейнера. Получено новое достаточное условие $r$-раскрашиваемости для некоторого класса подобных систем в терминах ограничения на максимальную степень вершины. Кроме того, в качестве следствия получена новая нижняя оценка для пороговой вероятности $r$-раскрашиваемости случайного гиперграфа в биномиальной модели.
Ключевые слова:
раскраски гиперграфов, разреженные гиперграфы, метод случайной перекраски, частичные системы Штейнера, случайный гиперграф.
Образец цитирования:
А. Б. Купавский, Д. А. Шабанов, “Раскраски частичных систем Штейнера и их приложения”, Фундамент. и прикл. матем., 18:3 (2013), 77–115; J. Math. Sci., 206:5 (2015), 511–538
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/fpm1518 https://www.mathnet.ru/rus/fpm/v18/i3/p77
|
Статистика просмотров: |
Страница аннотации: | 402 | PDF полного текста: | 178 | Список литературы: | 54 | Первая страница: | 2 |
|