|
This article is cited in 25 scientific papers (total in 25 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.
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
Linking options:
https://www.mathnet.ru/eng/sm6359https://doi.org/10.1070/SM2009v200n06ABEH004019 https://www.mathnet.ru/eng/sm/v200/i6/p3
|
Statistics & downloads: |
Abstract page: | 1029 | Russian version PDF: | 318 | English version PDF: | 31 | References: | 70 | First page: | 24 |
|