|
This article is cited in 8 scientific papers (total 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.
Received: 14.07.2020 Revised: 06.11.2020 Accepted: 07.11.2020
Citation:
A. V. Berdnikov, A. M. Raigorodskii, “Bounds on Borsuk numbers in distance graphs of a special type”, Probl. Peredachi Inf., 57:2 (2021), 44–50; Problems Inform. Transmission, 57:2 (2021), 136–142
Linking options:
https://www.mathnet.ru/eng/ppi2340 https://www.mathnet.ru/eng/ppi/v57/i2/p44
|
Statistics & downloads: |
Abstract page: | 227 | Full-text PDF : | 11 | References: | 33 | First page: | 33 |
|