Estimating the chromatic numbers of Euclidean space by convex minimization methods
Sbornik. Mathematics, Tome 200 (2009) no. 6, pp. 783-801
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{SM_2009_200_6_a0,
author = {E. S. Gorskaya and I. M. Mitricheva (Shitova) and V. Yu. Protasov and A. M. Raigorodskii},
title = {Estimating the chromatic numbers of {Euclidean} space by convex minimization methods},
journal = {Sbornik. Mathematics},
pages = {783--801},
publisher = {mathdoc},
volume = {200},
number = {6},
year = {2009},
language = {en},
url = {http://geodesic.mathdoc.fr/item/SM_2009_200_6_a0/}
}
TY - JOUR AU - E. S. Gorskaya AU - I. M. Mitricheva (Shitova) AU - V. Yu. Protasov AU - A. M. Raigorodskii TI - Estimating the chromatic numbers of Euclidean space by convex minimization methods JO - Sbornik. Mathematics PY - 2009 SP - 783 EP - 801 VL - 200 IS - 6 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/SM_2009_200_6_a0/ LA - en ID - SM_2009_200_6_a0 ER -
%0 Journal Article %A E. S. Gorskaya %A I. M. Mitricheva (Shitova) %A V. Yu. Protasov %A A. M. Raigorodskii %T Estimating the chromatic numbers of Euclidean space by convex minimization methods %J Sbornik. Mathematics %D 2009 %P 783-801 %V 200 %N 6 %I mathdoc %U http://geodesic.mathdoc.fr/item/SM_2009_200_6_a0/ %G en %F SM_2009_200_6_a0
E. S. Gorskaya; I. M. Mitricheva (Shitova); V. Yu. Protasov; A. M. Raigorodskii. Estimating the chromatic numbers of Euclidean space by convex minimization methods. Sbornik. Mathematics, Tome 200 (2009) no. 6, pp. 783-801. http://geodesic.mathdoc.fr/item/SM_2009_200_6_a0/