Научная тема: «ЭКСТРЕМАЛЬНЫЕ И ВЕРОЯТНОСТНЫЕ ЗАДАЧИ ТЕОРИИ ГИПЕРГРАФОВ И АДДИТИВНОЙ КОМБИНАТОРИКИ»
Специальность: 01.01.05
Год: 2013
Основные научные положения, сформулированные автором на основании проведенных исследований:
  1. Разработан многоэтапный вариант метода случайной перекраски Бека - Спенсера в теории раскрасок гиперграфов. С его помощью получены новые нижние оценки в задаче Эрдеша - Хайнала о минимальном числе ребер гиперграфа в классе n-однородных гиперграфов с хроматическим числом больше r, а также обоснована новая нижняя оценка максимальной степени вершины n-однородного гиперграфа с хроматическим числом больше r.
  2. Предложено обобщение техники Радхакришнана - Сринивасана для случайной перекраски вершин разреженных гиперграфов. С ее помощью доказаны новые нижние оценки в задаче Эрдеша - Ловаса о минимальном числе ребер гиперграфа в классе n-однородных простых гиперграфов с хроматическим числом больше r, а также получена новая нижняя оценка максимальной степени ребра в (n,l)-системе с большим хроматическим числом.
  3. Доказаны новые верхние и нижние оценки минимально возможного числа ребер гиперграфа в классе (n,l)-систем с хроматическим числом больше r.
  4. Предложены модификации метода случайной перекраски Бека - Спенсера для случая простых гиперграфов. С их помощью получены новые нижние оценки максимальной степени вершины n-однородного простого гиперграфа с хроматическим числом больше r.
  5. Разработана модификация метода случайной перекраски Бека - Спенсера для случая гиперграфов с обхватом больше трех. С ее помощью обоснована новая нижняя оценка максимальной степени вершины гиперграфа в классе n-однородных гиперграфов с большим хроматическим числом и обхватом больше трех.
  6. Предложен случайный процесс с непрерывным временем для перекраски множества вершин гиперграфа с большим обхватом. С его помощью обоснованы новые нижние оценки максимальной степени вершины и количества ребер гиперграфа в классе n-однородных гиперграфов с большим хроматическим числом и обхватом больше пяти.
  7. Получено новое достаточное условие r-раскрашиваемости неоднородного гиперграфа Н = (V, Е) с обхватом больше трех в терминах ограничения на функцию fr(H) = ^ f1-lel.
  8. С помощью вероятностных методов (метод случайной перекраски, случайные гиперграфы) доказаны новые нижние и верхние оценки в задаче Косточки о минимально возможном количестве ребер гиперграфа в классе n-однородных гиперграфов, не допускающих полноцветных г-раскрасок.
  9. Найдена асимптотика предписанного хроматического числа полного г-дольного графа с равным размером долей т в широкой области значений параметров In г = o(lnm).
  10. На основе разработанных улучшений метода случайной перекраски доказаны новые нижние асимптотические оценки функции Ван дер Вар-дена.
  11. Найдены новые оценки пороговой вероятности r-раскрашиваемости случайного гиперграфа в биномиальной модели.
Список опубликованных работ
01 Д. А. Шабанов, “Экстремальные задачи для раскрасок равномерных гиперграфов”, Известия РАН. Серия математическая, 71:6 (2007), с. 183–222.

02 Д. А. Шабанов, “О хроматическом числе конечных систем подмножеств”, Математические заметки, 85:6 (2009), с. 951-954.

03 Д. А. Шабанов, “Об улучшении нижней оценки в комбинаторной задаче Эрдеша - Хайнала”, Доклады Академии Наук, 426:2 (2009), с. 177-178.

04 А. П. Розовская, Д. А. Шабанов, “О правильных раскрасках гиперграфов в предписанные цвета”, Дискретная математика, 22:3 (2010), с. 94-109.

05 Д. А. Шабанов, “О нижних оценках числа ребер гиперграфа из некоторых классов”, Доклады Академии Наук, 434:1 (2010), с. 33-37.

06 Д. А. Шабанов, “О существовании полноцветных раскрасок для равномерных гиперграфов”, Математический Сборник, 201:4 (2010), с. 137-160.

07 Д. А. Шабанов, “О нижней оценке функции Ван дер Вардена”, Математические заметки, 87:6 (2010), с. 951–953.

08 Д. А. Шабанов, “О нижних оценках в комбинаторной задаче Эрдеша – Ловаса”, Доклады Академии Наук, 431:5 (2010), с. 602–604.

09 D. A. Shabanov, “On a generalization of Rubin’s theorem”, Journal of Graph Theory, 67:3 (2011), с. 226–234.

10 Д. А. Шабанов, “Функция Ван дер Вардена и раскраски гиперграфов”, Известия РАН. Серия математическая, 75:5 (2011), с. 195–224.

11 D. A. Shabanov, “On coloring uniform hypergraphs without 3-cycles”, Moscow Journal of Combinatorics and Number Theory, 1:2 (2011), с. 100–126.

12 А. М. Райгородский, Д. А. Шабанов, “Задача Эрдеша–Хайнала о раскрасках гиперграфов, ее обобщения и смежные проблемы”, Успехи математических наук, 66:5 (2011), с. 109–182.

13 Д. А. Шабанов, “Частичные системы Штейнера и случайные гиперграфы”, Современные проблемы математики и механики, 7:1 (2011), с. 68– 76.

14 D. A. Shabanov, “On r-chromatic hypergraphs”, Discrete Mathematics, 312:2 (2012), с. 441–458.

15 D. A. Shabanov, “Random coloring method in the combinatorial problem of Erd˝os and Lov´asz”, Random Structures and Algorithms, 40:2 (2012), с. 227–253.

16 Д. А. Шабанов, “Об одном обобщении задачи Эрдеша–Ловаса”, Труды МФТИ, 4:1 (2012), с. 131–140.

17 А. Б. Купавский, Д. А. Шабанов, “Раскраски однородных гиперграфов с большим обхватом”, Доклады Академии Наук, 443:4 (2012), с. 422-426.