RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 2021 Volume 57, Issue 2, Pages 44–50 (Mi ppi2340)

This article is cited in 8 papers

Large Systems

Bounds on Borsuk numbers in distance graphs of a special type

A. V. Berdnikova, A. M. Raigorodskiibcdef

a Department of Discrete Mathematics, Faculty of Innovation and High Technology, Moscow Institute of Physics and Technology (State University), Moscow, Russia
b Department of Mathematical Statistics and Random Processes, Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
c Caucasus Mathematical Center, Adyghe State University, Maykop, Republic of Adygea, Russia
d Institute of Mathematics and Computer Science, Buryat State University, Ulan-Ude, Russia
e Laboratory of Advanced Combinatorics and Network Applications, Moscow Institute of Physics and Technology (State University), Moscow, Russia
f Phystech School of Applied Mathematics and Informatics, Moscow Institute of Physics and Technology (State University), Moscow, Russia

Abstract: In 1933, Borsuk stated a conjecture, which has become classical, that the minimum number of parts of smaller diameter into which an arbitrary set of diameter $1$ in $\mathbb{R}^n$ can be partitioned is $n+1$. In 1993, this conjecture was disproved using sets of points with coordinates $0$ and $1$. Later, the second author obtained stronger counterexamples based on families of points with coordinates $-1$, $0$, and $1$. We establish new lower bounds for Borsuk numbers in families of this type.

Keywords: Borsuk's problem, $(0,1)$-vectors, partitions, diameter graphs, colorings.

UDC: 621.391 : 519.174.7

Received: 14.07.2020
Revised: 06.11.2020
Accepted: 07.11.2020

DOI: 10.31857/S0555292321020030


 English version:
Problems of Information Transmission, 2021, 57:2, 136–142

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025