A. R. Akhiiarov, A. V. Bobu, A. M. Raigorodskii, “Constructive lower bounds on the independence numbers of distance graphs with vertices in <nobr>$\{-1, 0, 1\}^n$</nobr>”, Probl. Peredachi Inf., 2025, Volume 61, Issue 2,Pages <nobr>69

Large Systems

Constructive lower bounds on the independence numbers of distance graphs with vertices in $\{-1, 0, 1\}^n$

A. R. Akhiiarov^a, A. V. Bobu^b, A. M. Raigorodskii^cdea

^a Moscow Institute of Physics and Technology (State University)
^b Criteo S.A., Paris, France
^c Department of Mathematical Statistics and Random Processes, Faculty of Mechanics and Mathematics, Lomonosov Moscow State University
^d Caucasus Mathematical Center, Adyghe State University, Maykop, Republic of Adygea
^e Institute of Mathematics and Computer Science, Buryat State University, Ulan-Ude

Abstract: New constructive lower bounds on the independence numbers of distance graphs with vertices in $\{-1,0,1\}^n$ are presented. Asymptotically significant lower bounds valid for a wide range of parameters are obtained. Numerical calculations demonstrate relationships between the obtained results and known upper bounds.

Keywords: distance graphs, linear algebraic method, $(-1,0,1)$-vectors.

UDC: 621.391 : 519.157.4 : 519.176

Received: 04.05.2025
Revised: 02.08.2025
Accepted: 05.08.2025

DOI: 10.31857/S0555292325020054