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

Конструктивные нижние оценки чисел независимости дистанционных графов с вершинами в $\{-1, 0, 1\}^n$

А. Р. Ахияров^a, А. В. Бобу^b, А. М. Райгородский<sup>cdea

a</sup> Московский физико-технический институт (национальный исследовательский университет)
^b Criteo S. A., Париж, Франция
^c МГУ им. М.В. Ломоносова, механико-математический факультет, кафедра математической статистики и случайных процессов
^d Кавказский математический центр Адыгейского государственного университета
^e Бурятский государственный университет, институт математики и информатики

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

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

УДК: 621.391 : 519.157.4 : 519.176

Поступила в редакцию: 04.05.2025
После переработки: 02.08.2025
Принята к печати: 05.08.2025

DOI: 10.31857/S0555292325020054