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 11 in Rn 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.
The research was supported in part by the Russian Foundation for Basic Research, project
no. 18-01-00355, and the President of the Russian Federation Council for State Support of Leading
Scientific Schools, grant no. NSh-2540.2020.1.
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
\Bibitem{BerRai21}
\by A.~V.~Berdnikov, A.~M.~Raigorodskii
\paper Bounds on Borsuk numbers in distance graphs of a special type
\jour Probl. Peredachi Inf.
\yr 2021
\vol 57
\issue 2
\pages 44--50
\mathnet{http://mi.mathnet.ru/ppi2340}
\crossref{https://doi.org/10.31857/S0555292321020030}
\transl
\jour Problems Inform. Transmission
\yr 2021
\vol 57
\issue 2
\pages 136--142
\crossref{https://doi.org/10.1134/S0032946021020034}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000671394500003}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85109744675}
Linking options:
https://www.mathnet.ru/eng/ppi2340
https://www.mathnet.ru/eng/ppi/v57/i2/p44
This publication is cited in the following 7 articles:
Ya. K. Shubin, “On the Minimal Number of Edges in Induced Subgraphs of Special Distance Graphs”, Math. Notes, 111:6 (2022), 961–969
V. S. Karas, A. M. Raigorodskii, “On Ramsey numbers for arbitrary sequences of graphs”, Dokl. Math., 105:1 (2022), 14–17
Ya. K. Shubin, “Lower bound on the minimum number of edges in subgraphs of Johnson graphs”, Problems Inform. Transmission, 58:4 (2022), 382–388
A.D. Tolmachev, D.S. Protasov, V.A. Voronov, “Coverings of planar and three-dimensional sets with subsets of smaller diameter”, Discrete Applied Mathematics, 320 (2022), 270
N. A. Dubinin, “New Turán type bounds for Johnson graphs”, Problems Inform. Transmission, 57:4 (2021), 373–379
Ph. A. Pushnyakov, A. M. Raigorodskii, “Estimate of the number of edges in subgraphs of a Johnson graph”, Dokl. Math., 104:1 (2021), 193–195