RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы передачи информации // Архив

Пробл. передачи информ., 2021, том 57, выпуск 2, страницы 44–50 (Mi ppi2340)

Эта публикация цитируется в 8 статьях

Большие системы

Оценки чисел Борсука по дистанционным графам специального вида

А. В. Бердниковa, А. М. Райгородскийbcdef

a Московский физико-технический институт (государственный университет), факультет инноваций и высоких технологий, кафедра дискретной математики
b Московский государственный университет им. М.В. Ломоносова, механико-математический факультет, кафедра математической статистики и случайных процессов
c Кавказский математический центр Адыгейского государственного университета, Майкоп
d Бурятский государственный университет, институт математики и информатики, Улан-Удэ
e Московский физико-технический институт (государственный университет), лаборатория продвинутой комбинаторики и сетевыхприложений
f Московский физико-технический институт (государственный университет), Физтех-школа прикладной математики и информатики

Аннотация: В 1933 г. Борсук сформулировал ставшую классической гипотезу о том, что минимальное число частей меньшего диаметра, на которые может быть разбито произвольное множество диаметра $1$ в $\mathbb{R}^n$, равно $n+1$. В 1993 г. гипотеза была опровергнута с помощью совокупностей точек с координатами $0$ и $1$. Позже вторым автором статьи были получены более сильные контрпримеры, основанные на семействах точек с координатами $-1,0,1$. В настоящей статье устанавливаются новые нижние оценки для чисел Борсука в семействах такого типа.

Ключевые слова: проблема Борсука, $(0,1)$-векторы, разбиения, графы диаметров, раскраски.

УДК: 621.391 : 519.174.7

Поступила в редакцию: 14.07.2020
После переработки: 06.11.2020
Принята к печати: 07.11.2020

DOI: 10.31857/S0555292321020030


 Англоязычная версия: Problems of Information Transmission, 2021, 57:2, 136–142

Реферативные базы данных:


© МИАН, 2024