RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Mat. Sb.: Year: Volume: Issue: Page: Find

 Mat. Sb., 2002, Volume 193, Number 10, Pages 139–160 (Mi msb688)

The Borsuk problem for integral polytopes

A. M. Raigorodskii

M. V. Lomonosov Moscow State University

Abstract: Let $f(d)$ be the minimum number of parts of smaller diameter into which one can partition an arbitrary bounded subset of $d$-dimensional Euclidean space $\mathbb R^d$. In 1933, Borsuk conjectured that $f(d)=d+1$. Recent results of Kahn–Kalai, Nilli, and the present author demonstrate that the class of integral polytopes is one of the most important classes having a direct connection with Borsuk's conjecture and problems close to it.
In the present paper, with the use of the methods of the set-covering problem new upper bounds are obtained for the minimum number of parts of smaller diameter into which each $d$-dimensional $(0,1)$-polytope or cross-polytope can be partitioned. These bounds are substantially better than the author's similar former results as well as all previously known bounds for $f(d)$.
In addition, $(0,1)$-polytopes and cross-polytopes in small dimensions are studied in this paper.

DOI: https://doi.org/10.4213/sm688

Full text: PDF file (398 kB)
References: PDF file   HTML file

English version:
Sbornik: Mathematics, 2002, 193:10, 1535–1556

Bibliographic databases:

MSC: Primary 51M20, 52B12, 52B20, 05C15, 05A05; Secondary 52C10

Citation: A. M. Raigorodskii, “The Borsuk problem for integral polytopes”, Mat. Sb., 193:10 (2002), 139–160; Sb. Math., 193:10 (2002), 1535–1556

Citation in format AMSBIB
\Bibitem{Rai02} \by A.~M.~Raigorodskii \paper The Borsuk problem for integral polytopes \jour Mat. Sb. \yr 2002 \vol 193 \issue 10 \pages 139--160 \mathnet{http://mi.mathnet.ru/msb688} \crossref{https://doi.org/10.4213/sm688} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=1937039} \zmath{https://zbmath.org/?q=an:1055.52011} \transl \jour Sb. Math. \yr 2002 \vol 193 \issue 10 \pages 1535--1556 \crossref{https://doi.org/10.1070/SM2002v193n10ABEH000688} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000180375800013} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-0036767848} 

• http://mi.mathnet.ru/eng/msb688
• https://doi.org/10.4213/sm688
• http://mi.mathnet.ru/eng/msb/v193/i10/p139

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Raigorodskii A.M., “The Erdős-Hadwiger problem and the chromatic numbers of finite geometric graphs”, Dokl. Math., 68:2 (2003), 216–220
2. Raigorodskii A.M., “The problems of Borsuk, Hadwiger, and Grunbaum for some classes of polytopes and graphs”, Dokl. Math., 67:1 (2003), 85–89
3. A. M. Raigorodskii, “The problems of Borsuk and Grünbaum on lattice polytopes”, Izv. Math., 69:3 (2005), 513–537
4. A. M. Raigorodskii, “On the structure of distance graphs with large chromatic numbers”, Math. Notes, 80:3 (2006), 451–453
5. A. M. Raigorodskii, “Around Borsuk's Hypothesis”, Journal of Mathematical Sciences, 154:4 (2008), 604–623
6. Goldshtein V.B., “O probleme gryunbauma dlya (0,1)- i (-1,0,1)-mnogogrannikov v prostranstvakh maloi razmernosti”, Trudy moskovskogo fiziko-tekhnicheskogo instituta, 2012, 41–50
7. E. I. Ponomarenko, A. M. Raigorodskii, “New Upper Bounds for the Independence Numbers of Graphs with Vertices in $\{-1,0,1\}^n$ and Their Applications to Problems of the Chromatic Numbers of Distance Graphs”, Math. Notes, 96:1 (2014), 140–148
8. A. V. Bobu, O. A. Kostina, A. E. Kupriyanov, “Independence numbers and chromatic numbers of some distance graphs”, Problems Inform. Transmission, 51:2 (2015), 165–176
9. A. V. Burkin, “Small subgraphs in random distance graphs”, Theory Probab. Appl., 60:3 (2016), 367–382
10. A. V. Burkin, “The threshold probability for the property of planarity of a random subgraph of a regular graph”, Russian Math. Surveys, 70:6 (2015), 1170–1172
11. S. N. Popova, “Zero-one law for random subgraphs of some distance graphs with vertices in $\mathbb Z^n$”, Sb. Math., 207:3 (2016), 458–478
12. A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “Asymptotic study of the maximum number of edges in a uniform hypergraph with one forbidden intersection”, Sb. Math., 207:5 (2016), 652–677
13. S. N. Popova, “Zero-one laws for random graphs with vertices in a Boolean cube”, Siberian Adv. Math., 27:1 (2017), 26–75
14. Raigorodskii A.M., “Combinatorial Geometry and Coding Theory*”, Fundam. Inform., 145:3 (2016), 359–369
•  Number of views: This page: 404 Full text: 157 References: 34 First page: 1