|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Задачи комбинаторного анализа для независимых множеств и раскрасок гиперграфовНИР
Problems of combinatorial analisys for independent sets and colorings of hypergraphs
- Руководитель НИР: Шабанов Д.А.
- Участники НИР: Балобанов А.Е., Семенов А.С., Хузиева А.Э., Ширгазина И.Р.
- Подразделение: Механико-математический факультет
- Срок исполнения: 14 марта 2016 г. - 31 декабря 2017 г.
- Номер договора (контракта, соглашения): МД-5650.2016.1
- Номер ЦИТИС: АААА-А17-117121420016-2
- Тип: Фундаментальная
- Приоритетное направление научных исследований: Дискретная математика, математическая кибернетика и искусственный интеллект
-
Рубрики ГРНТИ:
- 27.43.51 Применение теоретико-вероятностных и статистических методов
- 27.45.00 Комбинаторный анализ. Теория графов
- 27.45.15 Общая теория комбинаторного анализа
- 27.45.17 Теория графов
-
Ключевые слова:
предписанные раскраски, регулярный гиперграф, однородный гиперграф, он-лайн раскраски, случайный гиперграф, хроматическое число, проблема эрдеша-хайнала, независимые множества, экстремальная теория множеств, вероятностные методы
chromatic number, uniform hypergraph, on-line colorings, random hypergraph, independent sets, extremal set theory, erdos-hjanal problem, regular hypergraph, list colorings, probabilistic methods -
Описание:
НИР посвящена исследованию ряда экстремальных и вероятностных задач теории гиперграфов. Основные цели настоящего исследования. 1) Исследование проблемы Эрдеша-Хайнала в случае большого числа цветов, а также ее обобщения для случая он-лайн раскрасок. 2) Исследование асимптотического поведения предписанного хроматического числа полных многодольных гиперграфов. 3) Поиск оценок числа j-независимых множеств в однородных простых регулярных гиперграфах. 4) Установление закона больших чисел для числа независимости случайного гиперграфа, доказательство существования и нахождение предельных констант. 5) Развитие вероятностных методов асимптотического изучения экстремальных задач типа Эрдеша–Хайнала о раскрасках гиперграфов. 6) Развитие метода контейнеров для случая j-независимых множеств.
- Добавил в систему: Шабанов Дмитрий Александрович
Источник финансирования НИР
| грант Президента РФ |
Этапы НИР
| # | Сроки | Название |
| 1 | 14 марта 2016 г.-31 декабря 2016 г. | Задачи комбинаторного анализа для независимых множеств и раскрасок гиперграфов |
| Результаты этапа: Получены новые результаты в классической проблеме Эрдеша-Хайнала о раскрасках гиперграфов и ее обобщениях. Доказаны законы больших чисел для чисел независимости случайного гиперграфа в биномиальной модели. | ||
| 2 | 1 января 2017 г.-30 ноября 2017 г. | Задачи комбинаторного анализа для независимых множеств и раскрасок гиперграфов |
| Результаты этапа: Получены новые оценки в задачах об он-лайн раскрасках. Найдена асимптотика предписанного хроматического числа полных многодольных гиперграфов. Получены оценки числа j-независимых множеств в однородных простых гиперграфах. Доказан закон больших чисел для числа j-независимости случайного гиперграфа. | ||
Прикрепленные к НИР результаты
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".