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., 2009, Volume 200, Number 6, Pages 3–22 (Mi msb6359)  

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

Estimating the chromatic numbers of Euclidean space by convex minimization methods

E. S. Gorskaya, I. M. Mitricheva (Shitova), V. Yu. Protasov, A. M. Raigorodskii

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: The chromatic numbers of the Euclidean space ${\mathbb R}^n$ with $k$ forbidden distances are investigated (that is, the minimum numbers of colours necessary to colour all points in ${\mathbb R}^n$ so that no two points of the same colour lie at a forbidden distance from each other). Estimates for the growth exponents of the chromatic numbers as $n\to\infty$ are obtained. The so-called linear algebra method which has been developed is used for this. It reduces the problem of estimating the chromatic numbers to an extremal problem. To solve this latter problem a fundamentally new approach is used, which is based on the theory of convex extremal problems and convex analysis. This allows the required estimates to be found for any $k$. For $k\le20$ these estimates are found explicitly; they are the best possible ones in the framework of the method mentioned above.
Bibliography: 18 titles.

Keywords: chromatic number, distance graph, convex optimization.
Author to whom correspondence should be addressed


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

English version:
Sbornik: Mathematics, 2009, 200:6, 783–801

Bibliographic databases:

UDC: 514.177.2+517.272+519.157
MSC: Primary 52C10, 51K05, 05C15; Secondary 05C12
Received: 05.05.2008 and 09.12.2008

Citation: E. S. Gorskaya, I. M. Mitricheva (Shitova), V. Yu. Protasov, A. M. Raigorodskii, “Estimating the chromatic numbers of Euclidean space by convex minimization methods”, Mat. Sb., 200:6 (2009), 3–22; Sb. Math., 200:6 (2009), 783–801

Citation in format AMSBIB
\by E.~S.~Gorskaya, I.~M.~Mitricheva~(Shitova), V.~Yu.~Protasov, A.~M.~Raigorodskii
\paper Estimating the chromatic numbers of Euclidean space by convex minimization methods
\jour Mat. Sb.
\yr 2009
\vol 200
\issue 6
\pages 3--22
\jour Sb. Math.
\yr 2009
\vol 200
\issue 6
\pages 783--801

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. Kupavskiy A., “On the chromatic number of $\mathbb R^n$ with an arbitrary norm”, Discrete Math., 311:6 (2011), 437–440  crossref  mathscinet  zmath  isi  elib  scopus
    2. A. B. Kupavskii, “On the colouring of spheres embedded in $\mathbb R^n$”, Sb. Math., 202:6 (2011), 859–886  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib
    3. I. M. Mitricheva (Shitova), “On the Chromatic Number for a Set of Metric Spaces”, Math. Notes, 91:3 (2012), 399–408  mathnet  crossref  crossref  mathscinet  isi  elib  elib
    4. A. M. Raigorodskii, D. V. Samirov, “Chromatic Numbers of Spaces with Forbidden Monochromatic Triangles”, Math. Notes, 93:1 (2013), 163–171  mathnet  crossref  crossref  mathscinet  zmath  isi  elib  elib
    5. E. E. Demekhin, A. M. Raigorodskii, O. I. Rubanov, “Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size”, Sb. Math., 204:4 (2013), 508–538  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib
    6. A. B. Kupavskii, A. M. Raigorodskii, “Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii”, Sb. Math., 204:10 (2013), 1435–1479  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    7. S. N. Popova, “Zero-one law for random distance graphs with vertices in $\{-1,0,1\}^n$”, Problems Inform. Transmission, 50:1 (2014), 57–78  mathnet  crossref  isi
    8. D. V. Samirov, A. M. Raigorodskii, “New bounds for the chromatic number of a space with forbidden isosceles triangles”, Dokl. Math., 89:3 (2014), 313–316  crossref  crossref  mathscinet  zmath  isi  elib  elib  scopus
    9. A. E. Zvonarev, A. M. Raigorodskii, D. V. Samirov, A. A. Kharlamova, “On the chromatic number of a space with forbidden equilateral triangle”, Sb. Math., 205:9 (2014), 1310–1333  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib
    10. A. E. Zvonarev, A. M. Raigorodskii, D. V. Samirov, A. A. Kharlamova, “Improvement of the Frankl-Rödl theorem on the number of edges in hypergraphs with forbidden cardinalities of edge intersections”, Dokl. Math., 90:1 (2014), 432–434  crossref  crossref  mathscinet  zmath  isi  elib  elib  scopus
    11. A. V. Berdnikov, A. M. Raigorodskii, “On the Chromatic Number of Euclidean Space with Two Forbidden Distances”, Math. Notes, 96:5 (2014), 827–830  mathnet  crossref  crossref  mathscinet  zmath  isi  elib  elib
    12. E. I. Ponomarenko, A. M. Raigorodskii, “New Lower Bound for the Chromatic Number of a Rational Space with One and Two Forbidden Distances”, Math. Notes, 97:2 (2015), 249–254  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    13. 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
    14. A. V. Berdnikov, “Estimate for the Chromatic Number of Euclidean Space with Several Forbidden Distances”, Math. Notes, 99:5 (2016), 774–778  mathnet  crossref  crossref  mathscinet  isi  elib
    15. 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
    16. A. V. Berdnikov, “Chromatic numbers of distance graphs with several forbidden distances and without cliques of a given size”, Problems Inform. Transmission, 54:1 (2018), 70–83  mathnet  crossref  isi  elib
    17. E. S. Gorskaya, I. M. Mitricheva, “The chromatic number of the space $(\mathbb R^n, l_1)$”, Sb. Math., 209:10 (2018), 1445–1462  mathnet  crossref  crossref  isi  elib
    18. L. I. Bogolubsky, A. M. Raigorodskii, “A Remark on Lower Bounds for the Chromatic Numbers of Spaces of Small Dimension with Metrics $\ell_1$ and $\ell_2$”, Math. Notes, 105:2 (2019), 180–203  mathnet  crossref  crossref  isi  elib
  • ћатематический сборник Sbornik: Mathematics (from 1967)
    Number of views:
    This page:803
    Full text:188
    First page:24

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