name: О числе рёбер в индуцированных подграфах специальных дистанционных графов
keyword_list: Экстремальная комбинаторика, теория графов, теорема Турана
abstract: В данной работе рассматривается задача оценки числа рёбер в подграфах специальных дистанционных графов. Рассмотрение дистанционных графов глубоко мотивировано некоторыми знаменитыми задачами комбинаторной геометрии, в частности — задачей Нельсона-Эрдеша-Хадвигера, проблемой Борсука, задачей о кодах с запрещенным расстоянием и другими. Большая часть данной работы посвящена рассмотрению специального дистанционного графа 𝐺(𝑛,3,1), вершинами которого являются точки в 𝑛-мерном булевом кубе, у которых ровно 3 единицы, а ребро между такими вершинами проводится тогда и только тогда, когда евклидово расстояние между соответствующими точками равно 2, или, что то же самое, когда скалярное произведение соответствующих векторов равно 1. Для данного графа получены значительные улучшения верхней и нижней оценок на число рёбер в произвольном подграфе. Более того, предложено обобщение полученных методов для случая 𝐺(𝑛, 𝑟, 𝑠), которые являются естественными обобщениями конструкций, разработанных для графа 𝐺(𝑛, 3, 1).
chairman_dissertation_council.surname: Шабанов Д. А.
chairman_dissertation_council.position: ведущий научный сотрудник
chairman_dissertation_council.degree: Доктор физико-математических наук
organization_supervisor.surname: Кудрявцев Н. Н.
organization_supervisor.position: ректор
organization_supervisor.degree: Доктор физико-математических наук
rubrics.code: 27.45.17
rubrics.name: Теория графов
oecds.code: 01.01.PQ
oecds.name: MATHEMATICS
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.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные автономные учреждения