Matematicheskie Zametki
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. Zametki:

Personal entry:
Save password
Forgotten password?

Mat. Zametki, 2019, Volume 105, Issue 6, Pages 890–898 (Mi mz12000)  

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

Counterexamples to Borsuk's Conjecture with Large Girth

R. I. Prosanovab

a Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region
b University of Fribourg, Switzerland

Abstract: Borsuk's celebrated conjecture, which has been disproved, can be stated as follows: in $\mathbb R^n$, there exist no diameter graphs with chromatic number larger than $n+1$. In this paper, we prove the existence of counterexamples to Borsuk's conjecture which, in addition, have large girth. This study is in the spirit of O'Donnell and Kupavskii, who studied the existence of distance graphs with large girth. We consider both cases of strict and nonstrict diameter graphs. We also prove the existence of counterexamples with large girth to a statement of Lovász concerning distance graphs on the sphere.

Keywords: distance graph, Borsuk's problem.

Funding Agency Grant Number
Ministry of Education and Science of the Russian Federation НШ-6760.2018.1
Swiss National Science Foundation SNSF-200021_169391
This work was supported by the program “Leading Scientific Schools” under grant NSh-6760.2018.1 and by the Swiss National Science Foundation under grant SNSF-200021_169391.


Full text: PDF file (510 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Mathematical Notes, 2019, 105:6, 874–880

Bibliographic databases:

UDC: 514.17
Received: 14.03.2018

Citation: R. I. Prosanov, “Counterexamples to Borsuk's Conjecture with Large Girth”, Mat. Zametki, 105:6 (2019), 890–898; Math. Notes, 105:6 (2019), 874–880

Citation in format AMSBIB
\by R.~I.~Prosanov
\paper Counterexamples to Borsuk's Conjecture with Large Girth
\jour Mat. Zametki
\yr 2019
\vol 105
\issue 6
\pages 890--898
\jour Math. Notes
\yr 2019
\vol 105
\issue 6
\pages 874--880

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. Yu. A. Demidovich, “Distance Graphs with Large Chromatic Number and without Cliques of Given Size in the Rational Space”, Math. Notes, 106:1 (2019), 38–51  mathnet  crossref  crossref  mathscinet  isi  elib
    2. A. A. Sagdeev, “On a Frankl–Wilson Theorem”, Problems Inform. Transmission, 55:4 (2019), 376–395  mathnet  crossref  crossref  isi  elib
    3. Sagdeev A.A., Raigorodskii A.M., “On a Frankl-Wilson Theorem and Its Geometric Corollaries”, Acta Math. Univ. Comen., 88:3 (2019), 1029–1033  mathscinet  isi
    4. Ph. A. Pushnyakov, A. M. Raigorodskii, “Estimate of the Number of Edges in Special Subgraphs of a Distance Graph”, Math. Notes, 107:2 (2020), 322–332  mathnet  crossref  crossref  isi  elib
    5. R. Prosanov, “A new proof of the larman-rogers upper bound for the chromatic number of the euclidean space”, Discret Appl. Math., 276:SI (2020), 115–120  crossref  mathscinet  zmath  isi
    6. M. M. Ipatov, M. M. Koshelev, A. M. Raigorodskii, “Modularity of some distance graphs”, Dokl. Math., 101:1 (2020), 60–61  crossref  isi
    7. A. M. Raigorodskii, M. M. Koshelev, “New bounds for the clique-chromatic numbers of johnson graphs”, Dokl. Math., 101:1 (2020), 66–67  crossref  mathscinet  isi
    8. A. M. Raigorodskii, M. M. Koshelev, “New bounds on clique-chromatic numbers of johnson graphs”, Discret Appl. Math., 283 (2020), 724–729  crossref  mathscinet  zmath  isi
    9. V. O. Koval, “O razbienii ploskikh mnozhestv na $6$ chastei malogo diametra”, Kombinatorika i teoriya grafov. XII, Zap. nauchn. sem. POMI, 497, POMI, SPb., 2020, 100–123  mathnet
    10. P. A. Ogarok, A. M. Raigorodskii, “Ob ustoichivosti chisla nezavisimosti nekotorogo distantsionnogo grafa”, Probl. peredachi inform., 56:4 (2020), 50–63  mathnet  crossref
    11. A. V. Berdnikov, A. M. Raigorodskii, “Otsenki chisel Borsuka po distantsionnym grafam spetsialnogo vida”, Probl. peredachi inform., 57:2 (2021), 44–50  mathnet  crossref
  • Математические заметки Mathematical Notes
    Number of views:
    This page:183
    First page:22

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021