General information
Latest issue
Forthcoming papers
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Mat. Sb.:

Personal entry:
Save password
Forgotten password?

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

This article is cited in 14 scientific papers (total in 14 papers)

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.


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
Received: 20.02.2002

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
\by A.~M.~Raigorodskii
\paper The Borsuk problem for integral polytopes
\jour Mat. Sb.
\yr 2002
\vol 193
\issue 10
\pages 139--160
\jour Sb. Math.
\yr 2002
\vol 193
\issue 10
\pages 1535--1556

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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 Erdős-Hadwiger problem and the chromatic numbers of finite geometric graphs”, Dokl. Math., 68:2 (2003), 216–220  mathnet  mathscinet  zmath  isi
    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  mathnet  mathscinet  zmath  isi
    3. A. M. Raigorodskii, “The problems of Borsuk and Grünbaum on lattice polytopes”, Izv. Math., 69:3 (2005), 513–537  mathnet  crossref  crossref  mathscinet  zmath  isi  elib  elib
    4. A. M. Raigorodskii, “On the structure of distance graphs with large chromatic numbers”, Math. Notes, 80:3 (2006), 451–453  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    5. A. M. Raigorodskii, “Around Borsuk's Hypothesis”, Journal of Mathematical Sciences, 154:4 (2008), 604–623  mathnet  crossref  mathscinet  zmath  elib
    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  elib
    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  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    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  mathnet  crossref  isi  elib
    9. A. V. Burkin, “Small subgraphs in random distance graphs”, Theory Probab. Appl., 60:3 (2016), 367–382  mathnet  crossref  crossref  mathscinet  isi  elib
    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  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    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  mathnet  crossref  crossref  mathscinet  adsnasa  isi  elib
    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  mathnet  crossref  crossref  mathscinet  adsnasa  isi  elib
    13. S. N. Popova, “Zero-one laws for random graphs with vertices in a Boolean cube”, Siberian Adv. Math., 27:1 (2017), 26–75  mathnet  crossref  crossref  mathscinet  elib
    14. Raigorodskii A.M., “Combinatorial Geometry and Coding Theory*”, Fundam. Inform., 145:3 (2016), 359–369  crossref  mathscinet  zmath  isi  scopus
  • Математический сборник - 1992–2005 Sbornik: Mathematics (from 1967)
    Number of views:
    This page:404
    Full text:157
    First page:1

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020