О раскрасках случайных гиперграфов с большой однородностью

ФИО студента: Давлетшин Фарид Наилевич

Руководитель: Шабанов Дмитрий Александрович

Программа: Математика (Бакалавриат)

Год защиты: 2021

В 1964 П. Эрдеш доказал, что k-граф (i.e. k-равномерный гиперграф) с \dfrac{k^2}{2} вершинами и m(k)=(1+o(1))\dfrac{e \ln2}{4}k^22^k случайно выбранными ребрами размера k асимптотически почти наверное не имеет правильной двухцветной раскраски [1]. Д. Шабанов, Я. Козик и Л. Дурай (2020) показали, что m(k) - это \textit{пороговая функция} [2]. Это значит, что для любого \epsilon > 0 любой k-граф с $(1-\epsilon)m(k) случайно и равномерно выбранными ребрами асимптотически почти наверное имеет правильную двухцветную раскраску. Данная работа есть адаптация метода второго момента, который был использован в вышеупомянутом исследовании. Мы доказываем утверждение аналогичное теореме из [2], но уже для трех цветов. Раскраска у нас сбалансированная.

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

ВКР являются объектами авторских прав, на их использование распространяются ограничения, предусмотренные законодательством Российской Федерации об интеллектуальной собственности.

В случае использования ВКР, в том числе путем цитирования, указание имени автора и источника заимствования обязательно.

Реестр дипломов НИУ ВШЭ