name: Раскраски метрических пространств с запрещенными одноцветными конфигурациями
keyword_list: проблема Борсука дистанционные графы хроматическое число пространства
abstract: В диссертации получены новые результаты, связанные с двумя классическими задачами комбинаторной геометрии — задачей Хадвигера — Нельсона о хроматическом числе пространства и задачей Борсука о разбиении множества на части меньшего диаметра. 
  В связи с задачей Хадвигера — Нельсона рассматривается хроматическое число n-мерного пространства, снабженного l_q-нормой, с несколькими запрещенными расстояниями. Для любого C < 1/(1+q) и каждого n и k роизводится построение полного дистанционного графа в n-мерном пространстве с k запрещенными расстояниями, хроматическое число которого оценивается снизу как Bk в степени Cn, где B — константа, не зависящая от n и k. Оценка хроматического числа дистанционного граафа производится с помощью линейно-алгебраического метода в комбинаторике. Полученный результат позволяет получить оценку асимптотического роста хроматического числа таких пространств, которая хорошо согласуется с найденными ранее численными оценками, полученными в евклидовых пространствах малых размерностей. Также с помощью вероятностного метода в комбинаторике доказано существование дистанционных графов, не имеющих клик фиксированного размера, чье хроматическое число тоже можно оценить снизу как (Bk)^(Cn).
  В связи с задачей Борсука производится построение конструкций на основе (−1, 1)-векторов, а также (−1, 0, 1)-векторов, дающих новые контрпримеры к гипотезе Борсука с нелинейным ростом числа Борсука на сферах произвольного радиуса, превышающего 1/2. Для оценки хроматического числа графов диаметров применяется линейно-алгебраический метод в комбинаторике.
chairman_dissertation_council.name: Дмитрий
chairman_dissertation_council.surname: Шабанов
chairman_dissertation_council.patronymic: Александрович
chairman_dissertation_council.position: ведущий научный сотрудник
chairman_dissertation_council.degree: Доктор физико-математических наук
chairman_dissertation_council.rank: Доцент
chairman_dissertation_council.wos_research_id: N-5607-2019
chairman_dissertation_council.scopus_author_id: 6602787390
chairman_dissertation_council.rinc_id: 157097
chairman_dissertation_council.orcid: 0000-0002-1851-569X
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Виталий
organization_supervisor.surname: Баган
organization_supervisor.patronymic: Анатольевич
organization_supervisor.position: Проректор по научной работе
organization_supervisor.degree: Доктор физико-математических наук
organization_supervisor.territory: РОССИЯ
rubrics.code: 27.45.17
rubrics.name: Теория графов
oecds.code: 01.01.PQ
oecds.name: MATHEMATICS
oecds.code: 01.01.PN
oecds.name: MATHEMATICS, APPLIED
speciality_codes.name: Дискретная математика и математическая кибернетика
speciality_codes.code: 01.01.09
supervisors.fio: Райгородский А.М.
supervisors.scientific_degree: Доктор физико-математических наук
supervisors.speciality_code: Дискретная математика и математическая кибернетика
supervisors.responsible_type: Научный руководитель
opponents.fio: -
opponents.responsible_type: Оппонент
protection_organization.short_name: МФТИ
protection_organization.name: Федеральное государственное автономное образовательное учреждение высшего образования "Московский физико-технический институт (национальный исследовательский  университет)"
protection_organization.ogrn: 1027739386135
protection_organization.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные автономные учреждения
author_organization.short_name: МФТИ
author_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ (НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)"
author_organization.ogrn: 1027739386135
author_organization.supervisor_name: НИКОЛАЙ
author_organization.supervisor_surname: КУДРЯВЦЕВ
author_organization.supervisor_patronymic: НИКОЛАЕВИЧ
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные автономные учреждения